HHCRSP implementado utilizando Simulated Annealing

Como trabalho final da disciplina de Otimização Combinatória, implementaremos o problema The home health care routing and scheduling problem with interdependent services utilizando ambos solver matemático e a meta-heurística Simulated Annealing!

Sumário

• Definição
  • Instância
  • Objetivo
• Estrutura do Projeto
• Execução
  • Execução Simples
  • Compilação
• Contato

Definição

Considere um conjunto de veículos V, e um conjunto C que representam pacientes de um plano de saúde. O plano de saúde contempla atendimentos de um conjunto de especialidades médicas S e tanto pacientes quanto profissionais da saúde só podem requisitar ou prestar atendimento de especialidades cobertas pelo plano.

No problema de home care, considera-se que cada veículo tem uma equipe de profissionais de saúde fixa. Em outras palavras, um veículo só pode atender uma certa especialidade médica caso haja um profissional adequado na equipe do veículo. Todos os veículos partem, inicialmente, de uma garagem central, e devem retornar para ela no final das suas operações. Cada paciente do problema possui uma ou mais demandas de saúde que devem ser atendidas por algum dos veículos do problema. Cada demanda refere-se a uma especialidade médica distinta, e leva um certo tempo de atendimento para ser cumprida.

Além disso, cada paciente possui uma faixa de horário ideal para atendimento; Atendimentos antes do horário de início são proibidos; Atendimentos extrapolando o horário de término são penalizados como atraso. São conhecidas as distâncias entre todos os locais do problema, incluindo-se a garagem.

Instância

Consideramos o seguinte conjunto de dados como instância de entrada para o problema:

In the name of each instance InstanzCplex_HCSRP_m_n.txt, m represents the number of nodes whereas n represents the instance index for this size of problem, n ranges between 1 and 10

nbNodes

number of nodes in the network; note that the depot is counted as the first (1) and the last node (ndNodes), i. e. for nbNodes = 12 nodes, node 1 and 12 are depot nodes and nodes 2..11 represent the patients

nbVehi

number of staff members (vehicles)

nbServi

number of service types

r

service requirement of each patient

DS

patients, who require double service

a

qualification of staff members

x

x-coordinates of the nodes

y

y-coordinates of the nodes

d

distance matrix

p

processing time of each service at each patient provided by each staff member

mind

minimal time gap between service activities for double service patients

maxd

maximal time gap between service activities for double service patients

e

beginning of time window

l

end of time window

Objetivo

Segue o objetivo definido:

Encontrar uma solução cuja a soma dos seguintes fatores seja mínima:
- Distâncias percorridas pelos veículos;
- Soma dos atrasos nos atendimentos;
- Tempo do maior atraso observado na solução.

Sendo assim, a solução de uma instância seguirá o seguinte modelo:

Para cada veículo, uma rota com a ordem de visitação dos pacientes.
Para cada paciente, o horário que começa e encerra o atendimento de cada especialidade médica requisitada.

Estrutura do Projeto

Segue a estrutura básica do projeto, comentada:

.                             # root do projeto
├── build                     # pasta de build, caso seja utilizada a opção de make
├── instances                 # pasta de dados, que guarda as instâncias
├── labbook                   # pasta para o lab-book, guardando infos sobre os experimentos
├── report                    # pasta para o relatório
└── src                       # pasta para fontes, nela fica o script principal
    ├── MathSolver            # módulo do solver matemático
    ├── SimulatedAnnealing    # módulo da heurística simulated annealing
    └── Utils                 # módulo para utilidades diversas

8 directories

Execução

Para a execução do programa, você tem duas opções:

1. Utilizando uma chamada comum a julia
2. Compilar e utilizar como executável

Execução Simples

Execute qualquer uma das seguintes chamadas na linha de comando:

julia src/hhcrsp.jl --help

# ou

./src/hhcrsp.jl --help

Essa chamada imprimirá na tela a utilização do programa e seus parâmetros opcionais de entrada.

Compilação

Para isso, execute uma simples chamada ao make:

make

Atenção: Para executar esse passo, é necessário ter instalado o pacote PackageCompiler de julia!

Ao fim do processo, uma pasta chamada build/ será criada no root do repositório, com o executável compilado.

Ao compilar o programa nós evitamos o longo tempo de compilação JIT que julia realiza quando executa qualquer código fonte.

Agora, realize os seguintes comandos:

cd build/

./hhcrsp --help

Que obterás o mesmo resultado que executando estilo script.

Contato

Você pode entrar em contato comigo pelo seguinte email:

hcpsilva@inf.ufrgs.br