An ant colony optimization metaheuristic for single-path multicommodity network flow problems

An ant colony optimization metaheuristic for single-path multicommodity network flow problems

0.00 Avg rating0 Votes
Article ID: iaor20105724
Volume: 61
Issue: 9
Start Page Number: 1340
End Page Number: 1355
Publication Date: Sep 2010
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: heuristics: ant systems
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.

Reviews

Required fields are marked *. Your email address will not be published.