Computational Intelligence - February 2016 - 60

represents the total number of vehicles. Then, if we can reduce the number of job sequences in a solution, we
will be able to reduce the fleet size.
To reduce the number of job
sequences, we can try to remove all
jobs in one randomly chosen
sequence (let us call it s_delete) and,
if possible, insert them into the other
sequences. This is equivalent to asking
other vehicles to take over all the jobs
originally assigned to the s_delete
vehicle. If this can be done, the s_
delete job sequence will disappear
and the fleet size will be reduced by
one (Alg. 2 and Fig. 4).
2) Mutation: There might be a local
optimum situation where the local
search cannot remove the chosen s_
delete sequence, because there is no
available place in the other sequences
to further insert the remaining jobs
from s_delete. We propose a mutation
operator to help the algorithm escape
such a situation. Instead of moving
jobs from s_delete to other sequences,
we try to move jobs among the other
sequences, in the hope that this
movement would change the structure of these sequences, which in
turn would open up space into
which jobs from s_delete can be slotted in (see Alg. 3 and Fig. 4).

Algorithm 1 Repair(Individual X ).

1: Identify ViolConst3, the set of jobs in individual X that violate Const. (3)
2: for all jobs j e ViolConst3
3: Update all but one "y" variables corresponding to job j with the sink node //keep one of the "y"
variables unchanged randomly
4: Identify ViolConst4, the set of triples < x i, y i, x j > that violate Const. (4)
5: for all triples < x i, y i, x j > e ViolConst4
6: if x i is compatible with x j then Update y i with x j
7: else Update y i with the sink node

Algorithm 2 ReduceJobSequences().
1: for all jobs j e JobSeqs_delete
2: if job j can be inserted into JobSeq l at position k (1 # l # FS, l ! s_delete and
1 # k # length ^ JobSeq l h)
3:
insert job j into J l at position k
4:
remove job j from JobSeqs_delete
5: if all jobs are removed from JobSeqs_delete //vehicle s_delete was removed from the fleet size
successfully
6: Randomly choose another vehicle to be s_delete
7: if any job is removed from JobSeqs_delete then a := 0
8: else a := a + 1
9: adaptiveLearning()
where JobSeql is the sequence of jobs for vehicle l, FS is the fleet size, a is the number of generations
that JobSeqs_delete has remained unchanged, and the adaptiveLearning() is our proposed learning method
to help FSEA to get out of local minima (see Subsec. IV-E).

To repair the violation, the repair operator checks whether x 3 ^ j 31h in pair
< x 3, y 3 > of job 3 is compatible with
x 1 ^ j 11h in pair < x 1, y 1 >. If this is the
case, the repair operator changes the
value of y 1 to j 31. Otherwise, it updates
the value of y 1 with the sink node (t ) to
terminate the path of vehicle 1 at job 1
and starts a new path from job 3. For
this type of violation, the repair operator
always changes the y variables of the
preceding job rather than the x variables of the violated job. This is because,
if the repair operator changes the x
variable of the violated job, the consecutive jobs might not be compatible and

hence the rest of the path might
become invalid. The pseudo-code of the
repair procedure is shown in Alg. 1.
D. Reproduction

We propose a reproduction method,
which is a combination of a mutation
operator and a local search. The mutation operator is used to create offspring
and the local search is used to improve
the fitness of each offspring.
1) Local search: Recall from II-A3 that (i)
we model a solution as a graph containing multiple paths (job sequences)
from the source to the sink and (ii)
the total number of job sequences

j11

j11
Veh.
1

Veh.
1

j12

Veh.
2

j32

Veh.
2

j21
s_delete

j12

j41

(a) Original Solution

t
j32

Veh.
2

j21
s_delete

s : The Source Node
j31

: A Node in a Path
: A Node Not in a Path

Veh.
1
j31

As mentioned in Subsec. IV-D, the algorithm might be trapped in a local optimum where it is not possible to move
the remaining jobs from a randomly

j11

j12

j31

E. Adaptive Learning Method

j41

(b) Mutated Solution

t
j32
j21
j41

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
: An Arc in the Path
of s_delete

Figure 4 In this example, if job 3 in the original solution (left plot) is moved from vehicle 2 to vehicle 1 thanks to the mutation operator (middle plot), job 4 can be moved by the local search from vehicle s_delete to vehicle 2 (right plot). As a result, we can delete vehicle s_delete and
reduce the fleet size by one.

IEEE ComputatIonal IntEllIgEnCE magazInE | FEbruary 2016

Table of Contents for the Digital Edition of Computational Intelligence - February 2016