A STAGE-BASED FORMULATION FOR THE FLYING SIDEKICK TRAVELING SALESMAN PROBLEM WITH JETSUITE
Main Article Content
Abstract
This paper introduces the Flying Sidekick Traveling Salesman Problem with JetSuite (FSTSP-JS), a heterogeneous last-mile delivery problem involving a truck, a standard drone, and a human-piloted JetSuite. The drone can perform flexible launch-and-recovery sorties, whereas the JetSuite performs stationary loop sorties that require the truck to wait at the launch node. We propose a compact three-index stage-based mixed-integer linear programming formulation to minimize the route makespan. Computational results on 180 instances with 10 customers show that FSTSP-JS reduces the average makespan by 21.3% and requires less average solution time than the classical truck-drone FSTSP baseline.
Keywords
FSTSP; JetSuite; truck-drone routing; last-mile delivery; mixed-integer programming.
Article Details
References
[2] Boccia, M., Masone, A., Sforza, A., and Sterle, C. A new arc-based formulation and branch-and-cut for the flying sidekick traveling salesman problem. Transportation Science, 2023.
[3] Dell’Amico, M., Montemanni, R., and Novellani, S. Models and algorithms for the flying sidekick traveling salesman problem. Optimization Letters, 13, 1613–1641, 2019.
[4] Murray, C. C., and Chu, A. G. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C, 54, 86–109, 2015.
[5] Roberti, R., and Ruthmair, M. Exact methods for the traveling salesman problem with drone. Transportation Science, 55(2), 315–335, 2021.
[6] Sacramento, D., Pisinger, D., and Ropke, S. An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C, 102, 289–315, 2019.
[7] Wang, K., Yuan, B., Zhao, M., and Lu, Y. Cooperative truck and drone delivery with timedependent road travel. Transportation Research Part C, 2022.