(Created page with " == Abstract == Traditional solutions to shortest path problems on time-varying transportation networks use traffic information only at precise moments regardless of consider...") |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 3: | Line 3: | ||
Traditional solutions to shortest path problems on time-varying transportation networks use traffic information only at precise moments regardless of considering the fact that the travel time through any link is dependent on the time entering that link. In this study, travel speed rather than travel time on each link is used as the time period dependent parameter to model time-dependent transportation networks, and a First-In-First-Out (FIFO) condition satisfied computational function of link travel time is then deduced based on kinematics. Finally, a temporally adaptive A* shortest path algorithm on this FIFO network is presented, where the time factor is introduced into the evaluation function, and the Euclidean distance divided by the maximum possible travel speed is used as a heuristic evaluator. An experiment on a real road network shows that the proposed algorithm is capable of foreseeing and bypassing forthcoming traffic congestion, at a cost only about 10% more in computational time than the traditional algorithm. In addition, frequent path reoptimization required with use of the traditional algorithm is effectively avoided. | Traditional solutions to shortest path problems on time-varying transportation networks use traffic information only at precise moments regardless of considering the fact that the travel time through any link is dependent on the time entering that link. In this study, travel speed rather than travel time on each link is used as the time period dependent parameter to model time-dependent transportation networks, and a First-In-First-Out (FIFO) condition satisfied computational function of link travel time is then deduced based on kinematics. Finally, a temporally adaptive A* shortest path algorithm on this FIFO network is presented, where the time factor is introduced into the evaluation function, and the Euclidean distance divided by the maximum possible travel speed is used as a heuristic evaluator. An experiment on a real road network shows that the proposed algorithm is capable of foreseeing and bypassing forthcoming traffic congestion, at a cost only about 10% more in computational time than the traditional algorithm. In addition, frequent path reoptimization required with use of the traditional algorithm is effectively avoided. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| Line 15: | Line 10: | ||
* [http://www.isprs.org/proceedings/XXXVIII/part2/Papers/89_Paper.pdf http://www.isprs.org/proceedings/XXXVIII/part2/Papers/89_Paper.pdf] | * [http://www.isprs.org/proceedings/XXXVIII/part2/Papers/89_Paper.pdf http://www.isprs.org/proceedings/XXXVIII/part2/Papers/89_Paper.pdf] | ||
| + | |||
| + | * [http://www.springerlink.com/index/pdf/10.1007/978-3-642-25926-5_14 http://www.springerlink.com/index/pdf/10.1007/978-3-642-25926-5_14], | ||
| + | : [http://dx.doi.org/10.1007/978-3-642-25926-5_14 http://dx.doi.org/10.1007/978-3-642-25926-5_14] | ||
| + | |||
| + | * [https://link.springer.com/chapter/10.1007/978-3-642-25926-5_14 https://link.springer.com/chapter/10.1007/978-3-642-25926-5_14], | ||
| + | : [https://www.scipedia.com/public/Zheng_Lu_2012a https://www.scipedia.com/public/Zheng_Lu_2012a], | ||
| + | : [https://rd.springer.com/chapter/10.1007/978-3-642-25926-5_14 https://rd.springer.com/chapter/10.1007/978-3-642-25926-5_14], | ||
| + | : [https://doi.org/10.1007/978-3-642-25926-5_14 https://doi.org/10.1007/978-3-642-25926-5_14], | ||
| + | : [https://dblp.uni-trier.de/db/conf/sdh/sdh2010.html#ZhengL10 https://dblp.uni-trier.de/db/conf/sdh/sdh2010.html#ZhengL10], | ||
| + | : [https://academic.microsoft.com/#/detail/63403264 https://academic.microsoft.com/#/detail/63403264] | ||
Latest revision as of 17:07, 21 January 2021
Abstract
Traditional solutions to shortest path problems on time-varying transportation networks use traffic information only at precise moments regardless of considering the fact that the travel time through any link is dependent on the time entering that link. In this study, travel speed rather than travel time on each link is used as the time period dependent parameter to model time-dependent transportation networks, and a First-In-First-Out (FIFO) condition satisfied computational function of link travel time is then deduced based on kinematics. Finally, a temporally adaptive A* shortest path algorithm on this FIFO network is presented, where the time factor is introduced into the evaluation function, and the Euclidean distance divided by the maximum possible travel speed is used as a heuristic evaluator. An experiment on a real road network shows that the proposed algorithm is capable of foreseeing and bypassing forthcoming traffic congestion, at a cost only about 10% more in computational time than the traditional algorithm. In addition, frequent path reoptimization required with use of the traditional algorithm is effectively avoided.
Original document
The different versions of the original document can be found in:
Document information
Published on 01/01/2012
Volume 2012, 2012
DOI: 10.1007/978-3-642-25926-5_14
Licence: CC BY-NC-SA license
Share this document
Keywords
claim authorship
Are you one of the authors of this document?