Abstract
For many applications of vehicle routing, there is still a large gap between the requirements and the performance of today’s decision support systems. Although there has been a tremendous increase in the ability to solve ever more complex VRPs (partly due to methodological improvements, partly due to the general increase in computing power), the ability to consistently provide better routing plans in shorter time across a variety of instances will give substantial additional savings. In a generic vehicle routing tool, some form of approximate solution method is required [7,8]. Metaheuristics constitute a popular basis for solving rich and large-size VRPs [2,3,6]. For trajectory based metaheuristics, the typical computational bottleneck is neighborhood evaluation. Similarly, the evaluation of individuals is the bottleneck of population based metaheuristics. These tasks are embarrassingly parallel and prime candidates for parallelization [1]. Around year 2000, the architecture of processors for commodity computers started to change. Due to technological limits, the still prevailing Moore’s law no longer materialized in the form of a doubling of clock speed every 18 months or so. Hence, the tongue-in-cheek ”Beach law” was no longer true. Multi-core processors with an increasing number of cores and higher theoretical performance than their single core predecessors emerged, but each core had lower clock speed. Solution methods for Discrete Optimization Problems (DOPs) need task parallelization to benefit from this development. In addition, there has been a drastic improvement of performance and general programmability of massively parallel stream processing (data parallel) accelerators such as Graphics Processing Units (GPUs). To fully profit from the general recent and future hardware development on modern PC architectures, heterogeneous DOP methods that combine task and data parallelism must be developed. The heterogeneous architecture also invites to a fundamental re-