An ant colony optimization metaheuristic for single-path multicommodity networkflow problems

This paper studies the single-path multicommodity network flow problem (SMNF), inwhich the flow of each commodity can only use one path linking its origin anddestination in the network. We study two versions of this problem based on twodifferent objectives. The first version is to minimize network congestion, anissue of concern in traffic grooming over wavelength division multiplexing(WDM), and in which there generally exists a commodity flow between every pairof nodes. The second problem is a constrained version of the general linearmulticommodity flow problem, in which, for each commodity, a single path isallowed to send the required flow, and the objective is to determine a flowpattern that obeys the arc capacities and minimizes the total shipping cost.Based on the node-arc and the arc-chain representations, we first present twoformulations. Owing to computational impracticality of exact algorithms forpractical networks, we propose an ant colony optimization-(ACO) basedmetaheuristic to deal with SMNF. Considering different problem properties, wedevise two versions of ACO metaheuristics to solve these two problems,respectively. The proposed algorithms’ efficiencies are experimentallyinvestigated on some generated instances of SMNF. The test results demonstratethat the proposed ACO metaheuristics are computationally efficient and robustapproaches for solving SMNF.