Metaheuristics for solving a multimodal home-healthcare scheduling problem

被引:157
作者
Hiermann, Gerhard [1 ]
Prandtstetter, Matthias [2 ]
Rendl, Andrea [2 ]
Puchinger, Jakob [2 ]
Raidl, Guenther R. [1 ]
机构
[1] Vienna Univ Technol, Inst Comp Graph & Algorithms, A-1040 Vienna, Austria
[2] AIT Austrian Inst Technol GmbH, Mobil Dept, Dynam Transportat Syst, A-1210 Vienna, Austria
关键词
Home health care; Vehicle routing; Optimization; Metaheuristics; SCATTER SEARCH; METHODOLOGY;
D O I
10.1007/s10100-013-0305-8
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We present a general framework for solving a real-world multimodal home-healthcare scheduling (MHS) problem from a major Austrian home-healthcare provider. The goal of MHS is to assign home-care staff to customers and determine efficient multimodal tours while considering staff and customer satisfaction. Our approach is designed to be as problem-independent as possible, such that the resulting methods can be easily adapted to MHS setups of other home-healthcare providers. We chose a two-stage approach: in the first stage, we generate initial solutions either via constraint programming techniques or by a random procedure. During the second stage, the initial solutions are (iteratively) improved by applying one of four metaheuristics: variable neighborhood search, a memetic algorithm, scatter search and a simulated annealing hyper-heuristic. An extensive computational comparison shows that the approach is capable of solving real-world instances in reasonable time and produces valid solutions within only a few seconds.
引用
收藏
页码:89 / 113
页数:25
相关论文
共 31 条
[1]  
[Anonymous], MEMETIC ALGORITHMS S
[2]   A simulated annealing hyper-heuristic methodology for flexible decision support [J].
Bai, Ruibin ;
Blazewicz, Jacek ;
Burke, Edmund K. ;
Kendall, Graham ;
McCollum, Barry .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2012, 10 (01) :43-66
[3]   A Hybrid Evolutionary Approach to the Nurse Rostering Problem [J].
Bai, Ruibin ;
Burke, Edmund K. ;
Kendall, Graham ;
Li, Jingpeng ;
McCollum, Barry .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2010, 14 (04) :580-590
[4]   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
[5]   A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem [J].
Bertels, S ;
Fahle, T .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (10) :2866-2890
[6]   Vehicle routing problem with time windows, part 1:: Route construction and local search algorithms [J].
Bräysy, I ;
Gendreau, M .
TRANSPORTATION SCIENCE, 2005, 39 (01) :104-118
[7]   Vehicle routing problem with time windows, part II:: Metaheuristics [J].
Bräysy, I ;
Gendreau, M .
TRANSPORTATION SCIENCE, 2005, 39 (01) :119-139
[8]  
Burke E, 2003, INT SER OPER RES MAN, V57, P457, DOI 10.1007/0-306-48056-5_16
[9]   A scatter search methodology for the nurse rostering problem [J].
Burke, E. K. ;
Curtois, T. ;
Qu, R. ;
Vanden Berghe, G. .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2010, 61 (11) :1667-1679
[10]   The state of the art of nurse rostering [J].
Burke, EK ;
De Causmaecker, P ;
Vanden Berghe, G ;
Van Landeghem, H .
JOURNAL OF SCHEDULING, 2004, 7 (06) :441-499