Research on New Tabu Search Algorithm for Min-Max Vehicle Routing Problem - Advanced Research on Computer Education, Simulation and Modeling - page 80

2 Mathematical Model

⎧ ⎫

∑∑∑
∈∈∈

Z = Min Max X

ijk d

(1)

⎨ ⎬ ij

⎩ ⎭

i S j S k V

Constraints:

∑∑
∈∈

q X ≤ W , k ∈ V

(2)

i ijk k

i H j S

∑
∈

X = Y , j ∈ S , k ∈ V

(3)

ijk ik

i S

∑
∈

X = Y , i ∈ S , k ∈ V

(4)

ijk ik

j S

{ }

∑∑
∈∈

x ≤ m − 1 ∀ m ⊆ 2 ..., n , k ∈ V

(5)

ijk

i S j S

{ }

is a series of aggregations of distribution centre in the
place R (this essay only has one);

In the formula:

G r r = 1 ,..., R

{

}

H i i = R + 1 ,... R + N

is a series of clients' aggregations

{} { }

in the place N ; S G H is the combination of all distribution centres and clients.

U

{ }

V k k = 1 ,... K

is travel vehicle k 's aggregation; q is the demand amount of cli-

( )

ent i i ∈ H ;

W is travel vehicle k 's loading capacity;

i d is the linear distance from

client i to client j .

3 Parameter Design for Tabu Search Algorithm

3.1 The Formation of Initial Solution

Given

h as the total number of client nodes served by vehicle k , aggregation
} to correspond the client nodes served by the number k vehicle,

i Y signified that vehicle k served in node i ,

R = { y 0 ≤ i ≤ h

k ik k

Y 0 signified that the number k vehicle's
beginning point was distribution centre. The procedures as such:

k

Step1: Order vehicles' initial remaining load capacity: w

1

= w , k = 0 ,

h

= 0 ,

k k

R ;
Step2: The demand amount corresponding to the i client node in a route

= Φ

q , order

k = 1 ;

{

1
k

1 1

Step3: if q

i w

≤ , then order w = Min ( w − q ), w } , if not turn to Step6;

k k i k