A variable neighborhood search approach for solving the crew constrained home care routing problem with time windows

Official URL: http://risc01.sabanciuniv.edu/record=b1659331 (Table of Contents)

Population aging, global increase in chronic diseases and decrease in informal care have substantially increased the demand for Home Health Care (HHC), in recent years. To gain competitive advantage in the market and to lower public expenditure, HHC service providers and governmental institutions mainly focus on increasing service quality and decreasing costs. These objectives have resulted in various challenging optimization problems among which the HHC routing and scheduling problems have gained popularity in the past few years. In this thesis we study a HHC routing and scheduling problem with time windows, where service is provided to patients requesting di erent types of care and the crew is limited. The problem is motivated by a real life case of a company that provides HHC service to a district municipality in Istanbul and referred to as Crew Constrained Home Care Routing Problem with Time Windows (CC-HCRPTW). In order to solve the CC-HCRPTW, we present a Variable Neighborhood Search (VNS) heuristic with a problem speci c shaking mechanism and crashing algorithm. To investigate the performance of the proposed methodology, we conducted an extensive computational study on a newly generated set of instances which are modi ed from the classical Solomon's VRPTW benchmark instances. Our results show that the proposed methodology is e ective in, nding near optimal solutions for small-sized instances in moderate computational time, and signi cantly improving the initial solution of the real-sized problems.