A general model for the home health care routing and scheduling problem with route balancing

Abstract

Home health care organizations are inclined to optimize their activities since the rise of the demand for home care. Defining the routing of the caregivers are complex activities to perform because of the different objectives to optimize and constraints to handle. The objectives considered are often in conflict leading one objective to deteriorate the other ones. Indeed, balancing the traveling time may increase the total traveling time of caregivers as well as increase the soft patient time window and shared visits non-satisfaction. Therefore, a good balance must be found between these objectives. Thus, we propose a general mixed-integer programming model for the home health care routing and scheduling problem with route balancing. The proposed model handles most of the known characteristics in order to be application-based independent. A memetic algorithm is proposed to evaluate the multi-objective approach on several instances and support decision-making. The impact of the focus on route balancing is analyzed on the behavior of the objectives. The results highlight that the focus on route length balancing may become harmful by deteriorating the other objectives while not improving anymore the maximal route length difference. Moreover, the route length balancing shows some different sensitivities on the other objective functions depending on the instance structure.