A STAGE-BASED FORMULATION FOR THE FLYING SIDEKICK TRAVELING SALESMAN PROBLEM WITH JETSUITE
Nội dung chính của bài viết
Tóm tắt
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.
Từ khóa
FSTSP; JetSuite; truck-drone routing; last-mile delivery; mixed-integer programming.
Chi tiết bài viết
Tài liệu tham khảo
[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.