Premium
An algorithm for the resource constrained shortest path problem
Author(s) -
Beasley J. E.,
Christofides N.
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190402
Subject(s) - shortest path problem , integer programming , mathematical optimization , relaxation (psychology) , path (computing) , linear programming relaxation , computer science , branch and cut , reduction (mathematics) , integer (computer science) , tree (set theory) , flow network , minimum cost flow problem , resource (disambiguation) , k shortest path routing , mathematics , algorithm , theoretical computer science , combinatorics , graph , psychology , social psychology , geometry , programming language , computer network
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.