A bi-criteria moving-target travelling salesman problem under uncertainty

Loading...
Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Date

2023-08-16

Major/Subject

Mcode

Degree programme

Language

en

Pages

15
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