APPLICATION OF IMPROVED MULTISTAGE

VEHICLE ROUTING PROBLEM WITH TIME WINDOW

Dian Retno Sari Dewi1, Dini Endah Setyo Rahaju1, and Lisa Anjani1
1
Industrial Engineering, Widya Mandala Catholic University,Kalijudan 37,Surabaya,Indonesia,[email protected]

ABSTRACT
This paper presented an application of improved multistage vehicle routing problem with time window. By using
this improved method, we can solve a multistage vehicle routing problem issue. We applied this model for two layers
multistage. First layer consist of only one depot which distribute items among the distributors, second layer consist of
several distributors which distribute items among several retailers. Adaptation to Larsen model was for second layer, which
consist of several distributors which distribute to several retailers. Meanwhile Larsen model only worked on one depot
which distribute among several distributors. In this model, we worked on two steps. First step is to solve second layer
problems. We must determine the delivery area of retailers among the distributors by combine all possible path to minimize
distance within capacity vehicle constraint and time window constraint. Next step was to solve first layer problem. We
worked with Larsen model for solving the first layer. Using this improved multistage vehicle routing problem with time
window helped to solve multistage vehicle routing problem as well as minimize distance.

Keywords: multistage, mathematical modelling, time window ,vehicle routing problems

INTRODUCTION PROPOSED MULTISTAGE VRPTW

Logistic activities are much needed these days. MATHEMATICAL MODEL
Many manufacturing activities involved distribution of
finished goods to distributors, distributors to retailers and Larsen, 1999 developed a single depot VRPTW
retailers to customers. Third party logistics as logistic model. Here, we focus on developing Larsen,1999 model
partner run this distribution business to overcome the for multistage VRPTW. Figure 1 is network for
complexity of this distribution issues. Many kinds of daily Multistage vehicle routing problem. O is a Depot. A and B
activities involved on vehicle routing problems application are distributors, C,D,E,F are retailers.
such as: news paper distribution, water gallon
distribution,and mail delivery. 0

Many distribution and transport logistic problems First Layer Model

could be express as a vehicle routing problem which A B

objective function is minimize total distance of the Second Layer Developed

network or minimize cost of transportation under known Model
demand. Each node will be visited exactly once under the C D E F

vehicle capacity constraint [1].

Vehicle Routing Problem (VRP) can be portray Figure 1. Multistage vehicle routing problem Network
as the problem of scheming optimal route from one or
several node to a amount of node to minimize total The Improved Multistage vehicle routing problem with
distance under several constraints [2]. Vehicle Routing time window is solved by two steps, as follows:
Problem With Time Window (VRPTW) is a form of a Step1. Solving the solution for second layer. The second
VRP problems with time window restriction. Some of the layer consist of distributors and retailers. Each
practical example of VRPTW are postal deliveries, school distributor must distribute item to retailers which
bus way, and vendor distribution in just in time minimize total distance. There were several
manufacturing [3, 4]. possible solutions among the distributors to
As a result of value and complexities in a real distribute item to retailers. All possible solutions
life, VRPTW attract much thought from researchers. Much is modelled in Model VRPTW for second layer.
VRPTW works has been done both for optimization and Step 2. Solving the solution for first layer using Larsen
heuristic methods. Most of heuristic methods developed to Model. First layer consist of one depot and
defeat the VRP as NP-hard problems. Such of works can several distributors. Depot must distribute items
be founded in [1,3,5]. Meanwhile,very few works on VRP to several distributors. Solution for this step is
mathematical modeling, Larsen model was one of it. using Larsen model.
Multistage VRPTW is a network consist of two
or more layers of distribution network. First layer consist Mathematical Model VRPTW for second layer as follows:
of one depot which distribute items to several distributors. Objective Function
Second layer usually consist of several distributors which
distribute items to several retailers. Our main contribution Min Z = Y ij X ijk +
is that we develop model for Multistage vehicle routing kVh iC jC
problem with time window.
Y
kVh iD jC
hi X hik + Y
kVh iC
iN h X iN hk

hY hY i j
 two decision variables x and s. For each arc (i,j), which i
(1) j, i n+ 1; j 0, and each vehicle (k) we identify x ijk
as:
Subject to constrains :
X ijk =

kVh jC
X ijk =1 (2)
0, if vehicle k does not drive from node i to node j
iC hD i j
1, if vehicle k drives from node i to node j
X
i C
hik =1 (3) The decision variable s ik is described as start time to
hD k Vh service customer i with vehicle k. It is assumed a 0 = 0

X iN hk =1 (4)
and hence s ok = 0 for all k. The purpose here is that to
i C minimize total distance to each route, with subject to
hD k Vh constraint as follows:
1. Each node is used exactly once.
X
hD
hik - X
jC
ijk =0 2. Time windows are restricted to
constraint.
(5)
3. Vehicles capasity are not exceeded.
iC k Vh i j
W X
iC
i
jC
ijk Qk
Mathematical Model VRPTW for first layer as follows
(Larsen model):
(6) Objective Function:
k V hD
i j
h
Min = D
kv iN jN
ij X ijk

W X
kVh iC
i hik + W
kVh jC iC
j X ijk Q
h (11)
Subject to constraints:
(7)
hD X =1 yjk (12)
Sik + tij K (1-Xijk) Sjk (8) jN

i,j N k v iC
ai Sik bi (9)
i N k v X izk =1 (13)
X hik , X ijk {0,1} iN

(10) kv
The equation (1) is the objective function, to
minimize the total distance between node i to node j and X =1
kv jN
ijk (14)

iC
the others node by vehicle k and ensure to minimize
ij
distance from distributors to several retailers. Constraint
(2) represents that each retailers is visited just only once,
Constraint (3) means that each vehicle k leaves node, X X
iN
ihk
jN
hjk =0 (15)
Constraint (4) represents that each vehicle k arrive on
node, Constraint (5) ensure that vehicle k depart and leave hC kv
to the node N+1, Constraint (6, 7) is the capasity
restriction for every vehicle k, Constraint (8) means that W X
i C
i
j N
ijk Qk
vehicle k has to depart node i during t ij to node j if take a
(16)
trip from node i to node j, K is a large number. Constraint
(9) states a time window restriction, Constraint (10) is a kv
binary integer value for the decision variable. Sik + tij K (1-Xijk) Sjk (17)
A group of vehicles are represented by V, V=1,2, i,j N k v
, v and a set of retailers are represented by C
, C=a,b,.z. Depot represented by node h (driving-out ai Sik bi (18)
depot) and N+h (returning depot). The set of arcs (A)
i N kv
X {0,1}
correspond to connections among depot and retailers and
vice versa, the set of vertice correspond to 0,1,n+1 is ijk (19)
denoted N. Each arc (i,j), where i j. We related a distance i,j N kv
Yij and each customer demand (W i), each vehicle has a The equation (11) is a objective function, to
capacity Qk. Each depot and retailers has a time window minimize the total distance between node i to node j.
[ a i ,b i ], which is assumed identical. All vehicle can not Constraint (12) ensure that each vehicle k departs the
depart before a 0 and must arrive before b i . Model had depot, Constraint (13) ensure that each vehicle k will be
back to depot , Constraint (14) represents that each
distributors is visited only once, Constraint (15) ensure PT. Tirta Bahagia is a aqua gallon distributor company
that vehicle k depart and leave to the node N+1, Constraint which distribute aqua gallon in Surabaya district area.
(16) is the capasity restriction for every vehicle k, Distribution system consist of depot/manufacturing,
Constraint (17) means that vehicle k has to depart node i distributors, and retailers. Depot supervised 3 distributors,
during tij to node j if take a trip from node i to node j, K is and distributors supervised 14 retailers. In this case,
a large number. Constraint (18) ensure a time window distribution each area for distributors have not decided yet.
restriction, Constraint (19) is a binary integer value. This models works to solve distribution area for each
distributor. Second layers model works first as solving the
APPLICATION OF THE MULTISTAGE VRPTW
MATHEMATICAL MODEL
Table 2. Distance between Node (km)
A B C D E F G H I J K L M N O P Q
A 18 28 12 4.7 10.5 5.13 8.32 21.2 22.5 34.56 44.7 37.4 25.7 27.27 15.7 27.2
B 18 0 16 19 13 18.4 16.2 12.01 10.8 11.5 16.51 18.9 16.4 8.14 9.67 5.4 5.22
C 26 16 0 18 26 17.0 23.4 26.50 9.72 8.82 7.74 14.9 7.78 18.7 24.07 12.8 24.0
D 10 19 18 0 15 3.87 13.9 19.17 10.3 14.9 19.44 21.8 22.5 29.2 27.81 18.5 21.8
E 4.8 13 26 14 0 12.37 2.25 3.375 14.7 18.9 26.64 29.2 20.6 27.7 21.87 11.7 15.9
F 10 18 17 3.6 12 0 10.1 15.3 6.43 11.1 22.77 17.9 18.6 25.3 23.94 14.7 17.9
G 5.2 16 23 13 2.5 9.82 0 5.625 17.0 21.1 28.89 31.5 22.9 30.0 24.12 13.9 18.2
H 8.4 11 26 18 3.6 15 5.63 0 12.51 16.6 24.39 27.0 18.4 25.5 19.62 12.4 15.7
I 21 10 9.9 10 15 6.13 17.0 12.5 0 5.22 11.7 19.1 14.3 17.2 17.86 7.15 12.6
J 22 11 9.0 14 19 10.8 21.1 16.64 10.1 0 9.9 15.9 15.3 13.1 18.135 6.25 12.3
K 34 16 7.9 19 26 22.4 28.9 24.38 16.1 9.69 0 10.4 3.46 13.3 18.72 15.7 17.1

L 44 18 15 21 29 17.6 31.5 27.03 15.5 15.7 10.13 0 7.11 12.0 16.42 21.9 21.8
M 37 16 7.9 22 20 18.3 22.9 18.39 13.3 15.0 3.155 7.21 0 4.90 9.31 14.8 14.7
N 25 8.0 18 29 28 25.0 30.0 25.50 18.3 12.9 13.01 12.1 5.00 0 6.12 11.5 10.21
O 27 9.5 24 27 22 23.6 24.13 19.61 6.46 17.9 18.41 16.2 9.41 6.32 0 13.14 9.81
P 15 5.3 13 18 12 14.4 13.9 12.45 12.5 6.04 15.395 22.06 14.95 11.7 12.94 0 7.69
Q 27 5.2 24 21 16 17.6 18.2 15.695 0.21 12.16 16.88 21.9 14.8 10.41 9.61 7.68 0

area for distributor to minimize total distance.

Furthermore, first layers model will be solved using
Larsen model. The time window is from 08.00 WIB and
close at 14.00 WIB. It is assumed the velocity of the
vehicle 30 km/hours.There is 1 vehicles for servicing from
depot to distributors with 1000 box capasity and there are
3 vehicles for servicing from ditributors to retailers with
capasity 200 box each.

Table 1. Demand for retailers

Node Demand (Box) Y
A 573
B 322
C 662
D 36
E 35
F 25
G 28
H 7
I 28 Figure 2. Network Distribution of PT. Tirta Bahagia
J 21
K 17
L 17
M 18 Y as depot, A, B, C as distributors, D Q as retailers
N 35
O 17 Step 1. Solving for second layer.
P 16
Q 15
 2. All demand had already fulfilled and capasity of
the vehicle for each path not exceed.
3. Time Windows restriction was filled.
The result shown that all constraint had fullfilled to
minimize total distance for multistage vehicle routing
problems. Validation of the result showed that solving of
the second layer was consistent with distributors and
Figure 3. Network Distribution of second layer retailers nearnest location. Therefore, the model could
work well.
Mathematical Model VRPTW for second layer result:
a. Route 1(vehicle 1) : REFERENCES
AGEHPJIFDA
Total Distance = 54.8 km [1] H.C. Lao, Sim, M, Teo. KM, Vehicle Routing Problem
Total Load = 196 box With Time Window and a Limited number of
Total time = 173.89 minutes vehicles, European Journal Of Operation Research,
b. Route 2(vehicle 2) : B Q O N B 559-569, 2003
Total Distance = 29.1km [2] G. Laporte, "The Vehicle Routing Problem: An
Total Load = 67 box Overview of Exact and Approximate Algorithms",
Total time = 88.99 minutes European Journal of Operational Research, North-
Holland, 1992.
[3] J. Larsen, Parallelization of the Vehicle Routing
c. Vehicle 3 : C L M K C Problem with Time Windows, Technical University of
Total Distance = 33.0 km Denmark, 1999.
Total Load= 52 box [4] M. Gendreau, C.D, Tarantilis, Solving large scale
Total time = 82.52 minutes vehicle routing problems with time windows: state of
the art, CIRRELT, 2010
Step 2. Solving for first layer [5] Y. Chang, L. Chen, Solve The vehicle routing problem
with time Windows via a Genetic Algorithm, Discrete
and Continuous Dynamical Systems Suplement, p
240-249, 2007

Figure 4. Network Distribution of first layer

Y as depot, A, B, C as distributors

Mathematical Model VRPTW for first layer result:

a. Route 1 : Y A Y
Total Distance = 152.6 km
Total Load = 573 box
Total time = 305.3 minutes
b. Route 2: Y C B Y
Total Distance = 184.1 km
Total Load = 984 box
Total time = 346.2 minutes

Below is the result of The Multistage VRPTW

Mathematical Model:

Figure 5. Distribution as result of Improved multistage

VRPTW

CONCLUSION
The result of improved VRPTW had been
verified as follows:
1. Every node visited only once with only one
vehichle at time.