Figure 1.
The main steps of the TS-heuristics and SA-heuristics
-
Previous Article
Three-dimensional computer simulation of twill woven fabric by using polynomial mathematical model
- DCDS-S Home
- This Issue
-
Next Article
Efficient systolic multiplications in composite fields for cryptographic systems
August & September
2019, 12(4&5): 1147-1166.
doi: 10.3934/dcdss.2019079
The heterogeneous fleet location routing problem with simultaneous pickup and delivery and overloads
School of Business Administration, Jiangxi University of Finance and Economics, Nanchang 30013, China |
This paper addresses a new variant of the location routing problem (LRP), namely the heterogeneous fleet LRP with simultaneous pickup and delivery and overloads (HFLRPSPDO) which has not been previously tackled in literatures. In this problem, the heterogeneous fleet is comprised of vehicles with different capacities, and the vehicle overloads up to a specified upper bound is allowed. This paper proposes a polynomial-size mixed integer linear programming formulation for the problem in which a penalty function, allowing capacity violations of vehicles, is integrated into objective function. Furthermore, two heuristic algorithms, respectively based on tabu search and simulated annealing, are proposed to solve HFLRPSPDO. Computational results on simulated instances show the effectiveness of the proposed problem formulation and the efficiency of the proposed heuristic algorithms.
Keywords:
Heterogeneous fleet,
location-routing problem,
simultaneous pickup and delivery,
overloads.
Mathematics Subject Classification:
68U99.
Citation:
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
![]()
References:
| [1] |
D. Ambrosinoa,
Distribution network design: New problems and related models, European Journal of Operational Research, 165 (2005), 610-624.
doi: 10.1016/j.ejor.2003.04.009. |
| [2] |
R. T. Berger, C. R. Coullard and M. S. Daskin, Location-routing problems with distance constraints, Transportation Science, 41 (2007), 29-43. Google Scholar |
| [3] |
T. W. Chien, Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems, Decision Sciences, 24 (1993), 995-1021. Google Scholar |
| [4] |
C. H. Chu and J. Hopscotch,
Further discussion for transit system of chicago, Journal of Discrete Mathematical Sciences & Cryptography, 20 (2017), 717-724.
doi: 10.1080/09720529.2016.1197600. |
| [5] |
G. Clarke and J. W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12 (1964), 568-581. Google Scholar |
| [6] |
J. Dethloff,
Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR-Spektrum, 23 (2001), 79-96.
doi: 10.1007/PL00013346. |
| [7] |
J. Geunes and B. M. Chang, Operations Research Models for Supply Chain Management and Design, vol. 76, Springer US, 1994. Google Scholar |
| [8] |
B. Golden, A. Assad, L. Levy and F. Gheysens, The fleet size and mix vehicle routing problem, Computers & Operations Research, 11 (1984), 49-66. Google Scholar |
| [9] |
G. Ioannou, M. Kritikos and G. Prastacos, A greedy look-ahead heuristic for the vehicle routing problem with time windows, Journal of the Operational Research Society, 52 (2001), 523-537. Google Scholar |
| [10] |
H. Kamankesh and V. G. Agelidis, A sufficient stochastic framework for optimal operation of micro-grids considering high penetration of renewable energy sources and electric vehicles, Journal of Intelligent & Fuzzy Systems, 32 (2017), 373-387. Google Scholar |
| [11] |
I. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz,
A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery, European Journal of Operational Research, 211 (2011), 318-332.
doi: 10.1016/j.ejor.2011.01.003. |
| [12] |
I. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz, The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach, Omega, 40 (2012), 465-477. Google Scholar |
| [13] |
M. N. Kritikos and G. Ioannou, The heterogeneous fleet vehicle routing problem with overloads and time windows, International Journal of Production Economics, 144 (2013), 68-75. Google Scholar |
| [14] |
G. Laporte, Y. Nobert and D. Arpin, An exact algorithm for solving a capacitated location-routing problem, Annals of Operations Research, 6 (1986), 293-310. Google Scholar |
| [15] |
G. Laporte, Y. Nobert and S. Taillefer,
Solving a family of multi-depot vehicle routing and location-routing problems, Transportation Science, 22 (1988), 161-172.
doi: 10.1287/trsc.22.3.161. |
| [16] |
C. K. Y. Lin, C. K. Chow and A. Chen, A location-routing-loading problem for bill delivery services, Computers & Industrial Engineering, 43 (2002), 5-25. Google Scholar |
| [17] |
C. K. Y. Lin and R. C. W. Kwok, Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data, European Journal of Operational Research, 175 (2006), 1833-1849. Google Scholar |
| [18] |
M. Lundy and A. Mees,
Convergence of an annealing algorithm, Mathematical Programming, 34 (1986), 111-124.
doi: 10.1007/BF01582166. |
| [19] |
H. Min, Consolidation terminal location-allocation and consolidated routing problems, Journal of Business Logistics, 17 (1996), 235-263. Google Scholar |
| [20] |
H. Min, V. Jayaraman and R. Srivastava, Combined Location-Routing Problems: A Synthesis and Future Research Directions, vol. 108, Springer Berlin Heidelberg, 1998. Google Scholar |
| [21] |
G. Nagy and S. Salhi,
Location-routing: Issues, models and methods, European Journal of Operational Research, 177 (2007), 649-672.
doi: 10.1016/j.ejor.2006.04.004. |
| [22] |
G. Nagy and S. Salhi, Nested heuristic methods for the location-routing problem, 47 (1996), 1166-1174. Google Scholar |
| [23] |
C. Prodhon,, in http://prodhonc.free.fr/homepage, 2016. Google Scholar |
| [24] |
S. Salhi and M. Fraser, An integrated heuristic approach for the combined location vehicle fleet mix problem, Studies in Locational Analysis, 8 (1996), 3-21. Google Scholar |
| [25] |
S. Salhi and G. Nagy, A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the Operational Research Society, 50 (1999), 1034-1042. Google Scholar |
| [26] |
M. Schwardt and J. Dethloff, Solving a continuous location-routing problem by use of a self-organizing map, International Journal of Physical Distribution & Logistics Management, 35 (2005), 390-408. Google Scholar |
| [27] |
R. Srivastava, Alternate solution procedures for the location-routing problem, Omega, 21 (1993), 497-506. Google Scholar |
| [28] |
D. Tuzun and L. I. Burke, A two-phase tabu search approach to the location routing problem, European Journal of Operational Research, 116 (1999), 87-99. Google Scholar |
| [29] |
T. H. Wu, C. Low and J. W. Bai, Heuristic solutions to multi-depot location-routing problems, Computers & Operations Research, 29 (2002), 1393-1415. Google Scholar |
| [30] |
X. Zhang, Z. B. Zhang, H. Broersma and X. Wen,
On the complexity of edge-colored subgraph partitioning problems in network optimization, Discrete Mathematics & Theoretical Computer Science Dmtcs, 17 (2016), 227-244.
|
show all references
References:
| [1] |
D. Ambrosinoa,
Distribution network design: New problems and related models, European Journal of Operational Research, 165 (2005), 610-624.
doi: 10.1016/j.ejor.2003.04.009. |
| [2] |
R. T. Berger, C. R. Coullard and M. S. Daskin, Location-routing problems with distance constraints, Transportation Science, 41 (2007), 29-43. Google Scholar |
| [3] |
T. W. Chien, Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems, Decision Sciences, 24 (1993), 995-1021. Google Scholar |
| [4] |
C. H. Chu and J. Hopscotch,
Further discussion for transit system of chicago, Journal of Discrete Mathematical Sciences & Cryptography, 20 (2017), 717-724.
doi: 10.1080/09720529.2016.1197600. |
| [5] |
G. Clarke and J. W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12 (1964), 568-581. Google Scholar |
| [6] |
J. Dethloff,
Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up, OR-Spektrum, 23 (2001), 79-96.
doi: 10.1007/PL00013346. |
| [7] |
J. Geunes and B. M. Chang, Operations Research Models for Supply Chain Management and Design, vol. 76, Springer US, 1994. Google Scholar |
| [8] |
B. Golden, A. Assad, L. Levy and F. Gheysens, The fleet size and mix vehicle routing problem, Computers & Operations Research, 11 (1984), 49-66. Google Scholar |
| [9] |
G. Ioannou, M. Kritikos and G. Prastacos, A greedy look-ahead heuristic for the vehicle routing problem with time windows, Journal of the Operational Research Society, 52 (2001), 523-537. Google Scholar |
| [10] |
H. Kamankesh and V. G. Agelidis, A sufficient stochastic framework for optimal operation of micro-grids considering high penetration of renewable energy sources and electric vehicles, Journal of Intelligent & Fuzzy Systems, 32 (2017), 373-387. Google Scholar |
| [11] |
I. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz,
A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery, European Journal of Operational Research, 211 (2011), 318-332.
doi: 10.1016/j.ejor.2011.01.003. |
| [12] |
I. Karaoglan, F. Altiparmak, I. Kara and B. Dengiz, The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach, Omega, 40 (2012), 465-477. Google Scholar |
| [13] |
M. N. Kritikos and G. Ioannou, The heterogeneous fleet vehicle routing problem with overloads and time windows, International Journal of Production Economics, 144 (2013), 68-75. Google Scholar |
| [14] |
G. Laporte, Y. Nobert and D. Arpin, An exact algorithm for solving a capacitated location-routing problem, Annals of Operations Research, 6 (1986), 293-310. Google Scholar |
| [15] |
G. Laporte, Y. Nobert and S. Taillefer,
Solving a family of multi-depot vehicle routing and location-routing problems, Transportation Science, 22 (1988), 161-172.
doi: 10.1287/trsc.22.3.161. |
| [16] |
C. K. Y. Lin, C. K. Chow and A. Chen, A location-routing-loading problem for bill delivery services, Computers & Industrial Engineering, 43 (2002), 5-25. Google Scholar |
| [17] |
C. K. Y. Lin and R. C. W. Kwok, Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data, European Journal of Operational Research, 175 (2006), 1833-1849. Google Scholar |
| [18] |
M. Lundy and A. Mees,
Convergence of an annealing algorithm, Mathematical Programming, 34 (1986), 111-124.
doi: 10.1007/BF01582166. |
| [19] |
H. Min, Consolidation terminal location-allocation and consolidated routing problems, Journal of Business Logistics, 17 (1996), 235-263. Google Scholar |
| [20] |
H. Min, V. Jayaraman and R. Srivastava, Combined Location-Routing Problems: A Synthesis and Future Research Directions, vol. 108, Springer Berlin Heidelberg, 1998. Google Scholar |
| [21] |
G. Nagy and S. Salhi,
Location-routing: Issues, models and methods, European Journal of Operational Research, 177 (2007), 649-672.
doi: 10.1016/j.ejor.2006.04.004. |
| [22] |
G. Nagy and S. Salhi, Nested heuristic methods for the location-routing problem, 47 (1996), 1166-1174. Google Scholar |
| [23] |
C. Prodhon,, in http://prodhonc.free.fr/homepage, 2016. Google Scholar |
| [24] |
S. Salhi and M. Fraser, An integrated heuristic approach for the combined location vehicle fleet mix problem, Studies in Locational Analysis, 8 (1996), 3-21. Google Scholar |
| [25] |
S. Salhi and G. Nagy, A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the Operational Research Society, 50 (1999), 1034-1042. Google Scholar |
| [26] |
M. Schwardt and J. Dethloff, Solving a continuous location-routing problem by use of a self-organizing map, International Journal of Physical Distribution & Logistics Management, 35 (2005), 390-408. Google Scholar |
| [27] |
R. Srivastava, Alternate solution procedures for the location-routing problem, Omega, 21 (1993), 497-506. Google Scholar |
| [28] |
D. Tuzun and L. I. Burke, A two-phase tabu search approach to the location routing problem, European Journal of Operational Research, 116 (1999), 87-99. Google Scholar |
| [29] |
T. H. Wu, C. Low and J. W. Bai, Heuristic solutions to multi-depot location-routing problems, Computers & Operations Research, 29 (2002), 1393-1415. Google Scholar |
| [30] |
X. Zhang, Z. B. Zhang, H. Broersma and X. Wen,
On the complexity of edge-colored subgraph partitioning problems in network optimization, Discrete Mathematics & Theoretical Computer Science Dmtcs, 17 (2016), 227-244.
|
Table 1.
Problem cost parameters for simulated instances
| Parameter | Value | |
| Depot | Capacity ( |
Uniformly distributed over the interval [200,400] |
| Fixed cost ( |
3000 unit per depot | |
| Vehicle | Type | Type A, B, C for customers. |
| Fixed cost ( |
Cost (100,150,200) for type (A, B, C), respectively. | |
| Capacity ( |
Cost (100,200,300) for type (A, B, C), respectively | |
| Distance cost ratio | Unit cost distance (1, 1.5, 2) for type (A, B, C), respectively |
| Parameter | Value | |
| Depot | Capacity ( |
Uniformly distributed over the interval [200,400] |
| Fixed cost ( |
3000 unit per depot | |
| Vehicle | Type | Type A, B, C for customers. |
| Fixed cost ( |
Cost (100,150,200) for type (A, B, C), respectively. | |
| Capacity ( |
Cost (100,200,300) for type (A, B, C), respectively | |
| Distance cost ratio | Unit cost distance (1, 1.5, 2) for type (A, B, C), respectively |
Table 2.
Parameter settings of TS-heuristics and SA-heuristics
| TS-heuristics | SA -heuristics | |||
| Parameter | Value | Parameter | Value | |
| max-add | 5 | initial temperature (location and routing phases) | 50 | |
| max-swap | 8 | cooling rate (location phase) | 0.95 | |
| max-route | 6 | cooling rate (routing phase) | 0.9 | |
| tabu duration (location phase) |
8 | final temperature (location and routing phase) | 0.15 | |
| tabu duration (routing phase) |
10 | no-improvement number of cycles (location and routing phases) | 10 | |
| TS-heuristics | SA -heuristics | |||
| Parameter | Value | Parameter | Value | |
| max-add | 5 | initial temperature (location and routing phases) | 50 | |
| max-swap | 8 | cooling rate (location phase) | 0.95 | |
| max-route | 6 | cooling rate (routing phase) | 0.9 | |
| tabu duration (location phase) |
8 | final temperature (location and routing phase) | 0.15 | |
| tabu duration (routing phase) |
10 | no-improvement number of cycles (location and routing phases) | 10 | |
Table 3.
Computational results for the formulations on small-size test problems
| Original formulation | Strong formulation | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 15 | 3 | 45.82 | 86.29 | 10 | 5.04 | 48.02 | 10 | |
| 20 | 3 | 36.02 | 1973.64 | 8 | 1.47 | 2074.65 | 9 | |
| 20 | 4 | 51.80 | 2391.82 | 6 | 0.85 | 2619.46 | 7 | |
| 30 | 4 | 26.39 | 3729.65 | 5 | 13.23 | 3482.73 | 6 | |
| 40 | 4 | 38.74 | 5183.59 | 5 | 15.78 | 5827.84 | 5 | |
| 30 | 5 | 33.90 | 4734.64 | 4 | 21.92 | 5418.38 | 5 | |
| 40 | 5 | 46.29 | 5374.68 | 2 | 3.63 | 6016.73 | 3 | |
| 50 | 5 | 34.62 | 6739.52 | 2 | 8.51 | 6473.63 | 3 | |
| 40 | 6 | 29.43 | 7200.00 | 0 | 2.58 | 7200.00 | 0 | |
| 50 | 6 | 37.58 | 7200.00 | 0 | 16.28 | 7200.00 | 0 | |
| Average | 38.06 | 5279.52 | 8.93 | 4636.14 | ||||
| Original formulation | Strong formulation | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 15 | 3 | 45.82 | 86.29 | 10 | 5.04 | 48.02 | 10 | |
| 20 | 3 | 36.02 | 1973.64 | 8 | 1.47 | 2074.65 | 9 | |
| 20 | 4 | 51.80 | 2391.82 | 6 | 0.85 | 2619.46 | 7 | |
| 30 | 4 | 26.39 | 3729.65 | 5 | 13.23 | 3482.73 | 6 | |
| 40 | 4 | 38.74 | 5183.59 | 5 | 15.78 | 5827.84 | 5 | |
| 30 | 5 | 33.90 | 4734.64 | 4 | 21.92 | 5418.38 | 5 | |
| 40 | 5 | 46.29 | 5374.68 | 2 | 3.63 | 6016.73 | 3 | |
| 50 | 5 | 34.62 | 6739.52 | 2 | 8.51 | 6473.63 | 3 | |
| 40 | 6 | 29.43 | 7200.00 | 0 | 2.58 | 7200.00 | 0 | |
| 50 | 6 | 37.58 | 7200.00 | 0 | 16.28 | 7200.00 | 0 | |
| Average | 38.06 | 5279.52 | 8.93 | 4636.14 | ||||
Table 4.
Computational results for relaxations of the formulations
| LP of original formulation | LP of strong formulation | SLP of strong formulation | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | ||||
| 15 | 3 | 45.82 | 0.03 | 18.63 | 0.02 | 4.75 | 0.43 | ||
| 20 | 3 | 36.02 | 1.84 | 1.76 | 1.59 | 2.04 | 15.71 | ||
| 20 | 4 | 51.80 | 2.53 | 1.09 | 2.37 | 1.84 | 1.68 | ||
| 30 | 4 | 26.39 | 6.85 | 16.39 | 5.89 | 4.73 | 184.93 | ||
| 40 | 4 | 38.74 | 6.52 | 2.54 | 7.41 | 5.91 | 347.55 | ||
| 30 | 5 | 33.90 | 12.48 | 11.64 | 11.91 | 2.43 | 194.69 | ||
| 40 | 5 | 46.29 | 11.53 | 10.83 | 10.53 | 3.74 | 842.68 | ||
| 50 | 5 | 34.62 | 14.83 | 18.46 | 13.96 | 6.47 | 1043.79 | ||
| 40 | 6 | 29.43 | 17.35 | 13.58 | 15.37 | 10.25 | 357.73 | ||
| 50 | 6 | 37.58 | 28.59 | 17.36 | 22.54 | 12.54 | 1074.51 | ||
| Average | 38.06 | 10.26 | 11.23 | 13.13 | 5.47 | 406.37 | |||
| LP of original formulation | LP of strong formulation | SLP of strong formulation | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | ||||
| 15 | 3 | 45.82 | 0.03 | 18.63 | 0.02 | 4.75 | 0.43 | ||
| 20 | 3 | 36.02 | 1.84 | 1.76 | 1.59 | 2.04 | 15.71 | ||
| 20 | 4 | 51.80 | 2.53 | 1.09 | 2.37 | 1.84 | 1.68 | ||
| 30 | 4 | 26.39 | 6.85 | 16.39 | 5.89 | 4.73 | 184.93 | ||
| 40 | 4 | 38.74 | 6.52 | 2.54 | 7.41 | 5.91 | 347.55 | ||
| 30 | 5 | 33.90 | 12.48 | 11.64 | 11.91 | 2.43 | 194.69 | ||
| 40 | 5 | 46.29 | 11.53 | 10.83 | 10.53 | 3.74 | 842.68 | ||
| 50 | 5 | 34.62 | 14.83 | 18.46 | 13.96 | 6.47 | 1043.79 | ||
| 40 | 6 | 29.43 | 17.35 | 13.58 | 15.37 | 10.25 | 357.73 | ||
| 50 | 6 | 37.58 | 28.59 | 17.36 | 22.54 | 12.54 | 1074.51 | ||
| Average | 38.06 | 10.26 | 11.23 | 13.13 | 5.47 | 406.37 | |||
Table 5.
Perform comparison of HFLRPSPDO on the effect of capacity violation
| Cost without violation | Cost with violation | Improvement on cost (%) | CPU times (sec) |
Capacity violation (%) | ||
| 15 | 3 | 29222 | 24731 | 15.37 | 86.29 | 6.82 |
| 20 | 3 | 32626 | 29742 | 8.84 | 1973.64 | 7.38 |
| 20 | 4 | 30325 | 27387 | 9.69 | 2391.82 | 9.65 |
| 30 | 4 | 51172 | 48373 | 5.47 | 3729.65 | 4.27 |
| 40 | 4 | 66101 | 61382 | 7.14 | 5183.59 | 6.49 |
| 30 | 5 | 51798 | 46183 | 10.84 | 4734.64 | 3.85 |
| 40 | 5 | 62976 | 53284 | 15.39 | 5374.68 | 6.58 |
| 50 | 5 | 64828 | 59337 | 8.47 | 6739.52 | 9.83 |
| 40 | 6 | 59014 | 55833 | 5.39 | 7200.00 | 5.48 |
| 50 | 6 | 64188 | 57821 | 9.92 | 7200.00 | 6.29 |
| Average | 51225 | 46407 | 9.65 | 6.66 | ||
| Cost without violation | Cost with violation | Improvement on cost (%) | CPU times (sec) |
Capacity violation (%) | ||
| 15 | 3 | 29222 | 24731 | 15.37 | 86.29 | 6.82 |
| 20 | 3 | 32626 | 29742 | 8.84 | 1973.64 | 7.38 |
| 20 | 4 | 30325 | 27387 | 9.69 | 2391.82 | 9.65 |
| 30 | 4 | 51172 | 48373 | 5.47 | 3729.65 | 4.27 |
| 40 | 4 | 66101 | 61382 | 7.14 | 5183.59 | 6.49 |
| 30 | 5 | 51798 | 46183 | 10.84 | 4734.64 | 3.85 |
| 40 | 5 | 62976 | 53284 | 15.39 | 5374.68 | 6.58 |
| 50 | 5 | 64828 | 59337 | 8.47 | 6739.52 | 9.83 |
| 40 | 6 | 59014 | 55833 | 5.39 | 7200.00 | 5.48 |
| 50 | 6 | 64188 | 57821 | 9.92 | 7200.00 | 6.29 |
| Average | 51225 | 46407 | 9.65 | 6.66 | ||
Table 6.
Computational results of the TS and SA on small-size problems
| TS-heuristics | SA-heuristics | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 15 | 3 | 0.00 | 24731 | 38.13 | 0.00 | 24731 | 40.57 | |
| 20 | 3 | 0.00 | 29742 | 63.59 | 0.00 | 29742 | 54.13 | |
| 20 | 4 | 0.01 | 27387 | 73.82 | 0.02 | 27390 | 80.53 | |
| 30 | 4 | 0.23 | 48373 | 102.43 | 0.28 | 48397 | 138.62 | |
| 40 | 4 | 0.91 | 61382 | 162.57 | 0.73 | 61273 | 147.76 | |
| 30 | 5 | 0.35 | 46183 | 90.37 | 0.34 | 46178 | 128.54 | |
| 40 | 5 | 0.97 | 53284 | 194.63 | 1.14 | 53307 | 251.72 | |
| 50 | 5 | 1.24 | 59337 | 288.79 | 1.45 | 59460 | 300.05 | |
| 40 | 6 | 0.99 | 55833 | 239.40 | 1.06 | 55872 | 207.24 | |
| 50 | 6 | 1.93 | 57821 | 247.56 | 1.82 | 57759 | 277.42 | |
| Average | 0.66 | 46407 | 150.13 | 0.75 | 46411 | 162.66 | ||
| TS-heuristics | SA-heuristics | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 15 | 3 | 0.00 | 24731 | 38.13 | 0.00 | 24731 | 40.57 | |
| 20 | 3 | 0.00 | 29742 | 63.59 | 0.00 | 29742 | 54.13 | |
| 20 | 4 | 0.01 | 27387 | 73.82 | 0.02 | 27390 | 80.53 | |
| 30 | 4 | 0.23 | 48373 | 102.43 | 0.28 | 48397 | 138.62 | |
| 40 | 4 | 0.91 | 61382 | 162.57 | 0.73 | 61273 | 147.76 | |
| 30 | 5 | 0.35 | 46183 | 90.37 | 0.34 | 46178 | 128.54 | |
| 40 | 5 | 0.97 | 53284 | 194.63 | 1.14 | 53307 | 251.72 | |
| 50 | 5 | 1.24 | 59337 | 288.79 | 1.45 | 59460 | 300.05 | |
| 40 | 6 | 0.99 | 55833 | 239.40 | 1.06 | 55872 | 207.24 | |
| 50 | 6 | 1.93 | 57821 | 247.56 | 1.82 | 57759 | 277.42 | |
| Average | 0.66 | 46407 | 150.13 | 0.75 | 46411 | 162.66 | ||
Table 7.
Computational results of the TS and SA on larger-size problems
| TS-heuristics | SA-heuristics | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 50 | 8 | 2.41 | 54823 | 234.65 | 2.08 | 54711 | 208.40 | |
| 80 | 8 | 1.73 | 113897 | 383.59 | 2.36 | 114602 | 361.47 | |
| 100 | 8 | 0.96 | 137254 | 437.42 | 1.53 | 138029 | 472.43 | |
| 80 | 9 | 1.24 | 100286 | 369.38 | 2.37 | 101405 | 390.22 | |
| 100 | 9 | 0.72 | 130287 | 482.36 | 1.24 | 130960 | 538.52 | |
| 120 | 9 | 0.92 | 157239 | 501.36 | 0.83 | 157099 | 409.25 | |
| 150 | 9 | 1.09 | 186275 | 472.17 | 0.95 | 186117 | 463.47 | |
| 80 | 10 | 3.73 | 983673 | 302.54 | 2.54 | 982388 | 378.49 | |
| 100 | 10 | 2.27 | 125362 | 261.52 | 2.36 | 125472 | 330.52 | |
| 120 | 10 | 1.34 | 139927 | 289.55 | 2.03 | 140080 | 375.38 | |
| 150 | 10 | 1.46 | 173845 | 573.82 | 3.41 | 174186 | 593.54 | |
| 200 | 10 | 2.03 | 237419 | 479.53 | 3.56 | 238279 | 636.39 | |
| Average | 1.66 | 211690 | 398.99 | 2.11 | 211944 | 429.84 | ||
| TS-heuristics | SA-heuristics | |||||||
| Gap% | CPU | #OP | Gap% | CPU | #OP | |||
| 50 | 8 | 2.41 | 54823 | 234.65 | 2.08 | 54711 | 208.40 | |
| 80 | 8 | 1.73 | 113897 | 383.59 | 2.36 | 114602 | 361.47 | |
| 100 | 8 | 0.96 | 137254 | 437.42 | 1.53 | 138029 | 472.43 | |
| 80 | 9 | 1.24 | 100286 | 369.38 | 2.37 | 101405 | 390.22 | |
| 100 | 9 | 0.72 | 130287 | 482.36 | 1.24 | 130960 | 538.52 | |
| 120 | 9 | 0.92 | 157239 | 501.36 | 0.83 | 157099 | 409.25 | |
| 150 | 9 | 1.09 | 186275 | 472.17 | 0.95 | 186117 | 463.47 | |
| 80 | 10 | 3.73 | 983673 | 302.54 | 2.54 | 982388 | 378.49 | |
| 100 | 10 | 2.27 | 125362 | 261.52 | 2.36 | 125472 | 330.52 | |
| 120 | 10 | 1.34 | 139927 | 289.55 | 2.03 | 140080 | 375.38 | |
| 150 | 10 | 1.46 | 173845 | 573.82 | 3.41 | 174186 | 593.54 | |
| 200 | 10 | 2.03 | 237419 | 479.53 | 3.56 | 238279 | 636.39 | |
| Average | 1.66 | 211690 | 398.99 | 2.11 | 211944 | 429.84 | ||
| [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] |
Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199 |
| [3] |
Bo Duan, Zhengce Zhang. A reaction-diffusion-advection two-species competition system with a free boundary in heterogeneous environment. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021067 |
| [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.233
Tools
Article outline
Figures and Tables
[Back to Top]