A bi-criteria moving-target travelling salesman problem under uncertainty
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
2023-08-16
Major/Subject
Mcode
Degree programme
Language
en
Pages
15
271-285
271-285
Series
European Journal of Operational Research, Volume 309, issue 1
Abstract
This article concerns a variant of moving target travelling salesman problem where the number and locations of targets vary with time and realizations of random trajectories. Managerial objectives are to maximize the number of visits to different targets and to minimize the total travel distance. Employing a linear value function for finding supported Pareto-efficient solutions, we develop a two-stage stochastic programming model. We propose an iterative randomized dynamic programming (RDP) algorithm which converges to a global optimum with probability one. Each iteration in RDP involves a randomized backward and forward recursion stage as well as options for improving any given schedule: swaps of targets and optimization of timing for visits. An integer linear programming (ILP) model is developed and solved by a standard ILP solver to evaluate the performance of RDP on instances of real data for scheduling an environmental surveillance boat to visit ships navigating in the Baltic Sea. Due to a huge number ofbinary variables, the ILP model in practice becomes intractable. For small to medium size data sets, the Pareto-efficiency of solutions found by RDP and ILP solver are equal within a reasonable tolerance; however, RDP is significantly faster and able to deal with large-scale problems in practice.Description
Funding Information: The first author was financially supported by the University of Turku graduate school, doctoral programme in exact sciences (EXACTUS). Publisher Copyright: © 2023 The Author(s)
Keywords
Dynamic programming, Integer programming, Moving target, Stochastic programming, Travelling salesman
Other note
Citation
Maskooki , A & Kallio , M 2023 , ' A bi-criteria moving-target travelling salesman problem under uncertainty ' , European Journal of Operational Research , vol. 309 , no. 1 , pp. 271-285 . https://doi.org/10.1016/j.ejor.2023.01.009