A branch-and-price algorithm for the home-caregiver scheduling and routing problem with stochastic travel and service times

Ran Liu (), Biao Yuan and Zhibin Jiang
Additional contact information
Ran Liu: Shanghai Jiao Tong University
Biao Yuan: Shanghai Jiao Tong University
Zhibin Jiang: Shanghai Jiao Tong University

Flexible Services and Manufacturing Journal, 2019, vol. 31, issue 4, No 5, 989-1011

Abstract: Abstract This paper addresses the solution methods for the stochastic home-caregiver scheduling and routing problem which arises in many service industries such as home care and home health care. In the problem, the caregiver’s travel times and service times for customers are stochastic. A chance constraint is introduced to ensure the on-time service probability for the customers. Such stochastic travelling and service time and the chance constraint further complicate the problem. In this paper, a route-based mathematical model is introduced. A branch-and-price (B&P) algorithm and a discrete approximation method are combined to solve the problem. Herein, effective label algorithms are designed to generate negative reduced cost routes. The efficiency of the algorithm are improved by employing three acceleration strategies. The experiments on test instances validate the performances of the proposed B&P algorithm and demonstrate the necessity of considering the stochasticity of travel times of home-caregiver and service times to the customers.

Keywords: Home health care; Home-caregiver; Scheduling; Routing; Branch-and-price; Stochastic time (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1007/s10696-018-9328-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:flsman:v:31:y:2019:i:4:d:10.1007_s10696-018-9328-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10696

DOI: 10.1007/s10696-018-9328-8

Access Statistics for this article

Flexible Services and Manufacturing Journal is currently edited by Hans Günther

More articles in Flexible Services and Manufacturing Journal from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().