Solving the probabilistic TSP with ant colony optimization.

*(English)*Zbl 1079.90169Summary: 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.

##### MSC:

90C59 | Approximation methods and heuristics in mathematical programming |

90C35 | Programming involving graphs or networks |

90C27 | Combinatorial optimization |

PDF
BibTeX
XML
Cite

\textit{J. Branke} and \textit{M. Guntsch}, J. Math. Model. Algorithms 3, No. 4, 403--425 (2004; Zbl 1079.90169)

Full Text:
DOI

##### References:

[8] | Bianchi, L., Knowles, J. and Bowler, N.: Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms, European J. Oper. Res. (2004), to appear. · Zbl 1132.90364 |

[9] | Bowler, N., Fink, T. and Ball, R. C.: Characterization of the probabilistic travelling salesman problem, Phys. Rev. (2003), to appear. |

[10] | Branke, J. and Guntsch, M.: New ideas for applying ant colony optimization to the probabilistic TSP, in Applications of Evolutionary Computing: Proceedings of EvoWorkshops 2003, 2003, pp. 165-175. · Zbl 1033.90516 |

[11] | Dorigo, M. and Di Caro, G.: The ant colony optimization meta-heuristic, in D. Corne, M. Dorigo and F. Glover (eds), New Ideas in Optimization, 1999, pp. 11-32. |

[14] | Guntsch, M. and Middendorf, M.: Pheromone modification strategies for ant algorithms applied to dynamic TSP, in E. B. et al. (eds), Applications of Evolutionary Computing: Proceedings of EvoWorkshops 2001, 2000, pp. 213-222. · Zbl 0978.68571 |

[15] | Guntsch, M., Middendorf, M. and Schmeck, H.: An ant colony optimization approach to dynamic TSP, in L. S. et al. (eds), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), 2001, pp. 860-867. |

[17] | Jaillet, P.: Analysis of probabilistic combinatorial optimization problems in Euclidean spaces, MOR: Math. Oper. Res. 18 (1993). · Zbl 0777.90048 |

[22] | TSPLIB: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/index.html, 2002. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.