Abstract
In real world applications, the path-planning problem is one that is multi-criteria in nature though given the complexity of the task is one that is often condensed to a single criterion issue, either by the consideration of only a single objective or condensing several criteria into a single metric through aggregation or weighting. The thesis describes research that has led to the development and application of heuristic techniques in order to optimise shortest paths where more than one single criterion is to be evaluated. The techniques are described and demonstrated, and their effectiveness established by testing them using synthetic and real world datasets. The scalability of the heuristics to increasing numbers of criteria is demonstrated.Heuristic techniques are able to solve the Multi Objective Shortest Path Problem (MSPP). In several cases, the performance of the techniques outperform traditional algorithmic methods by over 30-50% in terms of runtime, whilst returning a good approximation of the optimal set of paths. Promising alternative methods for candidate path generation are presented. These offer a much faster runtime for the evolutionary algorithm approach, which is able to complete a run on larger graphs in around five seconds. Further, several potentially more promising methods have been identified for future work, these would lead to increased performance of the mechanisms with a decreased runtime whilst returning a more complete set of optimal solutions.
| Date of Award | Sep 2012 |
|---|---|
| Original language | English |
| Supervisor | Stuart Cole (Supervisor) & Colin Morris (Supervisor) |