Autoren:	Tilk, Christian Olkis, Katharina Irnich, Stefan
Titel:	The last-mile vehicle routing problem with delivery options
Online-Publikationsdatum:	27-Jun-2022
Erscheinungsdatum:	2021
Sprache des Dokuments:	Englisch
Zusammenfassung/Abstract:	The ongoing rise in e-commerce comes along with an increasing number of first-time delivery failures due to the absence of the customer at the delivery location. Failed deliveries result in rework which in turn has a large impact on the carriers’ delivery cost. In the classical vehicle routing problem (VRP) with time windows, each customer request has only one location and one time window describing where and when shipments need to be delivered. In contrast, we introduce and analyze the vehicle routing problem with delivery options (VRPDO), in which some requests can be shipped to alternative locations with possibly different time windows. Furthermore, customers may prefer some delivery options. The carrier must then select, for each request, one delivery option such that the carriers’ overall cost is minimized and a given service level regarding customer preferences is achieved. Moreover, when delivery options share a common location, e.g., a locker, capacities must be respected when assigning shipments. To solve the VRPDO exactly, we present a new branch-price-and-cut algorithm. The associated pricing subproblem is a shortest-path problem with resource constraints that we solve with a bidirectional labeling algorithm on an auxiliary network. We focus on the comparison of two alternative modeling approaches for the auxiliary network and present optimal solutions for instances with up to 100 delivery options. Moreover, we provide 17 new optimal solutions for the benchmark set for the VRP with roaming delivery locations.
DDC-Sachgruppe:	330 Wirtschaft 330 Economics 650 Management 650 Management and auxiliary services
Veröffentlichende Institution:	Johannes Gutenberg-Universität Mainz
Organisationseinheit:	FB 03 Rechts- und Wirtschaftswissenschaften
Veröffentlichungsort:	Mainz
ROR:	https://ror.org/023b0x485
DOI:	http://doi.org/10.25358/openscience-7219
Version:	Published version
Publikationstyp:	Zeitschriftenaufsatz
Nutzungsrechte:	CC BY
Informationen zu den Nutzungsrechten:	https://creativecommons.org/licenses/by/4.0/
Zeitschrift:	OR spectrum 43
Seitenzahl oder Artikelnummer:	877 904
Verlag:	Springer
Verlagsort:	Berlin u.a.
Erscheinungsdatum:	2021
ISSN:	1436-6304
DOI der Originalveröffentlichung:	10.1007/s00291-021-00633-0
Enthalten in den Sammlungen:	JGU-Publikationen