A matheuristic approach to the integration of worker assignment and vehicle routing problems: Application to home healthcare scheduling

• Published in: Expert systems with applications 2019-07, Vol.125, p.317-332
• Main Authors: Moussavi, S.E., Mahdjoub, M., Grunder, O.
• Format: Article
• Language: English
• Subjects: Combinatorial analysis; Computing time; Generalized assignment problem; Health care; Home health care; Home healthcare routing and scheduling; Human resource planning; Humanities and Social Sciences; Mathematical models; Matheuristic optimization algorithm; Optimization; Patients; Route planning; Schedules; Sequences; Statistical analysis; Vehicle routing
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2019.02.009

•A human resource planning for a home healthcare system based on the SGAP formulation.•Developing a planning for a duration of multiple days considering the off-days.•An optimization model to integrate the Assignment and Vehicle Routing problems.•A matheuristic based on the decomposition of the formulation to simplify the model.•A statistical analysis to evaluate the proposed optimization approaches. To model a home health care planning problem by classical VRP and AP formulation, the dimensions of the problem are: 1. The staff, 2. The patients, 3. The routes (sequence of the patients for each staff member). In this study, we present an extension of the home health care planning problem by adding the extra dimension of time so that the staff are not only assigned to the patients, but they are also assigned to daily periods. The scope of the planning problem extends to multiple days in which the patient required services vary from one day to another. Hence, the problem concerns a sequence of schedules (one schedule for each day) for the staff members. This variant of the home health care planning problem is modeled mathematically by employing the sequencing generalized assignment formulation and solved by applying the Gurobi mixed-integer solver. Considering that the studied combinatorial optimization is NP-complete, a matheuristic approach based on the decomposition of the formulation is proposed in this research to simplify the mathematical model and reduce the computational time needed to solve the problem. The numerical experiences and statistical analysis show that our matheuristic approach solves 90% of the instances to optimality with a significant reduction in the computational times.