An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems

TLDR

The relaxed, non‑elementary version of the ESPPRC underlies many column‑generation approaches for vehicle routing and crew pairing, often yielding optimal solutions quickly, but for some problems the elementary restriction is essential. This paper proposes an exact solution procedure for the ESPPRC that extends the classical label‑correcting algorithm used for the relaxed problem. The proposed algorithm extends label‑correcting, is embedded in a column‑generation scheme for the Vehicle Routing Problem with Time Windows, and is evaluated through computational experiments. Computational experiments demonstrate the algorithm’s effectiveness when applied to the VRPTW within a column‑generation framework. © 2004 Wiley Periodicals, Inc., NETWORKS 44(3), 216–229.

Abstract

Abstract In this article, we propose a solution procedure for the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). A relaxed version of this problem in which the path does not have to be elementary has been the backbone of a number of solution procedures based on column generation for several important problems, such as vehicle routing and crew pairing. In many cases relaxing the restriction of an elementary path resulted in optimal solutions in a reasonable computation time. However, for a number of other problems, the elementary path restriction has too much impact on the solution to be relaxed or might even be necessary. We propose an exact solution procedure for the ESPPRC, which extends the classical label correcting algorithm originally developed for the relaxed (nonelementary) path version of this problem. We present computational experiments of this algorithm for our specific problem and embedded in a column generation scheme for the classical Vehicle Routing Problem with Time Windows. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 216–229 2004