IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v50y2025i2d10.1007_s10878-025-01344-w.html
   My bibliography  Save this article

Moving horizon capacitated arc routing problem

Author

Listed:
  • Somnath Buriuly

    (IITB-Monash Research Academy
    IIT Bombay
    Monash University)

  • Leena Vachhani

    (IIT Bombay)

  • Arpita Sinha

    (IIT Bombay)

  • Sivapragasam Ravitharan

    (Monash University
    Monash University)

  • Sunita Chauhan

    (Monash University)

Abstract

In transportation networks, routing problems are cursed with arbitrary changes occurring in the dataset due to unpredictable events like agent breakdown (sensor or vehicle failure), network connectivity changes, resource/demand fluctuations, etc. Moreover, capacity restriction on the agents may require multi-trip solutions for meeting large demands over networks. For example, a battery-powered inspection wagon can only service a limited number of track sections in a single trip. We investigate a moving horizon approach for the multi-trip dynamic capacitated arc routing problem with limited duration to mitigate the limitations of CARP variants in the literature. The proposed approach addresses arbitrary changes in the underlying network, agent unavailability scenarios, and simultaneously satisfies the time limit on meeting all demands. The moving horizon approach subdivides the planning horizon to determine the current trip (single-trip) for all agents, hence coined as Moving Horizon Capacitated Arc Routing Problem (MH-CARP). The proposed MH-CARP is formulated as a set covering problem that considers both partial and full trips (trips may not start at the depot), making it suitable for tackling arbitrary events by re-planning. Theoretical results for the computation of dual variables are derived and then implemented in the column generation algorithm to obtain lower bounds. The algorithm is validated on a widely available dataset for CARP, having instances of up to 147 tasks that require servicing by up to 20 agents. Using this benchmark data, the partial-trip based re-planning strategy is also validated. Lastly, a simulation study is presented to demonstrate the re-planning strategy and compare an MH-CARP solution to two CARP based solutions - one with no arbitrary events and the other with known arbitrary events. The results also convey that greedy solutions are avoided to satisfy the limited duration restriction, and automatic re-ordering of the trips is achieved to compensate for arbitrary events.

Suggested Citation

  • Somnath Buriuly & Leena Vachhani & Arpita Sinha & Sivapragasam Ravitharan & Sunita Chauhan, 2025. "Moving horizon capacitated arc routing problem," Journal of Combinatorial Optimization, Springer, vol. 50(2), pages 1-35, September.
    • Handle: RePEc:spr:jcomop:v:50:y:2025:i:2:d:10.1007_s10878-025-01344-w
    DOI: 10.1007/s10878-025-01344-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-025-01344-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-025-01344-w?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

    for a different version of it.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    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:spr:jcomop:v:50:y:2025:i:2:d:10.1007_s10878-025-01344-w. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.