An Enhanced Branch-and-Price Algorithm for the Vehicle Routing Problem with Time Windows over Road Networks

JONAS LEVY ALFIE; GONZALO LERA-ROMERO; JUAN JOSÉ MIRANDA-BRONT; FRANCISCO J. SOULIGNAC

Conferencia; ALIO/EURO 2021-2022: XTH JOINT ALIO/EURO INTERNATIONAL CONFERENCE ON APPLIED COMBINATORIAL OPTIMIZATION; 2022

Classical Vehicle Routing Problem (VRP) variants are usually modeled through the so-called customer graph. The problem is formulated over a complete graph, where the vertices represent the set of requests and the depot and the set of arcs models the movement of a vehicle between two given customers. However, modelling the VRPs directly through the customer graph can show some limitations from a practical perspective. In some contexts, the path between two customers is affected by more than one metric,often opposing, such as the travel time and the cost of the route. In this paper we study the VRP with Time Windows over a Road Network (VRPTW-RN), a variant of the VRPTW where the vehicles are allowed to move only through the underlying network, composed of both customer vertices as well as non-customer nodes representing the connection between two relevant paths. We propose an enhanced Branch-and-Price algorithm, incorporating an improved bidirectional labeling algorithm as well as a new branching rule within the context of VRPs with intermediate stops. From our computational experiments, we observe a significant reduction in the computation times when compared to the other exact approach from the related literature.