A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements

Biao Yuan, Ran Liu and Zhibin Jiang

International Journal of Production Research, 2015, vol. 53, issue 24, 7450-7464

Abstract: Home health care (HHC) is defined as providing medical and paramedical services for patients at their own domicile. In the HHC industry, it is crucial for health care organisations to assign caregivers to patients and devise reasonable visiting routes to save total operational cost and improve the service quality. However, some special constraints make the problem hard to solve. For example, patients’ service times are usually stochastic due to their varying health conditions; caregivers are organised in a hierarchical structure according to their skills to satisfy patients’ demands. In this paper, we address a HHC scheduling and routing problem with stochastic service times and skill requirements. A stochastic programming model with recourse is proposed to formulate the problem in which the expected penalty for late arrival at customers is considered. To solve the problem, it is equivalently transformed into a master problem and a pricing sub-problem. A column generation algorithm is developed to solve the relaxation of the master problem and obtain its lower bound. A label algorithm and several effective accelerating techniques are devised to solve the pricing sub-problem. To obtain feasible solutions, the column generation procedure is embedded within the branch and bound framework. The effectiveness of the proposed algorithm is validated through numerical experiments.

Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2015.1082041 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:53:y:2015:i:24:p:7450-7464

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2015.1082041

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().