The problem presented in this paper was motivated by the need for a solution to be used in a search-and-rescue application and is formulated as a dynamic traveling salesman problem in a stochastic-state network setting. This problem formulation features a full-recourse decision framework and stochastic demands that are revealed only through direct observation. This problem is defined in a stochastic-state network setting, which allows the modeling of implicitly correlated demand stochasticity. The problem is then formulated as a Markovian decision process, and, finally, a heuristic solution is provided. The heuristic solution is based on a two-stage stochastic program with recourse solved on a set of aggregated networks generated by the use of an aggregating function. Subsets of the feasible solutions obtained at each stage are fixed, and the heuristic is used iteratively to further refine the routing policy.
Dynamic Traveling Salesman Problem in Stochastic-State Network Setting for Search-and-Rescue Application
Transportation Research Record: Journal of the Transportation Research Board
Transportation Research Record: Journal of the Transportation Research Board ; 2283 , 1 ; 122-130
2012-01-01
Article (Journal)
Electronic Resource
English
Neural Network Solves "Traveling-Salesman" Problem
NTRS | 1990
|Das asymmetrische Traveling-Salesman-Problem
SLUB | 1981
|A Comparison of Anticipatory Algorithms for the Dynamic and Stochastic Traveling Salesman Problem
Online Contents | 2012
|