TY - GEN
T1 - Variable time discretization for a time-dependent shortest path algorithm
AU - Tian, Ye
AU - Chiu, Yi Chang
AU - Gao, Yang
PY - 2011
Y1 - 2011
N2 - This paper introduces a variable time discretization strategy for a time-dependent A* shortest path algorithm. The strategy is aimed at determining the optimal memory allocation for time-dependent travel times data in order to achieve a desirable compromise between accuracy and memory usage. The proposed strategy is based on the dispersion index of the travel times/costs over the entire analysis period, as a result, producing different intervals for each link. The links with travel times that have a higher variance and a lower mean will need to have a shorter time discretization length due to greater fluctuation in travel times. The proposed strategy is implemented in the time-dependent A* algorithm and tested with a numerical experiment on a Tucson, AZ, traffic network. The results show that with the same amount of computer memory usage, the proposed variable time discretization strategy achieves much higher accuracy than that of uniform time discretization.
AB - This paper introduces a variable time discretization strategy for a time-dependent A* shortest path algorithm. The strategy is aimed at determining the optimal memory allocation for time-dependent travel times data in order to achieve a desirable compromise between accuracy and memory usage. The proposed strategy is based on the dispersion index of the travel times/costs over the entire analysis period, as a result, producing different intervals for each link. The links with travel times that have a higher variance and a lower mean will need to have a shorter time discretization length due to greater fluctuation in travel times. The proposed strategy is implemented in the time-dependent A* algorithm and tested with a numerical experiment on a Tucson, AZ, traffic network. The results show that with the same amount of computer memory usage, the proposed variable time discretization strategy achieves much higher accuracy than that of uniform time discretization.
UR - http://www.scopus.com/inward/record.url?scp=83755163815&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=83755163815&partnerID=8YFLogxK
U2 - 10.1109/ITSC.2011.6082871
DO - 10.1109/ITSC.2011.6082871
M3 - Conference contribution
AN - SCOPUS:83755163815
SN - 9781457721984
T3 - IEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC
SP - 588
EP - 593
BT - 2011 14th International IEEE Conference on Intelligent Transportation Systems, ITSC 2011
T2 - 14th IEEE International Intelligent Transportation Systems Conference, ITSC 2011
Y2 - 5 October 2011 through 7 October 2011
ER -