A Multi-objective Time-dependent Route Planner: A Real World Application to Milano City

The past decades have seen a great deal of research on algorithms for shortest path problems. However, real-world systems like route planners and mobile navigation systems require to take into account some additional conditions. Our work concerns a truck route planner for real-time navigation developed for an Italian firm and tested on real world data of Milano road network (about 61,000 nodes and 106,000 arcs). Given the vehicle GPS position and the destination, the route planner allows to find in a few seconds a path between them which minimizes simultaneously travel time, travel cost and risk. Beside the multi-objective optimization and the CPU efficiency, other challenging features faced by the algorithm that supports the route planner are the time-dependency of some attributes (e.g. the travel costs due to the congestion charge ruling the access to limited traffic zone in the Milano centre) and the presence of forbidden turns. Results on the real network of Milano are obtained and discussed.