An Initialization Method for the Bottleneck Transportation Problem

Abstract

The bottleneck transportation problem consists to determine the least total delay or traverse time when some goods are forwarded from m origins to n destinations under supply and demand constraints. The problem can be transformed into a classical Hitchcock transportation problem for which solution methods converge rapidly with a good initial solution. Several initialization methods with various efficiency are proposed in the literature. Among them one can cite the North-West corner method, the Vogel’s method and the Russell’s method. In this paper we propose a new and efficient initialization method which assigns value only if necessary and differs by this way to the other traditional methods. In opposition to other initialization methods, it starts to assign the value zero to the most costly origin-destination pairs. The complexity analysis shows that the method is O(mn(m + n)). Numerical experiments show that it gives excellent results for the bottleneck transportation problem. Indeed it often gives the optimal solution and in the case where this latter is not attained, we obtain a near-optimal solution.