An Aco-based Algorithm For Solving The Minimum Maximal Flow Problem

The network flow problem is the hot topic in many disciplines,such as Operations research, Network analysis.The minimum maximal flow problem was raised by Shi-Yamamoto in 1997. The algorithms have been raised in the multidimensional space, but the algorithm based on the Ant Colony Optimization will not be given to solve the minimum maximal flow problem. In view of the network characteristic and the superiority of the Ant Colony Optimization in solving the optimization problem. In order to solve the minimum maximal flow problem,we will design the algorithm to solve the problem based on the Ant Colony Optimization.First, the minimum maximal flow problem is analyzed theoretically, we will give the idea based on the Ant Colony Optimization,and we design the process to solve the problem. Then, we cast the minimum maximal flow problem into a linear optimization problem by the theorem, and construct a suitable model of the Ant Colony Optimization to solve the problem. Finding the the value vector of the linear optimization problem by using the Ant Colony Optimization and getting the optimal solution of the linear optimization problem by using the MATLAB. The optimal solution is a maximal flow,therefor we will get the minimum maximal flow.Design an algorithm in MATLAB for a complex traffic simulation network to get the the minimum maximal flow. The numerical experiment show that the algorithm based on the Ant Colony Optimization is effective. The numerical experiment also get the range of the parameter,it is0 <α≤5,0.1≤ρ≤0.99,0.5≤Q≤10. In the range, the algorithm can get the minimum maximal flow of the network. The algorithm greatly enrich the methods of solving the minimum maximal flow problem and promote the application of the Ant Colony Optimization.