Constrained shortest path tour problem: Branch-and-Price algorithm

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.