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.

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

BRUGLIERI, MAURIZIO;COLORNI VITALE, ALBERTO;LUE', ALESSANDRO
2014

Abstract

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.
congestion charge, multi-objective optimization, time-dependent path, turn prohibition
File in questo prodotto:
File Dimensione Formato  
Route_Planner_Bruglieri_etal_EWGT2014_PUBLISHED.pdf

accesso aperto

Descrizione: Articolo_principale
: Publisher’s version
Dimensione 636.78 kB
Formato Adobe PDF
636.78 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/986693
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact