ESTIMATION OF THE SHORTEST ROUTE ON A TIME BASIS IN A ROAD NETWORK

摘要

The invention relates to a device that comprises two modules for determining the shortest route based on a departure time, between source (Ns) and destination (Nd) nodes in an oriented graph (GRT) representative of a road network and covered by cells containing the graph nodes. For each couple of departure (Ci) and arrival (Cj) cells, one module determines a sub-graph (SGi, j) containing the nodes included in routes each connecting a node in the departure cell to a node in the arrival cell and having travel times shorter than a threshold. This module reduces, in the other module, the time for determining the shortest route from the source node to the destination node based on the sub-graph relative to the couple in which the departure cell is to be determined and the arrival cell contains the destination cell.