Solution of real-world postman problems

被引:31
作者
Irnich, Stefan [1 ]
机构
[1] Rhein Westfal TH Aachen, Deutsch Post Endowed Chair Optimizat Distribut Ne, D-52056 Aachen, Germany
关键词
postman problems; arc-routing; transformation into TSP;
D O I
10.1016/j.ejor.2007.06.002
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
The paper presents the results of a study performed by the Deutsche post endowed chair of optimization of distribution networks in collaboration with Deutsche Post World Net with the aim of improving the planning of letter mail delivery. Modelling and solution methods for real-world postman problems are presented which extend one of the most general postman problems studied in the literature, the windy rural postman problem, with regard to several aspects. The discussed extensions include turn and street crossing restrictions, cluster constraints, the option to have alternative service modes (including 'zigzag deliveries'), and the use of public transport to reach the postal district. The solution method is based on a transformation to the asymmetric TSP and uses non-standard neighbourhood search techniques. Extensive computational experiments show that the solution method clearly and consistently outperforms standard TSP heuristics on real-world instances. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码:52 / 67
页数:16
相关论文
共 27 条
[1]  
APPLEGATE D, 1999, CONCORDE COMPUTER CO
[2]   Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study [J].
Balas, E ;
Simonetti, N .
INFORMS JOURNAL ON COMPUTING, 2001, 13 (01) :56-75
[3]   The directed rural postman problem with turn penalties [J].
Benavent, E ;
Soler, D .
TRANSPORTATION SCIENCE, 1999, 33 (04) :408-418
[4]  
BODIN L, 2000, DROR 2000, P419
[5]   ON FINDING MINIMUM ROUTES IN A NETWORK WITH TURN PENALTIES [J].
CALDWELL, T .
COMMUNICATIONS OF THE ACM, 1961, 4 (02) :107-108
[6]  
Chisman J. A., 1975, Computers & Operations Research, V2, P115, DOI 10.1016/0305-0548(75)90015-5
[7]   Solving arc routing problems with turn penalties [J].
Clossey, J ;
Laporte, G ;
Soriano, P .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2001, 52 (04) :433-439
[8]   A GRASP heuristic for the mixed Chinese postman problem [J].
Corberán, A ;
Martí, R ;
Sanchis, JM .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 142 (01) :70-80
[9]  
CORBERAN A, 2005, BRANCH CUT ALGORITHM
[10]  
CORBERAN A, 2005, WINDY GEN ROUTING PO