Bounds and heuristics for the shortest capacitated paths problem

Bounds and heuristics for the shortest capacitated paths problem

0.00 Avg rating0 Votes
Article ID: iaor20042266
Country: Netherlands
Volume: 8
Issue: 4
Start Page Number: 449
End Page Number: 465
Publication Date: Jul 2002
Journal: Journal of Heuristics
Authors: , ,
Keywords: tabu search
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.

Reviews

Required fields are marked *. Your email address will not be published.