13
Uma abordagem metaheurística para o problema de roteamento de veículos com janelas de tempo e múltiplos entregadores Isabela N. Cavaco / Lívia S. Barreto Universidade Federal da Paraíba Departamento de Informática Disciplina: Análise e Projeto de Algoritmos Prof: Lucídio dos Anjos Formiga Cabral

Apresentação APA Final

Embed Size (px)

DESCRIPTION

Apresentação sobre metaheurística LNS para problema de Roteamento de Veículos com Janelas de Tempo e Multiplos Entregadores

Citation preview

Page 1: Apresentação APA Final

Uma abordagem metaheurística para o problema de roteamento de veículos com janelas de tempo e múltiplos entregadores

Isabela N. Cavaco / Lívia S. Barreto

Universidade Federal da Paraíba Departamento de InformáticaDisciplina: Análise e Projeto de AlgoritmosProf: Lucídio dos Anjos Formiga Cabral

Page 2: Apresentação APA Final

Processos de transporte podem representar entre 10% e 20% dos bens produzidos por uma empresa;

Investir esforços para o aprimoramento desses processos.

PRV - Problema de roteamento de veículos: • o menor custo;• quantidade mínima de veículos;• menor distância percorrida;• melhor tempo;

Problema genérico

Page 3: Apresentação APA Final

Problema - Explicação das variantesVariante do Problema de Roteamento de Veículos (PRV) - Roteamento de Veículos com Janelas de Tempo e Múltiplos Entregadores (PRVJTME): . quantidade mínima de entregadores;

• melhor ponto estratégico de parada para atender o máximo de clientes possíveis da região

* Exemplo

Variante trata:• decisões de roteirização;• programação de veículos;• definição do tamanho da tripulação por veículo; • janela de tempo.

Page 4: Apresentação APA Final

Problema - Estágios• Tempo de serviço linearmente dependente do número de

entregadores designados à rota

• 1° estágio: agrupar os clientes em torno de sítios de estacionamento para estabelecer rotas para visitar esses grupos.

• Cada cliente deve receber sua entrega dentro de sua janela de tempo;

Objetivos PRVJTME: * Determinar rotas que tenham custo mínimo; * Cada grupo deve ser visitado exatamente uma única vez; * A visita deve satisfazer a janela de tempo;

Page 5: Apresentação APA Final
Page 6: Apresentação APA Final

Solução: LNS

• Busca em Vizinhança Grande (LNS)• Supera dificuldades de buscas locais tradicionais, que não são capazes de se

deslocar entre áreas promissoras do espaço de soluções

• Método de melhoria global que utiliza heurísticas complementares de melhoria

• Executada múltiplas vezes até atingir um critério de parada

• Cada iteração gera uma solução inicial por meio da heurística construtiva, que é armazenada como a melhor solução atual

• Em seguida, entra num ciclo de melhoria da solução através de operações alternadas de destruição e reparação

Page 7: Apresentação APA Final

Heurística Construtiva

• Rotas são construídas sequencialmente ;

• Inicializado com o grupo mais distante em relação ao depósito (e que ainda não foi atendido);

• Define a tripulação inicial do veículo como a máx. possível.

• Uma vez que não podem ser inseridos mais grupo uma nova rota é inicializada, até todos os grupos sejam atendidos.

Page 8: Apresentação APA Final

LNS

• Em ambas operações, 1 tipo de operador é escolhido aleatoriamente:

• 4 tipos de operadores de remoção: remoção aleatória, pior posição, relacionada e orientada por tempo

• 2 tipos de operadores de inserção: gulosa e regret

• Em seguida, são aplicadas heurísticas complementares

• Ao final do ciclo, a melhor solução da execução atual da metaheurística é atualizada, aceitando apenas soluções melhores que a mesma.

• Toda vez que a metaheurística executa uma iteração, a melhor solução global é atualizada e a abordagem reinicia com a próxima iteração.

Page 9: Apresentação APA Final

Heurísticas Complementares

• Busca de Vizinhança Variável com Ordenação Aleatória (RVND)

• Heurística de Redução de Rotas

• Heurística de Redução de Entregadores

Page 10: Apresentação APA Final

Busca de Vizinhança Variável com Ordenação Aleatória (RVND)• Aplica um conjunto de buscas locais simples através de estruturas

de vizinhança para melhorar a solução atual

• Dado um conjunto V de vizinhanças da solução, se a vizinhança aleatoriamente escolhida não melhora a solução, ela é removida do conjunto V e a busca continua com estruturas remanescentes

• Se melhora, o conjunto V é restaurado

• O algoritmo termina quando o conjunto V se torna vazio

• Sempre que a estrutura de vizinhança consegue melhorar a soluçao, é executado o procedimento de redução de rotas

Page 11: Apresentação APA Final

Heurística de Redução de Rotas

• Itera todas as rotas da solução atual, e:• Remove todos os grupos e tenta reinseri-los em outras rotas, na melhor

posição possível

• Se todos os grupos são realocados, a solução atual conseguiu diminuir em uma rota a solução e esta é atualizada

• Se não conseguiu realocar todos os grupos, as tripulações das rotas são temporariamente incrementadas em 1, para aumentar a folga delas e facilitar a inserção desses grupos• Se forem inseridos dessa maneira, as tripulações tornam-se definitivas

• Heurística continua até alocar todos os grupos da rota inicialmente eliminada ou até todas as rotas terem experimentado o máximo de tamanho de tripulação e ainda ter grupos não atendidos

Page 12: Apresentação APA Final

Heurística de Redução de Entregadores

• Algumas rotas da solução podem ter mais entregadores que o necessário, seja pelo método construtivo ou pelos movimentos de melhoria

• Reduz iterativamente (para todas as rotas) o número de entregadores de cada uma, até atingir o número mínimo que a rota pode utilizar

Page 13: Apresentação APA Final

Conclusão

• Testes computacionais mostraram que a abordagem é capaz de produzir bons resultados quando comparadas com outras abordagens de outros autores (Busca Tabu e Colônia de Formigas)