An ant colony optimization metaheuristic for solving bi-objective multi-sources multicommodity communication flow problem

This paper studies the single path multi-sources multicommodity communication flow problem (MMCF). A predefined number of messages are to be routed in a capacitated network including a set of nodes that can be producers (sources) and/or consumers (destinations, decision makers) of information. A node might also be a simple relay. We assume that the same information might be provided by different sources. Each edge in the network is characterized by a capacity, a transmission delay and a cost. We propose a mathematical formulation of the MMCF as a biobjective optimization problem that minimizes the overall cost and delay. Network structural constraints are to be respected such as the capacity of the edges and the single path. We assume the non preemptiveness of the transmission. A solution of the proposed model provides for each request the assigned source node, the transmission path as well as the bandwidth allocated along the path. Multicast trees might be generated if the same source is assigned to send the same message to different destinations. An ant colony metaheuristic is proposed to solve the problem. This paper presents an empirical validation of the proposed approach.