American Institute of Mathematical Sciences

Advanced
  • 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

Chia-Chun Hsu 1,, , Hsun-Jung Cho 1,2, and  Shu-Cherng Fang 1,2,

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.

Keywords: Edge-disjoint paths, MEDP, routing and wavelength assignment problem, RWA.
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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

J. Kleinberg, Approximation Algorithms for Disjoint Paths Problems, Ph. D thesis, Massachusetts Institute of Technology, 1996. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

R. Poli, J. Kennedy and T. Blackwell, Particle swarm optimization -An overview, Swarm intelligence, 1 (2007), 33-57.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

J. Kleinberg, Approximation Algorithms for Disjoint Paths Problems, Ph. D thesis, Massachusetts Institute of Technology, 1996. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

R. Poli, J. Kennedy and T. Blackwell, Particle swarm optimization -An overview, Swarm intelligence, 1 (2007), 33-57.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

Figure 1.  Pseudocode of FD(FFD) Algorithm
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Pseudocode of FD(FFD) Algorithm
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Pseudocode of PSO Algorithm
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Pseudocode of a basic MEDP-RWA algorithm
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Pseudocode of GMR algorithm
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Number of times that the best value is achieved by different methods
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Frequency graphs of testing results on zib54
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  Frequency graphs of testing results on ta2
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  Frequency graphs of testing results on Germany50
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 10.  Relative difference of computational time on Norway
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 11.  Relative difference of computational time on giul
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 12.  Relative difference of computational time on graph Germany
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 13.  Relative difference of computational time on graph ta2
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Main quantitative characteristics of testing networks
Graph$\left | V \right |$$\left | E \right |$Min.Avg.Max.Diameter
CHNNET152733.655
NSF162523.144
New York164926.1113
APPANET203233.246
EON203923.975
France254523.6105
Norway275123.867
cost266375723.158
janos-us-ca396723.1510
giul398634.486
piro40408944.557
USAnet467523.3511
Germany50508823.559
zib54548013.0108
ta26510813.3108
(Min., Avg. and Max. denote the minimum, average and maximum degree, respectively)
Table Options

Download as excel

Graph$\left | V \right |$$\left | E \right |$Min.Avg.Max.Diameter
CHNNET152733.655
NSF162523.144
New York164926.1113
APPANET203233.246
EON203923.975
France254523.6105
Norway275123.867
cost266375723.158
janos-us-ca396723.1510
giul398634.486
piro40408944.557
USAnet467523.3511
Germany50508823.559
zib54548013.0108
ta26510813.3108
(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)FFFFDBFBFD
instancemaxavgminavg time# wl$t_{FF}$# wl$t_{FFD}$# wl$t_{BF}$# wl$t_{BFD}$
CHNNET_0244.042.0740.2440.1440.1150.14
CHNNET_0454.443.0250.1840.1550.2340.26
CHNNET_061111.01110.66110.70110.62110.81110.96
CHNNET_081414.01413.50151.02141.17141.21141.51
CHNNET_11615.01516.31151.48151.42161.75152.20
NSF_0255.052.4160.3450.1760.1960.18
NSF_0487.375.8090.3790.3580.5280.50
NSF_0698.887.97100.46100.4990.5990.64
NSF_081413.21315.11171.06151.10141.50141.47
NSF_11716.61622.89191.70171.45171.96172.08
NewYork_0222.021.3720.1420.0820.0720.08
NewYork_0433.032.6530.2330.2030.2330.23
NewYork_0654.143.9340.3340.3440.3440.33
NewYork_0876.066.7570.6460.5870.6260.81
NewYork_188.087.0380.7380.8081.0282.30
ARPANET_02109.1910.5890.5590.5390.6490.86
ARPANET_041312.11216.96121.05121.29121.31121.76
ARPANET_062121.02125.98212.70212.68213.39214.58
ARPANET_082929.02932.31305.46296.14307.822910.94
ARPANET_13333.03362.85346.85337.773410.193312.68
EON_0243.133.1930.2240.1740.3440.36
EON_0498.3814.74101.1091.1481.5381.54
EON_061111.01117.52131.21111.18111.94111.90
EON_081413.71326.63162.20132.99133.61133.72
EON_11918.11838.17223.64183.58185.77185.73
France_0288.088.8781.3081.2781.5781.72
France _041312.81216.05144.29134.90135.14136.03
France _062222.02239.07228.732210.552211.692215.27
France _082726.32647.092813.252714.002718.532624.20
France _13434.03460.093422.543423.993429.933435.84
Table Options

Download as excel

GA_MEDP_RWA (GMR)FFFFDBFBFD
instancemaxavgminavg time# wl$t_{FF}$# wl$t_{FFD}$# wl$t_{BF}$# wl$t_{BFD}$
CHNNET_0244.042.0740.2440.1440.1150.14
CHNNET_0454.443.0250.1840.1550.2340.26
CHNNET_061111.01110.66110.70110.62110.81110.96
CHNNET_081414.01413.50151.02141.17141.21141.51
CHNNET_11615.01516.31151.48151.42161.75152.20
NSF_0255.052.4160.3450.1760.1960.18
NSF_0487.375.8090.3790.3580.5280.50
NSF_0698.887.97100.46100.4990.5990.64
NSF_081413.21315.11171.06151.10141.50141.47
NSF_11716.61622.89191.70171.45171.96172.08
NewYork_0222.021.3720.1420.0820.0720.08
NewYork_0433.032.6530.2330.2030.2330.23
NewYork_0654.143.9340.3340.3440.3440.33
NewYork_0876.066.7570.6460.5870.6260.81
NewYork_188.087.0380.7380.8081.0282.30
ARPANET_02109.1910.5890.5590.5390.6490.86
ARPANET_041312.11216.96121.05121.29121.31121.76
ARPANET_062121.02125.98212.70212.68213.39214.58
ARPANET_082929.02932.31305.46296.14307.822910.94
ARPANET_13333.03362.85346.85337.773410.193312.68
EON_0243.133.1930.2240.1740.3440.36
EON_0498.3814.74101.1091.1481.5381.54
EON_061111.01117.52131.21111.18111.94111.90
EON_081413.71326.63162.20132.99133.61133.72
EON_11918.11838.17223.64183.58185.77185.73
France_0288.088.8781.3081.2781.5781.72
France _041312.81216.05144.29134.90135.14136.03
France _062222.02239.07228.732210.552211.692215.27
France _082726.32647.092813.252714.002718.532624.20
France _13434.03460.093422.543423.993429.933435.84
Table 3.  Results of GMR and bin-packing based methods (cont'd)
GA_MEDP_RWA (GMR)FFFFDBFBFD
instancemaxavgminavg time# wl$t_{FF}$# wl$t_{FFD}$# wl$t_{BF}$# wl$t_{BFD}$
Norway_0298.689.26101.6781.7891.9082.17
Norway _041514.61418.47153.75154.12154.56155.43
Norway _062221.42132.84227.87228.20229.732212.32
Norway _083029.52946.413115.053016.593119.793024.59
Norway _13736.63663.773721.993623.753828.583636.13
cost266_021918.21846.68197.34187.441910.381912.40
cost266_043534.133159.693527.283328.583636.353547.28
cost266_065453.153237.555467.185370.905598.0053117.30
cost266_086867.267275.2967120.7368144.2269190.5568273.40
janos-us-ca_022626.02654.752716.612616.532727.402727.58
janos-us-ca_044039.63997.424249.523959.494370.754088.45
janos-us-ca_066867.867210.3671110.9969124.1072157.5068200.32
janos-us-ca_088988.288326.3992199.0992212.1693257.3991345.67
giul_021110.31026.93107.40108.11108.891011.24
giul_042120.21982.661929.101931.701937.421946.16
giul_062524.624150.732548.912555.962559.102473.12
giul_083634.934226.8535113.8534125.2036134.2534181.70
piro40_0217171755.511710.671712.581715.201718.50
piro40_04282828118.502834.982838.002843.052854.44
piro40_06464646208.814661.984668.004684.3346109.15
piro40_08606060338.6160105.9760119.3560140.2060181.52
USAnet_022524.02386.132535.622637.952645.152556.09
USAnet_044745.945355.6447130.4345147.7648176.4345228.50
USAnet_066766.165422.6368244.0065287.5868346.6666432.89
USAnet_088886.585490.2088475.6985544.9889587.1186791.38
Germany50_022120.720109.282135.862136.102146.102258.58
Germany50_044544.243350.2445152.9044163.0048217.6048276.50
Germany50_066160.560584.9263347.7061410.6163430.8965544.74
Germany50_087674.773921.5977552.5075725.9079843.70761098.40
zib54_023231.130149.443352.283155.013577.703391.67
zib54_046765.765406.9067209.8065220.5073304.6471379.55
zib54_069290.088762.5691442.9589522.8599696.7898889.98
zib54_08122119.21171446.41117994.60117939.601301229.601271457.22
ta2_023534.634411.5935148.9334163.0035188.7535250.99
ta2_047270.169945.7972507.3069542.5073635.5770813.04
ta2_069997.4961865.20981311.70981484.001001881.30972047.40
ta2_08131129.71282835.571301935.301292577.901352644.431283713.46
Table Options

Download as excel

GA_MEDP_RWA (GMR)FFFFDBFBFD
instancemaxavgminavg time# wl$t_{FF}$# wl$t_{FFD}$# wl$t_{BF}$# wl$t_{BFD}$
Norway_0298.689.26101.6781.7891.9082.17
Norway _041514.61418.47153.75154.12154.56155.43
Norway _062221.42132.84227.87228.20229.732212.32
Norway _083029.52946.413115.053016.593119.793024.59
Norway _13736.63663.773721.993623.753828.583636.13
cost266_021918.21846.68197.34187.441910.381912.40
cost266_043534.133159.693527.283328.583636.353547.28
cost266_065453.153237.555467.185370.905598.0053117.30
cost266_086867.267275.2967120.7368144.2269190.5568273.40
janos-us-ca_022626.02654.752716.612616.532727.402727.58
janos-us-ca_044039.63997.424249.523959.494370.754088.45
janos-us-ca_066867.867210.3671110.9969124.1072157.5068200.32
janos-us-ca_088988.288326.3992199.0992212.1693257.3991345.67
giul_021110.31026.93107.40108.11108.891011.24
giul_042120.21982.661929.101931.701937.421946.16
giul_062524.624150.732548.912555.962559.102473.12
giul_083634.934226.8535113.8534125.2036134.2534181.70
piro40_0217171755.511710.671712.581715.201718.50
piro40_04282828118.502834.982838.002843.052854.44
piro40_06464646208.814661.984668.004684.3346109.15
piro40_08606060338.6160105.9760119.3560140.2060181.52
USAnet_022524.02386.132535.622637.952645.152556.09
USAnet_044745.945355.6447130.4345147.7648176.4345228.50
USAnet_066766.165422.6368244.0065287.5868346.6666432.89
USAnet_088886.585490.2088475.6985544.9889587.1186791.38
Germany50_022120.720109.282135.862136.102146.102258.58
Germany50_044544.243350.2445152.9044163.0048217.6048276.50
Germany50_066160.560584.9263347.7061410.6163430.8965544.74
Germany50_087674.773921.5977552.5075725.9079843.70761098.40
zib54_023231.130149.443352.283155.013577.703391.67
zib54_046765.765406.9067209.8065220.5073304.6471379.55
zib54_069290.088762.5691442.9589522.8599696.7898889.98
zib54_08122119.21171446.41117994.60117939.601301229.601271457.22
ta2_023534.634411.5935148.9334163.0035188.7535250.99
ta2_047270.169945.7972507.3069542.5073635.5770813.04
ta2_069997.4961865.20981311.70981484.001001881.30972047.40
ta2_08131129.71282835.571301935.301292577.901352644.431283713.46
Table 4.  Results of GMR and PSO (time unit: sec)
GA_MEDP_RWAPSO
instancemaxavgminavg timemaxavgminavg time
CHNNET_0244.042.0775.9512.97
CHNNET_0454.443.0297.5718.60
CHNNET_061111.01110.661815.51330.39
CHNNET_081414.01413.502420.41848.95
CHNNET_11615.01516.312521.51878.96
NSF_0255.052.4176.056.75
NSF_0487.375.80109.0813.75
NSF_0698.887.971110.0916.19
NSF_081413.21315.111715.51429.02
NSF_11716.61622.892018.91836.03
NewYork_0222.021.3732.927.37
NewYork _0433.032.6565.2418.78
NewYork _0654.143.9386.8625.51
NewYork _0876.066.75109.1838.35
NewYork _188.087.031210.71050.17
ARPANET_02109.1910.581311.31021.30
ARPANET_041312.11216.961916.31462.15
ARPANET_062121.02125.982824.92293.86
ARPANET_082929.02932.314036.533133.70
ARPANET_13333.03362.854641.236172.60
EON_0243.133.1954.3410.40
EON_0498.3814.741210.61035.34
EON_061111.01117.521513.01246.61
EON_081413.71326.632018.21748.92
EON_11918.11838.172522.92273.32
France_0288.088.871411.51050.60
France _041312.81216.052219.31786.48
France _062222.02239.073430.427129.16
France _082726.32647.094540.338290.72
France _13434.03460.095448.945236.64
Table Options

Download as excel

GA_MEDP_RWAPSO
instancemaxavgminavg timemaxavgminavg time
CHNNET_0244.042.0775.9512.97
CHNNET_0454.443.0297.5718.60
CHNNET_061111.01110.661815.51330.39
CHNNET_081414.01413.502420.41848.95
CHNNET_11615.01516.312521.51878.96
NSF_0255.052.4176.056.75
NSF_0487.375.80109.0813.75
NSF_0698.887.971110.0916.19
NSF_081413.21315.111715.51429.02
NSF_11716.61622.892018.91836.03
NewYork_0222.021.3732.927.37
NewYork _0433.032.6565.2418.78
NewYork _0654.143.9386.8625.51
NewYork _0876.066.75109.1838.35
NewYork _188.087.031210.71050.17
ARPANET_02109.1910.581311.31021.30
ARPANET_041312.11216.961916.31462.15
ARPANET_062121.02125.982824.92293.86
ARPANET_082929.02932.314036.533133.70
ARPANET_13333.03362.854641.236172.60
EON_0243.133.1954.3410.40
EON_0498.3814.741210.61035.34
EON_061111.01117.521513.01246.61
EON_081413.71326.632018.21748.92
EON_11918.11838.172522.92273.32
France_0288.088.871411.51050.60
France _041312.81216.052219.31786.48
France _062222.02239.073430.427129.16
France _082726.32647.094540.338290.72
France _13434.03460.095448.945236.64
Table 5.  Results of GMR and PSO (con't)
GA_MEDP_RWAPSO
instancemaxavgminavg timemaxavgminavg time
Norway_0298.689.261513.11161.56
Norway _041514.61418.472522.520101.40
Norway _062221.42132.843732.629202.11
Norway _083029.52946.414843.640254.75
Norway _13736.63663.775954.149323.64
cost266_021918.21846.682623.821105.22
cost266_043534.133159.695450.947239.95
cost266_065453.153237.557973.270436.38
cost266_086867.267275.299993.488703.53
janos-us-ca_022626.02654.754036.131288.18
janos-us-ca_044039.63997.426660.556529.74
janos-us-ca_066867.867210.36111102.794959.93
janos-us-ca_088988.288326.39144134.11221239.46
giul_021110.31026.931614.513294.44
giul_042120.21982.663228.826451.61
giul_062524.624150.734238.334738.65
giul_083634.934226.855953.549990.63
piro40_0217171755.512220.019159.88
piro40_04282828118.503633.732300.88
piro40_06464646208.816658.752474.73
piro40_08606060338.618679.473684.40
USAnet_022524.02386.134036.432446.56
USAnet_044745.945355.647669.565983.93
USAnet_066766.165422.6310698.1921418.73
USAnet_088886.585490.20139126.51201715.20
Germany50_022120.720109.283733.531379.56
Germany50_044544.243350.247469.466683.95
Germany50_066160.560584.9210295.791969.87
Germany50_087674.773921.59126120.51151271.90
zib54_023231.130149.447564.158619.63
zib54_046765.765406.90159141.61331462.19
zib54_069290.088762.56208195.21872955.29
zib54_08122119.21171446.41289266.32504147.09
ta2_023534.634411.597570.3661453.68
ta2_047270.169945.79152141.81332852.21
ta2_069997.4961865.20208198.71813867.39
ta2_08131129.71282835.57284271.02585953.52
Table Options

Download as excel

GA_MEDP_RWAPSO
instancemaxavgminavg timemaxavgminavg time
Norway_0298.689.261513.11161.56
Norway _041514.61418.472522.520101.40
Norway _062221.42132.843732.629202.11
Norway _083029.52946.414843.640254.75
Norway _13736.63663.775954.149323.64
cost266_021918.21846.682623.821105.22
cost266_043534.133159.695450.947239.95
cost266_065453.153237.557973.270436.38
cost266_086867.267275.299993.488703.53
janos-us-ca_022626.02654.754036.131288.18
janos-us-ca_044039.63997.426660.556529.74
janos-us-ca_066867.867210.36111102.794959.93
janos-us-ca_088988.288326.39144134.11221239.46
giul_021110.31026.931614.513294.44
giul_042120.21982.663228.826451.61
giul_062524.624150.734238.334738.65
giul_083634.934226.855953.549990.63
piro40_0217171755.512220.019159.88
piro40_04282828118.503633.732300.88
piro40_06464646208.816658.752474.73
piro40_08606060338.618679.473684.40
USAnet_022524.02386.134036.432446.56
USAnet_044745.945355.647669.565983.93
USAnet_066766.165422.6310698.1921418.73
USAnet_088886.585490.20139126.51201715.20
Germany50_022120.720109.283733.531379.56
Germany50_044544.243350.247469.466683.95
Germany50_066160.560584.9210295.791969.87
Germany50_087674.773921.59126120.51151271.90
zib54_023231.130149.447564.158619.63
zib54_046765.765406.90159141.61331462.19
zib54_069290.088762.56208195.21872955.29
zib54_08122119.21171446.41289266.32504147.09
ta2_023534.634411.597570.3661453.68
ta2_047270.169945.79152141.81332852.21
ta2_069997.4961865.20208198.71813867.39
ta2_08131129.71282835.57284271.02585953.52
[1]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037
[2]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002
[3]

Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edge-dislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361-387. doi: 10.3934/jgm.2015.7.361
[4]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[5]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[6]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[7]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[8]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[9]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[10]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[11]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[12]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1757-1778. doi: 10.3934/dcdss.2020453
[13]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis of a thermal frictional contact problem with long memory. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021031
[14]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090
[15]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[16]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[17]

Kuan-Hsiang Wang. An eigenvalue problem for nonlinear Schrödinger-Poisson system with steep potential well. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021030
[18]

Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (172)
  • HTML views (403)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences