IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v133y2020ics1366554518311815.html
   My bibliography  Save this article

New approaches for solving the convoy movement problem

Author

Listed:
  • Mokhtar, Hamid
  • Krishnamoorthy, Mohan
  • Dayama, Niraj Ramesh
  • Kumar, P.N. Ram

Abstract

The convoy movement problem (CMP) involves the routing and scheduling of a large number of vehicles and personnel across a network. A convoy is a group of (typically, army) vehicles and personnel that travel together as a group. Given the nature and context of these movements, it is necessary to avoid convoys crossing each other at a node, overtaking, or crossing each other on a road as they travel in the network from their individual origins to their destinations. The lengths and travel speeds are also major factors that determine the optimal travel paths and schedules for these convoys. In this paper, we review different variants of the CMP in the literature. We then propose a generalised problem statement for the CMP that accommodates all common variants. This generalised problem definition addresses several important side constraints that typically occur in real-world problems. We adapt and enhance existing formulations of the CMP in such a way that the generalised version can also be modelled. Further, we propose new approaches for solving large instances of the generalised CMP. Our computational experiments show that the techniques introduced in this paper substantially outperform existing approaches in the literature. We also generate a new dataset for the generalised CMP that provides a framework for the examination of various approaches for the CMP with a wider set of side constraints.

Suggested Citation

  • 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).
  • Handle: RePEc:eee:transe:v:133:y:2020:i:c:s1366554518311815
    DOI: 10.1016/j.tre.2019.10.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554518311815
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.tre.2019.10.007?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. 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.
    2. P. N. Ram Kumar & T. T. Narendran, 2009. "A Mathematical Approach for Variable Speed Convoy Movement Problem(CMP)," Defense & Security Analysis, Taylor & Francis Journals, vol. 25(2), pages 137-155, June.
    3. R Gopalan & N S Narayanaswamy, 2009. "Analysis of algorithms for an online version of the convoy movement problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1230-1236, September.
    4. 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.
    5. Azar Sadeghnejad-Barkousaraie & Rajan Batta & Moises Sudit, 2017. "Convoy movement problem: a civilian perspective," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 14-33, January.
    6. Nirup N. Krishnamurthy & Rajan Batta & Mark H. Karwan, 1993. "Developing Conflict-Free Routes for Automated Guided Vehicles," Operations Research, INFORMS, vol. 41(6), pages 1077-1090, December.
    7. Goldstein, Darin & Shehab, Tariq & Casse, Juan & Lin, Hsiu-Chin, 2010. "On the formulation and solution of the convoy routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(4), pages 520-533, July.
    8. 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.
    9. Higgins, A. & Kozan, E. & Ferreira, L., 1996. "Optimal scheduling of trains on a single line track," Transportation Research Part B: Methodological, Elsevier, vol. 30(2), pages 147-161, April.
    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. Lee, Enoch & Cen, Xuekai & Lo, Hong K., 2022. "Scheduling zonal-based flexible bus service under dynamic stochastic demand and Time-dependent travel time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).

    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. Ram Gopalan, 2015. "Computational complexity of convoy movement planning problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(1), pages 31-60, August.
    2. Alan J. Maniamkot & P. N. Ram Kumar & Mohan Krishnamoorthy & Hamid Mokhtar & Sridharan Rajagopalan, 2022. "Hybridised ant colony optimisation for convoy movement problem," Annals of Operations Research, Springer, vol. 315(2), pages 847-866, August.
    3. Azar Sadeghnejad-Barkousaraie & Rajan Batta & Moises Sudit, 2017. "Convoy movement problem: a civilian perspective," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 14-33, January.
    4. R Gopalan & N S Narayanaswamy, 2009. "Analysis of algorithms for an online version of the convoy movement problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1230-1236, September.
    5. 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.
    6. Limsawasd, Charinee & Athigakunagorn, Nathee & Khathawatcharakun, Phattadon & Boonmee, Atiwat, 2022. "Skip-Stop Strategy Patterns optimization to enhance mass transit operation under physical distancing policy due to COVID-19 pandemic outbreak," Transport Policy, Elsevier, vol. 126(C), pages 225-238.
    7. Gianmarco Garrisi & Cristina Cervelló-Pastor, 2019. "Train-Scheduling Optimization Model for Railway Networks with Multiplatform Stations," Sustainability, MDPI, vol. 12(1), pages 1-25, December.
    8. 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.
    9. Ballis, Athanasios & Golias, John, 2004. "Towards the improvement of a combined transport chain performance," European Journal of Operational Research, Elsevier, vol. 152(2), pages 420-436, January.
    10. Chiang, Wen-Chyuan & Kouvelis, Panagiotis & Urban, Timothy L., 2006. "Single- and multi-objective facility layout with workflow interference considerations," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1414-1426, November.
    11. Hernan Caceres & Rajan Batta & Qing He, 2017. "School Bus Routing with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 51(4), pages 1349-1364, November.
    12. Li, Feng & Sheu, Jiuh-Biing & Gao, Zi-You, 2014. "Deadlock analysis, prevention and train optimal travel mechanism in single-track railway system," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 385-414.
    13. Chang, Yu-Hern & Yeh, Chung-Hsing & Shen, Ching-Cheng, 2000. "A multiobjective model for passenger train services planning: application to Taiwan's high-speed rail line," Transportation Research Part B: Methodological, Elsevier, vol. 34(2), pages 91-106, February.
    14. Lin, Zhiyuan & Kwan, Raymond S.K., 2016. "A branch-and-price approach for solving the train unit scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 97-120.
    15. Wen, M. & Li, R. & Salling, K.B., 2016. "Optimization of preventive condition-based tamping for railway tracks," European Journal of Operational Research, Elsevier, vol. 252(2), pages 455-465.
    16. Zhang, Chuntian & Gao, Yuan & Yang, Lixing & Gao, Ziyou & Qi, Jianguo, 2020. "Joint optimization of train scheduling and maintenance planning in a railway network: A heuristic algorithm using Lagrangian relaxation," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 64-92.
    17. Paul Corry & Christian Bierwirth, 2019. "The Berth Allocation Problem with Channel Restrictions," Transportation Science, INFORMS, vol. 53(3), pages 708-727, May.
    18. Aliakbari, Mina & Geunes, Joseph & Ghahari, Amir & Prince, Mike, 2024. "Freight railcar-to-train assignment and departure scheduling in a railyard," European Journal of Operational Research, Elsevier, vol. 314(3), pages 950-962.
    19. Lesel, J. & Bourdon, D. & Claisse, G. & Debay, P. & Robyns, B., 2017. "Real time electrical power estimation for the energy management of automatic metro lines," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 131(C), pages 3-20.
    20. Jenny Nossack & Dirk Briskorn & Erwin Pesch, 2018. "Container Dispatching and Conflict-Free Yard Crane Routing in an Automated Container Terminal," Transportation Science, INFORMS, vol. 52(5), pages 1059-1076, October.

    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:eee:transe:v:133:y:2020:i:c:s1366554518311815. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    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.