A two-level routing approach to the Vehicle Routing Problem with Time Windows and Multiple Deliverymen: formulations and exact methods

• Grant number: 21/14441-5
• Support Opportunities: Scholarships in Brazil - Master
• Start date: March 01, 2022
• End date: July 31, 2024
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Reinaldo Morabito Neto
• Grantee: Fernando Ribeiro de Senna
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
• Associated research grant: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM
• Associated scholarship(s): 22/09679-5 - The vehicle routing problem with time windows and multiple deliverymen: clustering and two-level routing, BE.EP.MS

Abstract

The Vehicle Routing Problem is one of the most studied problems in Combinatorial Optimization due both to its complexity and real-world applications. The aim of this project is to study a variant of this problem - the Vehicle Routing Problem with Time Windows and Multiple Deliverymen. It will be studied considering a two-level routing process, which has never been done. This problem considers that each vehicle may have more than one deliveryman and clients are grouped in clusters. Thus, vehicles travel through primary routes (from cluster to cluster) and deliverymen travel through secondary routes (within each cluster, serving clients). To the best of our knowledge, no other study has addressed two-level routes in this problem. Therefore, the main goal of this project is to solve this problem in a two level routing approach with exact methods based on Linear and Integer Programming, such as column generation and cutting planes. This Project is related to the goals of Thematic Project 16/01860-1 "Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings", specifically, item "(E) routing problems".