2012 | 22 | 4 | 9-20
Article title

Algorithm for the Stochastic Generalized Transportation Problem

Selected contents from this journal
Title variants
Languages of publication
The equalization method for the stochastic generalized transportation problem has been presented. The algorithm allows us to find the optimal solution to the problem of minimizing the expected total cost in the generalized transportation problem with random demand. After a short introduction and literature review, the algorithm is presented. It is a version of the method proposed by the author for the nonlinear generalized transportation problem. It is shown that this version of the method generates a sequence of solutions convergent to the KKT point. This guarantees the global optimality of the obtained solution, as the expected cost functions are convex and twice differentiable. The computational experiments performed for test problems of reasonable size show that the method is fast.
Physical description
  • Department of Operations Research, Poznań University of Economics, al. Niepodległości 10, 61-875 Poznań, Poland
  • AHUJA R.K., MAGNANTI T.L., ORLIN J.B., Network Flows. Theory, Algorithms and Applications, Prentice Hall, Upper Saddle River, New Jersey 1993.
  • ANHOLCER M., On the Nonlinear generalized transportation problem, preprint.
  • ANHOLCER M., Convergence of the equalization method for Nonlinear Allocation Problems, [in:] Z prac Katedry Badań Operacyjnych, K. Piasecki, W. Sikora (Eds.), Zeszyty Naukowe Akademii Ekonomicznej w Poznaniu 64, 2005, 183–198 (in Polish).
  • ANHOLCER M., Comparative Analysis of Selected Algorithms for Nonlinear Problems of Allocation of Uniform Goods, Wydawnictwo Akademii Ekonomicznej w Poznaniu, Poznań 2008 (in Polish).
  • ANHOLCER M., Comparison of the Performance of Selected Algorithms for Nonlinear Allocation Problems, [in:] Metody i zastosowania badań operacyjnych, R. Kopańska-Bródka (Ed.), Prace Naukowe Akademii Ekonomicznej w Katowicach, Katowice 2008, 9–25 (in Polish).
  • ANHOLCER M., KAWA A., Optimization of Supply Chain via Reduction of Complaints Ratio, Lecture Notes in Computer Science, 2012, 7327, 622–628.
  • BALAS E., The Dual Method for the generalized transportation problem, Management Science, Series A, Sciences, 1966, 12 (7), 555–568.
  • BALAS E., IVANESCU P.L., On the generalized transportation problem, Management Science, Series A, Sciences, 1964, 11 (1), 188–202.
  • BAZARAA M.S., JARVIS J.J., SHERALI H.D., Linear Programming and Network Flows, 4th Ed., Wiley, New York 2010.
  • [10] BAZARAA M.S., SHERALI H.D., SHETTY C.M., Nonlinear Programing. Theory and Algorithms, 3rd Ed., Wiley, New York 2006.
  • GLOVER F., KLINGMAN D., NAPIER A., Basic Dual Feasible Solutions for a Class of Generalized Networks, Operations Research, 1972, 20 (1), 126–136.
  • GOLDBERG A.V., PLOTKIN S.A., TARDOS E., Combinatorial Algorithms for the Generalized Circulation Problem, Mathematics of Operations Research, 1991, 16 (2), 351–381.
  • HOLMBERG K., Efficient decomposition and linearization methods for the stochastic transportation problem, Computational Optimization and Applications, 1995, 4, 293–316.
  • HOLMBERG K., JÖRNSTEN K., Cross decomposition applied to the stochastic transportation problem, European Journal of Operational Research, 1984, 17, 361–368.
  • HOLMBERG K., TUY H., A production-transportation problem with stochastic demand and concave production costs, Mathematical Programming, 1999, 85, 157–179.
  • LOURIE J.R., Topology and computation of the generalized transportation problem, Management Science, Series A, Sciences, 1964, 11 (1), 177–187.
  • LUENBERGER D.G., YINYU Y., Linear and Nonlinear Programming, 3rd Ed., International Series in Operations Research and Management Science, Vol. 116, Springer, Berlin 2008.
  • NAGURNEY A., YU M., MASOUMI A.H., NAGURNEY L.S., Networks Against Time. Supply Chain Analytics for Perishable Products, Series Springer Briefs in Optimization, Springer, 2013.
  • PANDIAN P., ANURADHA D., Floating Point Method for Solving Transportation Problems with Additional Constraints, International Mathematical Forum, 2011, 6 (4), 1983–1992.
  • QI L., Forest iteration method for stochastic transportation problem, Mathematical Programming Study, 1985, 25, 142–163.
  • QI L., The A-forest iteration method for the stochastic generalized transportation problem, Mathematics of Operations Research, 1987, 12 (1), 1–21.
  • SIKORA W., Models and methods of optimal distribution of goods, Zeszyty Naukowe – Seria II, Prace Doktorskie i Habilitacyjne, Akademia Ekonomiczna w Poznaniu, Poznań 1993 (in Polish).
  • SIKORA W., RUNKA H., PYRZYŃSKI D., Optimization of flows in the area of distribution of uniform goods, Grant No. H/12/209/90-2, Akademia Ekonomiczna w Poznaniu, Poznań 1991 (in Polish).
  • WAYNE K.D., A Polynomial combinatorial algorithm for generalized minimum cost flow, Mathematics of Operations Research, 2002, 27 (3), 445–459.
Document Type
Publication order reference
YADDA identifier
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.