This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ghamlouche, I. Articles by Gendreau, M. Search for Related Content

Cycle-Based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design

Département d'informatique et recherche opárationnelle and Centre de recherche sur les transports, Université de Montráal, C.P.6128, succursale Centre-ville, Montráal, Québec, Canada H3C 3J7
Département de management et technologie, Université du Québec à Montráal, and Centre de recherche sur les transports, Université de Montráal, Montráal, Québec, Canada
Département d'informatique et recherche opárationnelle and Centre de recherche sur les transports, Université de Montráal, Montráal, Québec, Canada
ilfat{at}crt.umontreal.ca
theo{at}crt.umontreal.ca
michelg{at}crt.umontreal.ca

We propose new cycle-based neighbourhood structures for metaheuristics aimed at the fixed-charge capacitated multicommodity network design formulation. The neighbourhood defines moves that explicitly take into account the impact on the total design cost of potential modifications to the flow distribution of several commodities simultaneously. Moves are identified through a shortest-pathlike network optimization procedure and proceed by redirecting flow around cycles and closing and opening design arcs accordingly. These neighbourhoods are evaluated and tested within a simple tabu search algorithm. Experimental results show that the proposed approach is quite powerful and outperforms existing methods reported in the literature.

Subject classifications: Networks/graphs, multicommodity: fixed-charge capacitated multicommodity network design; Networks/graphs, heuristics: cycle-based neighbourhoods for metaheuristics; Transportation models, network: static and dynamic applications in infrastructure and service design.
History: Received January 2001; revision received November 2001; accepted April 2002.

This article has been cited by other articles:

				A. Cohn, S. Root, A. Wang, and D. Mohr Integration of the Load-Matching and Routing Problem with Equipment Balancing for Small Package Carriers Transportation Science, May 1, 2007; 41(2): 238 - 252. [Abstract] [PDF]