TexasScholarWorks
    • Login
    • Submit
    View Item 
    •   Repository Home
    • UT Electronic Theses and Dissertations
    • UT Electronic Theses and Dissertations
    • View Item
    • Repository Home
    • UT Electronic Theses and Dissertations
    • UT Electronic Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Home therapist network modeling

    Thumbnail
    View/Open
    SHAO-DISSERTATION.pdf (1.091Mb)
    Date
    2011-12
    Author
    Shao, Yufen
    Share
     Facebook
     Twitter
     LinkedIn
    Metadata
    Show full item record
    Abstract
    Home healthcare has been a growing sector of the economy over the last three decades with roughly 23,000 companies now doing business in the U.S. producing over $56 billion in combined annual revenue. As a highly fragmented market, profitability of individual companies depends on effective management and efficient operations. This dissertation aims at reducing costs and improving productivity for home healthcare companies. The first part of the research involves the development of a new formulation for the therapist routing and scheduling problem as a mixed integer program. Given the time horizon, a set of therapists and a group of geographically dispersed patients, the objective of the model is to minimize the total cost of providing service by assigning patients to therapists while satisfying a host of constraints concerning time windows, labor regulations and contractual agreements. This problem is NP-hard and proved to be beyond the capability of commercial solvers like CPLEX. To obtain good solutions quickly, three approaches have been developed that include two heuristics and a decomposition algorithm. The first approach is a parallel GRASP that assigns patients to multiple routes in a series of rounds. During the first round, the procedure optimizes the patient distribution among the available therapists, thus trying to reach a local optimum with respect to the combined cost of the routes. Computational results show that the parallel GRASP can reduce costs by 14.54% on average for real datasets, and works efficiently on randomly generated datasets. The second approach is a sequential GRASP that constructs one route at a time. When building a route, the procedure tracks the amount of time used by the therapists each day, giving it tight control over the treatment time distribution within a route. Computational results show that the sequential GRASP provides a cost savings of 18.09% on average for the same real datasets, but gets much better solutions with significantly less CPU for the same randomly generated datasets. The third approach is a branch and price algorithm, which is designed to find exact optima within an acceptable amount of time. By decomposing the full problem by therapist, we obtain a series of constrained shortest path problems, which, by comparison are relatively easy to solve. Computational results show that, this approach is not efficient here because: 1) convergence of Dantzig-Wolfe decomposition is not fast enough; and 2) subproblem is strongly NP-hard and cannot be solved efficiently. The last part of this research studies a simpler case in which all patients have fixed appointment times. The model takes the form of a large-scale mixed-integer program, and has different computational complexity when different features are considered. With the piece-wise linear cost structure, the problem is strongly NP-hard and not solvable with CPLEX for instances of realistic size. Subsequently, a rolling horizon algorithm, two relaxed mixed-integer models and a branch-and-price algorithm were developed. Computational results show that, both the rolling horizon algorithm and two relaxed mixed-integer models can solve the problem efficiently; the branch-and-price algorithm, however, is not practical again because the convergence of Dantzig-Wolfe decomposition is slow even when stabilization techniques are applied.
    Department
    Operations Research and Industrial Engineering
    Description
    text
    Subject
    Therapist scheduling
    Home healthcare
    Weekly planning
    Network modeling
    Mixed integer programming
    Exact algorithm
    Column generation
    Heuristic algorithm
    GRASP
    URI
    http://hdl.handle.net/2152/ETD-UT-2011-12-4500
    Collections
    • UT Electronic Theses and Dissertations

    University of Texas at Austin Libraries
    • facebook
    • twitter
    • instagram
    • youtube
    • CONTACT US
    • MAPS & DIRECTIONS
    • JOB OPPORTUNITIES
    • UT Austin Home
    • Emergency Information
    • Site Policies
    • Web Accessibility Policy
    • Web Privacy Policy
    • Adobe Reader
    Subscribe to our NewsletterGive to the Libraries

    © The University of Texas at Austin

     

     

    Browse

    Entire RepositoryCommunities & CollectionsDate IssuedAuthorsTitlesSubjectsDepartmentsThis CollectionDate IssuedAuthorsTitlesSubjectsDepartments

    My Account

    Login

    Statistics

    View Usage Statistics

    Information

    About Contact Policies Getting Started Glossary Help FAQs

    University of Texas at Austin Libraries
    • facebook
    • twitter
    • instagram
    • youtube
    • CONTACT US
    • MAPS & DIRECTIONS
    • JOB OPPORTUNITIES
    • UT Austin Home
    • Emergency Information
    • Site Policies
    • Web Accessibility Policy
    • Web Privacy Policy
    • Adobe Reader
    Subscribe to our NewsletterGive to the Libraries

    © The University of Texas at Austin