A Two-Stage Approach for Solving Assignment and Routing Problems in Home Health Care Services

Human resource planning in Home Health Care (HHC) services is a critical activity that may also affect the quality of the delivered care. The assignment of the patient to operators together with their routing in the served territory are relevant problems that service providers have to deal with on a daily frequency. These problems can be either solved with a two-stage approach or with a simultaneous approach. The simultaneous approach enables to hold both assignment and routing decisions at the same time, however solving this problem is computationally difficult. The two-stage approach is the easier way of solving the assignment and routing problems, but an estimation of travel times is required to properly decompose the simultaneous approach into the two stages. This paper presents a new method to estimate operator travel times based on the Kernel Regression technique. Estimation is made on the basis of the operator travel times observed from previous periods. Numerical results based on realistic problem instances show that the proposed estimation method performs better than the classical Average Value method and that the whole approach is promising to construct realistic schedules.