On an exact method for the constrained shortest path problem

The constrained shortest path (CSP) is a well known NP‐Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column‐generation solution methods for crew scheduling and crew rostering problems. We propose an exact solution method for the CSP capable of handling large‐scale networks in a reasonable amount of time. We compared our approach with three different state‐of‐the‐art algorithms for the CSP and found optimal solutions on networks with up to 40,000 nodes and 800,000 arcs. We extended the algorithm to effectively solve the auxiliary problems of a multi‐activity shift scheduling problem and a bus rapid transit route design problem tackled with column generation. We obtained significant speedups against alternative column generation schemes that solve the auxiliary problem with state‐of‐the‐art commercial (linear) optimizers. We also present a first parallel version of our algorithm that shows promising results.