American Institute of Mathematical Sciences

• Previous Article
Two-echelon supply chain model with manufacturing quality improvement and setup cost reduction
• JIMO Home
• This Issue
• Next Article
A multi-objective integrated model for closed-loop supply chain configuration and supplier selection considering uncertain demand and different performance levels
April  2017, 13(2): 1065-1084. doi: 10.3934/jimo.2016062

Solving routing and wavelength assignment problem with maximum edge-disjoint paths

 1 Department of Transportation and Logistics Management, National Chiao Tung University, Hsinchu 300, Taiwan 2 Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27606, USA

* Corresponding author

Received  October 2014 Revised  August 2016 Published  October 2016

The routing and wavelength assignment (RWA) problem in wave-length-division multiplexing optical networks is critically important for increasing the efficiency of wavelength-routed all-optical networks. Given the physical network structure and a set of connection requests, the problem aims to establishing routes for the requests and assigning a wavelength to each of them, subject to the wavelength continuous and wavelength clash constraints. The objective is to minimize he number of required wavelengths to satisfy all requests. The RWA problem was proven to be NP-hard and has been investigated for decades. In this paper, an algorithm based on the maximum edge-disjoint paths is proposed to tackle the RWA problem. Its performance is verified by experiments on some realistic network topologies. Compared with the state-of-the-art bin-packing based methods and the particle swarm optimization algorithm, the proposed method can find the best solution among all testing instances in reasonable computing time.

Citation: Chia-Chun Hsu, Hsun-Jung Cho, Shu-Cherng Fang. Solving routing and wavelength assignment problem with maximum edge-disjoint paths. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1065-1084. doi: 10.3934/jimo.2016062
References:

show all references

References:
Pseudocode of FD(FFD) Algorithm
Pseudocode of FD(FFD) Algorithm
Pseudocode of PSO Algorithm
Pseudocode of a basic MEDP-RWA algorithm
Pseudocode of GMR algorithm
Number of times that the best value is achieved by different methods
Frequency graphs of testing results on zib54
Frequency graphs of testing results on ta2
Frequency graphs of testing results on Germany50
Relative difference of computational time on Norway
Relative difference of computational time on giul
Relative difference of computational time on graph Germany
Relative difference of computational time on graph ta2
Main quantitative characteristics of testing networks
 Graph $\left | V \right |$ $\left | E \right |$ Min. Avg. Max. Diameter CHNNET 15 27 3 3.6 5 5 NSF 16 25 2 3.1 4 4 New York 16 49 2 6.1 11 3 APPANET 20 32 3 3.2 4 6 EON 20 39 2 3.9 7 5 France 25 45 2 3.6 10 5 Norway 27 51 2 3.8 6 7 cost266 37 57 2 3.1 5 8 janos-us-ca 39 67 2 3.1 5 10 giul 39 86 3 4.4 8 6 piro40 40 89 4 4.5 5 7 USAnet 46 75 2 3.3 5 11 Germany50 50 88 2 3.5 5 9 zib54 54 80 1 3.0 10 8 ta2 65 108 1 3.3 10 8 (Min., Avg. and Max. denote the minimum, average and maximum degree, respectively)
 Graph $\left | V \right |$ $\left | E \right |$ Min. Avg. Max. Diameter CHNNET 15 27 3 3.6 5 5 NSF 16 25 2 3.1 4 4 New York 16 49 2 6.1 11 3 APPANET 20 32 3 3.2 4 6 EON 20 39 2 3.9 7 5 France 25 45 2 3.6 10 5 Norway 27 51 2 3.8 6 7 cost266 37 57 2 3.1 5 8 janos-us-ca 39 67 2 3.1 5 10 giul 39 86 3 4.4 8 6 piro40 40 89 4 4.5 5 7 USAnet 46 75 2 3.3 5 11 Germany50 50 88 2 3.5 5 9 zib54 54 80 1 3.0 10 8 ta2 65 108 1 3.3 10 8 (Min., Avg. and Max. denote the minimum, average and maximum degree, respectively)
Results of GMR and bin-packing based methods (time unit: sec)
 GA_MEDP_RWA (GMR) FF FFD BF BFD instance max avg min avg time # wl $t_{FF}$ # wl $t_{FFD}$ # wl $t_{BF}$ # wl $t_{BFD}$ CHNNET_02 4 4.0 4 2.07 4 0.24 4 0.14 4 0.11 5 0.14 CHNNET_04 5 4.4 4 3.02 5 0.18 4 0.15 5 0.23 4 0.26 CHNNET_06 11 11.0 11 10.66 11 0.70 11 0.62 11 0.81 11 0.96 CHNNET_08 14 14.0 14 13.50 15 1.02 14 1.17 14 1.21 14 1.51 CHNNET_1 16 15.0 15 16.31 15 1.48 15 1.42 16 1.75 15 2.20 NSF_02 5 5.0 5 2.41 6 0.34 5 0.17 6 0.19 6 0.18 NSF_04 8 7.3 7 5.80 9 0.37 9 0.35 8 0.52 8 0.50 NSF_06 9 8.8 8 7.97 10 0.46 10 0.49 9 0.59 9 0.64 NSF_08 14 13.2 13 15.11 17 1.06 15 1.10 14 1.50 14 1.47 NSF_1 17 16.6 16 22.89 19 1.70 17 1.45 17 1.96 17 2.08 NewYork_02 2 2.0 2 1.37 2 0.14 2 0.08 2 0.07 2 0.08 NewYork_04 3 3.0 3 2.65 3 0.23 3 0.20 3 0.23 3 0.23 NewYork_06 5 4.1 4 3.93 4 0.33 4 0.34 4 0.34 4 0.33 NewYork_08 7 6.0 6 6.75 7 0.64 6 0.58 7 0.62 6 0.81 NewYork_1 8 8.0 8 7.03 8 0.73 8 0.80 8 1.02 8 2.30 ARPANET_02 10 9.1 9 10.58 9 0.55 9 0.53 9 0.64 9 0.86 ARPANET_04 13 12.1 12 16.96 12 1.05 12 1.29 12 1.31 12 1.76 ARPANET_06 21 21.0 21 25.98 21 2.70 21 2.68 21 3.39 21 4.58 ARPANET_08 29 29.0 29 32.31 30 5.46 29 6.14 30 7.82 29 10.94 ARPANET_1 33 33.0 33 62.85 34 6.85 33 7.77 34 10.19 33 12.68 EON_02 4 3.1 3 3.19 3 0.22 4 0.17 4 0.34 4 0.36 EON_04 9 8.3 8 14.74 10 1.10 9 1.14 8 1.53 8 1.54 EON_06 11 11.0 11 17.52 13 1.21 11 1.18 11 1.94 11 1.90 EON_08 14 13.7 13 26.63 16 2.20 13 2.99 13 3.61 13 3.72 EON_1 19 18.1 18 38.17 22 3.64 18 3.58 18 5.77 18 5.73 France_02 8 8.0 8 8.87 8 1.30 8 1.27 8 1.57 8 1.72 France _04 13 12.8 12 16.05 14 4.29 13 4.90 13 5.14 13 6.03 France _06 22 22.0 22 39.07 22 8.73 22 10.55 22 11.69 22 15.27 France _08 27 26.3 26 47.09 28 13.25 27 14.00 27 18.53 26 24.20 France _1 34 34.0 34 60.09 34 22.54 34 23.99 34 29.93 34 35.84
 GA_MEDP_RWA (GMR) FF FFD BF BFD instance max avg min avg time # wl $t_{FF}$ # wl $t_{FFD}$ # wl $t_{BF}$ # wl $t_{BFD}$ CHNNET_02 4 4.0 4 2.07 4 0.24 4 0.14 4 0.11 5 0.14 CHNNET_04 5 4.4 4 3.02 5 0.18 4 0.15 5 0.23 4 0.26 CHNNET_06 11 11.0 11 10.66 11 0.70 11 0.62 11 0.81 11 0.96 CHNNET_08 14 14.0 14 13.50 15 1.02 14 1.17 14 1.21 14 1.51 CHNNET_1 16 15.0 15 16.31 15 1.48 15 1.42 16 1.75 15 2.20 NSF_02 5 5.0 5 2.41 6 0.34 5 0.17 6 0.19 6 0.18 NSF_04 8 7.3 7 5.80 9 0.37 9 0.35 8 0.52 8 0.50 NSF_06 9 8.8 8 7.97 10 0.46 10 0.49 9 0.59 9 0.64 NSF_08 14 13.2 13 15.11 17 1.06 15 1.10 14 1.50 14 1.47 NSF_1 17 16.6 16 22.89 19 1.70 17 1.45 17 1.96 17 2.08 NewYork_02 2 2.0 2 1.37 2 0.14 2 0.08 2 0.07 2 0.08 NewYork_04 3 3.0 3 2.65 3 0.23 3 0.20 3 0.23 3 0.23 NewYork_06 5 4.1 4 3.93 4 0.33 4 0.34 4 0.34 4 0.33 NewYork_08 7 6.0 6 6.75 7 0.64 6 0.58 7 0.62 6 0.81 NewYork_1 8 8.0 8 7.03 8 0.73 8 0.80 8 1.02 8 2.30 ARPANET_02 10 9.1 9 10.58 9 0.55 9 0.53 9 0.64 9 0.86 ARPANET_04 13 12.1 12 16.96 12 1.05 12 1.29 12 1.31 12 1.76 ARPANET_06 21 21.0 21 25.98 21 2.70 21 2.68 21 3.39 21 4.58 ARPANET_08 29 29.0 29 32.31 30 5.46 29 6.14 30 7.82 29 10.94 ARPANET_1 33 33.0 33 62.85 34 6.85 33 7.77 34 10.19 33 12.68 EON_02 4 3.1 3 3.19 3 0.22 4 0.17 4 0.34 4 0.36 EON_04 9 8.3 8 14.74 10 1.10 9 1.14 8 1.53 8 1.54 EON_06 11 11.0 11 17.52 13 1.21 11 1.18 11 1.94 11 1.90 EON_08 14 13.7 13 26.63 16 2.20 13 2.99 13 3.61 13 3.72 EON_1 19 18.1 18 38.17 22 3.64 18 3.58 18 5.77 18 5.73 France_02 8 8.0 8 8.87 8 1.30 8 1.27 8 1.57 8 1.72 France _04 13 12.8 12 16.05 14 4.29 13 4.90 13 5.14 13 6.03 France _06 22 22.0 22 39.07 22 8.73 22 10.55 22 11.69 22 15.27 France _08 27 26.3 26 47.09 28 13.25 27 14.00 27 18.53 26 24.20 France _1 34 34.0 34 60.09 34 22.54 34 23.99 34 29.93 34 35.84
Results of GMR and bin-packing based methods (cont'd)
 GA_MEDP_RWA (GMR) FF FFD BF BFD instance max avg min avg time # wl $t_{FF}$ # wl $t_{FFD}$ # wl $t_{BF}$ # wl $t_{BFD}$ Norway_02 9 8.6 8 9.26 10 1.67 8 1.78 9 1.90 8 2.17 Norway _04 15 14.6 14 18.47 15 3.75 15 4.12 15 4.56 15 5.43 Norway _06 22 21.4 21 32.84 22 7.87 22 8.20 22 9.73 22 12.32 Norway _08 30 29.5 29 46.41 31 15.05 30 16.59 31 19.79 30 24.59 Norway _1 37 36.6 36 63.77 37 21.99 36 23.75 38 28.58 36 36.13 cost266_02 19 18.2 18 46.68 19 7.34 18 7.44 19 10.38 19 12.40 cost266_04 35 34.1 33 159.69 35 27.28 33 28.58 36 36.35 35 47.28 cost266_06 54 53.1 53 237.55 54 67.18 53 70.90 55 98.00 53 117.30 cost266_08 68 67.2 67 275.29 67 120.73 68 144.22 69 190.55 68 273.40 janos-us-ca_02 26 26.0 26 54.75 27 16.61 26 16.53 27 27.40 27 27.58 janos-us-ca_04 40 39.6 39 97.42 42 49.52 39 59.49 43 70.75 40 88.45 janos-us-ca_06 68 67.8 67 210.36 71 110.99 69 124.10 72 157.50 68 200.32 janos-us-ca_08 89 88.2 88 326.39 92 199.09 92 212.16 93 257.39 91 345.67 giul_02 11 10.3 10 26.93 10 7.40 10 8.11 10 8.89 10 11.24 giul_04 21 20.2 19 82.66 19 29.10 19 31.70 19 37.42 19 46.16 giul_06 25 24.6 24 150.73 25 48.91 25 55.96 25 59.10 24 73.12 giul_08 36 34.9 34 226.85 35 113.85 34 125.20 36 134.25 34 181.70 piro40_02 17 17 17 55.51 17 10.67 17 12.58 17 15.20 17 18.50 piro40_04 28 28 28 118.50 28 34.98 28 38.00 28 43.05 28 54.44 piro40_06 46 46 46 208.81 46 61.98 46 68.00 46 84.33 46 109.15 piro40_08 60 60 60 338.61 60 105.97 60 119.35 60 140.20 60 181.52 USAnet_02 25 24.0 23 86.13 25 35.62 26 37.95 26 45.15 25 56.09 USAnet_04 47 45.9 45 355.64 47 130.43 45 147.76 48 176.43 45 228.50 USAnet_06 67 66.1 65 422.63 68 244.00 65 287.58 68 346.66 66 432.89 USAnet_08 88 86.5 85 490.20 88 475.69 85 544.98 89 587.11 86 791.38 Germany50_02 21 20.7 20 109.28 21 35.86 21 36.10 21 46.10 22 58.58 Germany50_04 45 44.2 43 350.24 45 152.90 44 163.00 48 217.60 48 276.50 Germany50_06 61 60.5 60 584.92 63 347.70 61 410.61 63 430.89 65 544.74 Germany50_08 76 74.7 73 921.59 77 552.50 75 725.90 79 843.70 76 1098.40 zib54_02 32 31.1 30 149.44 33 52.28 31 55.01 35 77.70 33 91.67 zib54_04 67 65.7 65 406.90 67 209.80 65 220.50 73 304.64 71 379.55 zib54_06 92 90.0 88 762.56 91 442.95 89 522.85 99 696.78 98 889.98 zib54_08 122 119.2 117 1446.41 117 994.60 117 939.60 130 1229.60 127 1457.22 ta2_02 35 34.6 34 411.59 35 148.93 34 163.00 35 188.75 35 250.99 ta2_04 72 70.1 69 945.79 72 507.30 69 542.50 73 635.57 70 813.04 ta2_06 99 97.4 96 1865.20 98 1311.70 98 1484.00 100 1881.30 97 2047.40 ta2_08 131 129.7 128 2835.57 130 1935.30 129 2577.90 135 2644.43 128 3713.46
 GA_MEDP_RWA (GMR) FF FFD BF BFD instance max avg min avg time # wl $t_{FF}$ # wl $t_{FFD}$ # wl $t_{BF}$ # wl $t_{BFD}$ Norway_02 9 8.6 8 9.26 10 1.67 8 1.78 9 1.90 8 2.17 Norway _04 15 14.6 14 18.47 15 3.75 15 4.12 15 4.56 15 5.43 Norway _06 22 21.4 21 32.84 22 7.87 22 8.20 22 9.73 22 12.32 Norway _08 30 29.5 29 46.41 31 15.05 30 16.59 31 19.79 30 24.59 Norway _1 37 36.6 36 63.77 37 21.99 36 23.75 38 28.58 36 36.13 cost266_02 19 18.2 18 46.68 19 7.34 18 7.44 19 10.38 19 12.40 cost266_04 35 34.1 33 159.69 35 27.28 33 28.58 36 36.35 35 47.28 cost266_06 54 53.1 53 237.55 54 67.18 53 70.90 55 98.00 53 117.30 cost266_08 68 67.2 67 275.29 67 120.73 68 144.22 69 190.55 68 273.40 janos-us-ca_02 26 26.0 26 54.75 27 16.61 26 16.53 27 27.40 27 27.58 janos-us-ca_04 40 39.6 39 97.42 42 49.52 39 59.49 43 70.75 40 88.45 janos-us-ca_06 68 67.8 67 210.36 71 110.99 69 124.10 72 157.50 68 200.32 janos-us-ca_08 89 88.2 88 326.39 92 199.09 92 212.16 93 257.39 91 345.67 giul_02 11 10.3 10 26.93 10 7.40 10 8.11 10 8.89 10 11.24 giul_04 21 20.2 19 82.66 19 29.10 19 31.70 19 37.42 19 46.16 giul_06 25 24.6 24 150.73 25 48.91 25 55.96 25 59.10 24 73.12 giul_08 36 34.9 34 226.85 35 113.85 34 125.20 36 134.25 34 181.70 piro40_02 17 17 17 55.51 17 10.67 17 12.58 17 15.20 17 18.50 piro40_04 28 28 28 118.50 28 34.98 28 38.00 28 43.05 28 54.44 piro40_06 46 46 46 208.81 46 61.98 46 68.00 46 84.33 46 109.15 piro40_08 60 60 60 338.61 60 105.97 60 119.35 60 140.20 60 181.52 USAnet_02 25 24.0 23 86.13 25 35.62 26 37.95 26 45.15 25 56.09 USAnet_04 47 45.9 45 355.64 47 130.43 45 147.76 48 176.43 45 228.50 USAnet_06 67 66.1 65 422.63 68 244.00 65 287.58 68 346.66 66 432.89 USAnet_08 88 86.5 85 490.20 88 475.69 85 544.98 89 587.11 86 791.38 Germany50_02 21 20.7 20 109.28 21 35.86 21 36.10 21 46.10 22 58.58 Germany50_04 45 44.2 43 350.24 45 152.90 44 163.00 48 217.60 48 276.50 Germany50_06 61 60.5 60 584.92 63 347.70 61 410.61 63 430.89 65 544.74 Germany50_08 76 74.7 73 921.59 77 552.50 75 725.90 79 843.70 76 1098.40 zib54_02 32 31.1 30 149.44 33 52.28 31 55.01 35 77.70 33 91.67 zib54_04 67 65.7 65 406.90 67 209.80 65 220.50 73 304.64 71 379.55 zib54_06 92 90.0 88 762.56 91 442.95 89 522.85 99 696.78 98 889.98 zib54_08 122 119.2 117 1446.41 117 994.60 117 939.60 130 1229.60 127 1457.22 ta2_02 35 34.6 34 411.59 35 148.93 34 163.00 35 188.75 35 250.99 ta2_04 72 70.1 69 945.79 72 507.30 69 542.50 73 635.57 70 813.04 ta2_06 99 97.4 96 1865.20 98 1311.70 98 1484.00 100 1881.30 97 2047.40 ta2_08 131 129.7 128 2835.57 130 1935.30 129 2577.90 135 2644.43 128 3713.46
Results of GMR and PSO (time unit: sec)
 GA_MEDP_RWA PSO instance max avg min avg time max avg min avg time CHNNET_02 4 4.0 4 2.07 7 5.9 5 12.97 CHNNET_04 5 4.4 4 3.02 9 7.5 7 18.60 CHNNET_06 11 11.0 11 10.66 18 15.5 13 30.39 CHNNET_08 14 14.0 14 13.50 24 20.4 18 48.95 CHNNET_1 16 15.0 15 16.31 25 21.5 18 78.96 NSF_02 5 5.0 5 2.41 7 6.0 5 6.75 NSF_04 8 7.3 7 5.80 10 9.0 8 13.75 NSF_06 9 8.8 8 7.97 11 10.0 9 16.19 NSF_08 14 13.2 13 15.11 17 15.5 14 29.02 NSF_1 17 16.6 16 22.89 20 18.9 18 36.03 NewYork_02 2 2.0 2 1.37 3 2.9 2 7.37 NewYork _04 3 3.0 3 2.65 6 5.2 4 18.78 NewYork _06 5 4.1 4 3.93 8 6.8 6 25.51 NewYork _08 7 6.0 6 6.75 10 9.1 8 38.35 NewYork _1 8 8.0 8 7.03 12 10.7 10 50.17 ARPANET_02 10 9.1 9 10.58 13 11.3 10 21.30 ARPANET_04 13 12.1 12 16.96 19 16.3 14 62.15 ARPANET_06 21 21.0 21 25.98 28 24.9 22 93.86 ARPANET_08 29 29.0 29 32.31 40 36.5 33 133.70 ARPANET_1 33 33.0 33 62.85 46 41.2 36 172.60 EON_02 4 3.1 3 3.19 5 4.3 4 10.40 EON_04 9 8.3 8 14.74 12 10.6 10 35.34 EON_06 11 11.0 11 17.52 15 13.0 12 46.61 EON_08 14 13.7 13 26.63 20 18.2 17 48.92 EON_1 19 18.1 18 38.17 25 22.9 22 73.32 France_02 8 8.0 8 8.87 14 11.5 10 50.60 France _04 13 12.8 12 16.05 22 19.3 17 86.48 France _06 22 22.0 22 39.07 34 30.4 27 129.16 France _08 27 26.3 26 47.09 45 40.3 38 290.72 France _1 34 34.0 34 60.09 54 48.9 45 236.64
 GA_MEDP_RWA PSO instance max avg min avg time max avg min avg time CHNNET_02 4 4.0 4 2.07 7 5.9 5 12.97 CHNNET_04 5 4.4 4 3.02 9 7.5 7 18.60 CHNNET_06 11 11.0 11 10.66 18 15.5 13 30.39 CHNNET_08 14 14.0 14 13.50 24 20.4 18 48.95 CHNNET_1 16 15.0 15 16.31 25 21.5 18 78.96 NSF_02 5 5.0 5 2.41 7 6.0 5 6.75 NSF_04 8 7.3 7 5.80 10 9.0 8 13.75 NSF_06 9 8.8 8 7.97 11 10.0 9 16.19 NSF_08 14 13.2 13 15.11 17 15.5 14 29.02 NSF_1 17 16.6 16 22.89 20 18.9 18 36.03 NewYork_02 2 2.0 2 1.37 3 2.9 2 7.37 NewYork _04 3 3.0 3 2.65 6 5.2 4 18.78 NewYork _06 5 4.1 4 3.93 8 6.8 6 25.51 NewYork _08 7 6.0 6 6.75 10 9.1 8 38.35 NewYork _1 8 8.0 8 7.03 12 10.7 10 50.17 ARPANET_02 10 9.1 9 10.58 13 11.3 10 21.30 ARPANET_04 13 12.1 12 16.96 19 16.3 14 62.15 ARPANET_06 21 21.0 21 25.98 28 24.9 22 93.86 ARPANET_08 29 29.0 29 32.31 40 36.5 33 133.70 ARPANET_1 33 33.0 33 62.85 46 41.2 36 172.60 EON_02 4 3.1 3 3.19 5 4.3 4 10.40 EON_04 9 8.3 8 14.74 12 10.6 10 35.34 EON_06 11 11.0 11 17.52 15 13.0 12 46.61 EON_08 14 13.7 13 26.63 20 18.2 17 48.92 EON_1 19 18.1 18 38.17 25 22.9 22 73.32 France_02 8 8.0 8 8.87 14 11.5 10 50.60 France _04 13 12.8 12 16.05 22 19.3 17 86.48 France _06 22 22.0 22 39.07 34 30.4 27 129.16 France _08 27 26.3 26 47.09 45 40.3 38 290.72 France _1 34 34.0 34 60.09 54 48.9 45 236.64
Results of GMR and PSO (con't)
 GA_MEDP_RWA PSO instance max avg min avg time max avg min avg time Norway_02 9 8.6 8 9.26 15 13.1 11 61.56 Norway _04 15 14.6 14 18.47 25 22.5 20 101.40 Norway _06 22 21.4 21 32.84 37 32.6 29 202.11 Norway _08 30 29.5 29 46.41 48 43.6 40 254.75 Norway _1 37 36.6 36 63.77 59 54.1 49 323.64 cost266_02 19 18.2 18 46.68 26 23.8 21 105.22 cost266_04 35 34.1 33 159.69 54 50.9 47 239.95 cost266_06 54 53.1 53 237.55 79 73.2 70 436.38 cost266_08 68 67.2 67 275.29 99 93.4 88 703.53 janos-us-ca_02 26 26.0 26 54.75 40 36.1 31 288.18 janos-us-ca_04 40 39.6 39 97.42 66 60.5 56 529.74 janos-us-ca_06 68 67.8 67 210.36 111 102.7 94 959.93 janos-us-ca_08 89 88.2 88 326.39 144 134.1 122 1239.46 giul_02 11 10.3 10 26.93 16 14.5 13 294.44 giul_04 21 20.2 19 82.66 32 28.8 26 451.61 giul_06 25 24.6 24 150.73 42 38.3 34 738.65 giul_08 36 34.9 34 226.85 59 53.5 49 990.63 piro40_02 17 17 17 55.51 22 20.0 19 159.88 piro40_04 28 28 28 118.50 36 33.7 32 300.88 piro40_06 46 46 46 208.81 66 58.7 52 474.73 piro40_08 60 60 60 338.61 86 79.4 73 684.40 USAnet_02 25 24.0 23 86.13 40 36.4 32 446.56 USAnet_04 47 45.9 45 355.64 76 69.5 65 983.93 USAnet_06 67 66.1 65 422.63 106 98.1 92 1418.73 USAnet_08 88 86.5 85 490.20 139 126.5 120 1715.20 Germany50_02 21 20.7 20 109.28 37 33.5 31 379.56 Germany50_04 45 44.2 43 350.24 74 69.4 66 683.95 Germany50_06 61 60.5 60 584.92 102 95.7 91 969.87 Germany50_08 76 74.7 73 921.59 126 120.5 115 1271.90 zib54_02 32 31.1 30 149.44 75 64.1 58 619.63 zib54_04 67 65.7 65 406.90 159 141.6 133 1462.19 zib54_06 92 90.0 88 762.56 208 195.2 187 2955.29 zib54_08 122 119.2 117 1446.41 289 266.3 250 4147.09 ta2_02 35 34.6 34 411.59 75 70.3 66 1453.68 ta2_04 72 70.1 69 945.79 152 141.8 133 2852.21 ta2_06 99 97.4 96 1865.20 208 198.7 181 3867.39 ta2_08 131 129.7 128 2835.57 284 271.0 258 5953.52
 GA_MEDP_RWA PSO instance max avg min avg time max avg min avg time Norway_02 9 8.6 8 9.26 15 13.1 11 61.56 Norway _04 15 14.6 14 18.47 25 22.5 20 101.40 Norway _06 22 21.4 21 32.84 37 32.6 29 202.11 Norway _08 30 29.5 29 46.41 48 43.6 40 254.75 Norway _1 37 36.6 36 63.77 59 54.1 49 323.64 cost266_02 19 18.2 18 46.68 26 23.8 21 105.22 cost266_04 35 34.1 33 159.69 54 50.9 47 239.95 cost266_06 54 53.1 53 237.55 79 73.2 70 436.38 cost266_08 68 67.2 67 275.29 99 93.4 88 703.53 janos-us-ca_02 26 26.0 26 54.75 40 36.1 31 288.18 janos-us-ca_04 40 39.6 39 97.42 66 60.5 56 529.74 janos-us-ca_06 68 67.8 67 210.36 111 102.7 94 959.93 janos-us-ca_08 89 88.2 88 326.39 144 134.1 122 1239.46 giul_02 11 10.3 10 26.93 16 14.5 13 294.44 giul_04 21 20.2 19 82.66 32 28.8 26 451.61 giul_06 25 24.6 24 150.73 42 38.3 34 738.65 giul_08 36 34.9 34 226.85 59 53.5 49 990.63 piro40_02 17 17 17 55.51 22 20.0 19 159.88 piro40_04 28 28 28 118.50 36 33.7 32 300.88 piro40_06 46 46 46 208.81 66 58.7 52 474.73 piro40_08 60 60 60 338.61 86 79.4 73 684.40 USAnet_02 25 24.0 23 86.13 40 36.4 32 446.56 USAnet_04 47 45.9 45 355.64 76 69.5 65 983.93 USAnet_06 67 66.1 65 422.63 106 98.1 92 1418.73 USAnet_08 88 86.5 85 490.20 139 126.5 120 1715.20 Germany50_02 21 20.7 20 109.28 37 33.5 31 379.56 Germany50_04 45 44.2 43 350.24 74 69.4 66 683.95 Germany50_06 61 60.5 60 584.92 102 95.7 91 969.87 Germany50_08 76 74.7 73 921.59 126 120.5 115 1271.90 zib54_02 32 31.1 30 149.44 75 64.1 58 619.63 zib54_04 67 65.7 65 406.90 159 141.6 133 1462.19 zib54_06 92 90.0 88 762.56 208 195.2 187 2955.29 zib54_08 122 119.2 117 1446.41 289 266.3 250 4147.09 ta2_02 35 34.6 34 411.59 75 70.3 66 1453.68 ta2_04 72 70.1 69 945.79 152 141.8 133 2852.21 ta2_06 99 97.4 96 1865.20 208 198.7 181 3867.39 ta2_08 131 129.7 128 2835.57 284 271.0 258 5953.52
 [1] Bettina Klaus, Frédéric Payot. Paths to stability in the assignment problem. Journal of Dynamics & Games, 2015, 2 (3&4) : 257-287. doi: 10.3934/jdg.2015004 [2] Delia Ionescu-Kruse. Short-wavelength instabilities of edge waves in stratified water. Discrete & Continuous Dynamical Systems - A, 2015, 35 (5) : 2053-2066. doi: 10.3934/dcds.2015.35.2053 [3] Nurhadi Siswanto, Stefanus Eko Wiratno, Ahmad Rusdiansyah, Ruhul Sarker. Maritime inventory routing problem with multiple time windows. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1185-1211. doi: 10.3934/jimo.2018091 [4] Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240 [5] Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial & Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87 [6] Xuefeng Wang. The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1147-1166. doi: 10.3934/dcdss.2019079 [7] Huai-Che Hong, Bertrand M. T. Lin. A note on network repair crew scheduling and routing for emergency relief distribution problem. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1729-1731. doi: 10.3934/jimo.2018119 [8] Ming Chen, Chongchao Huang. A power penalty method for the general traffic assignment problem with elastic demand. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1019-1030. doi: 10.3934/jimo.2014.10.1019 [9] R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using F-MSG algorithm. Journal of Industrial & Management Optimization, 2007, 3 (2) : 173-191. doi: 10.3934/jimo.2007.3.173 [10] Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial & Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211 [11] Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041 [12] Erfan Babaee Tirkolaee, Alireza Goli, Mani Bakhsi, Iraj Mahdavi. A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026 [13] Ahmed Tarajo Buba, Lai Soon Lee. Differential evolution with improved sub-route reversal repair mechanism for multiobjective urban transit routing problem. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 351-376. doi: 10.3934/naco.2018023 [14] Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749 [15] Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469 [16] Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435 [17] Omer Faruk Yilmaz, Mehmet Bulent Durmusoglu. A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007 [18] Gang Qian, Deren Han, Lingling Xu, Hai Yang. Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities. Journal of Industrial & Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255 [19] Qinglan Xia. On landscape functions associated with transport paths. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1683-1700. doi: 10.3934/dcds.2014.34.1683 [20] Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

2018 Impact Factor: 1.025