[CHM02] Bounds and heuristics for the Shortest Capacited Paths Problem

Revue Internationale avec comité de lecture : Journal Journal of Heuristics (Kluwer), vol. 8(4), 2002
Résumé: 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.Keywords minimum cost integer multicommodity flow problem, bandwidth packing problem, Lagrangian relaxation, tabu search. (


@article {
title="{Bounds and heuristics for the Shortest Capacited Paths Problem}",
author="M.-C. Costa and A. Hertz and M. Mittaz",
journal="Journal of Heuristics (Kluwer)",