Experimental Evaluation of Solution Approaches for the K-Route Maximum Flow Problem

We describe the implementation and testing of approaches for the solution of the maximum K-route flow problem. More specifically, we focus on Kishimoto’s algorithm, the binary search algorithm and the K-route flow algorithm. With the aim to compare the performances of the aforementioned methods, we report results of computational experiments carried out on a large set of randomly generated problems with varying topology and arc capacities. The numerical results show that Kishimoto’s algorithm is generally the fastest for solving fully random networks and 3-D grid random networks. The binary search algorithm provides the best performance in solving grid random networks. The K-route 'ow algorithm is generally the fastest for solving fully random networks and 3-D grid random networks with capacity range of [1,1000] and certain values of K.