Figure 1.
Example of the allocation problem
-
Previous Article
Financing strategies for a capital-constrained supplier under yield uncertainty
- JIMO Home
- This Issue
-
Next Article
Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization
March
2020, 16(2): 857-885.
doi: 10.3934/jimo.2018182
An iterated greedy algorithm with variable neighborhood descent for the planning of specialized diagnostic services in a segmented healthcare system
| 1. | Tecnológico de Monterrey, Campus Toluca, Department of Industrial Engineering, Av. Eduardo Monroy Cárdenas 2000, San Antonio Buenavista, Toluca 50110, Mexico |
| 2. | Universidad Autónoma de Nuevo León (UANL), Graduate Program in Systems Engineering, Av. Universidad s/n, Cd. Universitaria, San Nicolás de los Garza, NL 66455, Mexico |
In this paper, a problem arising in the planning of specialized diagnostic services in a segmented public healthcare system is addressed. The problem consists of deciding which hospitals will provide the service and their capacity levels, the allocation of demand in each institution, and the reallocation of uncovered demand to other institutions or private providers, while minimizing the total equivalent annual cost of investment and operating cost required to satisfy all the demand. An associated mixed-integer linear programming model can be solved by conventional branch and bound for relatively small instances; however, for larger instances the problem becomes intractable. To effectively address larger instances, a hybrid metaheuristic framework combining iterated greedy (IGA) and variable neighborhood descent (VND) components for this problem is proposed. Two greedy construction heuristics are developed, one starting with an infeasible solution and iteratively adding capacity and the other starting with a feasible, but expensive, solution and iteratively decrease capacity. The iterated greedy algorithm includes destruction and reconstruction procedures. Four different neighborhood structures are designed and tested within a VND procedure. In addition, the computation of local search components benefit from an intelligent exploitation of problem structure since, when the first-level location variables (hospital location and capacity) are fixed, the remaining subproblem can be solved efficiently as it is very close to a transshipment problem. All components and different strategies were empirically assessed both individually and within the IGA-VND framework. The resulting metaheuristic is able to obtain near optimal solutions, within 3% of optimality, when tested over a data base of 60- to 300-hospital instances.
Keywords:
Healthcare planning,
integer programming,
hybrid metaheuristics,
iterated greedy algorithm,
variable neighborhood descent.
Mathematics Subject Classification:
Primary: 90C10, 90C59; Secondary: 90B80, 90C06, 90C90.
Citation:
Rodolfo Mendoza-Gómez, Roger Z. Ríos-Mercado, Karla B. Valenzuela-Ocaña. An iterated greedy algorithm with variable neighborhood descent for the planning of specialized diagnostic services in a segmented healthcare system. Journal of Industrial and Management Optimization,
2020, 16
(2)
: 857-885.
doi: 10.3934/jimo.2018182
![]()
References:
| [1] |
A. Ahmadi-Javid, P. Seyedi and S. S. Syam,
A survey of healthcare facility location, Computers & Operations Research, 79 (2017), 223-226.
doi: 10.1016/j.cor.2016.05.018. |
| [2] |
N. Ayvaz and W. T. Huh,
Allocation of hospital capacity to multiple types of patients, Journal of Revenue and Pricing Management, 9 (2010), 386-398.
|
| [3] |
A. Chauhan and A. Singh,
Healthcare waste management: A state-of-the-art literature review, International Journal of Environment and Waste Management, 18 (2016), 120-144.
|
| [4] |
M. J. Coté, S. S. Syam, W. B. Vogel and D. C. Cowper,
A mixed integer programming model to locate traumatic brain injury treatment units in the department of veterans affairs: A case study, Health Care Management Science, 10 (2007), 253-267.
|
| [5] |
T. G. Crainic, M. Gendreau, P. Hansen, N. Hoeb and N. Mladenović,
Cooperative parallel variable neighborhood search for the p-median, Journal of Heuristics, 10 (2004), 293-314.
|
| [6] |
M. S. Daskin and L. K. Dean, Location of health care facilities, in Operations Research and Health Care: A Handbook of Methods and Applications (eds. M. L. Brandeau, F. Sainfort and W. P. Pierskalla), Springer, New York, 2005, chapter 3, 43-76. |
| [7] |
Z. Diakova and Y. Kochetov,
A double VNS heuristic for the facility location and pricing problem, Electronic Notes in Discrete Mathematics, 39 (2012), 29-34.
doi: 10.1016/j.endm.2012.10.005. |
| [8] |
F. García-López, B. Melián-Batista, J. A. Moreno-Pérez and J. M. Moreno-Vega,
The parallel variable neighborhood search for the p-median problem, Journal of Heuristics, 8 (2002), 375-388.
|
| [9] |
P. Hansen and N. Mladenović,
Variable neighborhood search for the p-median, Location Science, 5 (1997), 207-226.
|
| [10] |
P. Hansen and N. Mladenović,
Variable neighborhood decomposition search, Journal of Heuristics, 7 (2001), 335-350.
|
| [11] |
H. H. Hoos and T. Stützle,
Stochastic Local Search: Foundations and Applications, Morgan Kaufmann, San Francisco, 2004. |
| [12] |
I. Ljubić, A hybrid VNS for connected facility location, in Hybrid Metaheuristics (eds. T. Bartz-Beielstein, M. J. Blesa Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph and M. Sampels), vol. 4771 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, 2007,157-169. |
| [13] |
H. R. Lourenço, O. C. Martin and T. Stützle, Iterated local search, in Handbook of Metaheuristics (eds. F. Glover and G. A. Kochenberger), Springer, Boston, 2003, chapter 11,320-353. |
| [14] |
S. Mahar, K. M. Bretthauer and P. A. Salzarulo,
Locating specialized service capacity in a multi-hospital network, European Journal of Operational Research, 212 (2011), 596-605.
|
| [15] |
M. Marić, Z. Stanimirović and S. Božović,
Hybrid metaheuristic method for determining locations for long-term health care facilities, Annals of Operations Research, 227 (2013), 3-23.
doi: 10.1007/s10479-013-1313-8. |
| [16] |
S. McLafferty and D. Broe,
Patient outcomes and regional planning of coronary care services: A location-allocation approach., Social Science and Medicine, 30 (1990), 297-305.
|
| [17] |
R. Mendoza-Gómez, R. Z. Ríos-Mercado and K. B. Valenzuela,
Efficient Planning of Specialized Diagnostic Services in a Segmented Healthcare System, Technical report PISIS-2016-01, Graduate Program in Systems Engineering, Universidad Autónoma de Nuevo León, 2016. |
| [18] |
A. M. Mestre, M. D. Oliveira and A. P. Barbosa-Póvoa,
Location-allocation approaches for hospital network planning under uncertainty, European Journal of Operational Research, 240 (2015), 791-806.
|
| [19] |
N. Mladenović and P. Hansen,
Variable neighborhood search, Computers and Operations Research, 24 (1997), 1097-1100.
doi: 10.1016/S0305-0548(97)00031-2. |
| [20] |
N. Mladenović and P. Hansen,
Solving the p-center problem by tabu search and variable neighborhood search, Networks, 42 (2003), 48-64.
doi: 10.1002/net.10081. |
| [21] |
Q. K. Pan and R. Ruiz,
An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem, Omega, 44 (2014), 41-50.
|
| [22] |
D. R. Quevedo-Orozco and R. Z. Ríos-Mercado,
Improving the quality of heuristic solutions for the capacitated vertex $ p $-center problem through iterated greedy local search and variable neighborhood descent, Computers and Operations Research, 62 (2015), 133-144.
doi: 10.1016/j.cor.2014.12.013. |
| [23] |
A. Rais and A. Viana,
Operations research in healthcare: A survey, International Transactions in Operational Research, 18 (2011), 1-31.
doi: 10.1111/j.1475-3995.2010.00767.x. |
| [24] |
N. Rego and J. P. de Sousa, Supply chain coordination in hospitals, in Leveraging Knowledge for Innovation in Collaborative Networks (eds. L. M. Camarinha-Matos, I. Paraskakis and H. Afsarmanesh), vol. 307 of IFIP Advances in Information and Communication Technology (IFIPAICT), Springer, Berlin, Germany, 2009,117-127. |
| [25] |
I. Ribas, R. Companys and X. Tort-Martorell,
An iterated greedy algorithm for the flowshop scheduling problem with blocking, Omega, 39 (2011), 293-301.
|
| [26] |
R. Ruiz and T. Stützle,
A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177 (2006), 2033-2049.
|
| [27] |
R. Ruiz and T. Stützle,
An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, European Journal of Operational Research, 187 (2008), 1143-1159.
|
| [28] |
R. J. Ruth,
A mixed integer programming model for regional planning of a hospital inpatient service, Management Science, 27 (1981), 521-533.
|
| [29] |
C. Stummer, K. Doerner, A. Focke and K. Heidenberger,
Determining location and size of medical departments in a hospital network: A multiobjective decision support approach, Health Care Management Science, 7 (2004), 63-71.
|
| [30] |
S. S. Syam and M. J. Coté,
A location-allocation model for service providers with application to not-for-profit health care organizations, Omega, 38 (2010), 157-166.
|
| [31] |
S. S. Syam and M. J. Coté,
A comprehensive location-allocation method for specialized healthcare services, Operations Research for Health Care, 1 (2012), 73-83.
|
| [32] |
H. Tlahig, A. J. H. Bouchriha and P. Ladet,
Centralized versus distributed sterilization service: A location-allocation decision model, Operations Research for Health Care, 2 (2013), 75-85.
|
| [33] |
Z. Yuan, A. Fügenschuh, H. Homfeld, P. Balaprakash, T. Stützle and M. Schoch, Iterated greedy algorithms for a real-world cyclic train scheduling problem, in Hybrid Metaheuristics (eds. M. J. Blesa, C. Blum, C. Cotta, A. J. Fernández, J. E. Gallardo, A. Roli and M. Sampels), vol. 5296 of Lecture Notes in Computer Science, Springer, 2008,102-116. |
| [34] |
N. Zarrinpoor, M. S. Fallahnezhad and M. S. Pishvaee,
Design of a reliable hierarchical location-allocation model under disruptions for health service networks: A two-stage robust approach, Computers & Industrial Engineering, 109 (2017), 130-150.
|
show all references
References:
| [1] |
A. Ahmadi-Javid, P. Seyedi and S. S. Syam,
A survey of healthcare facility location, Computers & Operations Research, 79 (2017), 223-226.
doi: 10.1016/j.cor.2016.05.018. |
| [2] |
N. Ayvaz and W. T. Huh,
Allocation of hospital capacity to multiple types of patients, Journal of Revenue and Pricing Management, 9 (2010), 386-398.
|
| [3] |
A. Chauhan and A. Singh,
Healthcare waste management: A state-of-the-art literature review, International Journal of Environment and Waste Management, 18 (2016), 120-144.
|
| [4] |
M. J. Coté, S. S. Syam, W. B. Vogel and D. C. Cowper,
A mixed integer programming model to locate traumatic brain injury treatment units in the department of veterans affairs: A case study, Health Care Management Science, 10 (2007), 253-267.
|
| [5] |
T. G. Crainic, M. Gendreau, P. Hansen, N. Hoeb and N. Mladenović,
Cooperative parallel variable neighborhood search for the p-median, Journal of Heuristics, 10 (2004), 293-314.
|
| [6] |
M. S. Daskin and L. K. Dean, Location of health care facilities, in Operations Research and Health Care: A Handbook of Methods and Applications (eds. M. L. Brandeau, F. Sainfort and W. P. Pierskalla), Springer, New York, 2005, chapter 3, 43-76. |
| [7] |
Z. Diakova and Y. Kochetov,
A double VNS heuristic for the facility location and pricing problem, Electronic Notes in Discrete Mathematics, 39 (2012), 29-34.
doi: 10.1016/j.endm.2012.10.005. |
| [8] |
F. García-López, B. Melián-Batista, J. A. Moreno-Pérez and J. M. Moreno-Vega,
The parallel variable neighborhood search for the p-median problem, Journal of Heuristics, 8 (2002), 375-388.
|
| [9] |
P. Hansen and N. Mladenović,
Variable neighborhood search for the p-median, Location Science, 5 (1997), 207-226.
|
| [10] |
P. Hansen and N. Mladenović,
Variable neighborhood decomposition search, Journal of Heuristics, 7 (2001), 335-350.
|
| [11] |
H. H. Hoos and T. Stützle,
Stochastic Local Search: Foundations and Applications, Morgan Kaufmann, San Francisco, 2004. |
| [12] |
I. Ljubić, A hybrid VNS for connected facility location, in Hybrid Metaheuristics (eds. T. Bartz-Beielstein, M. J. Blesa Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph and M. Sampels), vol. 4771 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, 2007,157-169. |
| [13] |
H. R. Lourenço, O. C. Martin and T. Stützle, Iterated local search, in Handbook of Metaheuristics (eds. F. Glover and G. A. Kochenberger), Springer, Boston, 2003, chapter 11,320-353. |
| [14] |
S. Mahar, K. M. Bretthauer and P. A. Salzarulo,
Locating specialized service capacity in a multi-hospital network, European Journal of Operational Research, 212 (2011), 596-605.
|
| [15] |
M. Marić, Z. Stanimirović and S. Božović,
Hybrid metaheuristic method for determining locations for long-term health care facilities, Annals of Operations Research, 227 (2013), 3-23.
doi: 10.1007/s10479-013-1313-8. |
| [16] |
S. McLafferty and D. Broe,
Patient outcomes and regional planning of coronary care services: A location-allocation approach., Social Science and Medicine, 30 (1990), 297-305.
|
| [17] |
R. Mendoza-Gómez, R. Z. Ríos-Mercado and K. B. Valenzuela,
Efficient Planning of Specialized Diagnostic Services in a Segmented Healthcare System, Technical report PISIS-2016-01, Graduate Program in Systems Engineering, Universidad Autónoma de Nuevo León, 2016. |
| [18] |
A. M. Mestre, M. D. Oliveira and A. P. Barbosa-Póvoa,
Location-allocation approaches for hospital network planning under uncertainty, European Journal of Operational Research, 240 (2015), 791-806.
|
| [19] |
N. Mladenović and P. Hansen,
Variable neighborhood search, Computers and Operations Research, 24 (1997), 1097-1100.
doi: 10.1016/S0305-0548(97)00031-2. |
| [20] |
N. Mladenović and P. Hansen,
Solving the p-center problem by tabu search and variable neighborhood search, Networks, 42 (2003), 48-64.
doi: 10.1002/net.10081. |
| [21] |
Q. K. Pan and R. Ruiz,
An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem, Omega, 44 (2014), 41-50.
|
| [22] |
D. R. Quevedo-Orozco and R. Z. Ríos-Mercado,
Improving the quality of heuristic solutions for the capacitated vertex $ p $-center problem through iterated greedy local search and variable neighborhood descent, Computers and Operations Research, 62 (2015), 133-144.
doi: 10.1016/j.cor.2014.12.013. |
| [23] |
A. Rais and A. Viana,
Operations research in healthcare: A survey, International Transactions in Operational Research, 18 (2011), 1-31.
doi: 10.1111/j.1475-3995.2010.00767.x. |
| [24] |
N. Rego and J. P. de Sousa, Supply chain coordination in hospitals, in Leveraging Knowledge for Innovation in Collaborative Networks (eds. L. M. Camarinha-Matos, I. Paraskakis and H. Afsarmanesh), vol. 307 of IFIP Advances in Information and Communication Technology (IFIPAICT), Springer, Berlin, Germany, 2009,117-127. |
| [25] |
I. Ribas, R. Companys and X. Tort-Martorell,
An iterated greedy algorithm for the flowshop scheduling problem with blocking, Omega, 39 (2011), 293-301.
|
| [26] |
R. Ruiz and T. Stützle,
A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177 (2006), 2033-2049.
|
| [27] |
R. Ruiz and T. Stützle,
An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, European Journal of Operational Research, 187 (2008), 1143-1159.
|
| [28] |
R. J. Ruth,
A mixed integer programming model for regional planning of a hospital inpatient service, Management Science, 27 (1981), 521-533.
|
| [29] |
C. Stummer, K. Doerner, A. Focke and K. Heidenberger,
Determining location and size of medical departments in a hospital network: A multiobjective decision support approach, Health Care Management Science, 7 (2004), 63-71.
|
| [30] |
S. S. Syam and M. J. Coté,
A location-allocation model for service providers with application to not-for-profit health care organizations, Omega, 38 (2010), 157-166.
|
| [31] |
S. S. Syam and M. J. Coté,
A comprehensive location-allocation method for specialized healthcare services, Operations Research for Health Care, 1 (2012), 73-83.
|
| [32] |
H. Tlahig, A. J. H. Bouchriha and P. Ladet,
Centralized versus distributed sterilization service: A location-allocation decision model, Operations Research for Health Care, 2 (2013), 75-85.
|
| [33] |
Z. Yuan, A. Fügenschuh, H. Homfeld, P. Balaprakash, T. Stützle and M. Schoch, Iterated greedy algorithms for a real-world cyclic train scheduling problem, in Hybrid Metaheuristics (eds. M. J. Blesa, C. Blum, C. Cotta, A. J. Fernández, J. E. Gallardo, A. Roli and M. Sampels), vol. 5296 of Lecture Notes in Computer Science, Springer, 2008,102-116. |
| [34] |
N. Zarrinpoor, M. S. Fallahnezhad and M. S. Pishvaee,
Design of a reliable hierarchical location-allocation model under disruptions for health service networks: A two-stage robust approach, Computers & Industrial Engineering, 109 (2017), 130-150.
|
Figure 2.
Calibration of $ \rho $ in the IGA
Figure 3.
Interval plot with a confidence interval of 95% for the number of suggested iterations
Table 1.
Comparison of constructive methods and B & B
| Method | Ave gap (%) |
Min gap (%) |
Max gap (%) |
Ave gap (s) |
Min gap (s) |
Max gap (s) |
|
| 60 | 0.32 | 0.00 | 2.31 | 6,755 | 18.5 | 10,800 | |
| 120 | 2.24 | 0.00 | 10.62 | 10,566 | 3,568 | 10,800 | |
| B & B | 180 | 6.98 | 0.81 | 23.91 | 10,654 | 8,244 | 10,800 |
| 240 | 20.94 | 3.11 | 59.43 | 10,693 | 7,557 | 10,800 | |
| 300 | 43.96 | 6.45 | 76.65 | 10,762 | 9,367 | 10,800 | |
| 60 | 2.11 | 0.26 | 7.91 | 0.7 | 0.2 | 1.7 | |
| 120 | 3.06 | 0.66 | 16.87 | 3.2 | 0.9 | 8.1 | |
| CM1 | 180 | 3.58 | 1.09 | 8.86 | 8.4 | 2.1 | 24.7 |
| 240 | 4.59 | 0.98 | 12.12 | 14.7 | 3.7 | 36.3 | |
| 300 | 5.49 | 1.75 | 10.52 | 27.2 | 5.8 | 59.0 | |
| 60 | 2.04 | 0.0 | 6.67 | 0.5 | 0.2 | 1.1 | |
| 120 | 2.46 | 0.81 | 6.50 | 1.8 | 0.7 | 3.2 | |
| CM2 | 180 | 3.38 | 0.56 | 10.07 | 5.0 | 1.3 | 10.9 |
| 240 | 3.36 | 0.70 | 9.43 | 8.5 | 2.6 | 18.5 | |
| 300 | 5.22 | 1.08 | 10.03 | 16.0 | 4.7 | 38.9 |
| Method | Ave gap (%) |
Min gap (%) |
Max gap (%) |
Ave gap (s) |
Min gap (s) |
Max gap (s) |
|
| 60 | 0.32 | 0.00 | 2.31 | 6,755 | 18.5 | 10,800 | |
| 120 | 2.24 | 0.00 | 10.62 | 10,566 | 3,568 | 10,800 | |
| B & B | 180 | 6.98 | 0.81 | 23.91 | 10,654 | 8,244 | 10,800 |
| 240 | 20.94 | 3.11 | 59.43 | 10,693 | 7,557 | 10,800 | |
| 300 | 43.96 | 6.45 | 76.65 | 10,762 | 9,367 | 10,800 | |
| 60 | 2.11 | 0.26 | 7.91 | 0.7 | 0.2 | 1.7 | |
| 120 | 3.06 | 0.66 | 16.87 | 3.2 | 0.9 | 8.1 | |
| CM1 | 180 | 3.58 | 1.09 | 8.86 | 8.4 | 2.1 | 24.7 |
| 240 | 4.59 | 0.98 | 12.12 | 14.7 | 3.7 | 36.3 | |
| 300 | 5.49 | 1.75 | 10.52 | 27.2 | 5.8 | 59.0 | |
| 60 | 2.04 | 0.0 | 6.67 | 0.5 | 0.2 | 1.1 | |
| 120 | 2.46 | 0.81 | 6.50 | 1.8 | 0.7 | 3.2 | |
| CM2 | 180 | 3.38 | 0.56 | 10.07 | 5.0 | 1.3 | 10.9 |
| 240 | 3.36 | 0.70 | 9.43 | 8.5 | 2.6 | 18.5 | |
| 300 | 5.22 | 1.08 | 10.03 | 16.0 | 4.7 | 38.9 |
Table 2.
Individual neighborhood evaluation, initial relative gap = 3.77%
| Final | Imp | Ave | Max | Average final gap (%) | |||||
| gap (%) | (%) | time (s) | time (s) | 60 | 120 | 180 | 240 | 300 | |
| LS1 | 3.30 | 12.28 | 0.9 | 15.0 | 1.93 | 2.62 | 3.12 | 3.92 | 4.93 |
| LS2 | 3.61 | 4.17 | 0.4 | 6.0 | 1.70 | 2.96 | 3.49 | 4.48 | 5.42 |
| LS3 | 2.85 | 24.40 | 18.1 | 198.0 | 1.61 | 2.32 | 2.69 | 3.43 | 4.18 |
| LS4 | 2.47 | 34.29 | 184.1 | 1,578.4 | 1.43 | 1.99 | 2.40 | 2.88 | 3.66 |
| Final | Imp | Ave | Max | Average final gap (%) | |||||
| gap (%) | (%) | time (s) | time (s) | 60 | 120 | 180 | 240 | 300 | |
| LS1 | 3.30 | 12.28 | 0.9 | 15.0 | 1.93 | 2.62 | 3.12 | 3.92 | 4.93 |
| LS2 | 3.61 | 4.17 | 0.4 | 6.0 | 1.70 | 2.96 | 3.49 | 4.48 | 5.42 |
| LS3 | 2.85 | 24.40 | 18.1 | 198.0 | 1.61 | 2.32 | 2.69 | 3.43 | 4.18 |
| LS4 | 2.47 | 34.29 | 184.1 | 1,578.4 | 1.43 | 1.99 | 2.40 | 2.88 | 3.66 |
Table 3.
VND evaluation, initial relative gap = 3.77%
| VND | Final | Imp | Ave | Max | Average final gap (%) | ||||
| ( | gap (%) | (%) | time (s) | time (s) | 60 | 120 | 180 | 240 | 300 |
| VND1(1-2-3) | 2.30 | 38.90 | 21.8 | 218.8 | 1.04 | 1.86 | 2.23 | 2.71 | 3.68 |
| VND2(1-2-3-4) | 2.04 | 48.87 | 263.5 | 2,660.5 | 0.91 | 1.62 | 1.89 | 2.44 | 3.34 |
| VND3(2-1-3) | 2.31 | 38.74 | 53.1 | 420.5 | 1.05 | 1.88 | 2.21 | 2.72 | 3.68 |
| VND4(2-1-3-4) | 2.05 | 45.70 | 257.4 | 2,139.6 | 0.91 | 1.60 | 1.88 | 2.45 | 3.39 |
| VND5(2-3) | 2.45 | 35.07 | 17.1 | 178.8 | 1.45 | 1.97 | 2.29 | 2.81 | 3.73 |
| VND | Final | Imp | Ave | Max | Average final gap (%) | ||||
| ( | gap (%) | (%) | time (s) | time (s) | 60 | 120 | 180 | 240 | 300 |
| VND1(1-2-3) | 2.30 | 38.90 | 21.8 | 218.8 | 1.04 | 1.86 | 2.23 | 2.71 | 3.68 |
| VND2(1-2-3-4) | 2.04 | 48.87 | 263.5 | 2,660.5 | 0.91 | 1.62 | 1.89 | 2.44 | 3.34 |
| VND3(2-1-3) | 2.31 | 38.74 | 53.1 | 420.5 | 1.05 | 1.88 | 2.21 | 2.72 | 3.68 |
| VND4(2-1-3-4) | 2.05 | 45.70 | 257.4 | 2,139.6 | 0.91 | 1.60 | 1.88 | 2.45 | 3.39 |
| VND5(2-3) | 2.45 | 35.07 | 17.1 | 178.8 | 1.45 | 1.97 | 2.29 | 2.81 | 3.73 |
Table 4.
Overall assessment of IGA-VND strategies
| Average relative gap for NS (%) | Ave | ||||||||
| Exp | | Iter | 60 | 120 | 180 | 240 | 300 | Global | time (s) |
| E1 | 0.20 | 50 | 0.87 | 1.44 | 1.64 | 2.26 | 3.63 | 1.97 | 1,902 |
| E2 | 0.20 | 50 | 0.83 | 1.38 | 1.67 | 2.21 | 3.61 | 1.94 | 1,907 |
| E3 | 0.20 | 50 | 0.68 | 0.97 | 1.49 | 2.03 | 3.06 | 1.65 | 1,743 |
| E4 | 0.20 | 100 | 0.67 | 0.97 | 1.45 | 2.02 | 3.06 | 1.64 | 2,495 |
| E5 | 0.10 | 50 | 0.67 | 1.05 | 1.58 | 2.04 | 3.11 | 1.69 | 1,550 |
| Method: | |||||||||
| E1 = IGA2_VND1 | |||||||||
| E2 = IGA2_VND1_LS4 | |||||||||
| E3 = CM1_IGA2_VND1_LS4 | |||||||||
| E4 = CM1_IGA2_VND1_LS4 | |||||||||
| E5 = CM1_IGA2_VND1_LS4 | |||||||||
| Average relative gap for NS (%) | Ave | ||||||||
| Exp | | Iter | 60 | 120 | 180 | 240 | 300 | Global | time (s) |
| E1 | 0.20 | 50 | 0.87 | 1.44 | 1.64 | 2.26 | 3.63 | 1.97 | 1,902 |
| E2 | 0.20 | 50 | 0.83 | 1.38 | 1.67 | 2.21 | 3.61 | 1.94 | 1,907 |
| E3 | 0.20 | 50 | 0.68 | 0.97 | 1.49 | 2.03 | 3.06 | 1.65 | 1,743 |
| E4 | 0.20 | 100 | 0.67 | 0.97 | 1.45 | 2.02 | 3.06 | 1.64 | 2,495 |
| E5 | 0.10 | 50 | 0.67 | 1.05 | 1.58 | 2.04 | 3.11 | 1.69 | 1,550 |
| Method: | |||||||||
| E1 = IGA2_VND1 | |||||||||
| E2 = IGA2_VND1_LS4 | |||||||||
| E3 = CM1_IGA2_VND1_LS4 | |||||||||
| E4 = CM1_IGA2_VND1_LS4 | |||||||||
| E5 = CM1_IGA2_VND1_LS4 | |||||||||
Table 5.
Assessment of individual components
| Omitted | Average relative gap for NS (%) | Ave. time (s) | ||||||||
| M | component | 60 | 120 | 180 | 240 | 300 | Global | Shift | Global | Shift |
| M1 | Neither | 0.68 | 0.97 | 1.49 | 2.03 | 3.06 | 1.65 | 1,743 | ||
| M2 | LS4 | 0.73 | 1.06 | 1.54 | 2.08 | 3.12 | 1.71 | 1,781 | | |
| M3 | CM1 | 0.83 | 1.38 | 1.67 | 2.21 | 3.61 | 1.94 | 1,907 | | |
| M4 | VND1 | 1.13 | 1.42 | 1.98 | 2.67 | 3.66 | 2.17 | 603 | | |
| M5 | IGA2 | 0.96 | 1.72 | 2.10 | 2.62 | 3.54 | 2.19 | 46 | | |
| Method: | ||||||||||
| M1 = CM1_IGA2_VND1_LS4 | ||||||||||
| M2 = CM1_IGA2_VND1 | ||||||||||
| M3 = IGA2_VND1_LS4 | ||||||||||
| M4 = CM1_IGA2_LS4 | ||||||||||
| M5 = CM1_VND1_LS4 | ||||||||||
| Omitted | Average relative gap for NS (%) | Ave. time (s) | ||||||||
| M | component | 60 | 120 | 180 | 240 | 300 | Global | Shift | Global | Shift |
| M1 | Neither | 0.68 | 0.97 | 1.49 | 2.03 | 3.06 | 1.65 | 1,743 | ||
| M2 | LS4 | 0.73 | 1.06 | 1.54 | 2.08 | 3.12 | 1.71 | 1,781 | | |
| M3 | CM1 | 0.83 | 1.38 | 1.67 | 2.21 | 3.61 | 1.94 | 1,907 | | |
| M4 | VND1 | 1.13 | 1.42 | 1.98 | 2.67 | 3.66 | 2.17 | 603 | | |
| M5 | IGA2 | 0.96 | 1.72 | 2.10 | 2.62 | 3.54 | 2.19 | 46 | | |
| Method: | ||||||||||
| M1 = CM1_IGA2_VND1_LS4 | ||||||||||
| M2 = CM1_IGA2_VND1 | ||||||||||
| M3 = IGA2_VND1_LS4 | ||||||||||
| M4 = CM1_IGA2_LS4 | ||||||||||
| M5 = CM1_VND1_LS4 | ||||||||||
Table 6.
Comparison between IGA-VND and B&B
| Average relative gap for NS (%) | |||||
| Method | 60 | 120 | 180 | 240 | 300 |
| B&B | 0.32 | 2.24 | 6.98 | 20.94 | 43.96 |
| CM1_IGA2_VND1_LS4 | 0.68 | 0.97 | 1.49 | 2.03 | 3.06 |
| Average run-time for NS (s) | |||||
| Method | 60 | 120 | 180 | 240 | 300 |
| B&B | 6,755 | 10,566 | 10,654 | 10,693 | 10,761 |
| CM1_IGA2_VND1_LS4 | 105 | 562 | 1,720 | 3,529 | 6,542 |
| Average relative gap for NS (%) | |||||
| Method | 60 | 120 | 180 | 240 | 300 |
| B&B | 0.32 | 2.24 | 6.98 | 20.94 | 43.96 |
| CM1_IGA2_VND1_LS4 | 0.68 | 0.97 | 1.49 | 2.03 | 3.06 |
| Average run-time for NS (s) | |||||
| Method | 60 | 120 | 180 | 240 | 300 |
| B&B | 6,755 | 10,566 | 10,654 | 10,693 | 10,761 |
| CM1_IGA2_VND1_LS4 | 105 | 562 | 1,720 | 3,529 | 6,542 |
| [1] |
Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 |
| [2] |
Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial and Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059 |
| [3] |
Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045 |
| [4] |
Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179 |
| [5] |
Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058 |
| [6] |
Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99 |
| [7] |
Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 |
| [8] |
Hongzhi Lin, Min Xu, Chi Xie. Location and capacity planning for preventive healthcare facilities with congestion effects. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022076 |
| [9] |
Omer Faruk Yilmaz, Mehmet Bulent Durmusoglu. A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007 |
| [10] |
Lu Han, Min Li, Dachuan Xu, Dongmei Zhang. Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2607-2614. doi: 10.3934/jimo.2020085 |
| [11] |
Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 |
| [12] |
Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial and Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31 |
| [13] |
Feng Bao, Thomas Maier. Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems. Foundations of Data Science, 2020, 2 (1) : 1-17. doi: 10.3934/fods.2020001 |
| [14] |
Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 |
| [15] |
Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213 |
| [16] |
Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67 |
| [17] |
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 |
| [18] |
Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020 |
| [19] |
Abdulkarim Hassan Ibrahim, Jitsupa Deepho, Auwal Bala Abubakar, Kazeem Olalekan Aremu. A modified Liu-Storey-Conjugate descent hybrid projection method for convex constrained nonlinear equations and image restoration. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021022 |
| [20] |
Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]