Finding Optimal Travel Routes with Uncertain Cost Data

Geospatial data analysis techniques are widely used to find optimal routes from specified starting points to specified destinations. Optimality is defined in terms of minimizing some impedance value over the length of the route – the value to be minimized might be distance, travel time, financial cost, or any other metric. Conventional analysis procedures assume that impedance values of all possible travel routes are known a priori, and when this assumption holds, efficient solution strategies exist that allow truly optimal solutions to be found for even very large problems. When impedance values are not known with certainty a priori, exact solution strategies do not exist and heuristics must be employed. This study evaluated how the quality of the solutions generated by one such heuristic were impacted by the nature of the uncertainty in the cost database, the nature of the costs themselves, and the parameters used in the heuristic algorithm. It was found that all of these factors influenced the qualities of the solutions produced by the heuristic, but encouragingly, an easily controlled parameter of the heuristic algorithm itself played the most important role in controlling solution quality.