A Bi-level Approach for a Dynamic Multiple Traveling Salesman Problem

Björn Martens ()
Additional contact information
Björn Martens: Universität der Bundeswehr München

Journal of Optimization Theory and Applications, 2025, vol. 207, issue 3, No 7, 34 pages

Abstract: 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.

Keywords: Bi-level; Mixed-integer optimization; Optimal control; Dynamic traveling salesman problem; Value function; Dynamic programming; 49L20; 49M25; 65K10; 90C11; 90C27 (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-025-02800-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:207:y:2025:i:3:d:10.1007_s10957-025-02800-7

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-025-02800-7

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().