Moving horizon capacitated arc routing problem

Somnath Buriuly (), Leena Vachhani, Arpita Sinha, Sivapragasam Ravitharan and Sunita Chauhan
Additional contact information
Somnath Buriuly: IITB-Monash Research Academy
Leena Vachhani: IIT Bombay
Arpita Sinha: IIT Bombay
Sivapragasam Ravitharan: Monash University
Sunita Chauhan: Monash University

Journal of Combinatorial Optimization, 2025, vol. 50, issue 2, No 3, 35 pages

Abstract: 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.

Keywords: Capacitated arc routing problem; Moving horizon; Column generation; Multi trip; Dynamic (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01344-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:2:d:10.1007_s10878-025-01344-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01344-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().