An exact method for a last-mile delivery routing problem with multiple deliverymen

Author(s)

Senna, Fernando ; Coelho, Leandro C. ; Morabito, Reinaldo ; Munari, Pedro

• Document type: Journal article
• Source: European Journal of Operational Research; v. 317, n. 2, p. 13-pg., 2024-05-20.

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 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 a cost minimization perspective, and discuss relevant solutions for urban logistics problems that can help decrease congestion and emissions. (AU)

• FAPESP's process: 21/14441-5 - A two-level routing approach to the Vehicle Routing Problem with Time Windows and Multiple Deliverymen: formulations and exact methods
• Grantee: Fernando Ribeiro de Senna
• Support Opportunities: Scholarships in Brazil - Master
• FAPESP's process: 22/05803-3 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
• Grantee: Reinaldo Morabito Neto
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 22/09679-5 - The vehicle routing problem with time windows and multiple deliverymen: clustering and two-level routing
• Grantee: Fernando Ribeiro de Senna
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
• Grantee: Francisco Louzada Neto
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC