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

Ilfat Ghamlouche (), Teodor Gabriel Crainic () and Michel Gendreau ()
Additional contact information
Ilfat Ghamlouche: 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
Teodor Gabriel Crainic: 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
Michel Gendreau: Département d'informatique et recherche opérationnelle and Centre de recherche sur les transports, Université de Montréal, Montréal, Québec, Canada

Operations Research, 2003, vol. 51, issue 4, 655-667

Abstract: 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.

Keywords: 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 (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.4.655.16098 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:4:p:655-667

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().