Differential Evolution for Permutation-Based Combinatorial Problems - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 17

STEP 0. Initialize, N = 1 , S p = { 1 } , S a = { 2 ,.., N } . For j = 2 ,..., N . r ( j )=1

c j , c ( j ) , or c c ( j ) , j . Set n = n + 1

STEP 1. Select new city. Find j ∗ = arg min
j ∈ S a

STEP 2. Insert j ∗ , update r ( j ) S a = S a j ∗ . Find City i ∗ ∈ S p such that i ∗ = −

arg min [ i ] ∈ S p c [ i ] j ∗ + c j ∗ , [ i +1] − c [ i ] , [ i +1] . Update S p = s 1 ,.., i ∗ , j ∗ , i ∗ + 1 ,.., s n

{ } .Forall

S a if min c j , j ∗ , c j ∗ , j < c j , r (1) then r ( j )= j ∗ .If n < N ,goto2.
As can be seen, the closest insertion algorithms a constructive method. In order to
understand the steps involved, let us consider an example related to changeover times
for a flexible manufacturing cell (FMC).

j ∈

Example 2.1

Table 2.1 shows the changeover times for a flexible manufacturing-cell. A machine is
finishing producing batch T1 and other batches are yet to be completed. We are to use
the closest insertion heuristic to find a job sequence, treating the problem as a TSP.

Ta b l e 2 . 1 . Changeover times (hrs)

Fro /To T1 T2 T3 T4 T5

T1 - 8 14 10 12

T2 4 - 15 11 13

T3 12 17 - 1 3

T4 12 17 5 - 3

T5 13 18 15 2 -

Solution

Step 0 S p = { 1 } , S a = { 2 , 3 , 4 , 5 } , r ( j )

j

= 1; j = 2 ,.., 5 This is equivalent to choosing

∈ S a

the first city from the partial-list and eliminating this city form the available list.

c j , r [ j ] and set n = n + 1

Select the new city: find j ∗ = arg min
j

Step 1

∈ S a

= 8; j ∗ =
2. But ignore c 21 , c 31 , c 41 and c 51 because city 1 is already considered in S a .

min

j ∈ S a {

c 12 , c 13 , c 14 , c 15 , c 21 , c 31 , c 41 , c 51 } = min { 8 , 14 , 10 , 12 , 0 , 0 , 0 , 0 }

Step 2 Insert city 2, and update r ( j ) for the remaining jobs 3, 4, and 5 S p = { 1 , 2 } ; S a =

{ 3 , 4 , 5 } , c 12 + c 21 − c 14 = 8 + 4 − 0 = 12

Step 1 Select new city:

min = 11; j ∗ = 4; n = 3. So { c 23 , c 24 , c 25 , c 32 , c 42 , c 52 } = { 15 , 11 , 13 , 17 , 17 , 18 }

wehavejob4afterjob1or2.

Step 2 Insert job 4 There are the following possibilities from { 1 , 2 } : { 1 , 2 , 4 } or

{ 1 , 4 , 2 }

For { 1 , 2 , 4 } , c 12 + c 24 − c 14 = 8 + 11 − 10 = 9

For 8 = 19

The minimum occurs for inserting job 2 after job 4. Update r ( j ) for remaining
jobs 3, 5 i.e., r(3) = r(5) = 4

{ 1 , 4 , 2 } , c 14 + c 42 − c 12 = 10 + 17 −