An iterative solution technique for capacitated two-stage time minimization transportation problem

Capacitated two-stage time minimization transportation problem is an important optimization problem arising in industries. In literature, there is only one approach to solving this problem, but it has a deficiency of resulting in memory overflow in implementation on computer for large scale instances. In this paper, this problem is reduced to a series of finding the feasible flow in a network with lower and upper arc capacities, and two iterative algorithms are proposed as more robust solution method for this problem as compared to the existing approach. It is proved that both iterative algorithms find the optimal solution to this problem in a polynomial time. Due to fully utilizing the network structure characteristics inherent to this problem, both iterative algorithms have the advantage of easy implementation on computer and high computational efficiency, and successfully overcome the deficiency of existing approach. Computational experiments validate that as compared to the existing approach, both iterative algorithms are efficient and more robust method to solve this problem, where one iterative algorithm significantly outperforms the other in terms of computational time, especially for large scale instances.