Reinforcement Learning Enhanced Meta-heuristic Approach for the Clustered Flying Sidekick Travelling Salesman Problem

• Grant number: 25/02409-0
• Support Opportunities: Scholarships abroad - Research Internship - Scientific Initiation
• Start date: June 01, 2025
• End date: September 30, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Mário César San Felice
• Grantee: Pedro Guilherme Torres das Neves
• Supervisor: Emrah Demir
• 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: Cardiff University, Wales
• Associated to the scholarship: 23/10946-0 - Evolutionary Meta-Heuristics for Routing Problems with Drones, BP.IC

Abstract

Vehicle Routing Problems (VRPs) play a critical role in optimizing logistics by minimizingfuel consumption and time, with applications ranging from deliveries to medical assistance.Recent advances in drone technology have introduced drones into VRPs, enabling faster andmore cost-effective solutions. This project focuses on the Clustered Flying Sidekick Travel-ling Salesman Problem (CFSTSP), a problem proposed as an extension of both the FlyingSidekick Travelling Salesman Problem (FSTSP) and the Clustered Travelling Salesman Prob-lem (CTSP). In the CFSTSP, a truck and a drone collaboratively serve customers grouped intoclusters, ensuring that all vertices within a cluster are visited before starting a new cluster. As an NP-Hard problem, finding optimal solutions for large instances of the CFSTSP using exactmethods is computationally infeasible. To address this, the project proposes a Q-Learningenhanced Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path Relinking(MP-BRKGA-IPR). This approach aims to combine the strengths of both methods to solvethe CFSTSP efficiently, with potential applications in last-mile delivery and other logistics challenges.