Skip to content
This repository has been archived by the owner on Oct 24, 2021. It is now read-only.

Latest commit

 

History

History
293 lines (276 loc) · 14.1 KB

roadmap.md

File metadata and controls

293 lines (276 loc) · 14.1 KB
Raw

Brainstorm

  • Historical reference

  • First care and home hospitalization

  • Social care

  • Taxonomy

  • Planning horizon

  • Preferences

  • Working regulations

  • Tactical, strategical, operational

  • Brazilian needs

    • Multi-disciplinary team
    • Usually composed by a driver + licensed healthcare professional + an intern + a nurse
    • Total of 19 fix teams
    • There are some additional supporting teams (Q: equipes de apoio contam por fora dessas 19? E servem para coleta?)
    • Support teams usually composed by tecnician + driver only
    • The manual approach
      • Selects which patient is visited by each team, by someone with knowledge of the city
      • Then start the routes on the nearest patient
      • The next in the sequence is chosen according nearest neighborhood
      • There is also the need of collecting material
      • Drug administration
      • Some of these tasks may require simultaneous attendance
      • Q: Quando tem coleta, precisa voltar imediatamente para a central?
    • Q: Veículos são compartilhados, quando uma equipe termina de usar, libera para outra.
    • Q: Equipamentos também precisam ser carregados quando uma equipe ocupa um carro
    • Motivation for HHC services
    • Brazilian population growth and aging
    • CoVID19
      • Testing
      • Vaccination
      • Currently: by walking, drive-thru (most cases)
      • Coordinated effort of public and private facilities
        • But all vaccines are aquired through SUS
      • On some capitais: vaccination-at-home, solutions ad-hoc
        • Refence to uMov-me service, and Circuit (APP)

  • Scope of the search based on the Brazilian needs

    • Routingh problem (Cheng and Rich [98])

  • Routing in HC is a rich research subtopic

    • Planning horizon length
    • Regulations
    • Preferences
    • Multiple visits
    • Uncertainty

  • Operational can also help dimensioning the strategical (??) planning:

    • what happens if the number of patients grows from 15 to 50?

  • Research methodology: seek for a problem similar to the one from porto alegre

  • Mankowska work

    • Routing component
    • Time windows
      • In porto alegre, usually the patient only knows the day, or the shift where the visit will happen
    • Service types
      • In PoA, a set most demanding key services are offered to some patients in HC modality
      • Q: PoA faz primeiro atendimento ou hospitalização domiciliar? Tem alguns exemplos do que são os serviços cobertos pelas equipes?
    • Synchronization
      • PoA requires simultaneous DS between the fixed and support teams ??
        • ??then the teams return to the central with blood samples, etc?

  • Model-based approaches

    • LB (scientific purposes)
    • MIP (only small instances)
    • Fix-and-optimize matheuristic

  • Meta-heuristic approaches

    • Literature on these problems often explores LS-based heuristics
      • There are some properties from VRPTW that can be applied to reduce the work of evaluating a neighborhood
      • Synchronization make things a bit more unpredictable
        • Movements can be expensive to evaluate
          • Specialized structures to represent the solution (MK)
          • Attempts to develop more "clever" solution structures
            • Have to deal with cross-synchronizations
          • Indirect representation of the solutions: our approach

  • During LB experiments

    • We have the MIP -> LB, or best LB from B&C search
    • Combinatorial relaxation of the problem
      • Drop synchronization constraints, and solve a VRPTW
      • Using the VRPSolver -> optimal solutions are consistently worse than the LB and LB+
        • Conclusion: the impact of synchronized visits is to important that even a powerful tool like VRPSolver is of low value
        • Additionally, it is hard to devise column generation algorithms in presence of the synchronization
          • Pricing needs to be able to adjust the service times according duals from synch of the master
          • Discussed by van den Akker, Rasmussen and Bredstrom

  • We are in contact with the managers of HHC in PoA

    • The head has interest on the optimization opportunities
    • Our proposal is to work into the optimization kernel, as a counterpart, the public power would develop the infra required for the implementation of the tool
    • Due to the pandemic: all schedules got tight
    • No teams available in short notice for collaborating with us
    • Then we changed our plans:
      • Propose the implementation of the tool interface as a research project for some undergraduating student
      • Generate realistic instances for the case of porto Alegre

  • Generation of realistic instances

    • Simulate the behavior of the daily demands for home healthcare
    • Realistic patient locations through the open addresses database
    • Realistic travel times
      • Google Maps has several limitations under the free modality
      • Alternative approach: using OpenStreetMaps and OpenSourceRoutingMachine
    • This tools have already been combined together by my reaseach fellow for VRPTW, CVRP, and PDPTW
    • So we need to implement a few changes to be able to generate instances for the HHC
    • Currently to check how well our proposed methods work on these daily instances
    • Can be extended for generating data within a time frame of a week

  • We have three major datasets

    • Bredstrom and Ronquvist (2008), which comprises only simultaneous attendances
      • hard tw
      • patient prefereces to caregivers
    • Mankowska
      • Base problem of our work
    • New instances using ovig generator
      • Similar to mankowska, but using realistic data
        • Regarding travel times
        • Regarding patient locations
        • Demands proportional to the number of qualified caregivers
        • Overshooting of DS patients and more strict time windows

Questões para o Kallil

  1. Em uma das nossas reuniões, tomei nota que há 19 equipes trabalhando no atendimento residêncial. Também tomei nota que existem equipes de suporte. Essas equipes de suporte já estão contabilizadas no total das 19? Além disso, equipe de suporte só auxilia na administração de medicamentos e coleta de material?

  2. Quando um material é coletado, a equipe pode armazenar esse material no carro até o final dos atendimentos? Isso tem impacto no número de atendimentos que a equipe faz? Fico pensando se uma equipe de suporte poderia ser utilizada para fazer o transporte desse material. Outra opção é que os atendimentos com coleta sejam feitos mais para o final dos trabalhos das equipes, assim o tempo de armazenamento poderia ser reduzido. Tu poderia fazer algum detalhamento a respeito disso?

  3. Recordo que o número de veículos disponíveis é menor que o número total de equipes. Pelas minhas notas, algumas equipes só começam as operações após uma outra terminar as suas e retornar para a central. É assim mesmo que funciona?

  4. Considerando as operações diárias de uma equipe, qual seria o número médio de atendimentos por equipe, em termos de pacientes atendidos? A literatura trabalha com um valor de 5 a 8 pacientes diários por equipe, dependendo da complexidade, distância entre pacientes, e duração dos atendimentos.

  5. Seria possivel dar alguns exemplos de serviços oferecidos por home care?

Presentation planning

  • Intro slide
  • Presentation outline
  • Introduction
    • A problem that is being studiend on the past 40 years
    • Is applied in the context of providing healthcare access to the population
    • Invert the role of patient and health providers
  • Literature review
    • The first works is from the 1974
      • Since 2006: at least one publication per year
      • At least three major surveys on hc systems
    • Most authors discuss the problem as a VRP with additional constraints
      • Example of a routing problem
      • But the HC topic is much more rich
      • Because most authors discuss the problem of home hospitalization using HC
      • But there are variations such as primary care and social care
    • But the entire hhc framework is much more complex
      • We have strategical, tactical and operational planning phases
      • For example, we have the problem of demand estimation
        • Access the epidemiological profile of population (STRAT,TACT)
        • Choice of health services to be covered by HC system (STRAT,TACT)
        • Hiring of professionals (TACT)
        • Assess visit frequency (OPER)
        • Routing caregivers and scheduling patient visits (OPER)
    • We will be conservative
      • We are focusing on the operational planning of HHC
      • As mentioned before, a VRP with additional constraints and
        • Several variations
        • No standard dataset
  • Problem definition
    • Motivation
      • To solve a real problem in Brazil
      • We have the "better in home" initiative
      • Develop a system for Porto Alegre
      • Knowledge transfer to practitioners
    • The real problem in porto alegre I
      • Started development in 2016
      • Pilot program on big Brazilian cities
      • Target of the system: patients eligible for home hospitalization
    • The real problem in porto alegre II
      • Currently in porto alegre we have 19 teams (viewed as a "vehicle")
      • 300 patients serviced weekly
      • But the planning is almost completely manual
    • The real problem in porto alegre III
      • A experienced caregiver takes most of the decisions
      • Step 1: chooses the patients to be serviced each day
      • Step 2: assign the patients for each team
      • Step 3: individual routing of the teams
        • Done by the driver of the vehicle
        • Mostly follows a "nearest neighbor" approach
    • The real problem in porto alegre IV
      • Additional complicating needs
        • Simultaneous attendance with "support" teams (no optimization done)
        • Uncertainty regarding patients => rescheduling
        • Less vehicles than teams : vehicle sharing!
        • Loading of medical equipments
        • Student of health sciences
    • Our methodology
      • To find, or either propose a "core" optimization problem
      • Complex enough
        • Valuable to the practictioner
        • Valuable from scientific perspective
      • But not too much constrainted/specific
    • Our methodology
      • The Home Health Care Routing and Scheduling Problem
        • Routing of caregivers
        • Scheduling of the visits
      • A model and heuristics
      • A public benchmark dataset
      • Already tested by other authors
    • Our methodology
      • Still lacks some important features
      • Uncertainty regarding service times
      • Last minute changes on the availability of patients
      • Current bottleneck: lack of a infrastructure to interact with the optimization algorithms
    • In regarding the problem
      • Single transportation mode
      • Patient time-windows, soft tw ending
      • Operations syncronization
    • Operations synchronization
      • Simultaneous attendance
        • Both caregivers to be present to start both attendances simultaneously
        • May incurr a waiting on the caregiver arriving earlier
      • Precedence constraints
        • Some services take priority over the others
        • After servicing the higher priority service, then the other service can be performed
    • Objective function
  • Proposed methods
    • From the literature, we have
      • Mankowska
        • MIP model
        • VNS-based meta-heuristic with deterministic moves
      • Lasfargeas et al
        • Several variations of a constructive heuristics
        • Also a VNS-based meta-heuristic with randomized moves
    • Proposed methods
      • MIP-based methods
        • Best lower bounds with CPLEX
          • In makowksa, CPLEX 12.3 (2011)
          • We used cplex 20.1 (dec 2020) with preprocessing routines to eliminate unnecessary variables and constraints
        • Fix-and-optimize matheuristic [2019]
          • Uses the model from the literature
          • MIP warmstart using mankowska constructive heuristic
          • On each iteration:
            • fix all routes
            • then select two routes to be optimized
            • run CPLEX up to 25 seconds
          • stops after achieving local optima
      • Indirect search methods
        • Biased random key genetic algorithm
        • Additional intensification components
  • Computational results
    • Improved lower bounds
      • For the entire dataset
      • Literature: 10 hours of cplex
      • Our experiment: 2 hours
      • On instances up to 75 patients -> improvement of up 14%
      • On large instances (300 patients) -> improvement of up to 37%
    • Fix-and-optimize
      • Up to 1.5 hours of runtime on the larger instances
      • On instances up to 75 patients
        • Mankowska: 930.3
        • Lasfargeas: 854.3
        • Matheuristic: 785.71
      • On instances with 100 patients
        • Mankowska: 1064.7
        • Lasfargeas: ---
        • Matheuristic: 863.74
      • Instance with 200 and 300 patients: Matheuristic makes no progress
    • GA
      • Up to 20 minutes of execution
      • On Instances up to 75 patients
        • Mankowksa: 930.3
        • Lasfargeas: 854.3
        • Matheuristic: 785.71
        • BRKGA: 791.5
        • BRKGA+IC: 783.06
      • On instances with 100 patients
        • Mankowska: 1064.7
        • Lasfargeas: ---
        • Matheuristic: 863.74
        • BRKGA: 845.50
        • BRKGA+IC: 828.74
      • On instances with 300 patients
        • Mankowska: 2161.2
        • Lasfargeas: ---
        • Matheuristic: ---
        • BRKGA: 1709.28
        • BRKGA+IC: 1629.92
  • Conclusions
    • HHC is a important topic
    • Its relevance grows in front of global population aging
    • Room for improvement of operations in Porto Alegre
    • Empirical results indicates the advantages of the indirect search approach
      • GA produces better results than most of other tested methods
      • Fast when solving large instances
      • Can be fine tweaked to other needs
    • Future works
      • Improve the GA decoder (less greedy)
      • Include other practical requirements
      • Strategy for re-scheduling in case of unexpected events
      • Solution pool based algorithm