Multiobjective Route Planning with Precalculated Heuristics

Enrique Machuca and Lawrence Mandow.
Multiobjective route planning with precalculated heuristics.
In L. Antunes, H. Sofia Pinto, R. Prada, and P. Trigo, editors, Proceedings of the 15th Portuguese Conference on Artificial Intelligence (EPIA 2011), pages 98-107. 2011.


This paper describes the application of multiobjective heuristic search algorithms to the problem of route planning in road maps. Multiobjective search reveals the trade-off between objectives and allows for more informed decisions than single objective search but, at the same time, it is known to be more complex computationally. The efficiency of existing search algorithms is known to depend on factors such as correlation between objectives and label selection schemes. The paper shows the application of multiobjective search techniques to route planning problems involving two relatively uncorrelated objectives: economic cost (including fuel and tolls ) and travel time. The impact of heuristic information and label selection in search efficiency are analyzed.


  affiliation={Universidad de M{\'a}laga Dpto. Lenguajes y Ciencias de la Computaci{\'o}n 29071 M{\'a}laga Spain},
  url={http: // = 601b4e18-cbbb-49eb-8857-832fd86ce8f1.pdf},
  author={Machuca, Enrique and Mandow, Lawrence},
  title={Multiobjective Route Planning with Precalculated Heuristics},
  editor={L. Antunes and H. Sofia Pinto and R. Prada and P. Trigo},
  booktitle={Proceedings of the 15th Portuguese Conference on Artificial Intelligence (EPIA 2011)},
Redmine Appliance - Powered by TurnKey Linux