期刊
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING
卷 16, 期 1, 页码 127-137出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TASE.2018.2874392
关键词
Column generation (CG); gossip algorithm; home healthcare (HHC); vehicle routing problem
资金
- Vastra Gotalandsregionen in Sweden [RUN 612-0974-13]
- PROSAM
- European Community [609391]
Home healthcare (HHC) is a service that dispatches caregivers to people in need of healthcare who live in the home. The task assignment and route generation for caregivers can be formulated as an extension of the well-known vehicle routing problem with time windows (VRPTW). Currently, the most successful exact algorithms for VRPTW are based on a framework combining column generation (CG) and branching. Although such methods could be successful for HHC routing and scheduling problem (HHCRSP) as well, fast approximate algorithms are appealing, especially for large problems. In an early version of this paper, we employed a heuristic distributed gossip algorithm to solve HHCRSP. In this paper, we integrate the gossip algorithm with a local solver based on CG, which makes it an effective algorithm for larger problem instances. As it will be shown with extensive numerical experiments, for large problem instances, gossip-CG performs better than the pure CG. Note to Practitioners-The task of routing and scheduling caregivers for HHC providers can be formulated as a mathematical problem that is theoretically challenging to solve to optimality for large-scale problems involving many clients and caregivers. Although extensive research and tools for tackling this problem already exist, in practice, even in developed countries, it is still common to rely on schedules generated manually by staff. What we present in this paper is the summary of our theoretical work on tackling such problems. The benefit of the framework that we propose, the CG-based gossip method, is that it can be preempted at any time if the staff requires to obtain a good schedule as soon as possible. If ample time is available, one can let our algorithm to run for a longer period of time to generate even shorter routes.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据