Multiobjective heuristic search in road maps

摘要

This article considers the application of exact multiobjective techniques to search in large size realistic road maps. In particular, the NAMOA∗ algorithm is successfully applied to several road networks from the DIMACS shortest path implementation challenge with two objectives. An efficient heuristic function previously proposed by Tung and Chew is evaluated. Heuristic values are precalculated with search. The precalculation effort is shown to pay off during the multiobjective search stage. An improvement to the calculation procedure is also proposed, resulting in added improved time performance in many problem instances.