Name
Abstract | ||
|---|---|---|
The constrained shortest path tour problem consists, given a directed graph G = (V boolean OR {s, t), A), an ordered set of disjoint vertex subsets T = {T-1, ..., T-k} and a length function c : A -> R+, in finding a path between s and t of minimum length in G intersecting every subset of T in the given order such that each arc is visited at most once. In this paper, we first show that this problem is NP-Hard even in the most particular case when T contains only one subset with a unique vertex. Then, we introduce a new mathematical model for the problem that helps its decomposition and develop an efficient Branch-and-Price algorithm. We demonstrate that it can easily be applied to several problem variants. Finally, we present extensive computational results with a benchmark against the state of the art Branch-and-Bound algorithm, called B&B-new, from Ferone et al. (2020). On a diverse set of instances, we show that our algorithm significantly decreases the worst computational time while the ranking of algorithms for the average varies over instances. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.cor.2022.105819 | COMPUTERS & OPERATIONS RESEARCH |
Keywords | DocType | Volume |
Shortest path tour, Complexity, Integer linear programming, Integral polytope, Column generation, Dantzig-Wolfe decomposition | Journal | 144 |
ISSN | Citations | PageRank |
0305-0548 | 1 | 0.35 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sebastien Martin | 1 | 1 | 0.35 |
| Youcef Magnouche | 2 | 1 | 0.35 |
| Corentin Juvigny | 3 | 1 | 0.35 |
| Jeremie Leguay | 4 | 303 | 28.78 |