An algorithm for the resource constrained shortest path problem

Abstract

Abstract In this paper we examine an integer programming formulation of the resource constrained shortest path problem. This is the problem of a traveller with a budget of various resources who has to reach a given destination as quickly as possible within the resource constraints imposed by his budget. A lagrangean relaxation of the integer programming formulation of the problem into a minimum cost network flow problem (which in certain circumstances reduces to an unconstrained shortest path problem) is developed which provides a lower bound for use in a tree search procedure. Problem reduction tests based on both the original problem and this lagrangean relaxation are given. Computational results are presented for the solution of problems involving up to 500 vertices, 5000 arcs, and 10 resources.