Chemical reaction inspired approach for routing problems with hard time constraints

Figures & data

Figure 1. Solution encoding.

Figure 2. Greedy randomized adaptive search procedure for population initialization.

Figure 3. Flow diagram of the optimization process.

Table 1. Elementary reactions according to molecularity.

	Uni-molecular reactions	Inter-molecular reactions
Fixed population size	On-wall ineffective collision	Inter-molecular ineffective collision
Variable population size	Decomposition	Synthesis

Table 2. Elementary reactions according to intensification and diversification.

Elementary reactions	Intensification	Diversification
On-wall ineffective collision	X
Decomposition		X
Inter-molecular ineffective collision	X
Synthesis		X

Figure 4. Illustration of on-wall ineffective collision.

Table

Algorithm 1. On-wall ineffective collision
Input: M, Buffer, objective function f, KELoss
Output: M, Buffer
generate M’ = Neighbourhood(M)
2. PEM = f(M)
3. If PEM + KEM≥PEM’ Then
4.   generate q in [KELoss, 1]
5.   KEw'= (PEw + KEw – PEw’) × q
6.   Buffer = Buffer + (PEw + KEw – PEw’) × (1 – q)
7.   M = M’

Figure 5. Illustration of inter-molecular ineffective collision.

Table

Algorithm 2. Inter-molecular ineffective collision
Input: M1, M2, objective function f
Output: M1, M2
M1’ =  Neighbourhood(M1)
2. M2’ = Neighbourhood (M2)
3. PEM1’ = f(M1’)
4. PEM2’ = f(M2’)
5. Diff = (PEM1 + PEM2 + PEM1’ + KEM1 + KEM2) – (PEM1’ – PEM2’)
6. If Diff > 0
7.   generate p in [0, 1]
8.   KEM1’ = Diff * p
9.   KEM2’ = Diff * (1 – p)
10   M1 = M1’
11.   M2 = M2’

Figure 6. Illustration of decomposition.

Table

Algorithm 3. Decomposition
Input: M, Buffer, objective function f, Success
Ouput: M1, M2, Buffer
1. M1 = Neighbourhood(M)
2. M2 = Neighbourhood(M)
3. PEM1 = f(M1)
4. PEM2 = f(M2)
5. Diff = PEM + KEM – PEM1 – PEM2
6. If Diff ≥ 0
7.   Success = True
8.   generate k in [0, 1]
9.   KEM1 = Diff * k
10   KEM2 = Diff * (1 – k)
11. Else If Diff + Buffer ≥ 0
12.   Success = True
13.   generate m1, m2, m3 et m4 in [0, 1]
14.   KEM1 = (Diff + Buffer) * m1* m2
15.   KEM2 = (Diff + Buffer – KEM1) * m3* m4
16. Else
17.   Success = False

Figure 7. Illustration of synthesis.

Table

Algorithm 4. Synthesis
Input: M1, M2
Output: M’, Success
1. generate M’ from M1, M2
2. PEM’ = f (M’)
3. If PEM1 + PEM2 + KEM1 + KEM2 ≥ PEM’
4.   Success = True
5. Else
6.   Success = False

Table 3. Characteristics of considered benchmark instances.

Instances	Number of customers	Vehicle capacity	Distribution of customers	Time windows
R101	25, 50 and 100	200	Random	Narrow
R102	25, 50 and 100	200	Random	Narrow
R103	25, 50 and 100	200	Random	Narrow
R201	25, 50 and 100	1000	Random	Wide
R202	25, 50 and 100	1000	Random	Wide
R203	25, 50 and 100	1000	Random	Wide
C101	25, 50 and 100	200	Cluseterd	Narrow
C102	25, 50 and 100	200	Cluseterd	Narrow
C103	25, 50 and 100	200	Cluseterd	Narrow
C201	25, 50 and 100	700	Cluseterd	Wide
C202	25, 50 and 100	700	Cluseterd	Wide
C203	25, 50 and 100	700	Cluseterd	Wide
RC101	25, 50 and 100	200	Random/Cluseterd	Narrow
RC102	25, 50 and 100	200	Random/Cluseterd	Narrow
RC103	25, 50 and 100	200	Random/Cluseterd	Narrow
RC201	25, 50 and 100	1000	Random/Cluseterd	Wide
RC202	25, 50 and 100	1000	Random/Cluseterd	Wide
RC203	25, 50 and 100	1000	Random/Cluseterd	Wide

Table 4. Part of parameter configuration for instances with 25 customers.

	NI = 1000 KELoss = 0.1 MoleColl = 0.7 α = 25 β = 0.5	NI = 15,000 KELoss = 0.5 MoleColl = 0.5 α = 50 β = 0.3	NI = 18,000 KELoss = 0.9 MoleColl = 0.1 α = 100 β = 0.1
R101	736.99	635.50	618.32
R102	682.08	573.69	549.35
R103	649.74	512.36	461.55
R201	666.86	493.52	465.18
R202	626.08	480.09	429.35
R203	607.10	441.07	425.51
C101	802.35	628.36	438.69
C102	667.98	524.56	434.30
C103	659.79	512.05	392.31
C201	794.12	574.24	457.53
C202	656.90	566.59	431.59
C203	655.37	528.11	387.33
RC101	1391.82	1126.56	984.65
RC102	1176.23	1058.01	880.66
RC103	1012.57	962.20	735.56
RC201	1197.17	1032.88	778.35
RC202	1073.30	872.61	708.11
RC203	954.23	862.35	643.88

Table 5. Part of parameter configuration for instances with 50 customers.

	NI = 1000 KELoss = 0.1 MoleColl = 0.7 α =  25 β =  0.5	NI = 15,000 KELoss = 0.5 MoleColl = 0.5 α =  50 β =  0.3	NI = 18,000 KELoss = 0.9 MoleColl = 0.1 α =  100 β =  0.1
R101	1347.89	1178.14	1068.42
R102	1181.89	1026.97	925.75
R103	1316.90	1053.95	791.90
R201	1285.25	1006.19	829.59
R202	1047.12	917.40	751.47
R203	883.08	729.01	662.14
C101	802.35	628.36	438.69
C102	667.98	524.56	434.30
C103	659.79	512.05	392.31
C201	794.12	574.24	457.53
C202	656.90	566.59	431.59
C203	655.37	528.11	387.33
RC101	1391.82	1126.56	984.65
RC102	1176.23	1058.01	880.66
RC103	1012.57	962.20	735.56
RC201	1197.17	1032.88	778.35
RC202	1073.30	872.61	708.11
RC203	954.23	862.35	643.88

Table 6. Part of parameter configuration for instances with 100 customers.

	NI = 1000 KELoss = 0.1 MoleColl = 0.7 α = 25 β = 0.5	NI = 15,000 KELoss = 0.5 MoleColl = 0.5 α = 50 β = 0.3	NI = 18,000 KELoss = 0.9 MoleColl = 0.1 α = 100 β = 0.1
R101	2292.05	2083.45	1721.11
R102	1980.61	1723.44	1545.36
R103	2416.67	1516.78	1268.39
R201	1944.10	1838.65	1296.00
R202	1976.17	1418.89	1191.39
R203	1713.91	1277.87	1027.29
C101	2164.96	1528.12	1197.03
C102	2045.35	1538.57	1112.34
C103	1938.25	1335.44	1029.15
C201	1982.80	1372.48	988.50
C202	1747.77	1116.16	910.23
C203	1785.02	1232.58	816.52
RC101	2723.29	2141.78	1827.18
RC102	2594.57	1887.86	1618.16
RC103	2686.07	1643.25	1423.28
RC201	2359.41	1878.72	1516.65
RC202	2148.55	1540.36	1335.08
RC203	2000.21	1365.97	1105.34

Figure 8. Simulation results for instances with 25 customers.

Figure 9. Simulation results for instances with 50 customers.

Figure 10. Simulation results for instances with 100 customers.

Table 7. Percent deviations from the best known solutions for instances with 25 customers.

Instances	R101	R102	R103	R201	R202	R203	C101	C102	C103	C201	C202	C203	RC101	RC102	RC103	RC201	RC202	RC203
Deviations	0.19	0.33	1.52	0.23	3.61	7.25	0.26	0.23	0.23	0.39	0.39	2.04	0.41	0.27	0.39	0.28	0.25	0.47

Table 8. Percent deviations from the best known solutions for instances with 50 customers.

Instances	R101	R102	R103	R201	R202	R203	C101	C102	C103	C201	C202	C203	RC101	RC102	RC103	RC201	RC202	RC203
Deviations	2.33	14.84	11.39	20.48	21.61	9.39	21.05	15.88	6.57	9.71	7.85	4.88	4.3	3.17	−4.45	0.41	1.79	3.16

Table 9. Percent deviations from the best known solutions for instances with 100 customers.

Instances	R101	R102	R103	R201	R202	R203	C101	C102	C103	C201	C202	C203	RC101	RC102	RC103	RC201	RC202	RC203
Deviations	4.21	3.47	−2.22	1.74	−4.54	5.77	37.07	24.56	24.7	17.18	17.62	18.82	3.91	0.66	5.43	1.85	−6.56	2.32