Bounds and Heuristics for the Shortest Capacitated Paths Problem
Source: Journal of Heuristics, Volume 8, Number 4, July 2002 , pp. 449-465(17)
Abstract:Given a graph G, the Shortest Capacitated Paths Problem (SCPP) consists of determining a set of paths of least total length, linking given pairs of vertices in G, and satisfying capacity constraints on the arcs of G.
We formulate the SCPP as a 0-1 linear program and study two Lagrangian relaxations for getting lower bounds on the optimal value. We then propose two heuristic methods. The first one is based on a greedy approach, while the second one is an adaptation of the tabu search meta-heuristic.
Document Type: Regular Paper
Publication date: July 1, 2002