Algorithm for the Stochastic Generalized Transportation Problem

• Authors: Marcin ANHOLCER
• Languages of publication: EN

Abstracts

EN

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.

Keywords

EN

generalized transportation problem; stochastic programming; convex programming; equalization method

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2012
• Volume: 22
• Issue: 4
• Pages: 9-20

Contributors

author

Marcin ANHOLCER

• Department of Operations Research, Poznań University of Economics, al. Niepodległości 10, 61-875 Poznań, Poland

References

• 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.

Identifiers

DOI

10.5277/ord120401