A Logic-Based Benders Approach to Home Healthcare Delivery

The authors propose an exact optimization method for home healthcare delivery that relies on logic-based Benders decomposition (LBBD). The objective is to match patients with healthcare aides and schedule multiple home visits over a given time horizon, to maximize the number of patients served while taking into account patient requirements, travel time, and scheduling constraints. Unlike classical Benders methods, LBBD allows the authors to exploit a natural decomposition of the problem into a master problem, solved by mixed integer programming, and a subproblem that decouples into small scheduling problems, solved by constraint programming. The authors report computational results based on data obtained from a major home hospice care provider. They find that LBBD is far superior to mixed integer programming on all but a few instances with narrow time windows. It solves problems of realistic size to optimality if the aim is to conduct staff planning on a rolling basis, without temporal dependencies between visits. The authors also find that a version of LBBD known as branch and check usually outperforms standard LBBD on the instances tested.

  • Record URL:
  • Availability:
  • Supplemental Notes:
    • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
  • Authors:
    • Heching, Aliza
    • Hooker, J N
    • Kimura, Ryo
  • Publication Date: 2019-3


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01703261
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Apr 22 2019 1:57PM