Performance Evaluation of Vehicle Routing Heuristics
L.H. Sikkes (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Neil Yorke-Smith – Mentor (TU Delft - Algorithmics)
Joost Donkers – Graduation committee member (Ortec B.V.)
Annibale Panichella – Graduation committee member (TU Delft - Software Engineering)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This thesis has researched the automation of performance evaluation of vehicle routing heuristics. The trade-off between solution quality, which is composed of multiple variables, and runtime make performance evaluation challenging. Therefore, it is often done by human experts. The research question of this thesis is: “How can we determine a performance measure that correctly represents the trade off between quality and runtime in vehicle routing heuristics?”. A literature review revealed that much research was done on performance evaluation, but not on heuristics specifically. The performance profile, a cumulative distribution function, is said to reflect all major performance characteristics of a solver. This, combined with a clustering algorithm, is used in this thesis in a classifier to detect performance anomalies. The performance profile needs a performance measure, for which three options were introduced: the area under the chart, the quality at the same time and the maximum difference. Through experimentation, 18 measure configurations were tested and rated on their accuracy and apparent issues. Three of the measure configurations have promising results, with an accuracy of roughly 80%.