POSTMAN ROUTING PROBLEM IN A HIERARCHICAL NETWORK

Publisher Website
Google Scholar
Abstract
This paper presents a technique for obtaining a very good solution to the Chinese Postman Problem (CPP) in a directed, hierarchical network. This type of problem arises in a network where it is required that a group of arcs be traversed prior to another group. Arcs of the same hierarchy are grouped together and the CPP is applied to each group to obtain the optimal routing strategy for that hierarchy. Sometimes all the arcs in a particular hierarchy may not be connected and the CPP can not be applied until it is converted to a directly connected network. A procedure is presented for selecting arcs from another hierarchy to include in the unconnected hierarchy in order to make it connected.