of objective j **in the reference set** P
ref **. For an alternative** x ∈ P
approx **to an**
alternative y ∈ P
ref **, the distance is measured by equation (13).**

$$c(x,y)=\operatorname*{max}_{j=1,\ldots,k}\left\{0;w_{j}\big(g_{j}(x)-g_{j}(y)\big)\right\}$$

Two approaches are used to obtain the distance of the approximation P
approx to the reference set P
ref **. We measure the average distance by equation (14)**
and the worst-case distance by equation (15).

$$(13)$$
$$d_{1}={\frac{1}{\mid P r e f\mid}}\sum_{y\in P r e f}\operatorname*{min}_{x\in M}\left\{c(x,y)\right\}$$  $$d_{2}=\operatorname*{max}_{y\in P r e f}\left\{\operatorname*{min}_{x\in M}\{c(x,y)\}\right\}$$
$$\left(14\right)$$ $$\left(15\right)$$

As our goal is to minimize the distance between the obtained approximations P
approx **and the reference set** P
ref , the distances d1 and d2 **are to be minimized.**
To come to stable and reliable conclusions, average values of d1 and d2 of several test runs with the same configuration are computed.

## 5.3 Results

The test runs were performed on a personal computer, equipped **with an 1**
GHz Intel Pentium III Processor and 384 MB RAM. Each algorithmic configuration was executed 100 times for each test problem in order to **obtain**
stable results. The average number of evaluations of the test runs and the performance of the implemented heuristics is given in table 1 in the appendix.

Resulting from the lower computational effort, the MOLSD is able to evaluate about 4.70 times more solutions per second than the GAs. Each second, 1,385 evaluations were computed by the MOLSD. As expected, all algorithms tend to converge slower in instances with dense and small time windows and random distributed customers. It is worth to mention, that the increase of the necessary evaluations of the MOLSD from a β = 20 to a β **= 30 was about factor 9.14, a huge increase compared to**
the additional computations of the GAs, having factors of 1.80 for **the PMX,**
1.96 for the OBX, 1.78 for the UOBX and 2.63 for the UOBX∧**2EX.**
The results, given in table 2 and 3 in the appendix indicate a strong dependency of the approximation quality on the distribution of the customers α.

The examined crossover operators PMX, OBX, UOBX itself as well as the genetic algorithm including the swap mutation UOBX∧**2EX were in most**
instances with an α = C **not able to outperform the simple local search**
approach MOLSD. Both defined measures d1 and d2 **are affected by this**
property and the distance between the values of the MOLSD to the **values of**
the GAs is increasing with falling γ or rising δ**. We conclude, that VRPSTW**
with a structured distribution of the customers are more easy to be solved