多周期家庭护理的路径规划与调度算法

Route Planning and Scheduling Algorithm of Multi Period Home Health Care

在家庭护理服务质量方面,现有研究大多考虑老人的服务需求是否得到满足、服务是否及时、老人对服务是否满意等因素,忽略了老人在选择护工上的偏好习惯。提出带服务约束的多周期家庭护理路径规划与调度问题,并将其归约为多车场车辆路径优化问题,证明该问题的NP难解性。为了在老人提供的黑名单、必选服务技能、服务价格等约束下最优化家庭护理机构的服务质量,提出贪心算法,优先为服务开始时间早的老人提供服务,为老人安排最高服务质量的护工。以贪心算法求得的结果作为初始解,并针对该问题的多周期性质,定制一个遗传算法对初始解进行优化,以获得更优的多周期护工路径规划方案。在3组不同规模的开源数据集上进行实验,结果表明,与基准算法和随机算法相比,所提出的贪心算法将服务质量分别提高了31.7%和79.8%,定制的遗传算法将服务质量分别提高了65.7%和126.3%。

Regarding service quality in Home Health Care(HHC),most relevant works mainly consider whether the service requirements of the elderly are met,whether the service is timely,or whether the elderly are satisfied with the services. However,few studies have considered the selection of caregivers for the elderly. To address this problem,this paper first proposes a Multi-period Home Health care routing and Scheduling Problem with service constraints(MHHSP).This paper provides a proof of its NP-hardness by reducing the problem to the multi-depot vehicle routing problem. To maximize the service quality of home care institutions under the constraints of a blacklist,required service skills,and service prices provided by the elderly,a greedy algorithm is proposed,which aims to maximize the service quality by assigning the caregiver with the maximum service quality to the elderly with the earliest time of starting service. To fit the multi-period property,the solution obtained by the greedy algorithm is further optimized by the customized genetic algorithm to obtain a better multi-cycle nursing path planning scheme. The experimental results on three groups of open-source datasets of different sizes show that compared with the benchmark and random algorithms,the proposed greedy algorithm improves the quality of service by 31.7% and 79.8%,respectively,and the customized genetic algorithm improves the quality of service by 65.7% and 126.3%,respectively.