A study of two-echelon routing problems applied to last-mile delivery: formulations and exact methods

Abstract

Vehicle routing in urban environments encompasses additional challenges for logistics services providers due to traffic conditions, city regulations, and difficulty in finding parking locations. To overcome these issues, companies usually adopt alternative delivery systems, such as the ones that are reflected in two-echelon routing problems. These problems are based on the idea of having larger vehicles taking goods from depots to intermediary facilities or parking locations, and smaller vehicles or walking deliverymen taking goods from these points to the final customers. Two examples of such problems are the two-echelon location-routing problem (2E-LRP) and the vehicle routing problem with time windows and multiple deliverymen (VRPTWMD). The first encompasses decisions on vehicle routing in both echelons and the facilities to be opened or used. The latter considers that vehicles may carry more than one deliveryman to increase vehicle efficiency. In this dissertation, we propose improvements for both of these problems, focusing on formulations, valid inequalities, Benders decomposition schemes, and exact solution methods. For the 2E-LRP, two novel formulations are presented and compared to the benchmark one. Their linear programming relaxations and their performance under a mixed-integer programming solver are compared, showing that the novel formulations greatly outperform the benchmark of the literature. Also, 125 new best known lower bounds and 55 new optimal solutions were found for the 131 benchmark instances evaluated. Regarding the VRPTWMD, two realistic extensions of the problem were proposed, incorporating in the optimization the deliveryman routes and the decision on which customers to serve in each vehicle stop, which are usually considered to be preprocessed in the literature. Valid inequalities and Benders decomposition schemes were proposed to develop exact solution algorithms for these new variants of the VRPTWMD. Managerial insights show the importance of applying these variants instead of the common approach from the literature, leading to cost reductions of around 10%.