Computational Intelligence - February 2016 - 59
B. A New Problem
Formulation for the FSP
This formulation is necessary for FSEA
as it is used in the population initialization to repair infeasible solutions and in
the recombination to maintain the feasibility of solutions. Let:
x i: represents the pickup time for job
i; y i: represents the chosen pickup time
for the next job to be done by the same
vehicle as job i; n: number of jobs,
neN; t: the sink node; S i: set of nodes
that correspond to the different possible
pickup times of job i; C xi: set of nodes
that are compatible with node x i;
e (a, b) = '
1 if a = b
0 otherwise
a, beN;
and
*
if i ! j and 7job k
so that: y i eS k and y j eS k,
0 otherwise.
Find x i and y i to:
b ^ y i, y j h =
1
Min / e (y i, t).
(1)
x i e S i , y i e C x i , 1 # i # n,
(2)
Subject to:
n
n
/ / b (y j, y i) = 0,
(3)
j=1 i=1
n
n
n
/ / e (x j, y i) + / e (y i, t) = n.
j=1 i=1
(4)
i=1
The objective function (1) counts
the number of times the y i variables
are set as t (the sink node). y i being set
as t means y i is at the end of the path
of one vehicle. Accordingly, the value
j11
Veh.
1
j11
Veh.
1
j12
Veh.
2
j21
(a) Violation of Const. (3)
Veh.
2
j21
(b) Violation of Const. (4)
C. Initialization and Repair
At the start of the algorithm, each variable is initialized with a random value.
Most probably, the initialized solutions
are not feasible. To repair such infeasible
solutions, we developed a repair operator.
Note that Const. (2) is never violated,
since individuals are initialized within the
domain ranges given in this constraint.
The repair operator repairs violations
of Consts. (3) and (4) as follows. First,
the repair operator checks the violation
of Const. (3). If it is violated, at least one
job is placed in more than one path. Fig.
3 (a) shows an example of such a violation. In order to repair individuals
regarding this violation, the duplicated
jobs are removed and replaced by the
sink node in all but one of the violated
paths. In the example in Fig. 3 (a), job 3
must be removed from one of the paths,
e.g. the path of vehicle 2, and be kept in
the path of vehicle 1. Consequently, this
violation is repaired (Fig. 3 (c)).
The individuals must then be
checked regarding the violation of
Const. (4). If this constraint is violated it
means that a path has two different
nodes corresponding to the same job
(Fig. 3 (b)). In the example in Fig. 3, two
different pickup time nodes of job 3
^ j 31 and j 32) are in the path of vehicle
1, hence this is a violation of Const. (4).
: A Node in a Path
j12
: A Node Not in a Path
s : The Source Node
j31
s
t
j32
is Const. (4).
j11
j31
s
t
j32
Veh.
1
j12
j31
s
/ nj = 1 / ni = 1 e (x j, ny i) +n / in= 1 e (y i, t),
w e h a v e / j = 1 / i = 1 e (x j , y i ) +
/ in= 1 e (y i, t) = m + ^n - mh = n. This
of the objective function (1) is the total
number of paths, which is equivalent to
the total number of vehicles. Const. (2)
defines the domain range of the x i and
y i variables. Const. (3) ensures that a
job must be in only one path (see Fig.
3). If a job j is included in more than
one path, j will be presented by more
than one " y " variable in the chromosome. Const. (3) prevents this from
happening by ensuring that, for each
job that is not the first or the last in a
path, there is one and only one " y "
variable corresponding to the job (see
Fig. 3). Const. (4) ensures that in all
paths there is no more than one node
referring to one job (see Fig. 3). In
other words, each job must have only
one node in only one path. The following example clarifies the meaning
of this constraint. Consider one path
where job j is set to be transported
after job i by the same vehicle. It
means that y i refers to one of the possible pickup time nodes of job j. The
path is only feasible if x j is equal to y i,
i.e. both x j and y i refer to the same
pickup time for job j if job i is not the
last job in the path. It means
e (x j, y i) = 1. Job i can only be picked
n
up once, so / i = 1 e (x j, y i) must be
equal to 1. Let m < n be the number of
jobs that are not the last jobs in their
n
n
paths, then / j = 1 / i = 1 e (x j, y i) must
be equal to m. Let k = n - m be the
number of jobs that are the last in their
n
paths, then / i = 1 e (y i, t) must be equal
t o k. Ta k e t h e s u m m a t i o n :
Veh.
2
t
j32
j21
t : The Sink Node
: An Arc in the Path
of Vehicle 1
: An Arc in the Path
of Vehicle 2
: An Arc Not in a Path
(c) Repaired Solution
Figure 3 Plot (a) shows an example of a solution violating Const. (3) (chromosome: [< x 1 = j 11, y 1 = j 31 >, < x 2 = j 21, y 2 = j 32 >, < x 3 = j 31, y 3 = t >])
and plot (b) shows a violation of Const. (4) where two different nodes of job 3 are placed in the path of vehicle 1 (chromosome: [< x 1 = j 11, y 1 = j 32 >,
< x 2 = j 21, y 2 = t >, < x 3 = j 31, y 3 = t >]). Plot (c) shows the repaired solution for these violations (chromosome: [< x 1 = j 11, y 1 = j 31 >, < x 2 = j 21,
y 2 = t >, < x 3 = j 31, y 3 = t >]).
February 2016 | Ieee ComputatIonal IntellIgenCe magazIne
59
Table of Contents for the Digital Edition of Computational Intelligence - February 2016
Computational Intelligence - February 2016 - Cover1
Computational Intelligence - February 2016 - Cover2
Computational Intelligence - February 2016 - 1
Computational Intelligence - February 2016 - 2
Computational Intelligence - February 2016 - 3
Computational Intelligence - February 2016 - 4
Computational Intelligence - February 2016 - 5
Computational Intelligence - February 2016 - 6
Computational Intelligence - February 2016 - 7
Computational Intelligence - February 2016 - 8
Computational Intelligence - February 2016 - 9
Computational Intelligence - February 2016 - 10
Computational Intelligence - February 2016 - 11
Computational Intelligence - February 2016 - 12
Computational Intelligence - February 2016 - 13
Computational Intelligence - February 2016 - 14
Computational Intelligence - February 2016 - 15
Computational Intelligence - February 2016 - 16
Computational Intelligence - February 2016 - 17
Computational Intelligence - February 2016 - 18
Computational Intelligence - February 2016 - 19
Computational Intelligence - February 2016 - 20
Computational Intelligence - February 2016 - 21
Computational Intelligence - February 2016 - 22
Computational Intelligence - February 2016 - 23
Computational Intelligence - February 2016 - 24
Computational Intelligence - February 2016 - 25
Computational Intelligence - February 2016 - 26
Computational Intelligence - February 2016 - 27
Computational Intelligence - February 2016 - 28
Computational Intelligence - February 2016 - 29
Computational Intelligence - February 2016 - 30
Computational Intelligence - February 2016 - 31
Computational Intelligence - February 2016 - 32
Computational Intelligence - February 2016 - 33
Computational Intelligence - February 2016 - 34
Computational Intelligence - February 2016 - 35
Computational Intelligence - February 2016 - 36
Computational Intelligence - February 2016 - 37
Computational Intelligence - February 2016 - 38
Computational Intelligence - February 2016 - 39
Computational Intelligence - February 2016 - 40
Computational Intelligence - February 2016 - 41
Computational Intelligence - February 2016 - 42
Computational Intelligence - February 2016 - 43
Computational Intelligence - February 2016 - 44
Computational Intelligence - February 2016 - 45
Computational Intelligence - February 2016 - 46
Computational Intelligence - February 2016 - 47
Computational Intelligence - February 2016 - 48
Computational Intelligence - February 2016 - 49
Computational Intelligence - February 2016 - 50
Computational Intelligence - February 2016 - 51
Computational Intelligence - February 2016 - 52
Computational Intelligence - February 2016 - 53
Computational Intelligence - February 2016 - 54
Computational Intelligence - February 2016 - 55
Computational Intelligence - February 2016 - 56
Computational Intelligence - February 2016 - 57
Computational Intelligence - February 2016 - 58
Computational Intelligence - February 2016 - 59
Computational Intelligence - February 2016 - 60
Computational Intelligence - February 2016 - 61
Computational Intelligence - February 2016 - 62
Computational Intelligence - February 2016 - 63
Computational Intelligence - February 2016 - 64
Computational Intelligence - February 2016 - 65
Computational Intelligence - February 2016 - 66
Computational Intelligence - February 2016 - 67
Computational Intelligence - February 2016 - 68
Computational Intelligence - February 2016 - 69
Computational Intelligence - February 2016 - 70
Computational Intelligence - February 2016 - 71
Computational Intelligence - February 2016 - 72
Computational Intelligence - February 2016 - Cover3
Computational Intelligence - February 2016 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com