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

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 of binary 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.