A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation
Theoretical research often assumes all users are homogeneous in their route choice decision and will always pick the route with the shortest travel cost, which is not necessarily the case in reality. This paper documents the research effort in developing a Constrained Time-Dependent K Shortest Paths...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
KeAi Communications Co., Ltd.
2015-01-01
|
Series: | International Journal of Transportation Science and Technology |
Subjects: | |
Online Access: | http://www.sciencedirect.com/science/article/pii/S2046043016301691 |
_version_ | 1797720184662786048 |
---|---|
author | Xianbiao Hu, PhD Yi-Chang Chiu |
author_facet | Xianbiao Hu, PhD Yi-Chang Chiu |
author_sort | Xianbiao Hu, PhD |
collection | DOAJ |
description | Theoretical research often assumes all users are homogeneous in their route choice decision and will always pick the route with the shortest travel cost, which is not necessarily the case in reality. This paper documents the research effort in developing a Constrained Time-Dependent K Shortest Paths Algorithm in order to find K Shortest Paths between two given locations. The goal of this research is to provide sound route options to travelers in order to assist their route choice decision process, during which the overlap and travel time deviation issues between the K paths will be considered. The proposed algorithm balancing overlap and travel time deviation is developed in this research. A numerical analysis is conducted on the Tucson I-10 network, the outcome of the case study shows that our proposed algorithm is able to find different shortest paths with a reasonable degree of similarity and close travel time, which indicates that the result of the proposed algorithm is satisfactory. |
first_indexed | 2024-03-12T09:15:50Z |
format | Article |
id | doaj.art-46cd8734ffb34b14b94c96b3b116125e |
institution | Directory Open Access Journal |
issn | 2046-0430 |
language | English |
last_indexed | 2024-03-12T09:15:50Z |
publishDate | 2015-01-01 |
publisher | KeAi Communications Co., Ltd. |
record_format | Article |
series | International Journal of Transportation Science and Technology |
spelling | doaj.art-46cd8734ffb34b14b94c96b3b116125e2023-09-02T14:47:20ZengKeAi Communications Co., Ltd.International Journal of Transportation Science and Technology2046-04302015-01-014437139410.1016/S2046-0430(16)30169-1A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time DeviationXianbiao Hu, PhD0Yi-Chang Chiu1Department of Civil Engineering and Engineering Mechanics, University of Arizona, Tucson, USAAssociate Professor, Department of Civil Engineering and Engineering Mechanics, University of Arizona, Tucson, USATheoretical research often assumes all users are homogeneous in their route choice decision and will always pick the route with the shortest travel cost, which is not necessarily the case in reality. This paper documents the research effort in developing a Constrained Time-Dependent K Shortest Paths Algorithm in order to find K Shortest Paths between two given locations. The goal of this research is to provide sound route options to travelers in order to assist their route choice decision process, during which the overlap and travel time deviation issues between the K paths will be considered. The proposed algorithm balancing overlap and travel time deviation is developed in this research. A numerical analysis is conducted on the Tucson I-10 network, the outcome of the case study shows that our proposed algorithm is able to find different shortest paths with a reasonable degree of similarity and close travel time, which indicates that the result of the proposed algorithm is satisfactory.http://www.sciencedirect.com/science/article/pii/S2046043016301691K shortest Paths Algorithm (KSP)Time Dependent Shortest Path (TDSP)Constrained Shortest Path, Route OverlapTravel time DeviationActive Traffic and Demand Management (ATDM)Route Choice |
spellingShingle | Xianbiao Hu, PhD Yi-Chang Chiu A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation International Journal of Transportation Science and Technology K shortest Paths Algorithm (KSP) Time Dependent Shortest Path (TDSP) Constrained Shortest Path, Route Overlap Travel time Deviation Active Traffic and Demand Management (ATDM) Route Choice |
title | A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation |
title_full | A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation |
title_fullStr | A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation |
title_full_unstemmed | A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation |
title_short | A Constrained Time-Dependent K Shortest Paths Algorithm Addressing Overlap and Travel Time Deviation |
title_sort | constrained time dependent k shortest paths algorithm addressing overlap and travel time deviation |
topic | K shortest Paths Algorithm (KSP) Time Dependent Shortest Path (TDSP) Constrained Shortest Path, Route Overlap Travel time Deviation Active Traffic and Demand Management (ATDM) Route Choice |
url | http://www.sciencedirect.com/science/article/pii/S2046043016301691 |
work_keys_str_mv | AT xianbiaohuphd aconstrainedtimedependentkshortestpathsalgorithmaddressingoverlapandtraveltimedeviation AT yichangchiu aconstrainedtimedependentkshortestpathsalgorithmaddressingoverlapandtraveltimedeviation AT xianbiaohuphd constrainedtimedependentkshortestpathsalgorithmaddressingoverlapandtraveltimedeviation AT yichangchiu constrainedtimedependentkshortestpathsalgorithmaddressingoverlapandtraveltimedeviation |