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

G-94-10

A Generalized Traveling Salesman Problem Approach to the Directed Rural Postman Problem

et

In this paper we examine an enumerative solution approach for the directed Rural Postman Problem (RPP) based on transforming the RPP into a version of a Generalized Traveling Salesman Problem (GTSP). As such, we demonstrate that with this solution approach we solve to optimality much larger RPP instances than previously reported, restricting somewhat the generality of these instances. This work also represents a simple yet elegant unifying view for some classes of arc and node routing problems.

, 16 pages

Ce cahier a été révisé en janvier 1995