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

Solving a Time-Space Network Formulation for the Convoy Movement Problem

Author

Listed:
  • P. Chardaire

    (School of Computing Sciences, University of East Anglia, Norwich NR4 7TJ, United Kingdom)

  • G. P. McKeown

    (School of Computing Sciences, University of East Anglia, Norwich NR4 7TJ, United Kingdom)

  • S. A. Verity-Harrison

    (Defence Science and Technology Laboratory, Malvern Technology Centre, St. Andrews Road, Malvern WR14 3PS, United Kingdom)

  • S. B. Richardson

    (QinetiQ, Malvern Technology Centre, St. Andrews Road, Malvern WR14 3PS, United Kingdom)

Abstract

We give a formal specification for a strategic network routing problem known as the convoy movement problem (CMP) and establish that the corresponding feasibility problem is NP-complete. We then introduce an integer programming (IP) model based on the concept of a time-space network and apply a Lagrangian relaxation to this model. We discuss how the dual function may be evaluated using a modified version of Dijkstra’s algorithm suitable to very large, implicitly defined graphs and show how heuristic solutions to the primal problem may be obtained. We present results for a number of instances of the CMP, most of which are based on real-world problems. The number of convoys in these instances varies between 15–25, and their movement time requires up to several thousand time units in networks ranging in size from a few dozen to several thousand vertices and edges. The most difficult instance tested involves 17 long convoys each taking four times the average link travel time to pass through a point in the network. This instance is solved within 3.3% of optimality in less than 3.5 hours of computing time on a Dell Precision 420 dual processor computer. Every other test instance is solved within 2% of the optimal value in less than 20 minutes of computing time.

Suggested Citation

  • P. Chardaire & G. P. McKeown & S. A. Verity-Harrison & S. B. Richardson, 2005. "Solving a Time-Space Network Formulation for the Convoy Movement Problem," Operations Research, INFORMS, vol. 53(2), pages 219-230, April.
    • Handle: RePEc:inm:oropre:v:53:y:2005:i:2:p:219-230
    DOI: 10.1287/opre.1040.0183
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1040.0183
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1040.0183?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. Ahmad I. Z. Jarrah & Gang Yu & Nirup Krishnamurthy & Ananda Rakshit, 1993. "A Decision Support Framework for Airline Flight Cancellations and Delays," Transportation Science, INFORMS, vol. 27(3), pages 266-280, August.
    2. Michael Held & Richard M. Karp, 1970. "The Traveling-Salesman Problem and Minimum Spanning Trees," Operations Research, INFORMS, vol. 18(6), pages 1138-1162, December.
    3. Haghani, Ali E., 1989. "Formulation and solution of a combined train routing and makeup, and empty car distribution model," Transportation Research Part B: Methodological, Elsevier, vol. 23(6), pages 433-452, December.
    4. Judith M. Farvolden & Warren B. Powell & Irvin J. Lustig, 1993. "A Primal Partitioning Solution for the Arc-Chain Formulation of a Multicommodity Network Flow Problem," Operations Research, INFORMS, vol. 41(4), pages 669-693, August.
    5. J.M. van den Akker & C.A.J. Hurkens & M.W.P. Savelsbergh, 2000. "Time-Indexed Formulations for Machine Scheduling Problems: Column Generation," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 111-124, May.
    6. Castro, J. & Nabona, N., 1996. "An implementation of linear and nonlinear multicommodity network flows," European Journal of Operational Research, Elsevier, vol. 92(1), pages 37-53, July.
    7. Jean-François Cordeau & Paolo Toth & Daniele Vigo, 1998. "A Survey of Optimization Models for Train Routing and Scheduling," Transportation Science, INFORMS, vol. 32(4), pages 380-404, November.
    8. Richard D. McBride & John W. Mamer, 1997. "Solving Multicommodity Flow Problems with a Primal Embedded Network Simplex Algorithm," INFORMS Journal on Computing, INFORMS, vol. 9(2), pages 154-163, May.
    9. John W. Mamer & Richard D. McBride, 2000. "A Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem," Management Science, INFORMS, vol. 46(5), pages 693-709, May.
    10. Haghani, Ali & Oh, Sei-Chang, 1996. "Formulation and solution of a multi-commodity, multi-modal network flow model for disaster relief operations," Transportation Research Part A: Policy and Practice, Elsevier, vol. 30(3), pages 231-250, May.
    11. Linda K. Nozick & George F. List & Mark A. Turnquist, 1997. "Integrated Routing and Scheduling in Hazardous Materials Transportation," Transportation Science, INFORMS, vol. 31(3), pages 200-215, August.
    12. Chih, Kenneth C.K. & Bodden, Michael P. & Hornung, March A. & Kornhauser, Alain L., 1990. "Routing and Inventory Logistics System (RAILS): A Heuristic Model for Optimally Managing Intermodal Double-Stack Trains," Journal of the Transportation Research Forum, Transportation Research Forum, vol. 31(1).
    13. Eleftherios Iakovou & Christos Douligeris & Huan Li & Chi Ip & Lalit Yudhbir, 1999. "A Maritime Global Route Planning Model for Hazardous Materials Transportation," Transportation Science, INFORMS, vol. 33(1), pages 34-48, February.
    14. Andreas Löbel, 1998. "Vehicle Scheduling in Public Transit and Lagrangean Pricing," Management Science, INFORMS, vol. 44(12-Part-1), pages 1637-1649, December.
    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. Mokhtar, Hamid & Krishnamoorthy, Mohan & Dayama, Niraj Ramesh & Kumar, P.N. Ram, 2020. "New approaches for solving the convoy movement problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    2. Bhoopalam, Anirudh Kishore & Agatz, Niels & Zuidwijk, Rob, 2018. "Planning of truck platoons: A literature review and directions for future research," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 212-228.

    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. Xin Wang & Teodor Gabriel Crainic & Stein W. Wallace, 2019. "Stochastic Network Design for Planning Scheduled Transportation Services: The Value of Deterministic Solutions," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 153-170, February.
    2. Kraft, Edwin R., 2002. "Scheduling railway freight delivery appointments using a bid price approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(2), pages 145-165, February.
    3. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.
    4. Richard D. McBride & John W. Mamer, 2004. "Implementing an LU Factorization for the Embedded Network Simplex Algorithm," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 109-119, May.
    5. Jin, Jian Gang & Zhao, Jun & Lee, Der-Horng, 2013. "A column generation based approach for the Train Network Design Optimization problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 1-17.
    6. Mohri, Seyed Sina & Mohammadi, Mehrdad & Gendreau, Michel & Pirayesh, Amir & Ghasemaghaei, Ali & Salehi, Vahid, 2022. "Hazardous material transportation problems: A comprehensive overview of models and solution approaches," European Journal of Operational Research, Elsevier, vol. 302(1), pages 1-38.
    7. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.
    8. Ruf, Moritz & Cordeau, Jean-François, 2021. "Adaptive large neighborhood search for integrated planning in railroad classification yards," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 26-51.
    9. Chen, Chongshuang & Dollevoet, Twan & Zhao, Jun, 2018. "One-block train formation in large-scale railway networks: An exact model and a tree-based decomposition algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 1-30.
    10. ÇalIskan, Cenk, 2011. "A specialized network simplex algorithm for the constrained maximum flow problem," European Journal of Operational Research, Elsevier, vol. 210(2), pages 137-147, April.
    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. Xueqiao Yu & Maoxiang Lang & Wenhui Zhang & Shiqi Li & Mingyue Zhang & Xiao Yu, 2019. "An Empirical Study on the Comprehensive Optimization Method of a Train Diagram of the China High Speed Railway Express," Sustainability, MDPI, vol. 11(7), pages 1-30, April.
    13. Chen, C. & Dollevoet, T.A.B. & Zhao, J., 2017. "One-block train formation in large-scale railway networks: An exact model and a tree-based decomposition algorithm," Econometric Institute Research Papers EI-2017-32, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    14. Xiao, Jie & Pachl, Joern & Lin, Boliang & Wang, Jiaxi, 2018. "Solving the block-to-train assignment problem using the heuristic approach based on the genetic algorithm and tabu search," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 148-171.
    15. Alena Otto & Erwin Pesch, 2019. "The train-to-yard assignment problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 549-580, June.
    16. A L Tuson & S A Harrison, 2005. "Problem difficulty of real instances of convoy planning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(7), pages 763-775, July.
    17. Endong Zhu & Teodor Gabriel Crainic & Michel Gendreau, 2014. "Scheduled Service Network Design for Freight Rail Transportation," Operations Research, INFORMS, vol. 62(2), pages 383-400, April.
    18. Belgacem Bouzaiene-Ayari & Clark Cheng & Sourav Das & Ricardo Fiorillo & Warren B. Powell, 2016. "From Single Commodity to Multiattribute Models for Locomotive Optimization: A Comparison of Optimal Integer Programming and Approximate Dynamic Programming," Transportation Science, INFORMS, vol. 50(2), pages 366-389, May.
    19. Dall'Orto, Leonardo Campo & Crainic, Teodor Gabriel & Leal, Jose Eugenio & Powell, Warren B., 2006. "The single-node dynamic service scheduling and dispatching problem," European Journal of Operational Research, Elsevier, vol. 170(1), pages 1-23, April.
    20. Arnt-Gunnar Lium & Teodor Gabriel Crainic & Stein W. Wallace, 2009. "A Study of Demand Stochasticity in Service Network Design," Transportation Science, INFORMS, vol. 43(2), pages 144-157, May.

    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:53:y:2005:i:2:p:219-230. 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: 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.