Study of Home Health Care Routing and Scheduling Problems

Because the growth rate of population is shrunk, the proportion of the elderly people is thus increasing in Taiwan. Due to the health technology’s development, the average life is lengthened; the elderly people living alone and people with disabilitie are increased. Therefore, the need for home health care is increased. The objective of this proposal is to provide the optimal schedule and assignment for daily routing and scheduling problem, which can increase the total profit and service quality of home health care company. If the objective of the home health care company is to maximize the profit under the constraint of customers’ time window and the available time of service workers, to decide which customers to be accepted and to determine the service sequence of these customers, this can be transformed health care problem as Team Orienteering Problem with Time Window (TOPTW). TOPTW belongs to NP-hard problem; therefore, how to find a (near) optimal solution using reasonable computational time is a critical challenge. However, profit is not only the consideration; some factors must be taken into consideration due to the social ethics. These factors, such as the number of customer served, or the number of customer served in remote district. It becomes a problem with multi-objective function, and requires the concept of Pareto set solutions to solve this kind of problem. Sometimes, there exists synchronization service or temporal precedence constraints for two home health care workers. For example, (1) after one worker is cooking for customer, another staff is to provide the injection or medication service; (2) two workers are collaborated to help customer to take a bath. These constraints will complicate the problem, and the solving methods should be changed. When planning the service routes, if there are multiple time windows exist for customers and more constraints are taken into consideration, it becomes more difficult to solve. Therefore, how to figure out this kind of problem effectively is an important issue. This proposal will provide the mathematics models of above problems and develop effective heuristics to solve various kinds of problems. There are few approaches developed to solve the home health care routing and scheduling problems; therefore, this proposal wants to develop a multi-start simulated annealing and an artificial bee colony algorithm to solve home health care routing and scheduling problems. It is expected that the (near) optimal solutions can be obtained within reasonable time.

Project ID:PB10202-0145
External Project ID:NSC101-2410-H182-004-MY2