Otimização

Prévia do material em texto

Apresentação do Modelo Matemático
Alessandro D’Angelo 18.2.4054
Bianca Marcelino 18.2.4048
Introdução
● Roteamento de veículo único com tempos de serviço estocásticos.
● O tempo de viagem pode ser maior devido as interferências, por 
exemplo, acidentes de carro, condições climáticas, etc.
● O objetivo é minimizar a duração esperada da rota mais as 
penalidades para chegadas tardias. 
● A estocástica é modelada usando um conjunto de cenários 
baseados em dados históricos.
#
#
#
#
Definição do problema
Um conjunto de clientes deve ser atendido em um único dia útil. Cada cliente tem uma janela de tempo para 
o início do serviço. Os limites superiores das janelas de tempo são suaves, enquanto os limites inferiores 
são rígidos. Ou seja, chegar a um local do cliente após o término da janela de tempo do cliente incorre em 
uma penalidade, que está aumentando (não necessariamente linearmente) na extensão do atraso. Quando 
o veículo chega ao local do cliente antes do início de sua janela de tempo, ele espera até que a janela seja 
aberta. Esta escolha de janelas de tempo representa a prática de operações de serviço de campo onde as 
chegadas tardias podem ser inevitáveis quando os tempos de viagem e serviço são desconhecidos. No 
entanto, chegadas antecipadas podem ser evitadas deixando o técnico em marcha lenta por algum tempo. 
Um único veículo está disponível para atender os clientes durante a jornada de trabalho. O veículo sai do 
depósito, não antes de um determinado horário, e retorna ao depósito após o serviço do último cliente ter 
sido concluído. O tempo de viagem é função da origem, destino, horário de partida e cenário. O tempo de 
atendimento é dado para cada cliente em cada cenário. Uma solução é uma sequência pela qual os clientes 
devem ser visitados para minimizar a soma esperada da duração da rota e as penalidades pelas violações 
das janelas de tempo em todos os cenários.
#
#
#
#
Notações
n = número de clientes; 0 representa o depósito.
K = número de cenários.
[ai,bi] = intervalo de tempo para atendimento no local do cliente.
Sik = tempo de atendimento no local do cliente i no cenário k.
tijk(t’) = intervalo de tempo entre clientes i e j na hora de partida t’ no cenário k. Estamos assumindo que o 
tempo de viagem em cada cenário segue a propriedade FIFO.
Gi(x) = função de penalidade por atraso na chegada ao local do cliente i. A forma exata da função de 
penalidade é uma entrada deste modelo e deve ser determinada pelo acordo do nível de serviço entre os 
provedores e seus clientes.
Variaveis de Decisão
Xij = variável binária que é igual a 1 se o cliente j é visitado imediatamente após o cliente i.
Uik = momento em que o serviço do cliente i começa no cenário k.
Oik = atraso no local do cliente i no cenário k.
Tk = tempo de duração da rota no cenário k.
 
Função Objetiva
01
Minimizar 
Minimizar a duração esperada da rota e os custos de penalidade
Restrições
Mantém a conservação do fluxo do veículo enquanto restringe
Garante que todos os clientes sejam visitados
Restrições
Relaciona os horários de início do serviço com as variáveis de roteamento
Impõe limites inferiores rígidos nos horários de início do serviço dos clientes que 
o veículo visita
Restrições
Relaciona as variáveis de atraso a esses tempos.
Relaciona a duração da rota com os horários de início das variáveis de serviço
Restrições
Definindo os domínios das variáveis de decisão
Muito Obrigado !!!