An ant colony optimization metaheuristic for single-path multicommodity network flow problems
Li X-Y,
Y P Aneja and
F Baki
Additional contact information
Li X-Y: Odette School of Business, University of Windsor
Y P Aneja: Odette School of Business, University of Windsor
F Baki: Odette School of Business, University of Windsor
Journal of the Operational Research Society, 2010, vol. 61, issue 9, 1340-1355
Abstract:
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.
Keywords: networks and graphs; multicommodity network flow; single path; routing strategy; ant colony optimization; heuristics (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)
Downloads: (external link)
http://link.springer.com/10.1057/jors.2009.86 Abstract (text/html)
Access to full text is restricted to subscribers.
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:pal:jorsoc:v:61:y:2010:i:9:d:10.1057_jors.2009.86
Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274
DOI: 10.1057/jors.2009.86
Access Statistics for this article
Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook
More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().