Figure 1.
Pseudo code for the hybrid VNS-DP approach
-
Previous Article
Multiobjective mathematical models and solution approaches for heterogeneous fixed fleet vehicle routing problems
- JIMO Home
- This Issue
-
Next Article
Selecting the supply chain financing mode under price-sensitive demand: Confirmed warehouse financing vs. trade credit
July
2021, 17(4): 2051-2072.
doi: 10.3934/jimo.2020058
A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem
| 1. | Industrial Engineering and Systems Management, Egypt-Japan University of Science and Technology, New Borg Elarab City, Alexandria 21934, Egypt |
| 2. | Mechanical Engineering Department, Faculty of Engineering, Fayoum University, Fayoum, Egypt |
| 3. | Industrial Engineering and Economics, School of Engineering, Tokyo Institute of Technology, Tokyo, Japan |
Nurse Rostering is the activity of assigning nurses to daily shifts in order to satisfy the cover requirements, taking into account the operational requirements and nurses' preferences. The problem is usually modeled as sets of hard and soft constraints with an objective function to minimize violations of soft constraints. The nurse rostering problem is known to be NP-hard. Many metaheuristics were used to tackle this problem. One of the frequently used heuristics is the Variable Neighbourhood Search (VNS). The VNS is usually used as a standalone method or in integration with another exact or heuristic method. In this paper, a new hybrid VNS and Dynamic Programming based heuristic approach is proposed to handle the nurse rostering problem. In the proposed approach, two perturbation mechanisms are adopted simultaneously. The proposed approach is tested on two different benchmark data sets. A comparison with state-of-the-art methods from literature revealed the competitive performance of the proposed approach.
Keywords:
Variable neighbourhood search,
heuristics,
dynamic programming,
nurse rostering,
timetabling.
Mathematics Subject Classification:
Primary: 90B35; Secondary: 90C59, 90C39.
Citation:
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
![]()
References:
| [1] |
M. Abdelgalil, Z. Yahia and A. B. Eltawil, A proposed new dynamic programming formulation for the nurse rostering problem, in Proceedings of 47th International Conference on Computers and Industrial Engineering, 2017, 1–8. |
| [2] |
H. Akita and A. Ikegami,
A network representation of feasible solution space for a subproblem of nurse scheduling, Proceedings of the Institute of Statistical Mathematics, 61 (2013), 79-95.
|
| [3] |
G. Alpan, R. Larbi and B. Penz,
A bounded dynamic programming approach to schedule operations in a cross docking platform, Computers and Industrial Engineering, 60 (2011), 385-396.
doi: 10.1016/j.cie.2010.08.012. |
| [4] |
M. A. Awadallah, M. A. Al-Betar, A. T. Khader, A. L. Bolaji and M. Alkoffash,
Hybridization of harmony search with hill climbing for highly constrained nurse rostering problem, Neural Computing and Applications, 28 (2017), 463-482.
doi: 10.1007/s00521-015-2076-8. |
| [5] |
J. Bautista and J. Pereira,
A dynamic programming based heuristic for the assembly line balancing problem, European Journal of Operational Research, 194 (2009), 787-794.
doi: 10.1016/j.ejor.2008.01.016. |
| [6] |
F. Bellanti, G. Carello, F. Della Croce and R. Tadei,
A greedy-based neighborhood search approach to a nurse rostering problem, European Journal of Operational Research, 153 (2004), 28-40.
doi: 10.1016/S0377-2217(03)00096-1. |
| [7] |
S. Bouajaja and N. Dridi,
A survey on human resource allocation problem and its applications, Operational Research, 17 (2017), 339-369.
doi: 10.1007/s12351-016-0247-8. |
| [8] |
J. D. Bunton, A. T. Ernst and M. Krishnamoorthy,
An integer programming based ant colony optimisation method for nurse rostering, Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, 11 (2017), 407-414.
doi: 10.15439/2017F237. |
| [9] |
E. Burke, P. De Causmaecker, S. Petrovic and G. V. Berghe, Variable neighborhood search for nurse rostering problems, in Metaheuristics: Computer Decision-Making, Springer, Boston, MA, 2003,153–172.
doi: 10.1007/978-1-4757-4137-7_7. |
| [10] |
E. K. Burke, T. Curtois, G. Post, R. Qu and B. Veltman,
A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem, European Journal of Operational Research, 188 (2008), 330-341.
doi: 10.1016/j.ejor.2007.04.030. |
| [11] |
E. K. Burke and T. Curtois,
New approaches to nurse rostering benchmark instances, European Journal of Operational Research, 237 (2014), 71-81.
doi: 10.1016/j.ejor.2014.01.039. |
| [12] |
E. K. Burke, J. Li and R. Qu,
A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems, European Journal of Operational Research, 203 (2010), 484-493.
doi: 10.1016/j.ejor.2009.07.036. |
| [13] |
E. K. Burke, T. Curtois, L. F. van Draat, J. Van Ommeren and G. Post,
Progress control in iterated local search for nurse rostering, Journal of the Operational Research Society, 62 (2011), 360-367.
doi: 10.1057/jors.2010.86. |
| [14] |
S. Ceschia, N. Dang, P. De Causmaecker, S. Haspeslagh and A. Schaerf, Second international nurse rostering competition, Annals of Operations Research, 274 (2019), 171–186, arXiv: 1501.04177.
doi: 10.1007/s10479-018-2816-0. |
| [15] |
T. Curtois and R. Qu, Technical Report: Computational Results on New Staff Scheduling Benchmark Instances, ASAP Research Group, School of Computer Science, University of Nottingham, UK, 2014. |
| [16] |
F. Della Croce and F. Salassa,
A variable neighborhood search based matheuristic for nurse rostering problems, Annals of Operations Research, 218 (2014), 185-199.
doi: 10.1007/s10479-012-1235-x. |
| [17] |
J. Van den Bergh, J. Beliën, P. De Bruecker, E. Demeulemeester and L. De Boeck,
Personnel scheduling: A literature review, European Journal of Operational Research, 226 (2013), 367-385.
doi: 10.1016/j.ejor.2012.11.029. |
| [18] |
S. C. Gao and C. W. Lin, Particle swarm optimization based nurses' shift scheduling, in Proceedings of the Institute of Industrial Engineers Asian Conference 2013, 2013,775–782.
doi: 10.1007/978-981-4451-98-7_93. |
| [19] |
R. A. M. Gomes, T. A. M. Toffolo and H. G. Santos,
Variable neighborhood search accelerated column generation for the nurse rostering problem, Electronic Notes in Discrete Mathematics, 58 (2017), 31-38.
doi: 10.1016/j.endm.2017.03.005. |
| [20] |
M. Hadwan, M. Ayob, N. R. Sabar and R. Qu,
A harmony search algorithm for nurse rostering problems, Information Sciences, 233 (2013), 126-140.
doi: 10.1016/j.ins.2012.12.025. |
| [21] |
S. Haspeslagh, P. De Causmaecker, A. Schaerf and M. Stølevik,
The first international nurse rostering competition 2010, Annals of Operations Research, 218 (2014), 221-236.
doi: 10.1007/s10479-012-1062-0. |
| [22] |
F. Knust and L. Xie,
Simulated annealing approach to nurse rostering benchmark and real-world instances, Annals of Operations Research, 272 (2019), 187-216.
doi: 10.1007/s10479-017-2546-8. |
| [23] |
Z. Lü and J.-K. Hao,
Adaptive neighborhood search for nurse rostering, European Journal of Operational Research, 218 (2012), 865-876.
|
| [24] |
R. M'Hallah and A. Alkhabbaz,
Scheduling of nurses: A case study of a Kuwaiti health care unit, Operations Research for Health Care, 2 (2013), 1-19.
doi: 10.1016/j.orhc.2013.03.003. |
| [25] |
N. Musliu and F. Winter,
A hybrid approach for the sudoku problem: Using constraint programming in iterated local search, IEEE Intelligent Systems, 32 (2017), 52-62.
doi: 10.1109/MIS.2017.29. |
| [26] |
F. Mischek and N. Musliu,
Integer programming model extensions for a multi-stage nurse rostering problem, Annals of Operations Research, 275 (2019), 123-143.
doi: 10.1007/s10479-017-2623-z. |
| [27] |
E. Rahimian, K. Akartunali and J. Levine,
A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems, European Journal of Operational Research, 258 (2017), 411-423.
doi: 10.1016/j.ejor.2016.09.030. |
| [28] |
E. Rahimian, K. Akartunali and J. Levine,
A hybrid integer and constraint programming approach to solve nurse rostering problems, Computers and Operations Research, 82 (2017), 83-94.
doi: 10.1016/j.cor.2017.01.016. |
| [29] |
H. G. Santos, T. A. M. Toffolo, R. A. M. Gomes and S. Ribas,
Integer programming techniques for the nurse rostering problem, Annals of Operations Research, 239 (2016), 225-251.
doi: 10.1007/s10479-014-1594-6. |
| [30] |
A. M. Shahidin, M. S. M. Said, N. H. M. Said and N. I. A. Sazali, Developing optimal nurses work schedule using integer programming, AIP Conference Proceedings, 1870 (2017), 040031.
doi: 10.1063/1.4995863. |
| [31] |
P. Smet, P. Brucker, P. D. Causmaecker and G. V. Berghe,
Polynomially solvable personnel rostering problems, European Journal of Operational Research, 249 (2016), 67-75.
doi: 10.1016/j.ejor.2015.08.025. |
| [32] |
I. P. Solos, I. X. Tassopoulos and G. N. Beligiannis,
A generic two-phase stochastic variable neighborhood approach for effectively solving the nurse rostering problem, Algorithms, 6 (2013), 278-308.
doi: 10.3390/a6020278. |
| [33] |
I. X. Tassopoulos, I. P. Solos and G. N. Beligiannis,
A two-phase adaptive variable neighborhood approach for nurse rostering, Computers and Operations Research, 60 (2015), 150-169.
doi: 10.1016/j.cor.2015.02.009. |
| [34] |
T.-H. Wu, J.-Y. Yeh and Y.-M. Lee,
A particle swarm optimization approach with refinement procedure for nurse rostering problem, Computers and Operations Research, 54 (2015), 52-63.
doi: 10.1016/j.cor.2014.08.016. |
| [35] |
Z. Zheng and X. Gong, Chemical reaction optimization for nurse rostering problem,, in Frontier and Future Development of Information Technology in Medicine and Education, Springer, Dordrecht, 2014, 3275–3279.
doi: 10.1007/978-94-007-7618-0_422. |
| [36] |
Z. Zheng, X. Liu and X. Gong,
A simple randomized variable neighbourhood search for nurse rostering, Computers and Industrial Engineering, 110 (2017), 165-174.
doi: 10.1016/j.cie.2017.05.027. |
| [37] |
, Instances & Results – Nurse Rostering Competition, (Accessed: April 25, 2019), https://www.kuleuven-kulak.be/nrpcompetition/instances-results. |
show all references
References:
| [1] |
M. Abdelgalil, Z. Yahia and A. B. Eltawil, A proposed new dynamic programming formulation for the nurse rostering problem, in Proceedings of 47th International Conference on Computers and Industrial Engineering, 2017, 1–8. |
| [2] |
H. Akita and A. Ikegami,
A network representation of feasible solution space for a subproblem of nurse scheduling, Proceedings of the Institute of Statistical Mathematics, 61 (2013), 79-95.
|
| [3] |
G. Alpan, R. Larbi and B. Penz,
A bounded dynamic programming approach to schedule operations in a cross docking platform, Computers and Industrial Engineering, 60 (2011), 385-396.
doi: 10.1016/j.cie.2010.08.012. |
| [4] |
M. A. Awadallah, M. A. Al-Betar, A. T. Khader, A. L. Bolaji and M. Alkoffash,
Hybridization of harmony search with hill climbing for highly constrained nurse rostering problem, Neural Computing and Applications, 28 (2017), 463-482.
doi: 10.1007/s00521-015-2076-8. |
| [5] |
J. Bautista and J. Pereira,
A dynamic programming based heuristic for the assembly line balancing problem, European Journal of Operational Research, 194 (2009), 787-794.
doi: 10.1016/j.ejor.2008.01.016. |
| [6] |
F. Bellanti, G. Carello, F. Della Croce and R. Tadei,
A greedy-based neighborhood search approach to a nurse rostering problem, European Journal of Operational Research, 153 (2004), 28-40.
doi: 10.1016/S0377-2217(03)00096-1. |
| [7] |
S. Bouajaja and N. Dridi,
A survey on human resource allocation problem and its applications, Operational Research, 17 (2017), 339-369.
doi: 10.1007/s12351-016-0247-8. |
| [8] |
J. D. Bunton, A. T. Ernst and M. Krishnamoorthy,
An integer programming based ant colony optimisation method for nurse rostering, Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, 11 (2017), 407-414.
doi: 10.15439/2017F237. |
| [9] |
E. Burke, P. De Causmaecker, S. Petrovic and G. V. Berghe, Variable neighborhood search for nurse rostering problems, in Metaheuristics: Computer Decision-Making, Springer, Boston, MA, 2003,153–172.
doi: 10.1007/978-1-4757-4137-7_7. |
| [10] |
E. K. Burke, T. Curtois, G. Post, R. Qu and B. Veltman,
A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem, European Journal of Operational Research, 188 (2008), 330-341.
doi: 10.1016/j.ejor.2007.04.030. |
| [11] |
E. K. Burke and T. Curtois,
New approaches to nurse rostering benchmark instances, European Journal of Operational Research, 237 (2014), 71-81.
doi: 10.1016/j.ejor.2014.01.039. |
| [12] |
E. K. Burke, J. Li and R. Qu,
A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems, European Journal of Operational Research, 203 (2010), 484-493.
doi: 10.1016/j.ejor.2009.07.036. |
| [13] |
E. K. Burke, T. Curtois, L. F. van Draat, J. Van Ommeren and G. Post,
Progress control in iterated local search for nurse rostering, Journal of the Operational Research Society, 62 (2011), 360-367.
doi: 10.1057/jors.2010.86. |
| [14] |
S. Ceschia, N. Dang, P. De Causmaecker, S. Haspeslagh and A. Schaerf, Second international nurse rostering competition, Annals of Operations Research, 274 (2019), 171–186, arXiv: 1501.04177.
doi: 10.1007/s10479-018-2816-0. |
| [15] |
T. Curtois and R. Qu, Technical Report: Computational Results on New Staff Scheduling Benchmark Instances, ASAP Research Group, School of Computer Science, University of Nottingham, UK, 2014. |
| [16] |
F. Della Croce and F. Salassa,
A variable neighborhood search based matheuristic for nurse rostering problems, Annals of Operations Research, 218 (2014), 185-199.
doi: 10.1007/s10479-012-1235-x. |
| [17] |
J. Van den Bergh, J. Beliën, P. De Bruecker, E. Demeulemeester and L. De Boeck,
Personnel scheduling: A literature review, European Journal of Operational Research, 226 (2013), 367-385.
doi: 10.1016/j.ejor.2012.11.029. |
| [18] |
S. C. Gao and C. W. Lin, Particle swarm optimization based nurses' shift scheduling, in Proceedings of the Institute of Industrial Engineers Asian Conference 2013, 2013,775–782.
doi: 10.1007/978-981-4451-98-7_93. |
| [19] |
R. A. M. Gomes, T. A. M. Toffolo and H. G. Santos,
Variable neighborhood search accelerated column generation for the nurse rostering problem, Electronic Notes in Discrete Mathematics, 58 (2017), 31-38.
doi: 10.1016/j.endm.2017.03.005. |
| [20] |
M. Hadwan, M. Ayob, N. R. Sabar and R. Qu,
A harmony search algorithm for nurse rostering problems, Information Sciences, 233 (2013), 126-140.
doi: 10.1016/j.ins.2012.12.025. |
| [21] |
S. Haspeslagh, P. De Causmaecker, A. Schaerf and M. Stølevik,
The first international nurse rostering competition 2010, Annals of Operations Research, 218 (2014), 221-236.
doi: 10.1007/s10479-012-1062-0. |
| [22] |
F. Knust and L. Xie,
Simulated annealing approach to nurse rostering benchmark and real-world instances, Annals of Operations Research, 272 (2019), 187-216.
doi: 10.1007/s10479-017-2546-8. |
| [23] |
Z. Lü and J.-K. Hao,
Adaptive neighborhood search for nurse rostering, European Journal of Operational Research, 218 (2012), 865-876.
|
| [24] |
R. M'Hallah and A. Alkhabbaz,
Scheduling of nurses: A case study of a Kuwaiti health care unit, Operations Research for Health Care, 2 (2013), 1-19.
doi: 10.1016/j.orhc.2013.03.003. |
| [25] |
N. Musliu and F. Winter,
A hybrid approach for the sudoku problem: Using constraint programming in iterated local search, IEEE Intelligent Systems, 32 (2017), 52-62.
doi: 10.1109/MIS.2017.29. |
| [26] |
F. Mischek and N. Musliu,
Integer programming model extensions for a multi-stage nurse rostering problem, Annals of Operations Research, 275 (2019), 123-143.
doi: 10.1007/s10479-017-2623-z. |
| [27] |
E. Rahimian, K. Akartunali and J. Levine,
A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems, European Journal of Operational Research, 258 (2017), 411-423.
doi: 10.1016/j.ejor.2016.09.030. |
| [28] |
E. Rahimian, K. Akartunali and J. Levine,
A hybrid integer and constraint programming approach to solve nurse rostering problems, Computers and Operations Research, 82 (2017), 83-94.
doi: 10.1016/j.cor.2017.01.016. |
| [29] |
H. G. Santos, T. A. M. Toffolo, R. A. M. Gomes and S. Ribas,
Integer programming techniques for the nurse rostering problem, Annals of Operations Research, 239 (2016), 225-251.
doi: 10.1007/s10479-014-1594-6. |
| [30] |
A. M. Shahidin, M. S. M. Said, N. H. M. Said and N. I. A. Sazali, Developing optimal nurses work schedule using integer programming, AIP Conference Proceedings, 1870 (2017), 040031.
doi: 10.1063/1.4995863. |
| [31] |
P. Smet, P. Brucker, P. D. Causmaecker and G. V. Berghe,
Polynomially solvable personnel rostering problems, European Journal of Operational Research, 249 (2016), 67-75.
doi: 10.1016/j.ejor.2015.08.025. |
| [32] |
I. P. Solos, I. X. Tassopoulos and G. N. Beligiannis,
A generic two-phase stochastic variable neighborhood approach for effectively solving the nurse rostering problem, Algorithms, 6 (2013), 278-308.
doi: 10.3390/a6020278. |
| [33] |
I. X. Tassopoulos, I. P. Solos and G. N. Beligiannis,
A two-phase adaptive variable neighborhood approach for nurse rostering, Computers and Operations Research, 60 (2015), 150-169.
doi: 10.1016/j.cor.2015.02.009. |
| [34] |
T.-H. Wu, J.-Y. Yeh and Y.-M. Lee,
A particle swarm optimization approach with refinement procedure for nurse rostering problem, Computers and Operations Research, 54 (2015), 52-63.
doi: 10.1016/j.cor.2014.08.016. |
| [35] |
Z. Zheng and X. Gong, Chemical reaction optimization for nurse rostering problem,, in Frontier and Future Development of Information Technology in Medicine and Education, Springer, Dordrecht, 2014, 3275–3279.
doi: 10.1007/978-94-007-7618-0_422. |
| [36] |
Z. Zheng, X. Liu and X. Gong,
A simple randomized variable neighbourhood search for nurse rostering, Computers and Industrial Engineering, 110 (2017), 165-174.
doi: 10.1016/j.cie.2017.05.027. |
| [37] |
, Instances & Results – Nurse Rostering Competition, (Accessed: April 25, 2019), https://www.kuleuven-kulak.be/nrpcompetition/instances-results. |
Figure 2.
Pseudo code for VNS algorithm
Figure 3.
Example for HWCF.1 structure
Figure 4.
Example for HWCF.2 structure
Figure 5.
Examples of vertical swaps
Figure 6.
Examples of horizontal swaps
Figure 7.
A dynamic programming structure for the nurse rostering problem
Figure 8.
Pseudo code for the proposed Dynamic Programming based heuristic algorithm
Table 1.
Benchmark instances main characteristics
| # | Days | Nurses | Shift types | Days-off | Shifts on/off |
| 01 | 14 | 8 | 1 | 8 | 26 |
| 02 | 14 | 14 | 2 | 14 | 62 |
| 03 | 14 | 20 | 3 | 20 | 64 |
| 04 | 28 | 10 | 2 | 20 | 71 |
| 05 | 28 | 16 | 2 | 32 | 106 |
| 06 | 28 | 18 | 3 | 36 | 135 |
| 07 | 28 | 20 | 3 | 40 | 168 |
| 08 | 28 | 30 | 4 | 60 | 225 |
| 09 | 28 | 36 | 4 | 72 | 232 |
| 10 | 28 | 40 | 5 | 80 | 284 |
| 11 | 28 | 50 | 6 | 100 | 336 |
| 12 | 28 | 60 | 10 | 120 | 422 |
| 13 | 28 | 120 | 18 | 240 | 841 |
| 14 | 42 | 32 | 4 | 128 | 359 |
| 15 | 42 | 45 | 6 | 180 | 490 |
| 16 | 56 | 20 | 3 | 120 | 280 |
| 17 | 56 | 30 | 4 | 160 | 480 |
| 18 | 84 | 22 | 3 | 176 | 414 |
| 19 | 84 | 40 | 5 | 320 | 834 |
| 20 | 182 | 50 | 6 | 900 | 2318 |
| 21 | 182 | 100 | 8 | 1800 | 4702 |
| 22 | 364 | 50 | 10 | 1800 | 4638 |
| 23 | 364 | 100 | 16 | 3600 | 9410 |
| 24 | 364 | 150 | 32 | 5400 | 13809 |
| # | Days | Nurses | Shift types | Days-off | Shifts on/off |
| 01 | 14 | 8 | 1 | 8 | 26 |
| 02 | 14 | 14 | 2 | 14 | 62 |
| 03 | 14 | 20 | 3 | 20 | 64 |
| 04 | 28 | 10 | 2 | 20 | 71 |
| 05 | 28 | 16 | 2 | 32 | 106 |
| 06 | 28 | 18 | 3 | 36 | 135 |
| 07 | 28 | 20 | 3 | 40 | 168 |
| 08 | 28 | 30 | 4 | 60 | 225 |
| 09 | 28 | 36 | 4 | 72 | 232 |
| 10 | 28 | 40 | 5 | 80 | 284 |
| 11 | 28 | 50 | 6 | 100 | 336 |
| 12 | 28 | 60 | 10 | 120 | 422 |
| 13 | 28 | 120 | 18 | 240 | 841 |
| 14 | 42 | 32 | 4 | 128 | 359 |
| 15 | 42 | 45 | 6 | 180 | 490 |
| 16 | 56 | 20 | 3 | 120 | 280 |
| 17 | 56 | 30 | 4 | 160 | 480 |
| 18 | 84 | 22 | 3 | 176 | 414 |
| 19 | 84 | 40 | 5 | 320 | 834 |
| 20 | 182 | 50 | 6 | 900 | 2318 |
| 21 | 182 | 100 | 8 | 1800 | 4702 |
| 22 | 364 | 50 | 10 | 1800 | 4638 |
| 23 | 364 | 100 | 16 | 3600 | 9410 |
| 24 | 364 | 150 | 32 | 5400 | 13809 |
Table 2.
Comparison for the performance of the VNS algorithm using classical and destroy-and-recreate perturbation mechanisms
| Instance | Classical mechanism | Destroy-and-recreate mechanism |
| 01 | 607 | 607 |
| 02 | 828 | 922 |
| 03 | 1001 | 1002 |
| 04 | 1721 | 1717 |
| 05 | 1249 | 1330 |
| 06 | 2053 | 2147 |
| 07 | 1077 | 1073 |
| 08 | 1425 | 1741 |
| 09 | 449 | 446 |
| 10 | 4679 | 4320 |
| 11 | 3458 | 3513 |
| 12 | 4217 | 4327 |
| 13 | 2423 | 2396 |
| 14 | 1377 | 1584 |
| 15 | 4996 | 5017 |
| 16 | 3550 | 3556 |
| 17 | 6391 | 6506 |
| 18 | 5177 | 5601 |
| 19 | 4789 | 5177 |
| 20 | 9097 | 7689 |
| 21 | 29486 | 27071 |
| 22 | 61690 | 58226 |
| 23 | 62195 | 53694 |
| 24 | 402313 | 248016 |
| Instance | Classical mechanism | Destroy-and-recreate mechanism |
| 01 | 607 | 607 |
| 02 | 828 | 922 |
| 03 | 1001 | 1002 |
| 04 | 1721 | 1717 |
| 05 | 1249 | 1330 |
| 06 | 2053 | 2147 |
| 07 | 1077 | 1073 |
| 08 | 1425 | 1741 |
| 09 | 449 | 446 |
| 10 | 4679 | 4320 |
| 11 | 3458 | 3513 |
| 12 | 4217 | 4327 |
| 13 | 2423 | 2396 |
| 14 | 1377 | 1584 |
| 15 | 4996 | 5017 |
| 16 | 3550 | 3556 |
| 17 | 6391 | 6506 |
| 18 | 5177 | 5601 |
| 19 | 4789 | 5177 |
| 20 | 9097 | 7689 |
| 21 | 29486 | 27071 |
| 22 | 61690 | 58226 |
| 23 | 62195 | 53694 |
| 24 | 402313 | 248016 |
Table 3.
Comparison between the proposed VNS–DP approach and other methods in literature
| Instance | VNS–DP | Ejection chain | Gurobi | Branch & price | CP–ILS |
| 01 | 607 | 607 | 607 | 607 | 607 |
| 02 | 828 | 837 | 828 | 828 | 828 |
| 03 | 1001 | 1003 | 1001 | 1001 | 1001 |
| 04 | 1716 | 1718 | 1716 | 1716 | 1716 |
| 05 | 1237 | 1358 | 1143 | 1160 | 1147 |
| 06 | 2141 | 2258 | 1950 | 1952 | 2050 |
| 07 | 1080 | 1269 | 1056 | 1058 | 1084 |
| 08 | 1452 | 2260 | 1306 | 1308 | 1464 |
| 09 | 446 | 463 | 439 | 439 | 454 |
| 10 | 4656 | 4797 | 4631 | 4631 | 4667 |
| 11 | 3512 | 3661 | 3443 | 3443 | 3457 |
| 12 | 4119 | 5211 | 4040 | 4046 | 4308 |
| 13 | 2120 | 2663 | 3109 | – | 2961 |
| 14 | 1344 | 1847 | 1278 | – | 1432 |
| 15 | 4637 | 5935 | 4843 | – | 4570 |
| 16 | 3458 | 4048 | 3225 | 3323 | 3748 |
| 17 | 6190 | 7835 | 5749 | – | 6609 |
| 18 | 5095 | 6404 | 4760 | – | 5416 |
| 19 | 4281 | 5531 | 5078 | – | 4364 |
| 20 | 7274 | 9750 | 3591 | – | 6654 |
| 21 | 26263 | 36688 | 132445 | – | 22549 |
| 22 | 56091 | 516686 | 265504 | – | 48382 |
| 23 | 51699 | 54384 | – | – | 38337 |
| 24 | 226490 | 156858 | – | – | 177037 |
| Instance | VNS–DP | Ejection chain | Gurobi | Branch & price | CP–ILS |
| 01 | 607 | 607 | 607 | 607 | 607 |
| 02 | 828 | 837 | 828 | 828 | 828 |
| 03 | 1001 | 1003 | 1001 | 1001 | 1001 |
| 04 | 1716 | 1718 | 1716 | 1716 | 1716 |
| 05 | 1237 | 1358 | 1143 | 1160 | 1147 |
| 06 | 2141 | 2258 | 1950 | 1952 | 2050 |
| 07 | 1080 | 1269 | 1056 | 1058 | 1084 |
| 08 | 1452 | 2260 | 1306 | 1308 | 1464 |
| 09 | 446 | 463 | 439 | 439 | 454 |
| 10 | 4656 | 4797 | 4631 | 4631 | 4667 |
| 11 | 3512 | 3661 | 3443 | 3443 | 3457 |
| 12 | 4119 | 5211 | 4040 | 4046 | 4308 |
| 13 | 2120 | 2663 | 3109 | – | 2961 |
| 14 | 1344 | 1847 | 1278 | – | 1432 |
| 15 | 4637 | 5935 | 4843 | – | 4570 |
| 16 | 3458 | 4048 | 3225 | 3323 | 3748 |
| 17 | 6190 | 7835 | 5749 | – | 6609 |
| 18 | 5095 | 6404 | 4760 | – | 5416 |
| 19 | 4281 | 5531 | 5078 | – | 4364 |
| 20 | 7274 | 9750 | 3591 | – | 6654 |
| 21 | 26263 | 36688 | 132445 | – | 22549 |
| 22 | 56091 | 516686 | 265504 | – | 48382 |
| 23 | 51699 | 54384 | – | – | 38337 |
| 24 | 226490 | 156858 | – | – | 177037 |
Table 4.
Comparison between the proposed VNS-DP approach and IP-VNS approach
| Instance | VNS–DP | IP–VNS |
| 01 | 607 | 607 |
| 02 | 828 | 828 |
| 03 | 1001 | 1001 |
| 04 | 1716 | 1716 |
| 05 | 1237 | 1143 |
| 06 | 2141 | 1950 |
| 07 | 1080 | 1056 |
| 08 | 1452 | 1344 |
| 09 | 446 | 439 |
| 10 | 4656 | 4631 |
| 11 | 3512 | 3443 |
| 12 | 4119 | 4040 |
| 13 | 2120 | 1905 |
| 14 | 1344 | 1279 |
| 15 | 4637 | 3928 |
| 16 | 3458 | 3225 |
| 17 | 6190 | 5750 |
| 18 | 5095 | 4662 |
| 19 | 4281 | 3224 |
| 20 | 7274 | 4913 |
| 21 | 26263 | 23191 |
| 22 | 56091 | 32126 |
| 23 | 51699 | 3794 |
| 24 | 226490 | 2281440 |
| Instance | VNS–DP | IP–VNS |
| 01 | 607 | 607 |
| 02 | 828 | 828 |
| 03 | 1001 | 1001 |
| 04 | 1716 | 1716 |
| 05 | 1237 | 1143 |
| 06 | 2141 | 1950 |
| 07 | 1080 | 1056 |
| 08 | 1452 | 1344 |
| 09 | 446 | 439 |
| 10 | 4656 | 4631 |
| 11 | 3512 | 3443 |
| 12 | 4119 | 4040 |
| 13 | 2120 | 1905 |
| 14 | 1344 | 1279 |
| 15 | 4637 | 3928 |
| 16 | 3458 | 3225 |
| 17 | 6190 | 5750 |
| 18 | 5095 | 4662 |
| 19 | 4281 | 3224 |
| 20 | 7274 | 4913 |
| 21 | 26263 | 23191 |
| 22 | 56091 | 32126 |
| 23 | 51699 | 3794 |
| 24 | 226490 | 2281440 |
Table 5.
Comparison between results of the proposed VNS-DP approach and other state-of-the-art approaches tested on the competition instances
| Instance | BKS | VNS–DP | ANS | VDS | RVNS | HHSA |
| Sprint_early01 | 56 | 56 | 56 | 56 | 56 | 56 |
| Sprint_early02 | 58 | 58 | 58 | 58 | 58 | 58 |
| Sprint_early03 | 51 | 51 | 51 | 51 | 51 | 51 |
| Sprint_early04 | 59 | 59 | 59 | 59 | 59 | 59 |
| Sprint_early05 | 58 | 58 | 58 | 58 | 58 | 58 |
| Sprint_early06 | 54 | 54 | 54 | 54 | 54 | 54 |
| Sprint_early07 | 56 | 56 | 56 | 56 | 56 | 56 |
| Sprint_early08 | 56 | 56 | 56 | 56 | 56 | 56 |
| Sprint_early09 | 55 | 55 | 55 | 55 | 55 | 55 |
| Sprint_early10 | 52 | 52 | 52 | 52 | 52 | 52 |
| Sprint_late01 | 37 | 37 | 37 | 37 | 37 | 37 |
| Sprint_late02 | 42 | 42 | 42 | 42 | 42 | 42 |
| Sprint_late03 | 48 | 48 | 48 | 48 | 48 | 48 |
| Sprint_late04 | 73 | 73 | 73 | 75 | 73 | 73 |
| Sprint_late05 | 44 | 45 | 44 | 44 | 44 | 44 |
| Sprint_late06 | 42 | 43 | 42 | 42 | 42 | 42 |
| Sprint_late07 | 42 | 47 | 42 | 42 | 43 | 43 |
| Sprint_late08 | 17 | 17 | 17 | 17 | 17 | 17 |
| Sprint_late09 | 17 | 17 | 17 | 17 | 17 | 17 |
| Sprint_late10 | 43 | 44 | 43 | 43 | 43 | 43 |
| Sprint_hidden01 | 32 | 34 | 32 | – | 32 | 32 |
| Sprint_hidden02 | 32 | 32 | 32 | – | 32 | 32 |
| Sprint_hidden03 | 62 | 62 | 62 | – | 62 | 62 |
| Sprint_hidden04 | 66 | 67 | 66 | – | 66 | 66 |
| Sprint_hidden05 | 59 | 59 | 59 | – | 59 | 59 |
| Sprint_hidden06 | 130 | 141 | 130 | – | – | 130 |
| Sprint_hidden07 | 153 | 153 | 153 | – | – | 153 |
| Sprint_hidden08 | 204 | 204 | 204 | – | – | 204 |
| Sprint_hidden09 | 338 | 338 | 338 | – | – | 338 |
| Sprint_hidden10 | 306 | 306 | 306 | – | – | 306 |
| Medium_early01 | 240 | 243 | 240 | 244 | 240 | 243 |
| Medium_early02 | 240 | 241 | 240 | 241 | 240 | 242 |
| Medium_early03 | 236 | 238 | 236 | 238 | 236 | 238 |
| Medium_early04 | 237 | 240 | 237 | 240 | 237 | 240 |
| Medium_early05 | 303 | 303 | 303 | 308 | 303 | 305 |
| Medium_late01 | 157 | 157 | 164 | 187 | 158 | 169 |
| Medium_late02 | 18 | 31 | 20 | 22 | 20 | 26 |
| Medium_late03 | 29 | 29 | 30 | 46 | 30 | 34 |
| Medium_late04 | 35 | 35 | 36 | 49 | 35 | 42 |
| Medium_late05 | 107 | 140 | 117 | 161 | 111 | 131 |
| Medium_hidden01 | 111 | 111 | 122 | – | 117 | 143 |
| Medium_hidden02 | 219 | 219 | 224 | – | 225 | 248 |
| Medium_hidden03 | 34 | 34 | 35 | – | 34 | 49 |
| Medium_hidden04 | 78 | 78 | 80 | – | 79 | 87 |
| Medium_hidden05 | 118 | 118 | 120 | – | 122 | 169 |
| Long_early01 | 197 | 197 | 197 | 198 | 197 | 197 |
| Long_early02 | 219 | 221 | 222 | 223 | 219 | 226 |
| Long_early03 | 240 | 240 | 240 | 242 | 240 | 240 |
| Long_early04 | 303 | 303 | 303 | 305 | 303 | 303 |
| Long_early05 | 284 | 284 | 284 | 286 | 284 | 284 |
| Long_late01 | 235 | 240 | 237 | 286 | 235 | 253 |
| Long_late02 | 229 | 229 | 229 | 290 | 229 | 256 |
| Long_late03 | 220 | 220 | 222 | 290 | 221 | 256 |
| Long_late04 | 221 | 221 | 227 | 280 | 224 | 263 |
| Long_late05 | 83 | 89 | 83 | 110 | 83 | 98 |
| Long_hidden01 | 346 | 346 | 346 | – | 349 | 380 |
| Long_hidden02 | 89 | 89 | 89 | – | 89 | 110 |
| Long_hidden03 | 38 | 38 | 38 | – | 38 | 44 |
| Long_hidden04 | 22 | 22 | 22 | – | 22 | 27 |
| Long_hidden05 | 41 | 41 | 45 | – | 41 | 53 |
| Instance | BKS | VNS–DP | ANS | VDS | RVNS | HHSA |
| Sprint_early01 | 56 | 56 | 56 | 56 | 56 | 56 |
| Sprint_early02 | 58 | 58 | 58 | 58 | 58 | 58 |
| Sprint_early03 | 51 | 51 | 51 | 51 | 51 | 51 |
| Sprint_early04 | 59 | 59 | 59 | 59 | 59 | 59 |
| Sprint_early05 | 58 | 58 | 58 | 58 | 58 | 58 |
| Sprint_early06 | 54 | 54 | 54 | 54 | 54 | 54 |
| Sprint_early07 | 56 | 56 | 56 | 56 | 56 | 56 |
| Sprint_early08 | 56 | 56 | 56 | 56 | 56 | 56 |
| Sprint_early09 | 55 | 55 | 55 | 55 | 55 | 55 |
| Sprint_early10 | 52 | 52 | 52 | 52 | 52 | 52 |
| Sprint_late01 | 37 | 37 | 37 | 37 | 37 | 37 |
| Sprint_late02 | 42 | 42 | 42 | 42 | 42 | 42 |
| Sprint_late03 | 48 | 48 | 48 | 48 | 48 | 48 |
| Sprint_late04 | 73 | 73 | 73 | 75 | 73 | 73 |
| Sprint_late05 | 44 | 45 | 44 | 44 | 44 | 44 |
| Sprint_late06 | 42 | 43 | 42 | 42 | 42 | 42 |
| Sprint_late07 | 42 | 47 | 42 | 42 | 43 | 43 |
| Sprint_late08 | 17 | 17 | 17 | 17 | 17 | 17 |
| Sprint_late09 | 17 | 17 | 17 | 17 | 17 | 17 |
| Sprint_late10 | 43 | 44 | 43 | 43 | 43 | 43 |
| Sprint_hidden01 | 32 | 34 | 32 | – | 32 | 32 |
| Sprint_hidden02 | 32 | 32 | 32 | – | 32 | 32 |
| Sprint_hidden03 | 62 | 62 | 62 | – | 62 | 62 |
| Sprint_hidden04 | 66 | 67 | 66 | – | 66 | 66 |
| Sprint_hidden05 | 59 | 59 | 59 | – | 59 | 59 |
| Sprint_hidden06 | 130 | 141 | 130 | – | – | 130 |
| Sprint_hidden07 | 153 | 153 | 153 | – | – | 153 |
| Sprint_hidden08 | 204 | 204 | 204 | – | – | 204 |
| Sprint_hidden09 | 338 | 338 | 338 | – | – | 338 |
| Sprint_hidden10 | 306 | 306 | 306 | – | – | 306 |
| Medium_early01 | 240 | 243 | 240 | 244 | 240 | 243 |
| Medium_early02 | 240 | 241 | 240 | 241 | 240 | 242 |
| Medium_early03 | 236 | 238 | 236 | 238 | 236 | 238 |
| Medium_early04 | 237 | 240 | 237 | 240 | 237 | 240 |
| Medium_early05 | 303 | 303 | 303 | 308 | 303 | 305 |
| Medium_late01 | 157 | 157 | 164 | 187 | 158 | 169 |
| Medium_late02 | 18 | 31 | 20 | 22 | 20 | 26 |
| Medium_late03 | 29 | 29 | 30 | 46 | 30 | 34 |
| Medium_late04 | 35 | 35 | 36 | 49 | 35 | 42 |
| Medium_late05 | 107 | 140 | 117 | 161 | 111 | 131 |
| Medium_hidden01 | 111 | 111 | 122 | – | 117 | 143 |
| Medium_hidden02 | 219 | 219 | 224 | – | 225 | 248 |
| Medium_hidden03 | 34 | 34 | 35 | – | 34 | 49 |
| Medium_hidden04 | 78 | 78 | 80 | – | 79 | 87 |
| Medium_hidden05 | 118 | 118 | 120 | – | 122 | 169 |
| Long_early01 | 197 | 197 | 197 | 198 | 197 | 197 |
| Long_early02 | 219 | 221 | 222 | 223 | 219 | 226 |
| Long_early03 | 240 | 240 | 240 | 242 | 240 | 240 |
| Long_early04 | 303 | 303 | 303 | 305 | 303 | 303 |
| Long_early05 | 284 | 284 | 284 | 286 | 284 | 284 |
| Long_late01 | 235 | 240 | 237 | 286 | 235 | 253 |
| Long_late02 | 229 | 229 | 229 | 290 | 229 | 256 |
| Long_late03 | 220 | 220 | 222 | 290 | 221 | 256 |
| Long_late04 | 221 | 221 | 227 | 280 | 224 | 263 |
| Long_late05 | 83 | 89 | 83 | 110 | 83 | 98 |
| Long_hidden01 | 346 | 346 | 346 | – | 349 | 380 |
| Long_hidden02 | 89 | 89 | 89 | – | 89 | 110 |
| Long_hidden03 | 38 | 38 | 38 | – | 38 | 44 |
| Long_hidden04 | 22 | 22 | 22 | – | 22 | 27 |
| Long_hidden05 | 41 | 41 | 45 | – | 41 | 53 |
Table 6.
Comparison for number of best known solutions achieved by each approach
| Competition track | VNS–DP | ANS | HHSA |
| Sprint (30 instances) | 77% | 100% | 97% |
| Medium (15 instances) | 60% | 33% | 0% |
| Long (15 instances) | 80% | 67% | 27% |
| Competition track | VNS–DP | ANS | HHSA |
| Sprint (30 instances) | 77% | 100% | 97% |
| Medium (15 instances) | 60% | 33% | 0% |
| Long (15 instances) | 80% | 67% | 27% |
| [1] |
Ryan Loxton, Qun Lin. Optimal fleet composition via dynamic programming and golden section search. Journal of Industrial and Management Optimization, 2011, 7 (4) : 875-890. doi: 10.3934/jimo.2011.7.875 |
| [2] |
Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure and Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473 |
| [3] |
Jérôme Renault. General limit value in dynamic programming. Journal of Dynamics and Games, 2014, 1 (3) : 471-484. doi: 10.3934/jdg.2014.1.471 |
| [4] |
Nur Aidya Hanum Aizam, Louis Caccetta. Computational models for timetabling problem. Numerical Algebra, Control and Optimization, 2014, 4 (3) : 269-285. doi: 10.3934/naco.2014.4.269 |
| [5] |
Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439 |
| [6] |
Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics and Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013 |
| [7] |
Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial and Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1 |
| [8] |
Qing Liu, Armin Schikorra. General existence of solutions to dynamic programming equations. Communications on Pure and Applied Analysis, 2015, 14 (1) : 167-184. doi: 10.3934/cpaa.2015.14.167 |
| [9] |
Adrian Korban, Serap Sahinkaya, Deniz Ustun. New type I binary $[72, 36, 12]$ self-dual codes from $M_6(\mathbb{F}_2)G$ - Group matrix rings by a hybrid search technique based on a neighbourhood-virus optimisation algorithm. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022032 |
| [10] |
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 |
| [11] |
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 |
| [12] |
Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030 |
| [13] |
Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial and Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136 |
| [14] |
Haiying Liu, Wenjie Bi, Kok Lay Teo, Naxing Liu. Dynamic optimal decision making for manufacturers with limited attention based on sparse dynamic programming. Journal of Industrial and Management Optimization, 2019, 15 (2) : 445-464. doi: 10.3934/jimo.2018050 |
| [15] |
Min Sha. Heuristics of the Cocks-Pinch method. Advances in Mathematics of Communications, 2014, 8 (1) : 103-118. doi: 10.3934/amc.2014.8.103 |
| [16] |
Haibo Jin, Long Hai, Xiaoliang Tang. An optimal maintenance strategy for multi-state systems based on a system linear integral equation and dynamic programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 965-990. doi: 10.3934/jimo.2018188 |
| [17] |
Matthew H. Henry, Yacov Y. Haimes. Robust multiobjective dynamic programming: Minimax envelopes for efficient decisionmaking under scenario uncertainty. Journal of Industrial and Management Optimization, 2009, 5 (4) : 791-824. doi: 10.3934/jimo.2009.5.791 |
| [18] |
Jeongmin Han. Local Lipschitz regularity for functions satisfying a time-dependent dynamic programming principle. Communications on Pure and Applied Analysis, 2020, 19 (5) : 2617-2640. doi: 10.3934/cpaa.2020114 |
| [19] |
Martino Bardi, Shigeaki Koike, Pierpaolo Soravia. Pursuit-evasion games with state constraints: dynamic programming and discrete-time approximations. Discrete and Continuous Dynamical Systems, 2000, 6 (2) : 361-380. doi: 10.3934/dcds.2000.6.361 |
| [20] |
Silvia Faggian. Boundary control problems with convex cost and dynamic programming in infinite dimension part II: Existence for HJB. Discrete and Continuous Dynamical Systems, 2005, 12 (2) : 323-346. doi: 10.3934/dcds.2005.12.323 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]