The vehicle routing problem with time windows and multiple deliverymen: clustering and two-level routing

• Grant number: 22/09679-5
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: January 16, 2023
• End date: July 15, 2023
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Reinaldo Morabito Neto
• Grantee: Fernando Ribeiro de Senna
• Supervisor: Leandro Callegari Coelho
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
• Institution abroad: Université Laval, Canada
• Associated to the scholarship: 21/14441-5 - A two-level routing approach to the Vehicle Routing Problem with Time Windows and Multiple Deliverymen: formulations and exact methods, BP.MS

Abstract

The Vehicle Routing Problem with Time Windows and Multiple Deliverymen is a variant of the Vehicle Routing Problem in which each vehicle may carry more than one deliveryman to reduce overall service time. In this problem, customers are grouped in clusters that are served by a single stop of the vehicle. The vehicles travel from the depot to the clusters through primary routes. When a vehicle arrives at a cluster, the deliverymen leave the vehicle serving the customers (secondary routes). In the literature, this problem is usually studied considering that clusters are predefined, and that clusters service time may be approximated without assessing the secondary routes performed by the deliverymen. The associated master's research project focuses on studying a variant of this problem in which secondary routes traveled by the deliverymen are part of the problem. In this Research Internship Abroad project, we propose including the clustering decisions in the optimization, in addition to the two-level routing that is already part of the original project. This approach is unprecedented in the literature and is important since it affects directly both primary and secondary routes, and the number of deliverymen in each vehicle, which are the main decisions of the problem. The problem will be solved using exact methods based on Mixed Integer Programming techniques, such as decompositions, column generation, and cutting planes. (AU)