Bounds and Heuristics for the Shortest Capacitated Paths Problem |
| |
Authors: | Marie-Christine Costa Alain Hertz Michel Mittaz |
| |
Institution: | (1) CEDRIC, CNAM, 292 rue Saint-Martin, 75003 Paris, France;(2) Department of Mathematics, EPFL, 1015 Lausanne, Switzerland |
| |
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. |
| |
Keywords: | minimum cost integer multicommodity flow problem bandwidth packing problem Lagrangian relaxation tabu search |
本文献已被 SpringerLink 等数据库收录! |
|