A bio-inspired optimization algorithm for the maximum flow problem

The maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum. It has been widely used in many real-world applications, such as aircraft scheduling, carpool problem. In this paper, a novel algorithm is proposed to solve the maximum flow problem based on the characteristics of Physarum polycephalum. This paper consists of two parts. First of all, by adding a virtual node and two virtual links into the network, the maximum flow of the network can be obtained by subtracting the flow along the virtual link from the network flow. Then, several examples are used to demonstrate the efficiency of the proposed algorithm. © 2015 ICIC International.