In the past, the vehicle routing problem has been subject to extensive research. Since its original statement in [4] much research has been conducted in finding both exact solutions for smaller instances as well as determine good heuristics for solving large instances. Several extensions have been defined [5, 6] and a robust method for solving the vehicle routing problem (VRP) is part of the repertoire of many optimization suites. While this problem has received much attention from an optimization perspective, trying to solve this problem and compare different solution approaches[2], little research has been done to understand the structure of the problem instances themselves. In [8] different distances metrics and a fitness-distance correlation analysis[7] is performed which points towards a big-valley structure of the local optima, which, however, could not be confirmed in [3]. In the latter article, however, fitness landscape analysis is used to tune the initial temperature of a simulated annealing algorithm. Also, in [11], the landscapes of different mutation and crossover operators are subjected to analysis.