Jurnal Teknik Industri, Vol. 23, No. 1, June 2021 DOI: 10.9744/jti.23.1.

75-82
ISSN 1411-2485 print / ISSN 2087-7439 online

Genetic Algorithm with Cluster-first Route-second to Solve the

Capacitated Vehicle Routing Problem with Time Windows:
A Case Study
Karina Aginta Putri1*, Nur Layli Rachmawati1, Mirna Lusiani1,
Anak Agung Ngurah Perwira Redi2

Abstract: In a distribution problem, designing the right distribution route can minimize the total
transportation costs. Therefore, this research aims to design a distribution route that produces a
minimal distribution distance by clustering the demand points first. We generated the clustering
method to cluster the demand points by considering the proximity among the demand points and
the total vehicle capacity. In solving this problem, we are using p-median to determine the cluster
and a genetic algorithm to determine the distribution route with the characteristics of the
CVRPTW problem. CVRPTW or capacitated vehicle routing problem with time windows is a type
of VRP problem where there is a limitation of the vehicle capacity and service time range of its
demand point. This research concludes that clustering the demand points provides a better result
in terms of total distribution costs by up to 16.26% compared to the existing delivery schedule. The
performance of the genetic algorithm shows an average difference of 1.73%, compared to the exact
or optimal method. The genetic algorithm is 89.68% faster than the exact method in the
computational time.

Keywords: Cluster-first route-second, P-median clustering, genetic algorithm, CVRPTW.

Introduction carried out first by considering the cluster capacity

and proximity among the demand points. Besides,
Distribution and marketing activities play an essen- there are 225 demand points and 15 vehicles
tial role in ensuring the successful sale of a product. In available. The CCAI Medan implemented a distri-
distribution activities, choosing the right distribution bution system intuitively. It is not based on
route can minimize the total cost of transportta- theoretical calculations to optimize the distribution
tion. Transportation costs are known to have a system. Figure 1. shows the mapping of the current
proportion of 29.4% of the total logistics costs [1]. This distribution system delivery day. Based on these
paper considers a real-world problem where a manu- problems we want to give the alternative solution to
facturer distributes products to retailers with diffe- make the distribution system more efficient than the
rent demands, heterogeneous fleets, capacitated vehi- existing condition.
cles, limitation of demand point's service time. Ano-
ther interest is the large number of demand points. To solve this problem, we proposed a cluster first
route second approach. The idea of this solution
Coca-Cola Amatil Indonesia or CCAI is a Fast- involves two stages of decisions (1) partitioning the
Moving Consumer Goods company that focused on outlet locations by considering its capacity and
selling soft drinks. In implementing its distribution distance first, which differs this paper from several
system, CCAI considers the limitations on their previous papers, and (2) sequencing the delivery in
demand point's service time windows, as well as the each cluster to get the assignment and routes of the
vehicle. Several problems implemented this app-
capacity of their vehicle. The distribution routes
roach, such as for solving ambulance routing problem
problem at CCAI is a Capacitated Vehicle Routing
[2], two-echelon location routing optimization [3],
Problem or CVRP with time windows or CVRPTW. In
application in waste collection problem [4]. First,
this study, clustering of its demand points will be
implement the p-median method for clustering,
considering the proximity among the demand points
1Faculty of Industrial Technology, Logistics Engineering Depart- and the total fleet capacity available each day. The
ment, Universitas Pertamina, Jl. Teuku Nyak Arief, Jakarta,
Indonesia 12220. Email: [email protected], cluster indicates the working days for the distribu-
[email protected], tion. Because there are five working days of delivery,
[email protected] so the number of clusters is five. K-Clustering,
2 Graduate Programme, Industrial Engineering Department, Bina
especially k-median and k-means, is the most popular
Nusantara University, Jl. Kebon Jeruk Raya 27, Jakarta Barat,
Indonesia 11530. Email: [email protected]
model to solve the general clustering problem [5]. In
this problem, we used the Capacitated P-Median
* Corresponding author Problem (CPMP) using Integer Linear Programming
 Putri et al. / The Application of Genetic Algorithm with Cluster-first Route-second / JTI, Vol. 23, No. 1, June 2021, pp. 75-82

(ILP). In the works of literature, there is extensive uses the P-Median clustering method since it
research using the P-Median problem. Mai et al. [6] considers the distance as well as the capacity. P-
using the capacitated p-median problem to test the Median clustering guarantees that the number of
proposed algorithm in which the observations consist demands in a cluster will not exceed the cluster's
of geographic locations of customers and the corres- capacity.
ponding demand of these customers. Garcia et al. [7]
used p-median problem with radius formulation to CVRPTW or capacitated vehicle routing problem
solve a large problem using heuristics approach. The with time windows is one type of VRP problem, where
algorithm proposed performs very well in general there are limitations in vehicle capacity and service
based on reduced formulation. Elloumi and Tighter time windows of each demand point. Molina et al. [21]
[8] proposed a new formulation by a mixed-integer also conducted research related to the CVRPTW
linear problem using a branch and cut algorithm. problem under resource limitation and more than one
Puerto et al. [9] solved a discrete location problem type of vehicle. This research could be categorized as
using p-median and analyzed from the sum, maxi- a HFVRPTW-LR problem or heterogeneous fleet
mum, and coverage point of view. vehicle routing problem with time windows and
limited resource. Furthermore, Ferreira et al. [22] also
Many modern routing applications use the CVRPTW researched VRPTW problems. However, the contrast
model, such as grocery home-delivery systems [10]. between the previous study and this study is that
Several methods are proposed in the literature to there is more than one service period or time window
solve this problem, such as mixed-integer program- at each demand point. Apart from the two studies
ming, heuristics [11], and stochastic programming above, Tohidifard et al. [23] also researched VRPTW
[12]. Then the routing is carried out using the genetic problems. The mathematical of CVRPTW [24] is
algorithm method, considering the time windows of formulated as follows:
each demand point and the vehicle capacity. This
research uses a Genetic Algorithm ([13,14]). Applying Objective function:
the genetic algorithm in some VRP cases effectively min ∑𝑁 𝑁 𝑁
𝑖=1 ∑𝑗=1 ∑𝑘=1 𝐷𝑖𝑗 𝐶 𝑋𝑖𝑗𝑘 (1)
and efficiently in terms of the computation results in Constraints:
reasonable computational time, and the proposed ∑𝑁𝑖=1 ∑𝑘=1 𝑋𝑖𝑗𝑘 = 1, for 𝑗 = 1, … , 𝑁 − 1
𝑁
(2)
solutions produce a feasible fitness value. [15] who 𝑁
∑𝑗=1 ∑𝑁 𝑋 = 1, for 𝑖 = 1, … , 𝑁 − 1 (3)
𝑘=1 𝑖𝑗𝑘
also use GA for routing problems state that using this ∑𝑖=1 ∑𝑗=1 𝑄𝑖 𝑋𝑖𝑗𝑘 ≤ 𝑃𝑘 , for 𝑘 = 1, … , 𝑦
𝑁 𝑁
(4)
algorithm produces consistent results.
∑𝑁𝑖=1 𝑋 𝑖𝑗𝑘 − ∑ 𝑁
𝑖=1 𝑋 𝑗𝑖𝑘 = 0, for 𝑘 = 1, . . , 𝑦; 𝑗 = 1, … , 𝑁
The insertion method is one of the well-known (5)
methods to solve the VRP problem. It is introduced by ∑𝑁 𝑋
𝑗=1 𝑜𝑗𝑘 = 1 , 𝑓𝑜𝑟 𝑘 = 1, … , 𝑦 (6)
[16], who examined VRPTW problems with the ∑𝑁 𝑋
𝑖=1 𝑖,𝑛+1,𝑘 = 1, 𝑓𝑜𝑟 𝑘 = 1, … , 𝑦 (7)
cluster-first route-second method with the urgency 𝑋𝑖𝑗𝑘 (𝑊𝑖𝑘 + 𝑆𝑖 + 𝑡𝑖𝑗 − 𝑊𝑗𝑘 ) ≤ 0 (8)
clustering method. Besides, the exact mix integer 𝐸 ≤ 𝑊𝑖𝑘 ≤ 𝑏𝑖 (9)
programming method is also often used in VRP 𝑊𝑖𝑘 + 𝑆𝑖 + 𝑡𝑖𝑗 − 𝑊𝑗𝑘 ≤ 𝑀𝑖𝑗 (1 − 𝑋𝑖𝑗𝑘 )for 𝑘 =
problems; one of these is used by [17]. They examined 1, … , 𝑦; ∀ (𝑖, 𝑗) ∈ 𝐴 (10)
CVRPTW problems as well as the cluster-first route- 𝑓𝑖 ≤ 𝑊𝑖𝑘 ≤ 𝑏𝑖 (11)
second technique with the k-means clustering 𝑋𝑖𝑗𝑘 = 0 or 1 (12)
method. Genetic algorithm methods applied in this
research are also commonly used in VRP problems, Where:
such as research conducted by [18]. They examined 𝑄𝑖 : demand for outlet 𝑖
CVRPTW problems using the cluster-first route- 𝐷𝑖𝑗 : distance from outlet 𝑖 to 𝑗
second method with the k-means clustering method. 𝑆𝑖 : service time of outlet 𝑖
𝐶 : fuel price per meter consumption
Methods 𝑋𝑖𝑗𝑘 : binary, 1 if vehicle 𝑘 is used to serve
outlet 𝑖 to 𝑗; 0 otherwise
The first step to solve this problem is to develop a 𝑃𝑘 : maximum capacity of vehicle 𝑘
cluster for customers based on the distance matrix 𝑊𝑖𝑘 : starting service time of outlet 𝑖 by
using P-Median. P-median is generally a method for vehicle 𝑘
solving location-allocation problems, aiming to 𝑊𝑗𝑘 : finishing service time of vehicle 𝑘 in
minimize the total distance from each demand point outlet 𝑗
to the closest number of supply points [19]. Moreover, 𝐸 : earliest departure time
P-median can also be applied for clustering problems. 𝐿 : latest departure time
As a clustering method, P-median can partition data 𝑖, 𝑗 : index of outlet to be served
sets into groups or clusters. Those clusters are built 𝑘 : index of vehicle
based on the proximity of the data [20]. This research 0 : index of depot
76
 Putri et al. / The Application of Genetic Algorithm with Cluster-first Route-second / JTI, Vol. 23, No. 1, June 2021, pp. 75-82

𝑁 : number of outlets (depot included) can survive are the good ones. A fitness value
𝑦 : number of vehicles represents the measure of good in the GA. The
𝐴 : set of arcs (𝑖, 𝑗) pseudocode for finding a solution using the genetic
𝑓𝑖 , 𝑏𝑖 : time windows of outlet 𝑖 algorithm method is as follows:

The objective function is to minimize the total distri- 1. Set Parameters

bution costs by multiplying the total distance traveled 2. Generate initial solution using permutation
and fuel cost. Constraints (2) and (3) indicate that an representation
outlet is only served by one vehicle. Constraint (4) 3. Calculate fitness
indicates that the number of products does not exceed 4. While nth iteration process < Set of Iteration do:
the vehicle's total capacity. Constraint (5) indicates If random number ≤ Crossover Rate do
that the vehicle will immediately leave outlet 𝑖 Crossover using partially mapped crossover
towards the outlet 𝑗 after finishing serving outlet 𝑖. (PMX)
Constraint (6) shows that the vehicle leaves the depot if random number ≤ Mutation Rate do
to carry out distribution. Constraint (7) shows that Mutation
the vehicle will return to the depot after serving all Selection
outlets. Constraint (8) shows the total service time of 5. End while
the vehicle 𝑘. Constraint (9) indicates that vehi- 6. Select the best fitness
cle k cannot serve outlet i before its upper limit and 7. Return to the best solution
does not perform service beyond its lower limit.
Constraint (10) indicates that vehicle k cannot serve The proposed GA produces distribution routes. The
outlet 𝑗 before it finishes serving outlet 𝑖. Constraint route sequences are represented using gene
(11) shows that vehicle 𝑘 is can only serve outlets at a permutations. In this study, we generated 300
certain time. population, i.e., 300 candidate sequences of genes or
distribution routes. Here are two examples of initial
A genetic algorithm or GA is a method based on solutions in cluster 1 before the crossover and
natural selection mechanisms and natural genetics mutation process is carried out:
[25]. Genetic algorithm refers to the theory of
evolution by Charles Darwin, where individuals who

Solution 1:
14 0 0 0 12 0 0 7 0 13 10 0 5 0 2 8 6 0 0 0 0 0 11 4 15 9 0 3 1
Solution 2:
0 0 13 2 0 10 0 0 0 0 15 0 8 0 0 12 0 7 11 0 0 0 3 4 5 6 9 14 1

In terms of crossover operation, the method used is PMX or partially mapped crossover. PMX Crossover
is carried out using the following steps:
1. Initialize parent 1 and parent 2 which are represented as P1 and P2 according to solutions 1 and 2.
Columns with a yellow highlight show the crossover indication points.
14 0 0 0 12 0 0 7 0 13 10 0 5 0 2
P1
8 6 0 0 0 0 0 11 4 15 9 0 3 1
0 0 13 2 0 10 0 0 0 0 15 0 8 0 0
P2
12 0 7 11 0 0 0 3 4 5 6 9 14 1
2. Next, the 0 value in the core solution is substituted into a negative number which aims to avoid
bias in the search process in the program, so that the solution becomes:
14 -1 -2 -3 12 -4 -5 7 -6 13 10 -7 5 -8 2
P1
8 6 -9 -10 -11 -12 -13 11 4 15 9 -14 3 1
-1 -2 13 2 -3 10 -4 -5 -6 -7 15 -8 8 -9 -10
P2
12 -11 7 11 -12 -13 -14 3 4 5 6 9 14 1
3. While the value in other points is changed to X. O1 and O2 represent the offspring 1 and 2 obtained
from this crossover process.
X X X X X X X X X -7 X X X -9 X
O1
X X X X X X X X X X X X X X
X X X X X X X X X 13 X X X -8 X
O2
X X X X X X X X X X X X X X

77
 Putri et al. / The Application of Genetic Algorithm with Cluster-first Route-second / JTI, Vol. 23, No. 1, June 2021, pp. 75-82

4. Furthermore, each X value is replaced according to the values in its respective parent, if there
is a similarity in value between points on one offspring, then the value at that point is still
written as x
14 -1 -2 -3 12 -4 -5 7 -6 -7 10 X 5 -9 2
O1
8 6 X -10 -11 -12 -13 11 4 15 9 -14 3 1
-1 -2 X 2 -3 10 -4 -5 -6 13 15 X 8 -8 -10
O2
12 -11 7 11 -12 -13 -14 3 4 5 6 9 14 1

For example, the values that should be at the 12th and 18th points on offspring 1 are -7 and -
9, while the -7 and -9 values are the results of the crossover at the 10th and 14th points, thus
the values at the 12th and 18th points are still written as X.

5. Then the X value is filled in according to the value of the opposite parent, for example, the 12th
and 18th values on offspring 1 are filled according to the value in parent 2 which is not owned
by offspring 1, which is read from left to right.
14 -1 -2 -3 12 -4 -5 7 -6 -7 10 13 5 -9 2
O1
8 6 -8 -10 -11 -12 -13 11 4 15 9 -14 3 1
-1 -2 -7 2 -3 10 -4 -5 -6 13 15 -9 8 -8 -10
O2
12 -11 7 11 -12 -13 -14 3 4 5 6 9 14 1

6. The final step is to change the negative value back to 0

14 0 0 0 12 0 0 7 0 0 10 13 5 0 2
O1
8 6 0 0 0 0 0 11 4 15 9 0 3 1
0 0 0 2 0 10 0 0 0 13 15 0 8 0 0
O2
12 0 7 11 0 0 0 3 4 5 6 9 14 1

After the crossover is carried out, the offspring that has been obtained through the crossover
process is mutated.

1. Initialize parent 1 and parent 2. Columns highlighted in yellow indicate the mutation points
14 0 0 0 12 0 0 7 0 0 10 13 5 0 2
P1
8 6 0 0 0 0 0 11 4 15 9 0 3 1
0 0 0 2 0 10 0 0 0 13 15 0 8 0 0
P2
12 0 7 11 0 0 0 3 4 5 6 9 14 1

2. The value of 0 at these points is also substituted with a negative number which also aims to
avoid bias in the scattering process
14 -1 -2 -3 12 -4 -5 7 -6 -7 10 13 5 -9 2
P1
8 6 -8 -10 -11 -12 -13 11 4 15 9 -14 3 1
-1 -2 -7 2 -3 10 -4 -5 -6 13 15 -9 8 -8 -10
P2
12 -11 7 11 -12 -13 -14 3 4 5 6 9 14 1

3. Furthermore, the mutation points are carried out by changing the value at the samae
offspring’s two mutation points, example, the value at the 10th point on offspring 1 is changed
to the value at the 14th point on offspring 1, and vice versa.
14 -1 -2 -3 12 -4 -5 7 -6 -9 10 13 5 -7 2
O1
8 6 -8 -10 -11 -12 -13 11 4 15 9 -14 3 1
-1 -2 -7 2 -3 10 -4 -5 -6 -8 15 -9 8 13 -10
O2
12 -11 7 11 -12 -13 -14 3 4 5 6 9 14 1

4. The final step is to change the negative number back to 0

14 0 0 0 12 0 0 7 0 0 10 13 5 0 2
O1
8 6 0 0 0 0 0 11 4 15 9 0 3 1
0 0 0 2 0 10 0 0 0 0 15 0 8 13 0
O2
12 0 7 11 0 0 0 3 4 5 6 9 14 1

78
 Putri et al. / The Application of Genetic Algorithm with Cluster-first Route-second / JTI, Vol. 23, No. 1, June 2021, pp. 75-82

While the selection process in GA in this study uses

the roulette wheel method which step is as follow:
1. Calculate the fitness of the initial population
2. Calculate the probability of each accepted
chromosome
3. Calculate the cumulative probability (𝑞) in each
chromosome. If the nth chromosome is 𝑞𝑛−1 <
random number < 𝑞𝑛 , then the chromosome is
selected for the next process.

Results and Discussions

Clustering is carried out using the p-median approach

and generated using LINGO 18.0. The data inputs
are the number of working days, the cluster capacity, Figure 1. Mapping of real condition
the total of all available fleet capacity in a day, the
demand of all outlets, and the distance among the
outlet obtained using the QGis software. This process
resulted in 5 clusters representing the days of distri-
bution and summarized in Figure 2.

Before running the genetic algorithm we need to set

the tuning parameters, they are the number of
iteration, number of population, crossover rate and
mutation rate. We set the number of iteration as 100
and 300, number of population 50 and 100, crossover
rate 0.5 and 0.9, mutation rate 0.1 and 0.5. Those
setting parameters was experimented in the third
cluster since it represents the average number of
demands. One Factor at a Time (OFAT) is used to Figure 2. Mapping after clustering
tune the parameters. In each experiment, we
replicate a set of tuning paramters 30 times. The heuristic and metaheuristic algorithms’ output is
results is summarized in Table1. good enough, it is necessary to compare the exact
method’s output with smaller data instances.
Table 1 and Figure 3 show that the more iterations Therefore, in this study, the exact method is also
and populationn, the objective function will reach applied to solve routing problems in 3 instances,
miniminum value. It is also time consuming. In the namely instance 1 with five nodes of demand points,
setting parameters, the fitness function reach mini- instance 2, or cluster 1 with 15 nodes of demand
mum at 300 iterations, 100 population, with cross points. The objective function values and the route
over and mutation rate 0.5. It needs 59.5 seconds to generated through calculations using the exact
find the minimum fittess function at Rp 1,301,854. method will then be compared with the genetic
algorithm’s objective function value.
Based on the previous best parameter setting, we run
the GA to find the minimized objective function. Furthermore, to test the genetic algorithm’s perfor-
Additionally, to the setting paramter, we generated a mance, the GA routing results of 5 nodes and 15 nodes
random number between 0 and 1 (0 ≤ 𝑟 ≤ 1) to routing are compared with the result obtained using
represent the crossover and mutation process in the exact methods. The comparison is based on the
GA algorithm. If the 𝑟 is smaller or equal to the objective function and computation time results.
mutation and/or crossover rate, then the mutation
and crossover can be executed. The minimum fitness Table 2 shows that solving the 5-points CVRPTW
function is reached at the 672nd iteration (see Figure problem using the exact method requires a shorter
4). computation time (CT) than genetic algorithms.
However, solving CVRPTW in the 15-point case using
VRP problems are np-hard problems, which means the exact method requires a significantly longer
that these problems cannot be solved optimally in the computation time than the computation time
polynomial timeframe. Therefore, the heuristic and required to use genetic algorithms. Where the
metaheuristic methods are considered quite efficient average difference in the objective function (OF)
in solving this problem. However, to compare whether between the exact method and the genetic algorithm

79
 Putri et al. / The Application of Genetic Algorithm with Cluster-first Route-second / JTI, Vol. 23, No. 1, June 2021, pp. 75-82

Table 1. Tunning parameter Table 3. Trasportation ost between the existing and
Objective
Xover Mut Comp prossed GA
Niter Npop function
Rate Rate time (s) Day / Existing
(Rp) Proposed GA
100 50 0.9 0.1 1,350,391 72 Cluster Condition
100 50 0.5 0.5 1,331,958 69.52 Mon / C1 1,510,106 308,190
300 100 0.9 0.1 1,331,958 39.52 Tue / C2 1,622,894 480,130
300 100 0.5 0.5 1,301,854 59.5 Wed / C3 595,270 1,329,308
Thu / C4 983,762 840,605
1360000 80 Fri / C5 1,384,786 2,147,124
Objective function

Computational time
1340000 Total 6,096,818 5,105,369
60
1320000 Gap (Rp) 991,458
40 Gap (%) 16.26%
1300000
(Rp)

1280000 20

(s)
1260000 0 Table 4. Statistical summary of the proposed GA
1 2 3 4 Objective function Computational time
Configuration Cluster (Rp) (s)
Mean Stdev Mean Stdev
Obj. Func. (Rp) Time (s) C1 309,467 2,785 30.3 3.28
C2 480,130 8,285 37.93 2.85
Figure 3. Tunning parameter graph C3 1.329,308 48,187 83.3 3.09
C4 840,605 3,090 72.27 1.34
C5 2,147,124 19,672 93.57 1.57
250000
Total
Objective function

200000 5,106,636 322.37

Cost/Week
150000 ,
100000
50000 Conclusion
0
0

1148
1312
1476
1640
1804
1968
164
328
492
656
820
984

The proposed solution using clustering and GA

algoritm reduced the distribution cost by 16.26%. It is
Iteration well-known that solving routing problem using meta-
heuristics approach will not reach global optimum.
Figure 4. Proposed GA convergency However, the computation time is reasonable
compared to solve using the linear model (exact
Table 2. Exact and GA comparison method). The objective function of the two methods
Obj Function (OF) Comp Time (CT) Gap
Node Exact GA Exact CT
shows an average difference of 1.73%. The difference
GA (s) OF (%)
(Rp) (Rp) (s) (%) in computation time in instances with the 15 points
5 89,063 89,063 0.38 0.06 0 84.21 between the genetic algorithm and the exact method
15 291,870 301,974 660 32 3.46 95.15
Average gap 1.73% 89.68% is 89.68%. It shows that the use of the genetic
algorithm is considered effective enough to solve
large-scale problems. Overall, the genetic algorithm
means in both cases is 14.375%. It shows that using method used in this research is a basic GA method,
genetic algorithms on a larger scale will be more and the clustering is generated by only considering
efficient than using the exact method and will not the distance of each outlet and the daily capacity.
show any different results than the optimal results. However, using another clustering method to cluster
the demand points might be worth considering as well
Next, we compared the results of the proposed solu- in considering the balance of the data in each cluster.
tion to the real condition, which only used an intuitive Finding efficient solution procedures remains an open
solution. Table 3 summarizes those comparisons. It avenue for future research.
exhibits that the proposed solution reduced trans-
portation costs by 16.26%. In this proposed solution, References
Cluster 3 and Cluster 5 have higher transportation
costs than the real condition. It happened since; those 1. Tseng, Y. Y., Taylor, M. A. P., and Yue, W. L., The
clusters are dense. There are many depots to visit. Role of Transportation in Logistics Chain, in
While Cluster 1, Cluster 2, and Cluster 4 have less Proceeding of the Eastern Asia Society for Trans-
transportation cost than the existing condition.
port Studies, Adelaide, 2005.
Figure 1 and Figure 2 show cluster differences. Table
4 shows the statistics summary for each cluster. 2. Tlili, T., Harzi, M., and Krichen, S., Swarm-based
Approach for Solving the Ambulance Routing

80
 Putri et al. / The Application of Genetic Algorithm with Cluster-first Route-second / JTI, Vol. 23, No. 1, June 2021, pp. 75-82

Problem, in International Conference on Know- 15. Suprayogi and D. B. Pailin, Algoritma Genetika
ledge Based and Intelligent Information and untuk Pemecahan Masalah Rute Kendaraan
Engineering Systems, KES2017, Marseille, dengan Ukuran dan Campuran Armada, Trip
France, 2017. Majemuk, Pengiriman Terbagi, Produk Maje-
3. Wang, Y., Assogba, K., Liu, Y., Ma, X., Xu, M., muk dan Kendaraan dengan Kompartemen
and Wang, Y., Two-echelon Location-routing Majemuk, Jurnal Teknik Industri, 19(2), 2017,
Optimization with Time Windows Based on pp. 115-124.
Customemr Clustering, Expert Systems With 16. Ghoseiri, K., and Ghannadpour, S. F., A Hybrid
Applications, 104, 2018. Genetic Algorithm for Multi-depot Homogenous
4. Rabbani, M., Farrokhi-Asl, H., and Asgarian, B., Locomotive Assignment with Time Windows,
Solving a Bi-objective Location Routing Problem Applied Soft Computing, 10, 2010, pp. 53-65.
by a NSGA-II Combined with Clustering
17. Mostafa, N. and Eltawil, A., Solving the
Approach: Application in Waste Collection
Heterogenous Capacitated Vehicle Routing
Problem, Journal of Industrial Engineering
Problem using K-Means Clustering and Valid
International, 13, 2016, pp. 13-27.
Inequalities, in Industrial Engineering and
5. Fomin, F. V., Golovach, P. A.. and Simonov, K.,
Parameterized k-Clustering: Tractability Operations Management, Rabat, 2017.
Island,Journal of Computer and System Sciences, 18. Alfiyatin, A. N., Mahmudy, W. F., and Anggodo,
117, 2021, 50-74. Y. P., K-Means Clustering and Genetic
6. Mai, F., Fry, M. J., and Ohlmann, J. W., Model- Algorithm to Solve Vehicle Routing Problem with
Based Capacitated Clustering with Posterior Time Windows Problem, Electrical Engineering
Regularization, European Journal of Operational and Computer Science, 11(2), 2018, pp. 462-468.
Research, 271(2), 2018, pp. 594-605. 19. Jackson, L. E., Rouskas, G. N., and Stallmann,
7. Garcia, S., Labbe, M., and Marin, A., Solving M. F. M., The Directional p-Median Problem:
Large p-median Problems with a Radius Definition, Complexity, and Algorithms, Euro-
Formulation, INFORMS Journal on Computing, pean Journal of Operational Research, 179, 2007,
23(4), 2011, 546-556. pp. 1097-1108.
8. Elloumi, S., A Tighter Formulation of the p- 20. Kohn, H. F., and Steinley, D., The p-Median
Median Problem, Journal Combinatorial Opti- Model as a Tool for Clustering Psychological
mization, 19, 2010, 69-83. Data, American Psychological Association, 15,
9. Puerto, J., Ramos, A., and Rodriguez-Chia, A., 2010, pp. 87-95.
Single-allocation Ordered Median Hub Location 21. Molina, J. C., Salmeron, J. L., Eguia, I. and
Problems, Computers & Operations Research, 38, Racero, J., The Heterogeneous Vehicle Routing
2011, 559-570. Problem with Time Windows and Limited
10. Hungerlander, P., Maier, K., Pocher, J., and Number of Resources, Enginerring Applications
Truden, C., Solning an On-Line Capacitated of Artificial Intelligence, 94, 2020, 1-15.
Vehicle Routing Problem with Structures Time
22. Ferreira, H. S., Bogue, E. T., Noronha, T. F.,
Windows, in Operations Research Proceedings,
Belhaiza, S., and Prins, C., Variable Neighbor-
2016.
hood Search for Vehicle Routing Problem with
11. Giovanni, L. D., Gastaldon, N., Lauriola, I., and
Sottovia, F., A Heuristic for Multi-attribute Multiple Time Windows, Electronic Notes in
Vehicle Routing Problems in Express Freight Discrete Mathematics, 66, 2018, pp. 207-214.
Transportation, in International Conference on 23. Tohidifard, M. , Moghaddam, T. R., Navazi, F.,
Optimization and Decision Science, 2017. and Partovi, M., A Multi-Depot Home Care
12. Bai, R., Wallace, S. W., Li, J., and Chong, A. Y.- Routing Problem with Time Windows and Fuzzy
L., Stochastic Service Network Design with Demands Solving by Particle Swarm Optimi-
Rerouting, Transportation Research Part B: zation and Genetic Algorithm," International
Methodological, 60, 2014, 50-65. Federation of Automatic Control, 51(11), 2018, pp.
13. da Costa, P. R. d. O., Mauceri, S., Caroll, P., and 358-363.
Pallonetto, F., A Genetic Algorithm for a Green 24. Kulkarni, R. V., and Bhave, P. R., Integer
Vehicle Routing Problem, Electronic Notes in Programming Formulation for Vehicle Routing
Discrete Mathematics, 64, 2018, pp. 65-74. Problem, European Journal of Operational
14. Tasan, A. S., and Gen, M., A Genetic Algorithm Research, 20,1985, pp. 57-68.
based Approach to Vehicle Routing Problem with 25. Goldberg, D. E., Genetic Algorithm in Search,
Simultaneous Pick-up and Deliveries, Computers Optimization, and Machine Learning, Addison-
& Industrial Engineering, 62, 2012, pp. 755-761. Wesley Professional, Massachusetts,1989.

81
Putri et al. / The Application of Genetic Algorithm with Cluster-first Route-second / JTI, Vol. 23, No. 1, June 2021, pp. 75-82

82