Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 2 (September 2018) 131-134___________________________________________________________________________________________________________Optimization for Line of Cars Manufacturing Plant using Constrained Genetic Algorithm
Keiji Kamei*

Department of Production Systems, Nishinippon Institute of Technology, 1-11 Aratsu
Kanda, Miyakogun, Fukuoka 800-0394, Japan†
Takafumi Arai

Nissan Motor Kyushu Co. Ltd., 1-3 Shinhama-cho
Kanda, Miyakogun, Fukuoka 800-0395, Japan
E-mail: kamei @nishitech.ac.jp
www.nishitech.ac.jp/~kamei/

Abstract
Recently, improvement of production efficiency on cars manufacturers is required. However, that improvements
under existing circumstances are depending on experience and intuition by workers. We propose to objectively andefficiently improve a production line based on a GA. The difficulty of applying a GA is the number of racks andboxes is predetermined, and so we apply constrained GA. The results of simulation for virtual production line showthat our proposal succeeded in reducing about 10 seconds per a car compared with random positioning.
Keywords: Constrained Genetic Algorithm, Plant Optimization, Industrial Application, Car manufacturing

Our optimization problem is similar to several path
planning problems such as “Traveling Salesman Problem(TSP),” “Minimum Spanning Tree problem(MST).”
Workers pick up assemblies while they goes back andforth between racks and an AGV. Accordingly, our
optimization problem becomes synonymous withminimization of total length of moving path of a worker.
The difference between path planning problems and ourproblem is that positions of waypoints for path planningproblems are fixed; on the other hand, our problem
changes positions of waypoints that are racks and boxes.
Since the number of racks and boxes ispredetermined as mentioned, our approach has to put
predetermined number of racks and boxes into a
production line. For this, there is also a problem of“Knapsack Problem(KP)” in our optimization problem.

1. Introduction
Recently, improvement of production efficiency on cars
manufacturers is required owing to increasing ofdemands in developing countries. On the other hand, thatimprovements under existing circumstances aredepending on experience and intuition by workers at a
production line1, 2. To overcome this situation, we
propose to objectively and efficiently improve aproduction line without depending on experience andintuition. The production line of candidate for
optimization is “Picking up assemblies” area, so that ouraim is to optimize the positions of racks and boxes for
assemblies. The difficulty of optimization of “Picking up
assemblies” area is that the number of racks to put
assembly boxes and that boxes is predetermined.

*In 2007 he obtained his PhD at the Department of Brain Science and Engineering, Kyushu Institute of Technology. From April, 2007 to March, 2014,
he was a lecturer. Since April, 2014, he has been an associate professor, Nishinippon Institute of Technology.

Copyright © 2018, the Authors. Published by Atlantis Press.
This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
131

Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 2 (September 2018) 131-134___________________________________________________________________________________________________________The results of simulation for virtual production line
show that our proposal succeeded in reducing about 10
seconds per a car compared with random positioning.

It can be said that our optimization problem combines
TSP, MST and KP for the reasons stated above.
To overcome difficulties, we propose to apply a
Genetic Algorithm(GA)3, 4 to optimization for positionsof racks and boxes. A GA is suitable for global search ina high dimensional space because a GA has also theability of probabilistic random search based on genetic
operations in addition to local search. A GA has manyindividuals(populations), and an individual has achromosome that cords the parameters for optimization.
Optimization processes are on the basis of genetic
operations, i. e., selection, crossover and mutation. A
process of crossover and mutation does not beconstrained because parameters for optimization in achromosome are independent in each; therefore,generated parameters of optimization are able to take allvalues within a set condition. By contrast, parameters ofoptimization in our problem are dependent on each otherbecause the number of racks to put assembly boxes andthat boxes is predetermined. Consequently, we are notable to apply a conventional GA to optimization. For this,
we apply a “constrained GA” to optimization for
positions of racks and boxes in a production line.
The details of our constrained GA are below. Geneloci correspond to racks and boxes positions in aconstrained GA. Selection process in genetic operations
is same way as a conventional GA. In crossover process,loss or duplication of some racks and boxes will occur.
The way of adjustment of the number of racks is that allof duplicative racks are deleted then missing racks are
randomly inserted to those positions. Mutation process
for racks is executed after the adjustment of crossoverprocess. Mutation process in a constrained GA changes
gene loci in order to meet the conditions for the numberof racks. Crossover and mutation process for positions ofboxes in racks is executed after crossover and mutation
process for racks. Crossover process for boxes isexecuted on the same stage each other, e.g., boxes in top
stage of a rack are changed with boxes in top stage ofanother rack. In mutation process, genes for boxes are
mutated randomly as same as a conventional GA in first.
Following that, excess boxes are randomly chosen, thenthose boxes are deleted. Subsequently, shortfall in boxes
are inserted randomly to meet the conditions for thenumber of boxes. From a constrained GA in above, ourproposal is able to meet the conditions for ouroptimization problem.

2. Virtual Environment of Production Line
We construct a virtual environment of production line tovalidate the effectiveness of our proposal. Table 1 shows
the conditions for virtual environment, and Table 2
shows the number of assembly boxes for each car.
Table 1. Conditions of virtual environment. Length unit ismillimeter.
Kinds of Rack(Length)3(1000, 1500, 2000)
Stages in a Rack
3(Top, Middle, Bottom)
Kinds of Assembly Boxes
3
Length of a Line15000
Distance of AGV and Racks
1500
Moving Speed of AGVWalking Speed of a Worker
Number of racks
Types of Cars(Car names)
Mixing Rate of Cars in
Productions

200[mm/s]
2000[mm/s]
1000×3, 1500×4, 2000×34(Car1, Car2, Car3, Car4)
Car1:0.5, Car2:0.25,
Car3:0.15, Car4:0.1

Table 2. Number of assembly boxes
for each car. “300”,”600” and “1000”
correspond to width of assembly boxes.
Width unit is millimeter.
Width of assembly boxes
300
600
1000
Car11542Car21531Car31031Car41001
Shared3055A worker in virtual environment picks up the all ofassemblies which correspond to a designated car in theTable 2. Besides, 20 shared assemblies are randomly
designated from the all of shared assemblies.
The Fig. 1 shows the bird’s-eye view of an exampleof virtual production line. The condition in that figure isinitial state of picking up assemblies. A worker goes backand forth between racks and an AGV. An AGV moves ata constant speed on a lane.

132

Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 2 (September 2018) 131-134___________________________________________________________________________________________________________Consequently, our optimization problem is same as
minimization of the moving distance of a worker.

Optimization processes are on the basis of geneticoperations, i. e., selection, crossover and mutation.
In a conventional GA, a process of crossover andmutation does not be constrained because parameters for
optimization in a chromosome are independent in each;
therefore, generated parameters of optimization are able
to take all values within a set condition. On the other hand,parameters of optimization in our problem depend oneach other because the number of racks and assemblyboxes is predetermined. For this, we apply a “constrainedGA” to optimization for positions of racks and boxes asmentioned in the next section.

3. Optimization Problem

4.2. Constrained Genetic Algorithm

1000

1500

2000

1500

1000

1500

2000

1500

2000

1000

1500
AGV
15000

Fig. 1. Bird’s eye view of an example of virtual production line.
Values are distance and size of rack. Unit is millimeter. The redcircle indicates a worker. The blue, yellow and magenta squares
correspond to 1000, 1500 and 2000 size of racks, respectively.

From the above section, our optimization problem issimilar to several path planning problems such as“Traveling Salesman Problem (TSP),” “MinimumSpanning Tree problem(MST).” Our optimization
problem becomes synonymous with minimization of
total length of moving distance of a worker. The
difference between path planning problems and ourproblem is that positions of waypoints for path planningproblems are fixed; on the other hand, our problem
changes positions of waypoints that are racks and boxes
in order to minimize length of moving distance.
In addition, since the number of racks and boxes ispredetermined as mentioned in the table 1 and 2, ourapproach has to put predetermined number of racks andboxes into a production line. For this, there is also aproblem of “Knapsack Problem(KP)” in our optimization
problem. It can be said that our optimization problem
combines TSP, MST and KP for the reasons stated above.

We explain the details of a “constrained GA” in thissection. Gene loci correspond to racks and to boxes
positions in a constrained GA. Selection process ingenetic operations is same way as a conventional GA. In
crossover process, loss or duplication of some racks andboxes will occur. The way of adjustment of the numberof racks is that all of duplicative racks are deleted thenmissing racks are randomly inserted to those positions.
The Fig. 2 illustrates an example of the way of adjustment.

(a)

P1
P2
C1C2

Racks
1000 1000 1000 1500 1500 1500 1500 2000 2000 2000
94
2
5
76
8
10
3
53
960
8
2
7
1
4
9
3
2
50
6
8
1
0
3
54
96
78
2
7
1
4

P1
P2
C1
C2

Racks
1000 1000 1000 1500 1500 1500 1500 2000 2000 2000
94
2
5
7
68
10
3
53
960
82
7
14
94
2
50
68
1
73
50
96
782314(b)Fig. 2. An example of crossover process for racks. P1, P2, C1
and C2 correspond to parent 1, 2 and child 1, 2, respectively.
(a)Duplication and loss. (b)After adjustment.

4. Genetic Algorithm and Constrained
To overcome difficulties mentioned in the section 3, we
propose to apply a GA to optimization for positions ofracks and boxes. We explain the details of a conventional
GA, and of a constrained GA to solve our problem.

Mutation process for racks is executed after theadjustment of crossover process. The Fig. 3 illustrates anexample of mutation for racks.

4.1. Genetic Algorithm
A Genetic Algorithm(GA) is suitable for global search ina high dimensional space because a GA has also theability of probabilistic random search based on genetic
operations in addition to local search. A GA has manyindividuals(populations), and an individual has achromosome that cords the parameters for optimization.

Before

C1
C2

After

C1
C2

Racks
1000 1000 1000 1500 1500 1500 1500 2000 2000 2000
942
5068173509678
2
3149540195
6046882237137Fig. 3. An example of mutation process for racks. C1 and C2
correspond to child 1 and 2, respectively. Colored cells
represent the mutated positions.

133

Journal of Robotics, Networking and Artificial Life, Vol. 5, No. 2 (September 2018) 131-134___________________________________________________________________________________________________________Mutation process in a conventional GA changes
genes; by contrast, that process in a constrained GAchanges gene loci in order to meet the conditions for thenumber of racks.
Crossover process for boxes is executed on the samestage each other, e.g., boxes in top stage of a rack arechanged with boxes in top stage of another rack. In
mutation process, genes for boxes are mutated randomly
as same way as a conventional GA. Following thoseprocesses, the adjustment process in order to meetconditions is proceeded. Firstly, excess boxes that do notmeet conditions in Table 2 are randomly chosen, thenthose boxes are deleted. Subsequently, shortfall in boxes
are inserted randomly to meet the conditions for thenumber of boxes. If a box may not be able to insert toanywhere, that individual is deleted and an individual isnewly generated.
From a constrained GA in above, our proposal isable to meet the conditions for our optimization problem.

In contrast with the first generation, the time forpicking up assemblies from the optimized positions inlast generation is about 61.7 second from Fig. 4. For this,our proposal achieved to reduce about 10 seconds per a
car compared with random positioning.

5. Experiments

6. Conclusions

In this section, we validate the effectiveness of aconstrained GA for optimization of a production line.
The parameters for a constrained GA are shown in Table
3. The fitness function is as the Eq. (1).

We propose to optimize a production line of cars
manufacturing plant by GA in this paper. The difficulties
of our aim are that parameters of optimization in ourproblem are dependent on each other because the numberof racks to put assembly boxes and that boxes ispredetermined. Consequently, we are not able to apply
conventional GA to optimization. For this, we apply a“constrained GA” to optimization for positions of racks
and boxes in a production line.
From the results of experiment, our proposal
achieved to reduce about 10 seconds per a car comparedwith random positioning.

66

Case 165

Case 2Fitness(sec）

64

63

62

61

1
1113
2225
3337
4449
5561
6673
7785
8897
10009
11121
12233
13345
14457
15569
16681
17793
18905
20017
21129
22241
23353
24465
25577
26689
27801
28913
30025
31137
32249
33361
34473
35585
36697
37809
38921
40033
41145
42257
43369
44481
45593
46705
47817
48929

60

Generation

Fig. 4. Optimization results. “Blue line” shows “Case 1” and“Orange line” shows “Case 2” in Table 3.

Table 3. The parameters for a constrained GA.
Case 1Case 2Num. of Individuals
4000
Num. of Generations
50000
Prob. of Crossover(Racks)
0.08
0.07
Prob. of Mutation(Racks)
0.02
0.025
Prob. of Crossover(Boxes)
0.08
0.07
Prob. of Mutation(Boxes)
0.02
0.025
Num. of Evaluation Cars
500

References
1. K. Kamei, T. Arai et. al., Development of the Recognition
Method for Black Objects under Black Background Colorin Proc. SISA2017, Fukuoka, 2017, pp.352–357.
2. S. Kido and K. Kamei, Extraction of the Certain Material
Image from an Image under Poor Light Conditions, in2017 Bachelor thesis of Nishinippon Institute ofTechnology (in Japanese).
3. D. Whitley, A genetic algorithm tutorial, in Statistics andcomputing (Springer, New York, 1994), pp.65–85.
4. R. Pfeifer and C. Scheier, Understanding Intelligence,(MIT Press, Cambridge, 1999).

𝑓 ∑ 𝑡 𝑁(1)
where 𝑖 is individual number, 𝑡 is total time of picking
up of all of assemblies for car 𝑗, 𝑁 is the number ofevaluation cars for an individual.
Fig. 4 illustrates the changes in the fitness value of thebest individual. Positions for racks and assembly boxes
are randomly determined in the first generation; therefore,the maximum time for picking up in the first generation
is about 70.9 second and the minimum is about 65.3
second.

134