A hybrid memetic-ant colony optimization algorithm for the home health care problem with time window, synchronization and working time balancing

被引:75
作者
Decerle, Jeremy [1 ]
Grunder, Olivier [1 ]
El Hassani, Amir Hajjam [1 ]
Barakat, Oussama [2 ]
机构
[1] Univ Bourgogne Franche Comte, Nanomed Lab, UTBM, F-90010 Belfort, France
[2] Univ Bourgogne Franche Comte, Nanomed Lab, F-25000 Besancon, France
关键词
Home health care; Memetic algorithm; Ant colony optimization; Workload balance; VEHICLE-ROUTING PROBLEM; PRECEDENCE; SYSTEM;
D O I
10.1016/j.swevo.2019.02.009
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper addresses the routing and scheduling of caregivers in a home health care problem. In order to obtain a valid planning, some skill, time window, and synchronization constraints must be met. Since the increase in demand, organizations providing home health care are eager to optimize the planning of caregivers which is often performed manually. Thus, many works have emerged on this research problem, taking into account new constraints gradually. One interesting aspect is the workload balancing between caregivers. Indeed, the workload must be roughly the same to obtain fairness. Already applied successfully to similar problems, the ant colony optimization algorithm has never been applied to the home health care problem. As a result, an original hybrid algorithm combining memetic and ant colony optimization algorithm is suggested for solving the home health care problem with working time balancing. Computational results on benchmark instances from the literature highlight the efficiency of the proposed hybrid algorithm in comparison with other metaheuristics and a commercial optimization solver.
引用
收藏
页码:171 / 183
页数:13
相关论文
共 45 条
[1]   Heuristic solutions for the vehicle routing problem with time windows and synchronized visits [J].
Afifi, Sohaib ;
Dang, Duc-Cuong ;
Moukrim, Aziz .
OPTIMIZATION LETTERS, 2016, 10 (03) :511-525
[2]   PSO-based algorithm for home care worker scheduling in the UK [J].
Akjiratikarl, Chananes ;
Yenradee, Pisal ;
Drake, Paul R. .
COMPUTERS & INDUSTRIAL ENGINEERING, 2007, 53 (04) :559-583
[3]  
[Anonymous], THESIS
[4]  
[Anonymous], 2013, Electron. Notes Discrete Math., DOI [10.1016/j.endm.2013.05, DOI 10.1016/J.ENDM.2013.05]
[5]  
[Anonymous], 2016, Gurobi optimizer reference manual
[6]   An integrated spatial DSS for scheduling and routing home-health-care nurses [J].
Begur, SV ;
Miller, DM ;
Weaver, JR .
INTERFACES, 1997, 27 (04) :35-48
[7]  
Bertrand D., 2010, ETUDES RESULTATS, V739
[8]   A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience [J].
Braekers, Kris ;
Hartl, Richard F. ;
Parragh, Sophie N. ;
Tricoire, Fabien .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 248 (02) :428-443
[9]   Combined vehicle routing and scheduling with temporal precedence and synchronization constraints [J].
Bredstrom, David ;
Ronnqvist, Mikael .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 191 (01) :19-31
[10]   A Multi-Facet Survey on Memetic Computation [J].
Chen, Xianshun ;
Ong, Yew-Soon ;
Lim, Meng-Hiot ;
Tan, Kay Chen .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2011, 15 (05) :591-607