A decomposition - construction approach for solving the home health care scheduling problem

Area of Science:

• Operations Research
• Computer Science

Background:

• Combinatorial Optimization Problems (COP) are computationally challenging, often exceeding the capabilities of classical modeling techniques for real-world applications.
• Hierarchical Optimization Models (HOM) offer a viable solution by simplifying complex problems through hierarchical decomposition into interconnected subproblems.

Purpose of the Study:

• To apply Hierarchical Optimization Models (HOM) to the Home Health Care Scheduling Problem (HCSP).
• To develop a novel approach for modeling and solving NP-hard optimization problems in healthcare logistics.

Main Methods:

• Decomposition of the Home Health Care Scheduling Problem (HCSP) into three distinct subproblems: grouping, assignment, and routing.
• Representation of the decomposed problem using a Hierarchical Directed Acyclic Graph (HDAG).
• Implementation of a generic algorithm to traverse the HDAG and solve each subproblem sequentially.

Main Results:

• The proposed Hierarchical Optimization Model (HOM) successfully modeled the Home Health Care Scheduling Problem (HCSP).
• The developed HDAG-based algorithm efficiently solved a real-life HCSP instance from Zealand Company.
• The results demonstrated superior performance compared to existing approaches for the HCSP.

Conclusions:

• Hierarchical Optimization Models (HOM) provide an effective framework for tackling complex NP-hard problems like the HCSP.
• The HDAG-based decomposition and solving strategy offers a significant improvement in efficiency and performance for healthcare scheduling.
• This research validates the utility of HOM in practical applications within the healthcare sector.