Author(s)

FRANCISCO A. ORTEGA, GUIDO MARSEGLIA, JUAN A. MESA, RAMÓN PIEDRA-DE-LA-CUADRA

Abstract

Navigation systems implemented in mobile devices allow users to search for the shortest routes between pairs of points. Many of the existing commercial products assume in a simplified way that the travel time to cross each arc of a road network is fixed, once a starting time has been established. However, the real travel time along a road section within cities depends on many factors that are related to traffic congestion, weather conditions, possible incidents, etc., and consequently, it depends on the time. As can easily be shown, determining the shortest itineraries in a network whose arcs are time-dependent can result in a diversity of optimal routes for a same origin–destination pair based on different departure times. Assuming the availability of the estimated data of the time required to travel along each section of the street network, once the departure time has been previously set, we propose in this work an efficient algorithm for obtaining faster routes on time-dependent arcs, in such a way that the sum of driving times is minimized, which in parallel allows improving fuel consumption and reducing associated polluting emissions. The possibility of introducing waiting periods in the nodes to optimize the total time spent on the trip has also been considered in the design of the proposed procedure. An experimental evaluation is carried out to show the effectiveness of the provided algorithm.

Keywords

route planning, guided transport systems, mobility, transport networks, Dijkstra’s algorithm