A decomposition-based iterative optimization algorithm for traveling salesman problem with drone

Yurek, E. E., & Ozmutlu, H. C. · 2018

citation-level

This paper is cited for an iterative decomposition of the TSP-D into truck routing and assignment, then drone-route optimization. It is a reference when someone wants a decomposition that stays close to exact solution. The method was not re-implemented to check this card.

Stage one chooses the truck route and which customers go to the drone. Stage two fixes those decisions and optimizes the drone side with a mixed-integer program. The authors report that uniform instances of about a dozen customers were solved in a short average time, and they propose an optimization-based heuristic for larger cases.

The sizes they solved are for their instance type. The algorithm should not be read as ready for a daily plan of several hundred customers. Detailed energy and no-fly geometry are not the main aim.