An Ant Colony Optimization Metaheuristic for the Undirected Rural Postman Problem

, , , et

référence BibTeX

This paper describes a new heuristic for the well-known Undirected Rural Postman Problem. It consists of two steps: it first constructs a partial solution using the Ant Colony Optimization metaheuristic, and the remaining required edges are then gradually inserted. Computational results on a set of benchmark instances are presented and comparisons with alternative heuristics are performed. The optimality gap is also computed by running a branch-and-cut algorithm.

, 22 pages

Axe de recherche

Application de recherche


G-2007-106.pdf (550 Ko)