Modeling and solving several classes of arc routing problems as traveling salesman problems

被引：56
作者：
Laporte, G [1 ]
机构：
[1] UNIV MONTREAL,CTR RECH TRANSPORTS,MONTREAL,PQ H3C 3J7,CANADA
来源：
COMPUTERS & OPERATIONS RESEARCH | 1997年 / 24卷 / 11期
关键词：
D O I：
10.1016/S0305-0548(97)00013-0
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
Several important types of are routing problems can be transformed into traveling salesman problems. Computational results indicate that the approach works well on low density graphs containing few edges. Instances involving up to 220 vertices, 660 arcs, and a few edges were solved to optimality. It constitutes the only known approach for solving Mixed Rural Postman Problems and Stacker Crane Problems to optimality. (C) 1997 Elsevier Science Ltd.
引用
收藏
页码：1057 / 1061
页数：5
相关论文
共 12 条
[1]  
Assad A. A., 1995, HDBK OPER R, P375, DOI 10.1016/S0927-0507(05)80109-4
[2]   SOME NEW BRANCHING AND BOUNDING CRITERIA FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM [J].
CARPANETO, G ;
TOTH, P .
MANAGEMENT SCIENCE, 1980, 26 (07) :736-743
[3]  
CHRISTOFIDES N, 1986, MATH PROGRAM STUD, V26, P155, DOI 10.1007/BFb0121091
[4]  
EDMONDS J, 1973, MATHEMATICAL PROGRAM, V5, P88
[5]   ARC ROUTING-PROBLEMS .1. THE CHINESE POSTMAN PROBLEM [J].
EISELT, HA ;
GENDREAU, M ;
LAPORTE, G .
OPERATIONS RESEARCH, 1995, 43 (02) :231-242
[6]   ARC ROUTING-PROBLEMS .2. THE RURAL POSTMAN PROBLEM [J].
EISELT, HA ;
GENDREAU, M ;
LAPORTE, G .
OPERATIONS RESEARCH, 1995, 43 (03) :399-414
[7]   CAPACITATED ARC ROUTING-PROBLEMS [J].
GOLDEN, BL ;
WONG, RT .
NETWORKS, 1981, 11 (03) :305-315
[8]   PATCHING ALGORITHM FOR THE NONSYMMETRIC TRAVELING-SALESMAN PROBLEM [J].
KARP, RM .
SIAM JOURNAL ON COMPUTING, 1979, 8 (04) :561-573
[9]  
Nobert Y, 1996, NETWORKS, V27, P95, DOI 10.1002/(SICI)1097-0037(199603)27:2<97::AID-NET1>3.0.CO
[10]  
2-8
12