Algorithms for the minimax transportation problem

R. K. Ahuja

Naval Research Logistics Quarterly, 1986, vol. 33, issue 4, 725-739

Abstract: In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow xij from a set of origins I to a set of destinations J for which max(i,j)εIxJ{cijxij} is minimum. In this paper, we develop a parametric algorithm and a primal‐dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal‐dual algorithm solves a sequence of related maximum flow problems. The primal‐dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal‐dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.

Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1002/nav.3800330415

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:33:y:1986:i:4:p:725-739

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().