1. A bi-criteria moving-target travelling salesman problem under uncertainty
- Author
-
Alaleh Maskooki, Markku Kallio, University of Turku, Department of Information and Service Management, Aalto-yliopisto, and Aalto University
- Subjects
Information Systems and Management ,General Computer Science ,Moving target ,Modeling and Simulation ,Travelling salesman ,Stochastic programming ,Integer programming ,Management Science and Operations Research ,Dynamic programming ,Industrial and Manufacturing Engineering - Abstract
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) 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.
- Published
- 2023