Online convoy movement problem with k blocked edges

Byung Jun Ju and Byung Do Chung

Transportation Research Part B: Methodological, 2025, vol. 199, issue C

Abstract: In this paper, we propose a novel online variant of the convoy movement problem, termed the online convoy movement problem with k blocked edges. This problem includes up to k unrecoverable blocked edges, which are unknown in advance and are gradually revealed as convoys encounter them. The goal is to obtain conflict-free paths for convoys under the online scenario to minimize the total flow time for all convoys. The competitive ratio is used to evaluate the performance of online algorithms, which involves comparing their worst-case performance with the optimal offline solutions. We prove a lower bound of 2k|C|+1 for the competitive ratio of all deterministic online algorithms for the proposed problem, where |C| denotes the cardinality of the set of convoys C. Additionally, we develop five online algorithms: backtrack, simple backtrack, iterative local search, modified iterative local search, and iterative disjoint path. We prove that the competitive ratios of the backtrack and simple backtrack algorithms are 2k+1 and |C|·(4k+2), respectively. However, the internal logic of these two algorithms may render them impractical in real-world situations. Therefore, we utilize the three other algorithms to find practically feasible conflict-free paths. Computational experiments are conducted to evaluate these five online algorithms on real-world instances.

Keywords: Convoy movement problem; Online routing problem; Online algorithm; Competitive analysis (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261525001328
Full text for ScienceDirect subscribers only

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:eee:transb:v:199:y:2025:i:c:s0191261525001328

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2025.103283

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().