Bounds and Heuristics for the Shortest Capacitated Paths Problem

Authors: Costa, M-C.1; Hertz, A.2; Mittaz, M.2

Source: Journal of Heuristics, Volume 8, Number 4, July 2002 , pp. 449-465(17)

Publisher: Springer

Buy & download fulltext article:


Price: $47.00 plus tax (Refund Policy)


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: Lagrangian relaxation; bandwidth packing problem; minimum cost integer multicommodity flow problem; tabu search

Document Type: Regular Paper

Affiliations: 1: CEDRIC, CNAM, 292 rue Saint-Martin, 75003 Paris, France 2: Department of Mathematics, EPFL, 1015 Lausanne, Switzerland

Publication date: July 1, 2002

Related content


Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page