VRP with Time Windows, Multiple Deliverymen and Two-Level Routing (VRPTWMD2R)
Supplementary material of the paper:
Senna, F.; Coelho, L.; Morabito, R.; Munari, P. An exact method for a last-mile delivery routing problem with multiple deliverymen. Technical Report CIRRELT-2023-35, CIRRELT, Canada. Oct, 2023.
Abstract: The demand for efficient last-mile delivery systems in large cities creates an opportunity to develop innovative logistics schemes. In this paper, we study a problem in which each vehicle may travel with more than one deliveryman to serve multiple customers with a single stop of the vehicle, increasing the delivery efficiency. We extend the vehicle routing problem with time windows and multiple deliverymen by explicitly considering the deliveryman routes. We introduce the problem, formally define it with a novel formulation, propose valid inequalities, and develop a tailored branch-and-Benders-cut (BBC) algorithm to solve it. The BBC is capable of solving 89% of the instances to proven optimality in reasonable times, many of them of realistic sizes. Additionally, we show the benefits of evaluating the deliveryman routes considering costs minimization perspective.