.png){kind=icon}
.png){kind=icon}
Return
Constrained shortest path tour problem: Branch-and-Price algorithm
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2022.105819.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Shortest path tour
Complexity
Integer linear programming
Integral polytope
Column generation
Dantzig-Wolfe decomposition
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W