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

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