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.