Cost-Optimal Time-dEpendent Routing with Time and Speed Constraints in Directed Acyclic Road Networks

Yaqiong Liu (), Hock Soon Seah and Guochu Shou
Additional contact information
Yaqiong Liu: Beijing Key Laboratory of Network System Architecture and Convergence, School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, 100876, P. R. China
Hock Soon Seah: #x2020;School of Computer Science and Engineering, Nanyang Technological University, 639798, Singapore
Guochu Shou: Beijing Key Laboratory of Network System Architecture and Convergence, School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, 100876, P. R. China

International Journal of Information Technology & Decision Making (IJITDM), 2016, vol. 15, issue 06, 1413-1450

Abstract: Travel costs on road networks always change over time which implies road networks are time dependent. Most studies on time-dependent road networks simply find the shortest path with the least travel time without considering waiting at some nodes, or fuel consumption and toll fee. In real-world applications or computer games, waiting may be allowed at some nodes but disallowed at other nodes; a user can traverse an edge at different speeds; monetary travel cost contains fuel cost and toll fees; and users usually prefer the minimum-cost route under time and speed constraints. Therefore, we study Cost-Optimal Time-dEpendent Routing (COTER) problem with time and speed constraints. We utilize two fuel consumption models and compute the minimum fuel consumption with given travel time for highway edges via nonlinear optimization. We allow the toll fee function to be an arbitrary single-valued time-dependent function. We define an Optimal Cost (OC) function for each candidate node ni, and derive the recurrence relation formula between ni’s incoming neighbors’ OC-functions and ni’s OC-functions. To solve COTER, we propose a five-step algorithm, namely, ALG-COTER, which uses Fibonacci-heap optimized Dijkstra, topological sorting, dynamic programming, binary min-heap optimization, nonlinear optimization, and backtracking algorithms. Experimental results on three real-world road networks of different sizes demonstrate that our algorithm finds the optimal route efficiently and is scalable to different parameters.

Keywords: Cost-optimal routing; nonlinear optimization; topological sorting; dynamic programming; speed and time constraint; time-dependent road network (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219622016500437
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:wsi:ijitdm:v:15:y:2016:i:06:n:s0219622016500437

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219622016500437

Access Statistics for this article

International Journal of Information Technology & Decision Making (IJITDM) is currently edited by Yong Shi

More articles in International Journal of Information Technology & Decision Making (IJITDM) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().