Decremental state space relaxation strategies and initialization heuristics for solving the Orienteering Problem with Time Windows with dynamic programming

被引：102
作者：
Righini, Giovanni [1 ]
Salani, Matteo [1 ]
机构：
[1] Univ Milan, Dipartimento Tecnol Informaz, I-26013 Crema, CR, Italy
来源：
COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 04期
关键词：
Combinatorial optimization; Traveling salesman problem; Shortest path problem; Dynamic programming; TRAVELING SALESMAN PROBLEM; SHORTEST-PATH PROBLEM; EXACT ALGORITHM;
D O I：
10.1016/j.cor.2008.01.003
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We present an exact optimization algorithm for the Orienteering Problem with Time Windows (OPTW). The algorithm is based on bi-directional and bounded dynamic programming with decremental state space relaxation. We compare different strategies proposed in the literature to guide decremental state space relaxation: our experiments on instances derived from the literature show that there is no dominance between these strategies. We also propose a new heuristic technique to initialize the critical vertex set and we provide experimental evidence of its effectiveness. (C) 2008 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1191 / 1203
页数：13
相关论文
共 22 条
[1]  
Bar-Yehuda R, 2003, LECT NOTES COMPUT SC, V2832, P55
[2]   AN ALGORITHM FOR THE RESOURCE CONSTRAINED SHORTEST-PATH PROBLEM [J].
BEASLEY, JE ;
CHRISTOFIDES, N .
NETWORKS, 1989, 19 (04) :379-394
[3]   Accelerated label setting algorithms for the elementary resource constrained shortest path problem [J].
Boland, N ;
Dethridge, J ;
Dumitrescu, I .
OPERATIONS RESEARCH LETTERS, 2006, 34 (01) :58-68
[4]   An exact algorithm for team orienteering problems [J].
Boussier, Sylvain ;
Feillet, Dominique ;
Gendreau, Michel .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2007, 5 (03) :211-230
[5]   STATE-SPACE RELAXATION PROCEDURES FOR THE COMPUTATION OF BOUNDS TO ROUTING-PROBLEMS [J].
CHRISTOFIDES, N ;
MINGOZZI, A ;
TOTH, P .
NETWORKS, 1981, 11 (02) :145-164
[6]  
Cordeau JF, 1997, NETWORKS, V30, P105, DOI 10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO
[7]  
2-G
[8]   Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem [J].
Dumitrescu, I ;
Boland, N .
NETWORKS, 2003, 42 (03) :135-153
[9]   Traveling salesman problems with profits [J].
Feillet, D ;
Dejax, P ;
Gendreau, M .
TRANSPORTATION SCIENCE, 2005, 39 (02) :188-205
[10]   An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems [J].
Feillet, D ;
Dejax, P ;
Gendreau, M ;
Gueguen, C .
NETWORKS, 2004, 44 (03) :216-229
123