IDEAS home Printed from https://ideas.repec.org/a/wut/journl/v4y2012p9-20id1025.html
   My bibliography  Save this article

Algorithm for the stochastic generalized transportation problem

Author

Listed:
  • Marcin Anholcer

Abstract

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.

Suggested Citation

  • Marcin Anholcer, 2012. "Algorithm for the stochastic generalized transportation problem," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 22(4), pages 9-20.
    • Handle: RePEc:wut:journl:v:4:y:2012:p:9-20:id:1025
    DOI: 10.5277/ord120401
    as

    Download full text from publisher

    File URL: https://ord.pwr.edu.pl/assets/papers_archive/1025%20-%20published.pdf
    Download Restriction: no
    File URL: https://libkey.io/10.5277/ord120401?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Holmberg, Kaj & Jornsten, Kurt O., 1984. "Cross decomposition applied to the stochastic transportation problem," European Journal of Operational Research, Elsevier, vol. 17(3), pages 361-368, September.
    2. Liqun Qi, 1987. "The A -Forest Iteration Method for the Stochastic Generalized Transportation Problem," Mathematics of Operations Research, INFORMS, vol. 12(1), pages 1-21, February.
    3. Janice R. Lourie, 1964. "Topology and Computation of the Generalized Transportation Problem," Management Science, INFORMS, vol. 11(1), pages 177-187, September.
    4. Fred Glover & D. Klingman & A. Napier, 1972. "Basic Dual Feasible Solutions for a Class of Generalized Networks," Operations Research, INFORMS, vol. 20(1), pages 126-136, February.
    5. Egon Balas, 1966. "The Dual Method for the Generalized Transportation Problem," Management Science, INFORMS, vol. 12(7), pages 555-568, March.
    6. E. Balas & P. L. Ivanescu, 1964. "On the Generalized Transportation Problem," Management Science, INFORMS, vol. 11(1), pages 188-202, September.
    7. Kevin D. Wayne, 2002. "A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow," Mathematics of Operations Research, INFORMS, vol. 27(3), pages 445-459, August.
    8. Andrew V. Goldberg & Serge A. Plotkin & Éva Tardos, 1991. "Combinatorial Algorithms for the Generalized Circulation Problem," Mathematics of Operations Research, INFORMS, vol. 16(2), pages 351-381, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Marcin Anholcer, 2013. "Stochastic Generalized Transportation Problem with discrete distribution of demand," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 23(4), pages 9-19.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Marcin Anholcer, 2013. "Stochastic Generalized Transportation Problem with discrete distribution of demand," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 23(4), pages 9-19.
    2. László A. Végh, 2017. "A Strongly Polynomial Algorithm for Generalized Flow Maximization," Mathematics of Operations Research, INFORMS, vol. 42(1), pages 179-211, January.
    3. László A. Végh, 2014. "Concave Generalized Flows with Applications to Market Equilibria," Mathematics of Operations Research, INFORMS, vol. 39(2), pages 573-596, May.
    4. Tomasz Radzik, 1998. "Faster Algorithms for the Generalized Network Flow Problem," Mathematics of Operations Research, INFORMS, vol. 23(1), pages 69-100, February.
    5. René Brandenberg & Paul Stursberg, 2021. "Refined cut selection for benders decomposition: applied to network capacity expansion problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 94(3), pages 383-412, December.
    6. Michael Holzhauser & Sven O. Krumke, 2018. "A generalized approximation framework for fractional network flow and packing problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 87(1), pages 19-50, February.
    7. Hochbaum, Dorit S., 2002. "Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations," European Journal of Operational Research, Elsevier, vol. 140(2), pages 291-321, July.
    8. A. Karakitsiou & A. Migdalas, 2016. "Convex optimization problems in supply chain planning and their solution by a column generation method based on the Frank Wolfe method," Operational Research, Springer, vol. 16(3), pages 401-421, October.
    9. Laszlo A. Vegh, 2011. "Concave Generalized Flows with Applications to Market Equilibria," Papers 1109.3893, arXiv.org, revised Apr 2012.
    10. Konstantinos Paparrizos & Nikolaos Samaras & Angelo Sifaleras, 2015. "Exterior point simplex-type algorithms for linear and network optimization problems," Annals of Operations Research, Springer, vol. 229(1), pages 607-633, June.
    11. Kevin D. Wayne, 2002. "A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow," Mathematics of Operations Research, INFORMS, vol. 27(3), pages 445-459, August.
    12. V. Balachandran & G.L. Thompson, 1974. "An Operator Theory of Parametric Programming for the Generalized Transportation Problem, I : Basic Theory," Discussion Papers 67, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    13. Hitoshi Hayakawa, 2014. "Complexity of Payment Network," CARF F-Series CARF-F-345, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo.
    14. Yolanda Hinojosa & Justo Puerto & Francisco Saldanha-da-Gama, 2014. "A two-stage stochastic transportation problem with fixed handling costs and a priori selection of the distribution channels," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(3), pages 1123-1147, October.
    15. Leo, Gianmaria & Lodi, Andrea & Tubertini, Paolo & Di Martino, Mirko, 2016. "Emergency Department Management in Lazio, Italy," Omega, Elsevier, vol. 58(C), pages 128-138.
    16. Maria Daneva & Torbjörn Larsson & Michael Patriksson & Clas Rydergren, 2010. "A comparison of feasible direction methods for the stochastic transportation problem," Computational Optimization and Applications, Springer, vol. 46(3), pages 451-466, July.
    17. Shiva Prakash Gupta & Urmila Pyakurel & Tanka Nath Dhamala, 2023. "Multi-commodity flow problem on lossy network with partial lane reversals," Annals of Operations Research, Springer, vol. 323(1), pages 45-63, April.
    18. Zhaowei Hao & Long He & Zhenyu Hu & Jun Jiang, 2020. "Robust Vehicle Pre‐Allocation with Uncertain Covariates," Production and Operations Management, Production and Operations Management Society, vol. 29(4), pages 955-972, April.
    19. V. Balachandran & G.L. Thompson, 1974. "A Note on 'Computational Simplifications in Solving Generalized Transportation Problems,' by Glover and Kingman," Discussion Papers 66, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    20. Goldfarb, Donald. & Jin, Zhiying. & Orlin, James B., 1953-., 1996. "Polynomial-time highest-gain augmenting path algorithms for the generalized circulation problem," Working papers 3909-96., Massachusetts Institute of Technology (MIT), Sloan School of Management.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wut:journl:v:4:y:2012:p:9-20:id:1025. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Adam Kasperski (email available below). General contact details of provider: https://edirc.repec.org/data/iopwrpl.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.