Hierarchical time-dependent shortest path algorithms for vehicle routing under ITS

Mark Mahyar Nejad, Lena Mashayekhy, Ratna Babu Chinnam and Anthony Phillips

IISE Transactions, 2016, vol. 48, issue 2, 158-169

Abstract: The development of efficient algorithms for vehicle routing on time-dependent networks is one of the major challenges in routing under intelligent transportation systems. Existing vehicle routing navigation systems, whether built-in or portable, lack the ability to rely on online servers. Such systems must compute the route in a stand-alone mode with limited hardware processing/memory capacity given an origin/destination pair and departure time. In this article, we propose a computationally efficient, yet effective, hierarchical algorithm to solve the time-dependent shortest path problem. Our proposed algorithm exploits community-based hierarchical representations of road networks, and it recursively reduces the search space in each level of the hierarchy by using our proposed search strategy algorithm. Our proposed algorithm is efficient in terms of finding shortest paths in milliseconds for large-scale road networks while eliminating the need to store preprocessed shortest paths, shortcuts, lower bounds, etc. We demonstrate the performance of the proposed algorithm using data from Detroit, New York, and San Francisco road networks.

Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/0740817X.2015.1078523 (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:taf:uiiexx:v:48:y:2016:i:2:p:158-169

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/0740817X.2015.1078523

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().