Solving the Probabilistic TSP with Ant Colony Optimization |
| |
Authors: | Jürgen Branke Michael Guntsch |
| |
Affiliation: | (1) Institute AIFB, University of Karlsruhe (TH), Germany |
| |
Abstract: | In this paper, we describe new ways to apply Ant Colony Optimization (ACO) to the Probabilistic Traveling Salesperson Problem (PTSP). PTSP is a stochastic extension of the well known Traveling Salesperson Problem (TSP), where each customer will require a visit only with a certain probability. The goal is to find an a priori tour visiting all customers with minimum expected length, customers not requiring a visit simply being skipped in the tour.We show that ACO works well even when only an approximative evaluation function is used, which speeds up the algorithm, leaving more time for the actual construction. As we demonstrate, this idea can also be applied successfully to other state-of-the-art heuristics. Furthermore, we present new heuristic guidance schemes for ACO, better adapted to the PTSP than what has been used previously. We show that these modifications lead to significant improvements over the standard ACO algorithm, and that the resulting ACO is at least competitive to other state-of-the-art heuristics. |
| |
Keywords: | Probabilistic Traveling Salesperson Problem PTSP Ant Colony Optimization ACO approximated evaluation heuristic guidance |
本文献已被 SpringerLink 等数据库收录! |
|