Groupe d’études et de recherche en analyse des décisions

G-2007-106

An Ant Colony Optimization Metaheuristic for the Undirected Rural Postman Problem

, , , et

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