{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T03:25:05Z","timestamp":1768879505760,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T00:00:00Z","timestamp":1755043200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T00:00:00Z","timestamp":1755043200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"dtec.bw, Next Generation EU"},{"name":"Universit\u00e4t der Bundeswehr M\u00fcnchen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>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.<\/jats:p>","DOI":"10.1007\/s10957-025-02800-7","type":"journal-article","created":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T04:09:42Z","timestamp":1755058182000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Bi-level Approach for a Dynamic Multiple Traveling Salesman Problem"],"prefix":"10.1007","volume":"207","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2439-1005","authenticated-orcid":false,"given":"Bj\u00f6rn","family":"Martens","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,13]]},"reference":[{"issue":"3","key":"2800_CR1","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1016\/j.ejor.2006.06.060","volume":"187","author":"A Allahverdi","year":"2008","unstructured":"Allahverdi, A., Ng, C.T., Cheng, T.C.E., Kovalyov, M.Y.: A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187(3), 985\u20131032 (2008). https:\/\/doi.org\/10.1016\/j.ejor.2006.06.060","journal-title":"Eur. J. Oper. Res."},{"key":"2800_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4755-1","author":"M Bardi","year":"2008","unstructured":"Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Modern Birkh\u00e4user Classics, Birkh\u00e4user, Boston (2008). https:\/\/doi.org\/10.1007\/978-0-8176-4755-1","journal-title":"Modern Birkh\u00e4user Classics, Birkh\u00e4user, Boston"},{"key":"2800_CR3","doi-asserted-by":"publisher","first-page":"2101","DOI":"10.1109\/LCSYS.2023.3284761","volume":"7","author":"J Bertoncini","year":"2023","unstructured":"Bertoncini, J., Nikitina, V., Gerdts, M.: Multi-Agent Dynamic Scheduling with a Posteriori Path Tracking and Collision Avoidance using Model Predictive Control. IEEE Control Systems Letters 7, 2101\u20132106 (2023). https:\/\/doi.org\/10.1109\/LCSYS.2023.3284761","journal-title":"IEEE Control Systems Letters"},{"issue":"7","key":"2800_CR4","doi-asserted-by":"publisher","first-page":"4292","DOI":"10.1137\/090762075","volume":"48","author":"O Bokanowski","year":"2010","unstructured":"Bokanowski, O., Forcadel, N., Zidani, H.: Reachability and minimal times for state constrained nonlinear problems without any controllability assumption. SIAM J. Control. Optim. 48(7), 4292\u20134316 (2010). https:\/\/doi.org\/10.1137\/090762075","journal-title":"SIAM J. Control. Optim."},{"key":"2800_CR5","unstructured":"Britzelmeier, A.: Decomposition and Hamilton-Jacobi-Bellman methods for non-convex generalized Nash equilibrium problems. Dissertation, Neubiberg, Universit\u00e4t der Bundeswehr M\u00fcnchen. (2021) https:\/\/athene-forschung.unibw.de\/85049?query=britzelmeier&show_id=140247"},{"issue":"1","key":"2800_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1080\/10556788.2018.1556661","volume":"35","author":"R Burlacu","year":"2020","unstructured":"Burlacu, R., Gei\u00dfler, B., Schewe, L.: Solving mixed-integer nonlinear programmes using adaptively refined mixed-integer linear programmes. Optimization Methods and Software 35(1), 37\u201364 (2020). https:\/\/doi.org\/10.1080\/10556788.2018.1556661","journal-title":"Optimization Methods and Software"},{"key":"2800_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BF02683336","volume":"36","author":"P Cardaliaguet","year":"1997","unstructured":"Cardaliaguet, P., Quincampoix, M., Saint-Pierre, P.: Optimal times for constrained nonlinear control problems without local controllability. Appl. Math. Optim. 36, 21\u201342 (1997). https:\/\/doi.org\/10.1007\/BF02683336","journal-title":"Appl. Math. Optim."},{"key":"2800_CR8","volume-title":"Foundations of Bi-level Programming","author":"S Dempe","year":"2002","unstructured":"Dempe, S.: Foundations of Bi-level Programming. Kluwer Academic Publishers, Dordrecht (2002)"},{"key":"2800_CR9","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1023\/A:1026461805159","volume":"108","author":"H Ehtamo","year":"2001","unstructured":"Ehtamo, H., Raivio, T.: On Applied Nonlinear and bi-level Programming for Pursuit-Evasion Games. J. Optim. Theory Appl. 108, 65\u201396 (2001). https:\/\/doi.org\/10.1023\/A:1026461805159","journal-title":"J. Optim. Theory Appl."},{"key":"2800_CR10","doi-asserted-by":"crossref","unstructured":"Garn, W.: Balanced dynamic multiple travelling salesmen: Algorithms and continuous approximations. Computers & Operations Research 136,(2021). DOI: https:\/\/doi.org\/10.1016\/j.cor.2021.105509","DOI":"10.1016\/j.cor.2021.105509"},{"key":"2800_CR11","doi-asserted-by":"publisher","DOI":"10.1515\/9783110249996","author":"M Gerdts","year":"2012","unstructured":"Gerdts, M.: Optimal Control of ODEs and DAEs. De Gruyter (2012). https:\/\/doi.org\/10.1515\/9783110249996","journal-title":"De Gruyter"},{"key":"2800_CR12","doi-asserted-by":"publisher","unstructured":"Gerdts, M., Rogovs, S., Valenti, G.: Solving Complex Intersection Management Problems Using Bi-level MINLPs and Piecewise Linearization Techniques. In: Klein C, Jarke M, Helfer, M, Berns K, Gusikhin O (eds) Smart Cities, Green Technologies, and Intelligent Transport Systems. Communications in Computer and Information Science 1612: 255\u2013273. (2022) https:\/\/doi.org\/10.1007\/978-3-031-17098-0_13","DOI":"10.1007\/978-3-031-17098-0_13"},{"key":"2800_CR13","unstructured":"Gurobi Optimization, L.L.C.: Gurobi Optimizer Reference Manual. https:\/\/docs.gurobi.com\/current\/index.html, Accessed: 22-04-2025 (2025)"},{"key":"2800_CR14","unstructured":"Larsen, A., Madsen, O.B.G.: The dynamic vehicle routing problem. Dissertation, Kgs. Lyngby, Denmark, Technical University of Denmark (DTU) (2000)"},{"key":"2800_CR15","doi-asserted-by":"publisher","unstructured":"McMenemy, P., Veerapen, N., Adair, J., Ochoa, G.: Rigorous Performance Analysis of State-of-the-Art TSP Heuristic Solvers. In: Liefooghe A, Paquete L (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2019. Lecture Notes in Computer Science 11452, Springer, Cham. (2019) https:\/\/doi.org\/10.1007\/978-3-030-16711-0_7","DOI":"10.1007\/978-3-030-16711-0_7"},{"issue":"6","key":"2800_CR16","doi-asserted-by":"publisher","first-page":"1203","DOI":"10.1080\/02331934.2015.1122006","volume":"65","author":"P Mehlitz","year":"2016","unstructured":"Mehlitz, P.: Bi-level programming problems with simple convex lower level. Optimization 65(6), 1203\u20131227 (2016). https:\/\/doi.org\/10.1080\/02331934.2015.1122006","journal-title":"Optimization"},{"issue":"4","key":"2800_CR17","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer Programming Formulation of Traveling Salesman Problems. J. ACM 7(4), 326\u2013329 (1960). https:\/\/doi.org\/10.1145\/321043.321046","journal-title":"J. ACM"},{"key":"2800_CR18","doi-asserted-by":"publisher","unstructured":"Palagachev, K.D., Gerdts, M.: Exploitation of the Value Function in a bi-level Optimal Control Problem. In: Bociu L, D\u00e9sid\u00e9ri JA, Habbal A (eds) System Modeling and Optimization, Springer, Cham. 410\u2013419. (2016) https:\/\/doi.org\/10.1007\/978-3-319-55795-3_39","DOI":"10.1007\/978-3-319-55795-3_39"},{"key":"2800_CR19","doi-asserted-by":"publisher","unstructured":"Palagachev, K.D., Gerdts, M.; Numerical Approaches Towards bi-level Optimal Control Problems with Scheduling Tasks. In: Ghezzi L, H\u00f6mberg D, Landry C (eds) Math for the Digital Factory 27. Springer, Cham. (2017) https:\/\/doi.org\/10.1007\/978-3-319-63957-4_10","DOI":"10.1007\/978-3-319-63957-4_10"},{"key":"2800_CR20","unstructured":"Palagachev, K.D.: Mixed-Integer Optimal Control and bi-level Optimization: Vanishing Constraints and Scheduling Tasks. Dissertation, Universit\u00e4t der Bundeswehr M\u00fcnchen, Neubiberg\/M\u00fcnchen. (2018) https:\/\/athene-forschung.unibw.de\/85049?query=palagachev&show_id=123583"},{"issue":"2","key":"2800_CR21","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1002\/oca.2389","volume":"39","author":"C Parzani","year":"2017","unstructured":"Parzani, C., Puechmorel, S.: On a Hamilton-Jacobi-Bellman approach for coordinated optimal aircraft trajectories planning. Optimal Control Applications and Methods, Special Issue: Global and robust optimization of dynamic systems 39(2), 933\u2013948 (2017). https:\/\/doi.org\/10.1002\/oca.2389","journal-title":"Optimal Control Applications and Methods, Special Issue: Global and robust optimization of dynamic systems"},{"key":"2800_CR22","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1002\/net.21628","volume":"67","author":"HN Psaraftis","year":"2015","unstructured":"Psaraftis, H.N., Wen, M., Kontovas, C.: Dynamic Vehicle Routing Problems: Three Decades and Counting. Networks 67, 3\u201331 (2015). https:\/\/doi.org\/10.1002\/net.21628","journal-title":"Networks"},{"key":"2800_CR23","unstructured":"v. Stackelberg, H.: Marktform und Gleichgewicht. Springer, Berlin (1934)"},{"issue":"5","key":"2800_CR24","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1287\/opre.2014.1301","volume":"62","author":"A Toriello","year":"2014","unstructured":"Toriello, A., Haskell, W., Poremba, M., Epstein, D.: A Dynamic Traveling Salesman Problem with Stochastic Arc Costs. Oper. Res. 62(5), 1107\u20131125 (2014). https:\/\/doi.org\/10.1287\/opre.2014.1301","journal-title":"Oper. Res."},{"issue":"2","key":"2800_CR25","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1137\/S0363012993256150","volume":"35","author":"JJ Ye","year":"1997","unstructured":"Ye, J.J.: Optimal Strategies For bi-level Dynamic Problems. SIAM J. Control. Optim. 35(2), 512\u2013531 (1997). https:\/\/doi.org\/10.1137\/S0363012993256150","journal-title":"SIAM J. Control. Optim."},{"issue":"2","key":"2800_CR26","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1137\/S1052623493257344","volume":"7","author":"JJ Ye","year":"1997","unstructured":"Ye, J.J., Zhu, D.L., Zhu, Q.J.: Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM J. Optim. 7(2), 481\u2013507 (1997). https:\/\/doi.org\/10.1137\/S1052623493257344","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2800_CR27","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.orl.2020.01.008","volume":"48","author":"Y Yuan","year":"2020","unstructured":"Yuan, Y., Cattaruzza, D., Ogier, M., Semet, F.: A note on the lifted Miller\u2013Tucker\u2013Zemlin subtour elimination constraints for routing problems with time windows. Oper. Res. Lett. 48(2), 167\u2013169 (2020). https:\/\/doi.org\/10.1016\/j.orl.2020.01.008","journal-title":"Oper. Res. Lett."},{"key":"2800_CR28","doi-asserted-by":"publisher","unstructured":"Yuan, Y., Cattaruzza, D., Ogier, M., Rousselot, C., Semet, F.: Mixed integer programming formulations for the generalized traveling salesman problem with time windows. 4OR-Q J Oper Res 19: 571\u2013592. https:\/\/doi.org\/10.1007\/s10288-020-00461-y (2021)","DOI":"10.1007\/s10288-020-00461-y"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-025-02800-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-025-02800-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-025-02800-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T07:43:45Z","timestamp":1758008625000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-025-02800-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,13]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["2800"],"URL":"https:\/\/doi.org\/10.1007\/s10957-025-02800-7","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,13]]},"assertion":[{"value":"31 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"47"}}