Dayane Artigo EJOR

An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem

Publicado em: European Journal of Operational Research
Apresentação: Dayane Perez Bravo

A necessidade


Reduzir os custos de produção de biodiesel


Coletar óleo vegetal usado para reutilização como matéria-prima
 85% do custo de produção é em óleo vegetal
 Se utilizado o óleo reciclado, esse custo cai pela metade



Custos de coleta e estocagem
 Respeitar o acordo feito com os estabelecimentos
 54 nós com localização distante da fábrica



Identificar as variáveis e restrições do problema


Atender a demanda diária mínima de matéria-prima para produção



Modelo inicial por Programação Linear Inteira Mista (PLIM)

O objetivo do problema


Minimizar o custo de coleta, estocagem, frota e compra de matéria-prima


SPIRP – Selective and Periodic Inventory Routing Problem
 Período fixo de 7 dias com frota homogênea
 Quantidade de óleo coletado e nós heterogêneos



Proposta de um novo método de solução melhor que o PLIM


ALNS – Adaptive Large Neighborhood Search (primeira metaheurística desenvolvida para o SPIRP)



Otimizar o tempo computacional através de um grupo de espaço de busca



Após criar as rotas pelo ALNS, determina-se a quantidade a ser entregue pelo fluxo mínimo



Além de atender satisfatoriamente o problema de 25 nós, ele se mostra bom inclusive com 100 nós

capacidade

Entrada e saída

Nó visitado
Evita sub-rotas

A proposta


Relaxação sem roteamento (RR)


Grafo direcionado



Transformar binárias em contínuas entre 0 e 1



Remover restrições de fluxo e rota



Adicionar variáveis inteiras



Permitir descarregamento e retorno para a rota

Caracterização do ALNS


Vizinhança grande




Mecanismo de busca adaptado




Seleção aleatória da vizinhança, de acordo com o desempenho anterior

Ajuste de peso adaptado




Número de mudanças na solução atual

A probabilidade de uma vizinhança ser escolhida aumenta a