Solving the probabilistic travelling salesperson problem with ant colony optimization

Solving the probabilistic travelling salesperson problem with ant colony optimization

0.00 Avg rating0 Votes
Article ID: iaor20051567
Country: Netherlands
Volume: 3
Issue: 4
Start Page Number: 403
End Page Number: 425
Publication Date: Dec 2004
Journal: Journal of Mathematical Modelling and Algorithms
Authors: ,
Keywords: heuristics
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 approximate 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.

Reviews

Required fields are marked *. Your email address will not be published.