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.

► We apply exact multiobjective search techniques to large size realistic road maps.
► Blind search, a distance heuristic, and a precalculated heuristic are tested.
► Precalculation effort is shown to pay off and to improve over the other heuristics.
► Problems in maps with two objectives and up to one million nodes are solved.