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

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.