IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v56y2005i6d10.1057_palgrave.jors.2601875.html
   My bibliography  Save this article

A heuristic approach to the multi-period multi-commodity transportation problem

Author

Listed:
  • K L Poh

    (The National University of Singapore)

  • K W Choo

    (The National University of Singapore)

  • C G Wong

    (Ministry of Defence)

Abstract

This paper describes an approach to solving a real-world problem which involves the transportation of multiple types of commodities from a number of sources to a number of destinations in discrete time periods, using a capacitated heterogeneous fleet of vehicles. The preliminary objective is to minimize the total number of discrete periods needed to complete the entire operation. The problem is first formulated as a mixed integer programme and its tractability is then greatly improved by reformulating it through backward decomposition into two separate models and solved iteratively. A heuristic approach harnessing specific features of the second approach is developed for solving large size problems to obtain near-optimal solutions within reasonable time. The design of the heuristic also takes into consideration the secondary objectives of minimizing the total vehicle capacity used and minimizing the total capacity of sources needed to satisfy the demands at the destinations. Computational results are provided for a variety of randomly generated problems as well as problems from the literature. The approach described here may be applied to the multi-period transportation of personnel and goods from multiple starting points to multiple destinations in both military and civilian applications.

Suggested Citation

  • K L Poh & K W Choo & C G Wong, 2005. "A heuristic approach to the multi-period multi-commodity transportation problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(6), pages 708-718, June.
    • Handle: RePEc:pal:jorsoc:v:56:y:2005:i:6:d:10.1057_palgrave.jors.2601875
    DOI: 10.1057/palgrave.jors.2601875
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601875
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2601875?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Klincewicz, J. G., 1991. "Heuristics for the p-hub location problem," European Journal of Operational Research, Elsevier, vol. 53(1), pages 25-37, July.
    2. Choi, W. & Hamacher, H. W. & Tufekci, S., 1988. "Modeling of building evacuation problems by network flows with side constraints," European Journal of Operational Research, Elsevier, vol. 35(1), pages 98-110, April.
    3. Leon Cooper, 1963. "Location-Allocation Problems," Operations Research, INFORMS, vol. 11(3), pages 331-343, June.
    4. Richard D. McBride, 1998. "Advances in Solving the Multicommodity-Flow Problem," Interfaces, INFORMS, vol. 28(2), pages 32-41, April.
    5. Cynthia Barnhart & Yosef Sheffi, 1993. "A Network-Based Primal-Dual Heuristic for the Solution of Multicommodity Network Flow Problems," Transportation Science, INFORMS, vol. 27(2), pages 102-117, May.
    6. Éva Tardos, 1986. "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Research, INFORMS, vol. 34(2), pages 250-256, April.
    7. Leon Cooper, 1972. "The Transportation-Location Problem," Operations Research, INFORMS, vol. 20(1), pages 94-108, February.
    8. J.M. Valério de Carvalho, 1999. "Exact solution of bin‐packing problems using column generation and branch‐and‐bound," Annals of Operations Research, Springer, vol. 86(0), pages 629-659, January.
    9. John J. Jarvis & H. Donald Ratliff, 1982. "Note---Some Equivalent Objectives for Dynamic Network Flow Problems," Management Science, INFORMS, vol. 28(1), pages 106-109, January.
    10. L. G. Chalmet & R. L. Francis & P. B. Saunders, 1982. "Network Models for Building Evacuation," Management Science, INFORMS, vol. 28(1), pages 86-105, January.
    11. Skorin-Kapov, Darko & Skorin-Kapov, Jadranka & O'Kelly, Morton, 1996. "Tight linear programming relaxations of uncapacitated p-hub median problems," European Journal of Operational Research, Elsevier, vol. 94(3), pages 582-593, November.
    12. H. W. Hamacher & S. Tufekci, 1987. "On the use of lexicographic min cost flows in evacuation modeling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(4), pages 487-503, August.
    13. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    Full references (including those not matched with items on IDEAS)

    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. Douglas Bish & Esra Agca & Roger Glick, 2014. "Decision support for hospital evacuation and emergency response," Annals of Operations Research, Springer, vol. 221(1), pages 89-106, October.
    2. Nadine Baumann & Martin Skutella, 2009. "Earliest Arrival Flows with Multiple Sources," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 499-512, May.
    3. Bretschneider, S. & Kimms, A., 2011. "A basic mathematical model for evacuation problems in urban areas," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(6), pages 523-539, July.
    4. Lovas, Gunnar G., 1995. "On performance measures for evacuation systems," European Journal of Operational Research, Elsevier, vol. 85(2), pages 352-367, September.
    5. Marianov, Vladimir & Serra, Daniel & ReVelle, Charles, 1999. "Location of hubs in a competitive environment," European Journal of Operational Research, Elsevier, vol. 114(2), pages 363-371, April.
    6. Dhyani, Sneha & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2019. "Alternate Second Order Conic Programming Reformulations for Hub Location with Capacity Selection under Demand," IIMA Working Papers WP 2018-12-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    7. Pursals, Salvador Casadesús & Garzón, Federico Garriga, 2009. "Optimal building evacuation time considering evacuation routes," European Journal of Operational Research, Elsevier, vol. 192(2), pages 692-699, January.
    8. S Opasanon & E Miller-Hooks, 2009. "The Safest Escape problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1749-1758, December.
    9. Milorad Vidović & Slobodan Zečević & Milorad Kilibarda & Jelena Vlajić & Nenad Bjelić & Snežana Tadić, 2011. "The p-hub Model with Hub-catchment Areas, Existing Hubs, and Simulation: A Case Study of Serbian Intermodal Terminals," Networks and Spatial Economics, Springer, vol. 11(2), pages 295-314, June.
    10. H. W. Hamacher & S. Tufekci, 1987. "On the use of lexicographic min cost flows in evacuation modeling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(4), pages 487-503, August.
    11. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    12. Ishfaq, Rafay & Sox, Charles R., 2011. "Hub location-allocation in intermodal logistic networks," European Journal of Operational Research, Elsevier, vol. 210(2), pages 213-230, April.
    13. M. Hakan Akyüz & Temel Öncan & İ. Kuban Altınel, 2019. "Branch and bound algorithms for solving the multi-commodity capacitated multi-facility Weber problem," Annals of Operations Research, Springer, vol. 279(1), pages 1-42, August.
    14. Jorge A. Huertas & Daniel Duque & Ethel Segura-Durán & Raha Akhavan-Tabatabaei & Andrés L. Medaglia, 2020. "Evacuation dynamics: a modeling and visualization framework," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 661-691, September.
    15. Samir Elhedhli & Huyu Wu, 2010. "A Lagrangean Heuristic for Hub-and-Spoke System Design with Capacity Selection and Congestion," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 282-296, May.
    16. Ismaila Abderhamane Ndiaye & Emmanuel Neron & Antoine Jouglet, 2017. "Macroscopic evacuation plans for natural disasters," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 231-272, January.
    17. Shin, Youngchul & Moon, Ilkyeong, 2023. "Robust building evacuation planning in a dynamic network flow model under collapsible nodes and arcs," Socio-Economic Planning Sciences, Elsevier, vol. 86(C).
    18. Cunha, Claudio B. & Silva, Marcos Roberto, 2007. "A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil," European Journal of Operational Research, Elsevier, vol. 179(3), pages 747-758, June.
    19. Bish, Douglas R. & Sherali, Hanif D., 2013. "Aggregate-level demand management in evacuation planning," European Journal of Operational Research, Elsevier, vol. 224(1), pages 79-92.
    20. Lichun Chen & Elise Miller‐Hooks, 2008. "The building evacuation problem with shared information," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(4), pages 363-376, June.

    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:pal:jorsoc:v:56:y:2005:i:6:d:10.1057_palgrave.jors.2601875. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    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.