Abstract

During the last years, many speed-up techniques for Dijkstra 's algorithm have been developed. As a result, computing a shortest path in a staticroad network is a matter of microseconds. However, only few of those techniques work in time-dependentnetworks. Unfortunately, such networks appear frequentely in reality: Roads are predictably congestured by traffic jams, and efficient timetable information systems rely on time-dependent networks. Hence, a fast technique for routing in such networks is needed. In this work, we present an exacttime-dependent speed-up technique based on our recent SHARC-algorithm. As a result, we are able to efficiently compute shortest paths in time-dependent continental-sized transportation networks, both of roads and of railways. Document type: Part of book or chapter of book

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. Document type: Part of book or chapter of book

Abstract

prototype for an operational ship routing Decision Support System using time-dependent meteo-oceanographic fields is presented. The control variable is ship course, which is modified using a directional resolution of less than 27 degrees. The shortest path is recovered using a modified Dijkstra’s algorithm. Safety restrictions for avoiding surfriding and parametric rolling according to the guidelines of the International Maritime Organization (IMO) are implemented. Numerical experiments tailored on a medium-size vessel are presented and perspectives of development of the system are outlined.