IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v29y1981i3p448-463.html
   My bibliography  Save this article

A New Optimization Method for Large Scale Fixed Charge Transportation Problems

Author

Listed:
  • Richard S. Barr

    (Southern Methodist University, Dallas, Texas)

  • Fred Glover

    (University of Colorado, Boulder, Colorado)

  • Darwin Klingman

    (University of Texas at Austin, Austin, Texas)

Abstract

This paper presents a branch-and-bound algorithm for solving fixed charge transportation problems where not all cells exist. The algorithm exploits the absence of full problem density in several ways, thus yielding a procedure which is especially applicable to solving real world problems which are normally quite sparse. Additionally, streamlined new procedures for pruning the decision tree and calculating penalties are presented. We present computational experience with both a set of large test problems and a set of dense test problems from the literature. Comparisons with other codes are uniformly favorable to the new method, which runs more than twice as fast as the best alternative.

Suggested Citation

  • Richard S. Barr & Fred Glover & Darwin Klingman, 1981. "A New Optimization Method for Large Scale Fixed Charge Transportation Problems," Operations Research, INFORMS, vol. 29(3), pages 448-463, June.
    • Handle: RePEc:inm:oropre:v:29:y:1981:i:3:p:448-463
    DOI: 10.1287/opre.29.3.448
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.29.3.448
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.29.3.448?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
    ---><---

    Citations

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


    Cited by:

    1. Borisovsky, P. & Dolgui, A. & Eremeev, A., 2009. "Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder," European Journal of Operational Research, Elsevier, vol. 195(3), pages 770-779, June.
    2. Sun, Minghe, 2002. "The transportation problem with exclusionary side constraints and two branch-and-bound algorithms," European Journal of Operational Research, Elsevier, vol. 140(3), pages 629-647, August.
    3. Yixin Zhao & Torbjörn Larsson & Elina Rönnberg & Panos M. Pardalos, 2018. "The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation," Journal of Global Optimization, Springer, vol. 72(3), pages 517-538, November.
    4. Sharmistha Halder (Jana) & Biswapati Jana, 2020. "Application of fuzzy programming techniques to solve solid transportation problem with additional constraints," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 30(1), pages 67-84.
    5. Dukwon Kim & Xinyan Pan & Panos Pardalos, 2006. "An Enhanced Dynamic Slope Scaling Procedure with Tabu Scheme for Fixed Charge Network Flow Problems," Computational Economics, Springer;Society for Computational Economics, vol. 27(2), pages 273-293, May.
    6. Sun, Minghe & Aronson, Jay E. & McKeown, Patrick G. & Drinka, Dennis, 1998. "A tabu search heuristic procedure for the fixed charge transportation problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 441-456, April.
    7. Gen, Mitsuo & Kumar, Anup & Ryul Kim, Jong, 2005. "Recent network design techniques using evolutionary algorithms," International Journal of Production Economics, Elsevier, vol. 98(2), pages 251-261, November.
    8. Gurwinder Singh & Amarinder Singh, 2021. "Solving fixed-charge transportation problem using a modified particle swarm optimization algorithm," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 12(6), pages 1073-1086, December.
    9. LeBlanc, Larry J. & Shtub, Avraham & Anandalingam, G., 1999. "Formulating and solving production planning problems," European Journal of Operational Research, Elsevier, vol. 112(1), pages 54-80, January.
    10. Yogesh Agarwal & Yash Aneja, 2012. "Fixed-Charge Transportation Problem: Facets of the Projection Polyhedron," Operations Research, INFORMS, vol. 60(3), pages 638-654, June.
    11. Bala Shetty, 1990. "A relaxation/decomposition algorithm for the fixed charged network problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(2), pages 327-340, April.
    12. Mi Gan & Shuai Yang & Dandan Li & Mingfei Wang & Si Chen & Ronghui Xie & Jiyang Liu, 2018. "A Novel Intensive Distribution Logistics Network Design and Profit Allocation Problem considering Sharing Economy," Complexity, Hindawi, vol. 2018, pages 1-15, April.
    13. Alexey Sorokin & Vladimir Boginski & Artyom Nahapetyan & Panos M. Pardalos, 2013. "Computational risk management techniques for fixed charge network flow problems with uncertain arc failures," Journal of Combinatorial Optimization, Springer, vol. 25(1), pages 99-122, January.
    14. Jeffery L. Kennington & Charles D. Nicholson, 2010. "The Uncapacitated Time-Space Fixed-Charge Network Flow Problem: An Empirical Investigation of Procedures for Arc Capacity Assignment," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 326-337, May.
    15. Gavin J. Bell & Bruce W. Lamar & Chris A. Wallace, 1999. "Capacity improvement, penalties, and the fixed charge transportation problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(4), pages 341-355, June.
    16. Hultberg, Tim H. & Cardoso, Domingos M., 1997. "The teacher assignment problem: A special case of the fixed charge transportation problem," European Journal of Operational Research, Elsevier, vol. 101(3), pages 463-473, September.
    17. ORTEGA, Francisco & WOLSEY, Laurence, 2000. "A branch-and-cut algorithm for the single commodity uncapacitated fixed charge network flow problem," LIDAM Discussion Papers CORE 2000049, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    18. Erika Buson & Roberto Roberti & Paolo Toth, 2014. "A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem," Operations Research, INFORMS, vol. 62(5), pages 1095-1106, October.
    19. Roberto Roberti & Enrico Bartolini & Aristide Mingozzi, 2015. "The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation," Management Science, INFORMS, vol. 61(6), pages 1275-1291, June.

    More about this item

    Statistics

    Access and download statistics

    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:inm:oropre:v:29:y:1981:i:3:p:448-463. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.