A Bi-level Approach for a Dynamic Multiple Traveling Salesman Problem
研究多个动态目标和代理从仓库出发的路径规划问题，目标是每个目标被一个代理到达且所有代理最短时间返回仓库，提出双层模型和离散化线性求解方法。
Abstract In this paper, we consider a routing problem with multiple dynamic targets and agents starting from a depot for which only the trajectories of the targets and depot are known. The objective is that each target is reached by exactly one agent and that all agents return to the depot in the minimum amount of time. This problem belongs to the class of dynamic multiple traveling salesman problems. We model this routing task as a bi-level problem with one leader and multiple followers: the durations required for traveling between targets are generated by solving optimal control problems on the lower level, whereas the routing of the agents on the upper level is represented by a mixed-integer nonlinear program (MINLP). Using the value functions of the lower level, the bi-level problem can be reformulated as a non-smooth, single-level MINLP. We derive sufficient conditions such that this MINLP has a global solution. Additionally, since the non-smooth MINLP cannot be solved by standard software, we propose a discretization that linearizes the program. We show that this linear problem has a solution that approximates a global solution of the MINLP. Communicated by Martin Schmidt.