A Gossip Algorithm for Home Healthcare Scheduling and Routing Problems

详细信息    查看全文

• 作者：Sarmad Riazi^* ; ^{sarmad.riazi@chalmers.se" class="auth_mail" title="E-mail the corresponding author} ; Payam Chehrazi^* ; ^{cherazi@student.chalmers.se" class="auth_mail" title="E-mail the corresponding author} ; Oskar Wigströ ; m^* ; ^{oskar.wigstrom@chalmers.se" class="auth_mail" title="E-mail the corresponding author} ; Kristofer Bengtsson^** ; ^{kristofer@sekvensa.se" class="auth_mail" title="E-mail the corresponding author} ; Bengt Lennartson^* ; ^{bengt.lennartson@chalmers.se" class="auth_mail" title="E-mail the corresponding author}
• 刊名：IFAC-PapersOnLine
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：47
• 期：3
• 页码：10754-10759
• 全文大小：305 K

文摘

Many people in need of care still live in their homes, requiring the caretakers to travel to them. Assigning tasks to nurses (or caretakers) and scheduling their work plans is an NP-hard problem, which can be expressed as a vehicle routing problem with time windows (VRPTW) that includes additional problem-specific constraints. In this paper, we propose to solve the Home Healthcare Scheduling and Routing Problem (HHCRSP) by a distributed Gossip algorithm. We also apply an extended version called n-Gossip, which provides the required flexibility to balance optimality versus computational speed. We also introduce a relaxation on the optimality of the underlying solver in the Gossip, which speeds up the iterations of the Gossip algorithm, and helps to quickly obtain solutions with good quality.