Analysis of algorithms for an online version of the convoy movement problem

R Gopalan () and N S Narayanaswamy
Additional contact information
R Gopalan: Temple University
N S Narayanaswamy: Indian Institute of Technology Madras

Journal of the Operational Research Society, 2009, vol. 60, issue 9, 1230-1236

Abstract: Abstract In the convoy movement problem (CMP), a set of convoys must be routed from specified origins to destinations in a transportation network, represented by an undirected graph. Two convoys may not cross each other on the same edge while travelling in opposing directions, a restriction referred to as blocking. However, convoys are permitted to follow each other on the same edge, with a specified headway separating them, but no overtaking is permitted. Further, the convoys to be routed are distinguished based on their length. Particle convoys have zero length and are permitted to traverse an edge simultaneously, whereas convoys with non-zero length have to follow each other, observing a headway. The objective is to minimize the total time taken by convoys to travel from their origins to their destinations, given the travel constraints on the edges. We consider an online version of the CMP where convoy demands arise dynamically over time. For the special case of particle convoys, we present an algorithm that has a competitive ratio of 3 in the worst case and (5/2) on average. For the particle convoy problem, we also present an alternate, randomized algorithm that provides a competitive ratio of (√13−1). We then extend the results to the case of convoys with length, which leads to an algorithm with an O(T+CL) competitive ratio, where T={Max e t(e)}/{Min e t(e)}, C is the maximum congestion (the number of distinct convoy origin–destination pairs that use any edge e) and L={Max c L(c)}/{Min c L(c)}; here L(c)>0 represents the time-headway to be observed by any convoy that follows c and t(e) represents the travel time for a convoy c on edge e.

Keywords: convoy movement problem; online algorithms; competitive ratio (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2602612 Abstract (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:60:y:2009:i:9:d:10.1057_palgrave.jors.2602612

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2602612

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().