with simple local search while the examined configurations of the genetic algorithm tend to get stucked in local optima. This effect grows with a **declining complexity of the underlying problem, expressed by a low coverage**
with time windows γ or wide time windows δ**. Similar results have already**
been reported for the single objective VRPTW [2] and can be confirmed for the multi-objective formulation. For VRPSTW with a random distribution of the customer we observe the contrary. In most test instances, the best results for the average distance d1 are obtained by the UOBX∧2EX. However, the advantage of the UOBX∧2EX
to the MOLSD is decreasing with falling γ or increasing δ**. For some problems** with large time windows δ and a small coverage γ**, e.g. the "R;30;1.00;80/95/115",**
MOLSD produces better results.

The results of d2 **indicate, that the average worst-case deviation of the approximation** P
approx **to the reference set** P
ref **is superior in the approach of**
the MOLSD, except for some smaller instances with β **= 20 and the hard**
"R;30;1.00;10".

A closer investigation of the results shows, that the superior results of the UOBX∧**2EX is due to the use of the swap mutation operator. Comparing the**
results for the crossover-only GAs, it can be seen that with respect to the distances d1 and d2 **OBX and UOBX perform in most instances better than**
PMX. On the other hand, a clear distinction between OBX and UOBX can't be concluded.

The results show a strong influence of the mutation operator on the effectiveness for the genetic algorithm. Although the GAs lead to weaker **results**
in clustered data sets than the proposed local search approach, **this behavior** seems to be typical for the presented multi-objective optimization **problem.**

## 6 Conclusions

The goal of the paper was to investigate the influence of the problem structure on the effectiveness of different configurations of a genetic algorithm.

A multi-objective formulation of the vehicle routing problem with soft **time**
windows has been presented, describing the requirements of practical logistics more detailed than single criterion models. For comparison reasons, an approach of a local search approach incorporating storage of multiple nondominated solutions was proposed.

The results show, that the problem structure, especially the distribution of the customers α**, is crucial for the behavior of the investigated algorithms.**
The genetic algorithms outperform the local search approach especially well in complex problems with dense and small time windows and a random distribution of the customers. However, the influence of the mutation operator seems to be stronger than expected and described in other publications on GAs. An important role of simple (local search based) mutations can indicate, that