Two-echelon routing in last-mile delivery: Formulations and exact methods

Last-mile delivery systems are getting more and more complex with the increase of urban deliveries. To overcome this challenge, several variants of the vehicle routing problem have been proposed. A popular approach is based on two-echelon systems, in which goods are first taken from depots to intermediary points and then shipped to the final customers by smaller vehicles or walking deliverymen. Two classical problems with these characteristics are the two-echelon location-routing problem (2E-LRP) and the vehicle routing problem with time windows and multiple deliverymen (VRPTWMD). This paper provides a summary of a master’s dissertation that addresses both problems. For the 2E-LRP, novel mixed-integer programming formulations were proposed, and they were theoretically and computationally compared. Improved best-known lower bounds and new optimal solutions of benchmark instances were found. For the VRPTWMD, variants were introduced to better reflect realistic settings. These variants were formulated and exact methods to solve them were proposed.