zbMATH — the first resource for mathematics

New ideas for applying ant colony optimization to the probabilistic TSP. (English) Zbl 1033.90516
Cagnoni, Stefano (ed.) et al., Applications of evolutionary computing. EvoWorkshops 2003: EvoBIO, EvoCOP, EvoIASP, EvoMUSART, EvoROB, and EvoSTIM, Essex, UK, April 14–16, 2003. Proceedings. Berlin: Springer (ISBN 3-540-00976-0/pbk). Lect. Notes Comput. Sci. 2611, 165-175 (2003).
Summary: The Probabilistic Traveling Salesperson Problem (PTSP) is a stochastic variant of the Traveling Salesperson Problem (TSP); each customer has to be serviced only with a given probability. The goal is to find an a priori tour with shortest expected tour-length, with the customers being served in the specified order and customers not requiring service being skipped. In this paper, we use the Ant Colony Optimization (ACO) metaheuristic to construct solutions for PTSP. We propose two new heuristic guidance schemes for this problem, and examine the idea of using approximations to calculate the expected tour length. This allows to find better solutions or use less time than the standard ACO approach.
For the entire collection see [Zbl 1017.68610].

90C35 Programming involving graphs or networks
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T05 Learning and adaptive systems in artificial intelligence
90C27 Combinatorial optimization
Full Text: Link