Performance Evaluation of Vehicle Routing Heuristics

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%