Exact solution of the generalized routing problem through graph transformations
- PDF / 124,777 Bytes
- 5 Pages / 595 x 794 pts Page_size
- 16 Downloads / 220 Views
r 2003 Operational Research Society Ltd. All rights reserved. 0160-5682/03 $25.00 www.palgrave-journals.com/jors
Exact solution of the generalized routing problem through graph transformations M Blais1,2 and G Laporte1* 1
HEC Montre´al, Montre´al, Canada; 2Inte´grale MBD, Montre´al, Canada
In the general routing problem, the aim is to determine a least cost traversal of a subset of edges, arcs and vertices of a graph. The problem can be transformed into an equivalent traveling salesman problem or rural postman problem and solved optimally. Computational results are reported. Journal of the Operational Research Society (2003) 54, 906–910. doi:10.1057/palgrave.jors.2601590 Keywords: generalized routing problem; traveling salesman problem; rural postman problem; generalized traveling salesman problem
Introduction The generalized routing problem (GRP) is defined on a graph G ¼ (V, A,E), where V ¼ {vi} is a set of vertices, A is a set of (directed) arcs and E is a set of (undirected) edges. Non-negative costs cij and dij are associated with arcs (vi, vj) and with edges [vi, vj], respectively. Denote by sij the length of a shortest path from i to j on G. The sets V 0 DV, A 0 DA and E 0 DE are required vertices, arcs and edges, respectively. If Aa+ and E ¼ +, the graph (and the GRP defined on it) is directed; if A ¼ + and Ea+, it is undirected; if Aa+ and Ea+, it is mixed. The GRP is to determine a minimum cost closed traversal of a subgraph of G including all required vertices, arcs and edges. This problem was introducted by Orloff1 and shown to be NP-hard by Lenstra and Rinnooy Kan.2 When V 0 is empty or contains only vertices incident to A 0 ,E 0 , then the GRP reduces to the rural postman problem (RPP).2 Recall that the RPP consists of determining a least cost traversal of all required arcs and edges of a graph. Here we assume without loss of generality that the vertices of V 0 are not incident to A 0 ,E 0 . The GRP arises in arc routing contexts where it is necessary not only to traverse some arcs or edges of a graph, corresponding to streets, but also some isolated vertices. Such problems are common in school bus routing where several children living on the same street must be collected by stopping at each house, but also groups of children who have to walk from their home to a specific bus stop. A similar situation arises in mail delivery problems where street segments and isolated buildings must be served. Despite the practical importance of the GRP, relatively few studies have been published on this problem. Orloff *Correspondence: G Laporte, HEC Montre´al, 3000 chemin de la CoˆteSainte-Catherine, Montre´al, Canada H3T 2A7. E-mail: [email protected]
proposed two heuristics to make the graph induced by V 0 and A 0 (or E 0 ) Eulerian by matching odd degree vertices, similar to what is done in the Chinese postman problem (see Edmonds and Johnson3), and then making the graph connected by branch-and-bound, as suggested by Bellmore and Malone.4 For the mixed case, he suggested first replacing each required edge b
Data Loading...
