the vehicle.

The objective of the problem is to maximize quality of service and to minimize cost, such that the requirements of the customers and the side-constraints are met. It is obvious, that the violation of the time windows has to be minimized in order to achieve a high quality of service. This can be done by minimizing the number of time window violations and the time window violations itself, measured in time units. The cost consist of a fixed part, induced by the number of used vehicles and a variable part, caused by the route length and the travel time.

## 2.3 Notation Of The Model

The customers and the depot are modelled as vertices V = {v0, v1**, ..., v**N } in a graph G = (V, A), connected by a set of arcs A. In V **, the depot is indexed** by 0 and the total number of customers is N.

With each arc (vi, vj ) from node vi to vj **, a nonnegative travel time** tvi,vj, a distance dvi,vj and a cost cvi,vj**is associated. It is assumed that** tvi,vj = dvi,vj = cvi,vj ∀(vi, vj ) ∈ A.

uvi: unloading time at customer vi, vi ∈ V . dvi: demand of customer vi, vi ∈ V .

d max**: capacity constraint of the vehicles.**
[avi
, bvi]: time window at customer vi, vi ∈ V . avi **defines the desired earliest,**
bvi**the latest time of service. It is necessary that** bvi ≥ avi ∀vi ∈ V .

t a vi
: arrival time of the vehicle at customer vi, vi ∈ V .

rk =-[1]k, [2]k, ..., [nk]k: route rk, representing nk **customers in a given sequence. To assure, that each customer is included in exactly one route, it is**
necessary that rk ∩ rk′ = ∅ ∀k 6= k
′ and | ∪rk |=| V \ {v0} |.

R = {r1, ..., rm}: set of routes of the solution. The number of routes m can be greater than one and does not have to be equal in every solution.

The time t(rk) to travel route rk **can now be obtained by calculating**

$$t(r_{k})=a_{v_{0}}+t_{v_{0},[1]_{k}}+t_{[n_{k}]_{k},v_{0}}+\sum_{[i]_{k}=1}^{n_{k}-1}(t_{[i]_{k},[i+1]_{k}}+u_{[i]_{k}})+u_{[n_{k}]_{k}},$$
$$\left(2\right)$$
$$\left({\mathrm{3}}\right)$$

$\mathbf{M}$
) + u[nk]k(2)
As the time window [av0

, bv0
**] defines the interval in which the vehicles are**
available, it is necessary that

$$t(r_{k})\leq b_{v_{0}}\quad\forall r_{k}\in R$$
t(rk) ≤ bv0 ∀rk ∈ R (3)
The quantity q(rk) of transported goods on route rk **is given by**

$$q(r_{k})=\sum_{i=1}^{n_{k}}d_{v_{i}}$$
$$\left({4}\right)$$
dvi(4)