6533b83afe1ef96bd12a7895

RESEARCH PRODUCT

An algorithm for the Rural Postman problem on a directed graph

Vicente CamposNicos ChristofidesÁNgel CorberánEnrique Mota

subject

CombinatoricsRoute inspection problemArborescenceBranch and boundComputer scienceDirected graphMinimum-cost flow problemTravelling salesman problemTree (graph theory)ConnectivityMathematicsofComputing_DISCRETEMATHEMATICS

description

The Directed Rural Postman Problem (DRPP) is a general case of the Chinese Postman Problem where a subset of the set of arcs of a given directed graph is ‘required’ to be traversed at minimum cost. If this subset does not form a weakly connected graph but forms a number of disconnected components the problem is NP-Complete, and is also a generalization of the asymmetric Travelling Salesman Problem. In this paper we present a branch and bound algorithm for the exact solution of the DRPP based on bounds computed from Lagrangean Relaxation (with shortest spanning arborescence sub-problems) and on the fathoming of some of the tree nodes by the solution of minimum cost flow problems. Computational results are given for graphs of up to 80 vertices, 179 arcs and 71 ‘required’ arcs.

yearjournalcountryeditionlanguage
1986-01-01
https://doi.org/10.1007/bfb0121091