An exact algorithm for robust flying-sidekick Traveling Salesman Problem
Date:
Youngjoo Roh, Jaegwan Joo, Chungmok Lee* ; Hankuk University of Foreign Studies, Korea, Republic of
More information here
The flying sidekick traveling salesman problem (FS-TSP) is a variant of the TSP, in which the drone can be dispatched from and re-docked to the vehicle to serve a customer. Unfortunately, the drone’s flights can be significantly impaired from uncertain flight conditions such as wind, rain, and air temperature. In this talk, we introduce a robust FS-TSP (RFS-TSP), which takes into the risk of drone operation account. We propose a novel coherent risk measure for the drone flights, which results in a nonlinear integer programming problem. Because the mathematical formulation for the problem is very challenging to solve due to the nonlinearity, we develop a decomposition approach combined with a divide-and-conquer method to obtain an optimal solution. The computational experiments show that the proposed algorithm significantly outperforms the state-of-the-art solvers.