|
 
|
[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
motcle:
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. (http://www.kluweronline.com/issn/1381-1231)
BibTeX
| @article { | |||
| CHM02, | |||
| 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)", | |
| year | = | 2002, | |
| volume | = | 8, | |
| number | = | 4, | |
| } | |||
