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