PD-4
An exact algorithm for robust flying-sidekick TSP
³ë¿µÁÖ, ÁÖÀç°ü, ÀÌÃæ¸ñ(Çѱ¹¿Ü±¹¾î´ëÇб³ »ê¾÷°æ¿µ°øÇаú)
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.
Close