Multitrip vehicle routing with delivery options: a data-driven application to the parcel industry

Abstract

To make the last mile of parcel delivery more efficient, service providers offer an increasing number of modes of delivery as alternatives to the traditional and often cost-intensive home delivery service. Parcel lockers and pickup stations can be utilized to reduce the number of stops and avoid costly detours. To design smart delivery networks, service providers must evaluate different business models. In this context, a multitrip vehicle routing problem with delivery options and location-dependent costs arises. We present a data-driven framework to evaluate alternative delivery strategies, formulate a corresponding model and solve the problem heuristically using adaptive large neighborhood search. By examining large, real-life instances from a major European parcel service, we determine the potential and benefits of different delivery options.