Adaptive large neighborhood search for the vehicle routing problem with synchronization constraints at the delivery location

Briseida Sarasola, Karl Franz Dörner

In this paper we introduce a vehicle routing problem with synchronization constraints arising in urban freight transportation, where it is common that both private and commercial customers require deliveries from one or more logistics service providers. These deliveries should be served in a compact way in order to reduce idle times at the delivery locations. Three strategies to achieve feasible schedules are evaluated: self-imposed time windows, exact determination of a feasible schedule, and fix time windows. A mathematical formulation is presented and an adaptive large neighborhood search is used to solve the problem. The performance is evaluated both on classical vehicle routing benchmark instances and on new instances based on real data. Our results show that idle times can be reduced from 54.12% to 79.77% by assuming an average cost rise of 9.87%. In addition, self-imposed time windows are on average 15.74% to 21.43% better than the exact feasibility checks for short runtimes, and 13.71% to 21.15% better than fix time windows.

Department of Business Decisions and Analytics, Department of Business Administration, Research Platform Data Science @ Uni Vienna
Networks (New York): an international journal
Publication date
Peer reviewed
Austrian Fields of Science 2012
Logistics, Operations research
Portal url