Abstract
This paper studies the single-path multicommodity network flow problem (SMNF), in which the flow of each commodity can only use one path linking its origin and destination in the network. We study two versions of this problem based on two different objectives. The first version is to minimize network congestion, an issue of concern in traffic grooming over wavelength division multiplexing (WDM), and in which there generally exists a commodity flow between every pair of nodes. The second problem is a constrained version of the general linear multicommodity flow problem, in which, for each commodity, a single path is allowed to send the required flow, and the objective is to determine a flow pattern that obeys the arc capacities and minimizes the total shipping cost. Based on the node-arc and the arc-chain representations, we first present two formulations. Owing to computational impracticality of exact algorithms for practical networks, we propose an ant colony optimization-(ACO) based metaheuristic to deal with SMNF. Considering different problem properties, we devise two versions of ACO metaheuristics to solve these two problems, respectively. The proposed algorithms’ efficiencies are experimentally investigated on some generated instances of SMNF. The test results demonstrate that the proposed ACO metaheuristics are computationally efficient and robust approaches for solving SMNF.
Similar content being viewed by others
References
Ahuja R, Magnanti T and Orlin J ( 1993 ). Network Flows: Theory, Algorithms, and Applications . Prentice Hall Inc: Upper Saddle, NJ .
Aneja Y, Bandyopadhyay S and Jaekel A ( 2006 ). On routing in large WDM networks . Opt Switching Netw 3 : 219 – 232 .
Bandyopadhyay S ( 2007 ). Dissemination of Information in Optical Networks: From Technology to Algorithms . Springer: Berlin .
Barnhart C, Hane CA and Vance PH ( 2000 ). Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems . Opns Res 48 : 318 – 326 .
Birattari M ( 2005 ). The problem of tuning metaheuristics as seen from a machine learning perspective . PhD thesis, Universite Libre De Bruxelles .
Blum C and Dorigo M ( 2004 ). The hyper-cube framework for ant colony optimization . IEEE Trans Syst Man Cybern B 34 : 1161 – 1172 .
Dorigo M and Stützle T ( 2004 ). Ant Colony Optimization . The MIT Press: Massachusetts .
Dutta R and Rouskas G ( 2000 ). A survey of virtual topology design algorithms for wavelength routed optical networks . Opt Network Mag 1 : 73 – 89 .
Fisher M ( 1981 ). The Lagrangian relaxation method for solving integer programming problems . Mngt Sci 27 : 1 – 18 .
Fisher M ( 1985 ). An applications oriented guide to Lagrangian relaxation . Interfaces 15 ( 2 ): 10 – 21 .
Hu JQ and Leida B ( 2004 ). Traffic grooming, routing, and wavelength assignment in optical wdm mesh networks . In: Proceedings of 2004 IEEE INFOCOM . IEEE Press: Piscataway, NJ, pp . 495 – 501 .
Klingman D, Napier A and Stutz J ( 1974 ). NETGEN: A program for generating large scale capacitated assignment transportation and minimum cost flow network problems . Mngt Sci 20 : 814 – 821 .
Ramaswami R and Sivarajan KN ( 2002 ). Optimal Networks: A Practical Perspective . Morgan Kaufmann Publishers: San Francisco, CA .
Rouskas G and Dutta R ( 2000 ). Design of logical topologies for wavelength routed networks . In: Sivalingam K and Subramanian S (eds) . Optical WDM Networks: Principles and Practice . Kluwer Academic Publishers: Norwell, MA, pp . 79 – 102 .
Sung CS and Rim HC ( 2004 ). Receiver set partitioning and sequencing for multicasting traffic in a WDM lightwave single-hop network . J Opl Res Soc 6 : 630 – 639 .
Acknowledgements
The authors thank the editor and the referees for their valuable comments and suggestions that have greatly improved the quality of this paper.
Author information
Authors and Affiliations
Additional information
This work was supported by research grant from the Natural Science and Engineering Research Council of Canada.
Rights and permissions
About this article
Cite this article
Li, XY., Aneja, Y. & Baki, F. An ant colony optimization metaheuristic for single-path multicommodity network flow problems. J Oper Res Soc 61, 1340–1355 (2010). https://doi.org/10.1057/jors.2009.86
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2009.86