Back

G-2007-106

An Ant Colony Optimization Metaheuristic for the Undirected Rural Postman Problem

, , , , and

BibTeX reference

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

Research Axis

Research application

Document

G-2007-106.pdf (500 KB)