Abstract
We give a necessary condition for the existence of a feasible solution for the transportation problem through a set of admissible cells, and an algorithm to find a set of admissible cells that satisfies the necessary condition. Either there exists a feasible solution through the admissible cells (which is therefore optimal since the complementary slackness conditions hold) or we could begin using the primal–dual algorithm (PDA) at this point. Our approach has two important advantages: Our O(mn) procedure for updating dual variables takes much less computing time than any procedure for solving a maximum flow problem in the primal phase of the PDA. We are never concerned by the degeneracy problem as we are not seeking basic solutions, but admissible cells. An example is presented for illustrating our approach. We finally provide computational results for a set of 30 randomly generated instances. Comparison of our method with the PDA reveals a real speed up.
Similar content being viewed by others
References
Arsham H (1992). Postoptimality analysis of the transportation problem. Journal of the Operational Research Society 43: 121–139.
Arsham H and Kahn AB (1989). A simplex-type algorithm for general transportation problems: An alternative to stepping-stone. Journal of the Operational Research Society 40: 581–590.
Bertsekas DP and Castanon DA (1989). The auction algorithm for the transportation problem. LIDS Report 1850, M.I.T.
Dubuc S, Kagabo I and Marcotte P (1999). A note on the uniqueness of solutions to the transportation problem. INFOR 37: 141–148.
Gass SL (1990). On solving the transportation problem. Journal of the Operational Research Society 41: 291–297.
Glover F, Karney D, Klingman D and Napier A (1974). A computation study on start procedures, basis change criteria, and solution algorithms for transportation problems. Management Science 20: 793–813.
Gondran M and Minoux M (1979). Graphes et Algorithmes. Eyrolles: Paris.
Goyal SK (1984). Improving VAM for the unbalanced transportation problem. Journal of the Operational Research Society 35: 1113–1114.
Intrator J and Szwarc W (1988). An inductive property of transportation problem. Asia-Pacific Journal of Operational Research 5: 79–83.
Ji P and Chu KF (2002). A dual-matrix approach to the transportation problem. Asia-Pacific Journal of Operational Research 19: 35–45.
Sultan A and Goyal SK (1988). Resolution of degeneracy in transportation problems. Journal of the Operational Research Society 39: 411–413.
Wilsdon CE (1990). A simple, easily programmed method for locating Rook's tours in the transportation problem. Journal of the Operational Research Society 41: 879–880.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Haddadi, S., Slimani, O. The transportation problem revisited—preprocessing before using the primal–dual algorithm. J Oper Res Soc 63, 1006–1009 (2012). https://doi.org/10.1057/jors.2011.106
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2011.106