Home health care problem An extended multiple Traveling Salesman Problem

Abstract This paper deals with the routing problem of health care sta in a home health care problem. Given a list of patients needing several cares, the problem is to assign cares to care workers. Some cares have to be performed by several persons and some cares cannot be performed with others. If a patient needs several cares, he may want to be treated by the same person. Moreover, some skills constraints and time windows have to be satis ed. We show that this problem is equivalent to a multiple traveling salesman problem with time windows (mTSPWT) with some speci c constraints. For solving this problem, we propose an integer linear program with some technical improvements. 1