Figure 1.
Pseudocode of FD(FFD) Algorithm
-
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 |
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.
Mathematics Subject Classification:
Primary: 58F15, 58F17; Secondary: 53C35.
Citation:
Chia-Chun Hsu, Hsun-Jung Cho, Shu-Cherng Fang. Solving routing and wavelength assignment problem with maximum edge-disjoint paths. Journal of Industrial and Management Optimization,
2017, 13
(2)
: 1065-1084.
doi: 10.3934/jimo.2016062
![]()
References:
| [1] |
D. Banerjee and B. Mukherjee,
A practical approach for routing and wavelength assignment in large wavelength-routed optical networks, IEEE Journal on Selected Areas in Communications, 14 (1996), 903-908.
doi: 10.1109/49.510913. |
| [2] |
M. J. Blesa and C. Blum,
Findinge edge-disjoint paths in networks: An ant colony optimization algorithm, Journal of Mathematical Modeling and Algorithms, 6 (2007), 367-391.
doi: 10.1007/s10852-007-9060-y. |
| [3] |
I. Chlamtac, A. Ganz and G. Karmi,
Lightpath communications: an approach to high bandwidth optical WAN's, IEEE Transactions on Communications, 40 (1992), 1171-1182.
doi: 10.1109/26.153361. |
| [4] |
J. S. Choi, N. Golmie, F. Lapeyrere, F. Mouveaux and D. Su, A functional classification of routing and wavelength assignment schemes in DWDM networks: Static Case, In Proceedings of the 7th International Conference on Optical Communications and Networks, (2000), 1109-1115. |
| [5] |
H. Choo and V. V. Shakhov,
Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths, Computational Science -ICCS 2004, 3038 (2004), 1138-1145.
doi: 10.1007/978-3-540-24688-6_147. |
| [6] |
T. Fischer, K. Bauer, P. Merz and K. Bauer,
Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm, Memetic Computing, 1 (2009), 101-123.
doi: 10.1007/s12293-008-0006-3. |
| [7] |
X. Guan, S. Guo, W. Gong and C. Qiao,
A new method for solving routing and wavelength assignment problems in optical networks, Journal of Lightwave Technology, 25 (2007), 1895-1909.
doi: 10.1109/JLT.2007.901344. |
| [8] |
A. Hassan, Particle Swarm Optimization for Routing and Wavelength Assignment in Next Generation WDM Networks, Ph. D thesis, Queen Mary University of London, 2010. |
| [9] |
C.-C. Hsu and H.-J. Cho,
A genetic algorithm for the maximum edge-disjoint paths problem, Neurocomputing, 148 (2015), 17-22.
doi: 10.1016/j.neucom.2012.10.046. |
| [10] |
C.-C. Hsu, H.-J. Cho and S.-C. Fang,
Routing and wavelength assignment in optical networks from maximum edge-disjoint paths, Genetic and Evolutionary Computing: Advances in Intelligent Systems and Computing, 238 (2014), 95-103.
doi: 10.1007/978-3-319-01796-9_10. |
| [11] |
Y. S. Kavian, A. Rashedi, A. Mahani and Z. Ghassemlooy,
Routing and wavelength assignment in optical networks using artificial bee colony algorithm, European Journal of Operational Research, 124 (2013), 1243-1249.
doi: 10.1016/j.ijleo.2012.03.022. |
| [12] |
J. Kleinberg, Approximation Algorithms for Disjoint Paths Problems, Ph. D thesis, Massachusetts Institute of Technology, 1996. |
| [13] |
P. Leesutthipornchai, C. Charnsripinyo and N. Wattanapongsakorn,
Solving multi-objective routing and wavelength assignment in WDM network using hybrid evolutionary computation approach, Computer Communications, 33 (2010), 2246-2259.
doi: 10.1016/j.comcom.2010.07.029. |
| [14] |
G. Li and R. Shmha, The partition coloring problem and its application to wavelength routing and assignment, In Proceedings of the First Workshop on Optical Networks, 2000. |
| [15] |
P. Manohar, D. Manjunath and R. K. Shevgaonkar,
Routing and wavelength assignment in optical networks from edge disjoint path algorithms, IEEE Communications Letters, 6 (2002), 211-213.
doi: 10.1109/4234.1001667. |
| [16] |
A. X. Martins, C. Duhamel, P. Mahey, R. R. Saldanha and M. C. de Souza,
Variable neighborhood descent with iterated local search for routing and wavelength assignment, Computers and Operations Research, 39 (2012), 2133-2141.
doi: 10.1016/j.cor.2011.10.022. |
| [17] |
T. F. Noronha, M. G. C. Resende and C. C. Ribeiro,
A biased random-key genetic algorithm for routing and wavelength assignment, Journal of Global Optimization, 50 (2011), 503-518.
doi: 10.1007/s10898-010-9608-7. |
| [18] |
T. F. Noronha and C. C. Ribeiro,
Routing and wavelength assignment by partition colouring, European Journal of Operational Research, 171 (2006), 797-810.
doi: 10.1016/j.ejor.2004.09.007. |
| [19] |
A. E. Ozdaglar and D. P. Bertsekas,
Routing and wavelength assignment in optical networks, IEEE/ACM Transactions on Networking, 11 (2003), 259-272.
doi: 10.1109/TNET.2003.810321. |
| [20] |
R. Poli, J. Kennedy and T. Blackwell,
Particle swarm optimization -An overview, Swarm intelligence, 1 (2007), 33-57.
|
| [21] |
N. Skorin-Kapov,
Routing and wavelength assignment in optical networks using bin packing based algorithms, European Journal of Operational Research, 177 (2007), 1167-1179.
doi: 10.1016/j.ejor.2006.01.003. |
| [22] |
Y. Wang, T. H. Cheng and M. H. Lim,
A Tabu search algorithm for static routing and wavelength assignment problem, IEEE Communications Letters, 9 (2005), 841-843.
doi: 10.1109/LCOMM.2005.1506721. |
| [23] |
W. J. Yoon, D. H. Kim, M. Y. Chung, T. J. Lee and H. Choo,
Routing with maximum EDPs and wavelength assignment with path conflict graphs, In Proceedings of the 2006 international conference on Computational Science and Its Applications, 3981 (2006), 856-865.
doi: 10.1007/11751588_89. |
| [24] |
H. Zang, J. P. Jue and B. Mukherjee,
A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks, Optical Networks Magazine, 1 (2000), 47-60.
|
show all references
References:
| [1] |
D. Banerjee and B. Mukherjee,
A practical approach for routing and wavelength assignment in large wavelength-routed optical networks, IEEE Journal on Selected Areas in Communications, 14 (1996), 903-908.
doi: 10.1109/49.510913. |
| [2] |
M. J. Blesa and C. Blum,
Findinge edge-disjoint paths in networks: An ant colony optimization algorithm, Journal of Mathematical Modeling and Algorithms, 6 (2007), 367-391.
doi: 10.1007/s10852-007-9060-y. |
| [3] |
I. Chlamtac, A. Ganz and G. Karmi,
Lightpath communications: an approach to high bandwidth optical WAN's, IEEE Transactions on Communications, 40 (1992), 1171-1182.
doi: 10.1109/26.153361. |
| [4] |
J. S. Choi, N. Golmie, F. Lapeyrere, F. Mouveaux and D. Su, A functional classification of routing and wavelength assignment schemes in DWDM networks: Static Case, In Proceedings of the 7th International Conference on Optical Communications and Networks, (2000), 1109-1115. |
| [5] |
H. Choo and V. V. Shakhov,
Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths, Computational Science -ICCS 2004, 3038 (2004), 1138-1145.
doi: 10.1007/978-3-540-24688-6_147. |
| [6] |
T. Fischer, K. Bauer, P. Merz and K. Bauer,
Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm, Memetic Computing, 1 (2009), 101-123.
doi: 10.1007/s12293-008-0006-3. |
| [7] |
X. Guan, S. Guo, W. Gong and C. Qiao,
A new method for solving routing and wavelength assignment problems in optical networks, Journal of Lightwave Technology, 25 (2007), 1895-1909.
doi: 10.1109/JLT.2007.901344. |
| [8] |
A. Hassan, Particle Swarm Optimization for Routing and Wavelength Assignment in Next Generation WDM Networks, Ph. D thesis, Queen Mary University of London, 2010. |
| [9] |
C.-C. Hsu and H.-J. Cho,
A genetic algorithm for the maximum edge-disjoint paths problem, Neurocomputing, 148 (2015), 17-22.
doi: 10.1016/j.neucom.2012.10.046. |
| [10] |
C.-C. Hsu, H.-J. Cho and S.-C. Fang,
Routing and wavelength assignment in optical networks from maximum edge-disjoint paths, Genetic and Evolutionary Computing: Advances in Intelligent Systems and Computing, 238 (2014), 95-103.
doi: 10.1007/978-3-319-01796-9_10. |
| [11] |
Y. S. Kavian, A. Rashedi, A. Mahani and Z. Ghassemlooy,
Routing and wavelength assignment in optical networks using artificial bee colony algorithm, European Journal of Operational Research, 124 (2013), 1243-1249.
doi: 10.1016/j.ijleo.2012.03.022. |
| [12] |
J. Kleinberg, Approximation Algorithms for Disjoint Paths Problems, Ph. D thesis, Massachusetts Institute of Technology, 1996. |
| [13] |
P. Leesutthipornchai, C. Charnsripinyo and N. Wattanapongsakorn,
Solving multi-objective routing and wavelength assignment in WDM network using hybrid evolutionary computation approach, Computer Communications, 33 (2010), 2246-2259.
doi: 10.1016/j.comcom.2010.07.029. |
| [14] |
G. Li and R. Shmha, The partition coloring problem and its application to wavelength routing and assignment, In Proceedings of the First Workshop on Optical Networks, 2000. |
| [15] |
P. Manohar, D. Manjunath and R. K. Shevgaonkar,
Routing and wavelength assignment in optical networks from edge disjoint path algorithms, IEEE Communications Letters, 6 (2002), 211-213.
doi: 10.1109/4234.1001667. |
| [16] |
A. X. Martins, C. Duhamel, P. Mahey, R. R. Saldanha and M. C. de Souza,
Variable neighborhood descent with iterated local search for routing and wavelength assignment, Computers and Operations Research, 39 (2012), 2133-2141.
doi: 10.1016/j.cor.2011.10.022. |
| [17] |
T. F. Noronha, M. G. C. Resende and C. C. Ribeiro,
A biased random-key genetic algorithm for routing and wavelength assignment, Journal of Global Optimization, 50 (2011), 503-518.
doi: 10.1007/s10898-010-9608-7. |
| [18] |
T. F. Noronha and C. C. Ribeiro,
Routing and wavelength assignment by partition colouring, European Journal of Operational Research, 171 (2006), 797-810.
doi: 10.1016/j.ejor.2004.09.007. |
| [19] |
A. E. Ozdaglar and D. P. Bertsekas,
Routing and wavelength assignment in optical networks, IEEE/ACM Transactions on Networking, 11 (2003), 259-272.
doi: 10.1109/TNET.2003.810321. |
| [20] |
R. Poli, J. Kennedy and T. Blackwell,
Particle swarm optimization -An overview, Swarm intelligence, 1 (2007), 33-57.
|
| [21] |
N. Skorin-Kapov,
Routing and wavelength assignment in optical networks using bin packing based algorithms, European Journal of Operational Research, 177 (2007), 1167-1179.
doi: 10.1016/j.ejor.2006.01.003. |
| [22] |
Y. Wang, T. H. Cheng and M. H. Lim,
A Tabu search algorithm for static routing and wavelength assignment problem, IEEE Communications Letters, 9 (2005), 841-843.
doi: 10.1109/LCOMM.2005.1506721. |
| [23] |
W. J. Yoon, D. H. Kim, M. Y. Chung, T. J. Lee and H. Choo,
Routing with maximum EDPs and wavelength assignment with path conflict graphs, In Proceedings of the 2006 international conference on Computational Science and Its Applications, 3981 (2006), 856-865.
doi: 10.1007/11751588_89. |
| [24] |
H. Zang, J. P. Jue and B. Mukherjee,
A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks, Optical Networks Magazine, 1 (2000), 47-60.
|
Figure 2.
Pseudocode of FD(FFD) Algorithm
Figure 3.
Pseudocode of PSO Algorithm
Figure 4.
Pseudocode of a basic MEDP-RWA algorithm
Figure 5.
Pseudocode of GMR algorithm
Figure 6.
Number of times that the best value is achieved by different methods
Figure 7.
Frequency graphs of testing results on zib54
Figure 8.
Frequency graphs of testing results on ta2
Figure 9.
Frequency graphs of testing results on Germany50
Figure 10.
Relative difference of computational time on Norway
Figure 11.
Relative difference of computational time on giul
Figure 12.
Relative difference of computational time on graph Germany
Figure 13.
Relative difference of computational time on graph ta2
Table 1.
Main quantitative characteristics of testing networks
| Graph | 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 | 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) | ||||||
Table 2.
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 | # wl | # wl | # wl | ||||
| 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 | # wl | # wl | # wl | ||||
| 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 |
Table 3.
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 | # wl | # wl | # wl | ||||
| 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 | # wl | # wl | # wl | ||||
| 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 |
Table 4.
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 |
Table 5.
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 and 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 and Continuous Dynamical Systems, 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 and Management Optimization, 2019, 15 (3) : 1185-1211. doi: 10.3934/jimo.2018091 |
| [4] |
Christopher Garcia. The synchronized multi-assignment orienteering problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022018 |
| [5] |
Anh Son Ta, Le Thi Hoai An, Djamel Khadraoui, Pham Dinh Tao. Solving Partitioning-Hub Location-Routing Problem using DCA. Journal of Industrial and Management Optimization, 2012, 8 (1) : 87-102. doi: 10.3934/jimo.2012.8.87 |
| [6] |
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 |
| [7] |
Xuefeng Wang. The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1147-1166. doi: 10.3934/dcdss.2019079 |
| [8] |
Huai-Che Hong, Bertrand M. T. Lin. A note on network repair crew scheduling and routing for emergency relief distribution problem. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1729-1731. doi: 10.3934/jimo.2018119 |
| [9] |
Ming Chen, Chongchao Huang. A power penalty method for the general traffic assignment problem with elastic demand. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1019-1030. doi: 10.3934/jimo.2014.10.1019 |
| [10] |
Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial and Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041 |
| [11] |
R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using F-MSG algorithm. Journal of Industrial and Management Optimization, 2007, 3 (2) : 173-191. doi: 10.3934/jimo.2007.3.173 |
| [12] |
Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial and Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211 |
| [13] |
Tony Lyons. Particle paths in equatorial flows. Communications on Pure and Applied Analysis, 2022, 21 (7) : 2399-2414. doi: 10.3934/cpaa.2022041 |
| [14] |
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 and Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026 |
| [15] |
Ahmed Tarajo Buba, Lai Soon Lee. Differential evolution with improved sub-route reversal repair mechanism for multiobjective urban transit routing problem. Numerical Algebra, Control and Optimization, 2018, 8 (3) : 351-376. doi: 10.3934/naco.2018023 |
| [16] |
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 and Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749 |
| [17] |
Bariş Keçeci, Fulya Altıparmak, İmdat Kara. A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1069-1100. doi: 10.3934/jimo.2020012 |
| [18] |
Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial and Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469 |
| [19] |
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 and Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435 |
| [20] |
Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021197 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]