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

Autor(en)
Briseida Sarasola, Karl Franz Dörner
Abstrakt

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.

Organisation(en)
Institut für Business Decisions and Analytics, Institut für Betriebswirtschaftslehre, Forschungsplattform Data Science @ Uni Vienna
Journal
Networks (New York): an international journal
Band
75
Seiten
64-85
Anzahl der Seiten
21
ISSN
0028-3045
DOI
https://doi.org/10.1002/net.21905
Publikationsdatum
2018
Peer-reviewed
Ja
ÖFOS 2012
Logistik, Operations Research
Link zum Portal
https://ucris.univie.ac.at/portal/de/publications/adaptive-large-neighborhood-search-for-the-vehicle-routing-problem-with-synchronization-constraints-at-the-delivery-location(312e826e-7aa3-4154-bb4f-fb9bc8b24612).html