Home Health Care Routing And Scheduling Problem With Electric Vehicles Under Uncertain Environment

The aging population,high incidence of chronic diseases,and other issues in China have gradually become prominent,along with the emergence of shortages in medical resources and inadequacies in medical services.As an effective medical service model,home health care is conducive to transforming the health care service model,allowing for more flexible and rational allocation and utilization of medical resources.It has become one of the research hotspots in healthcare operation management.The complexity of the home health care leads to facing many uncertainties and dynamics during the process,which requires home health care agencies to formulate high-quality robust solutions to cope with stochastic uncertainties and to respond promptly to dynamic changes.This poses significant challenges to model construction and solution in the field of home healthcare operation management.In addition,with the increasing attention to environmental protection and the continuous advancement of battery technology,electric vehicles have been widely used in green transportation and delivery practices,providing more options for home health care nursing travel.Therefore,this paper aims to address the operational challenges in home health care at the current stage,conducting research on home health care routing and scheduling problem with electric vehicles under uncertain and dynamic environments.The objective is to provide scientific basis and decision support for the management of home healthcare nursing operations in our country.Firstly,during the pre-planning phase of service plans,considering the uncertainty of electric vehicle travel time and treatment duration,a multi-period home health care routing and scheduling problem with electric vehicles is studied.In this problem,there is a certain interval between consecutive services for patients,and multiple services for patients require the same medical staff.A robust optimization model for multi-period 0-1 mixed integer programming is constructed,aiming to minimize the total assignment cost of staff,electric vehicle travel cost,and incompatible cost of staff and patients within the planned period.A logic-based Benders decomposition is designed based on the problem structure.A three-stage heuristic strategy is proposed to generate initial solutions to improve the initial lower bound of the problem.Additionally,0-1 variable reduction strategy is utilized to reduce the number of 0-1 variables in the Benders master problem,and a bidirectional labeling algorithm is designed to accurately solve the Benders subproblem.Extensive numerical experiments are conducted to validate the effectiveness of the designed acceleration strategies and the logic-based Benders decomposition algorithm,analyzing the advantages of considering uncertainty and robustness and conducting sensitivity analysis on key parameters.Secondly,during the daily nursing service planning phase,considering the uncertainty of electric vehicle travel time and treatment duration,a home health care routing and scheduling problem with electric vehicles and synergistic-transport mode(such as walking,subway,bus,shared bicycles,etc.)is studied.A 0-1 mixed integer linear robust optimization model is constructed to minimize the total assignment cost of staff,electric vehicle travel cost,staff walking cost,and incompatible cost of staff and patients.To accurately solve this robust optimization model,a branch-and-price-and-cut algorithm incorporating various acceleration strategies is designed.Subset row cut is utilized to improve the lower bound of the problem,a bidirectional labeling algorithm is designed for accurate solution of the pricing subproblem,and hierarchical column generation and variable neighborhood search are utilized to reduce the invocation of the bidirectional labeling algorithm.Extensive numerical experiments are conducted to validate the effectiveness of the acceleration strategies and the branch-and-price-and cut algorithm.An analysis is performed on the advantages of synergistic-transport mode,and sensitivity analysis was conducted on key parameters.Finally,during the execution phase of nursing service plans,considering the impact of sudden situations such as new demands or cancellations on existing nursing plans,a dynamic bi-objective home health care routing and scheduling problem facing dynamic changes in demand is studied.A dynamic multi-objective 0-1 mixed integer programming model is established to simultaneously minimize the total operating cost and the deviation cost between the rescheduling plan and the existing nursing plan.A reactive rescheduling strategy is adopted,and a fast non-dominated sorting genetic algorithm II(NSGA-II)based on special crowding distance and tabu search is developed within a re-optimization framework.A multi-level chromosome encoding method is designed to improve the algorithm’s search efficiency,and various crossover and mutation operators are introduced to increase population diversity.Fast non-dominated sorting and special crowding distance selection are used to select elite individuals from the final generation,and tabu search is applied to improve the elite individuals.Key algorithm parameters are determined through orthogonal experiments.Extensive numerical experiments are conducted to validate the effectiveness of the designed acceleration strategies and the NSGA-II algorithm,analyze the effectiveness of different dynamic service update strategies,and conduct sensitivity analysis on key parameters.