Målrettet mobilisering

Ropke e Pisinger (2006a) propuseram uma nova heurística denominada Adaptive

Large Neighborhood Search (ALNS), para resolver o Problema de Coleta e Entrega com

Janelas de Tempo (Pickup and Delivery Problem with Time Windows - PDPTW). A ALNS é uma extensão da Large Neighborhood Search (LNS) e funciona com a aplicação de diferentes métodos de remoção e inserção dos elementos de uma solução. Os diferentes métodos são escolhidos com base em estatísticas que refletem o sucesso deles durante o processo de busca.

O número de pedidos e o total de veículos são conhecidos no PDPTW. As mer- cadorias, referentes aos pedidos, devem ser coletadas em um local e entregues em outro, respeitando as restrições de janela de tempo impostas na coleta e na entrega, além de restrições da característica dos veículos viáveis para realizar a operação, a capacidade dos mesmos, entre outras. As janelas de tempo consistem em um intervalo de tempo limitado para que a coleta/distribuição das mercadorias seja realizada. O LNS parte de uma solução inicial, que pode ser gerada de forma gulosa, e tem como função principal a remoção e reinserção de pedidos na solução, que definem a robustez e performance da heurística. No ALNS, as heurísticas de remoção e inserção são escolhidas a partir das estatísticas recolhidas durante o processo de busca.

Ropke e Pisinger (2006a) apresentaram três heurísticas de remoção de pedidos:

Shaw, Random e Worst, e duas heurísticas de inserção de pedidos: Greedy e Regret. Todas

as heurísticas são utilizadas na busca e sua seleção é feita pelo princípio da roleta, sendo que para cada heurística é atribuído um peso, que é ajustado dinamicamente utilizando estatísticas de iterações anteriores. Esse peso mede o sucesso da heurística executada

recentemente e é atualizado a cada segmento. Um segmento é composto, geralmente, por 100 iterações ou por tempo de processamento. Em cada iteração, uma heurística de remoção e uma de inserção são escolhidas independentemente e aplicadas conjuntamente. Quando maior a pontuação, mais bem sucedida é a heurística. A metodologia proposta foi capaz de melhorar as melhores soluções conhecidas na literatura para mais de 50% dos problemas, indicando a vantagem de utilizar várias heurísticas de remoção e inserção concorrentemente ao invés de apenas um par de heurísticas. Tal procedimento representa a capacidade de adaptação às características de cada instância. Os mesmos autores integraram posteriormente novas heurísticas de remoção ao ALNS. Três novas heurísticas de remoção: Cluster, Neighbor Graph e Request Graph foram propostas e o problema passou a cobrir uma classe de Problemas de Roteamento de Veículos (ROPKE; PISINGER, 2006b). Mais tarde, os autores propuseram três novas heurísticas de remoção: time-oriented,

node-pair removal e historical request-pair, abrangendo diferentes variações do Problema de

Roteamento de Veículos, tais como problemas com janelas de tempo, capacidade restrita, número variável de depósitos, entre outras variações (PISINGER; ROPKE, 2007).

Pepin et al. (2009) compararam a performance de cinco heurísticas na resolução do Problema de Programação de Veículos com Múltiplos Depósitos (Multiple Depot Vehicle

Scheduling Problem - MDVSP). Dado um conjunto de viagens e uma frota de veículos

posicionados em um conjunto de depósitos, deve-se encontrar escalas de custo mínimo onde cada viagem é realizada apenas uma vez por cada veículo e o número de veículos por depósito não seja excedido. As heurísticas propostas são: o método branch-and-cut, heurística Lagrangiana, Geração de Colunas, LNS e a Busca Tabu. Para utilizar o LNS no MDVSP, r blocos de veículos da solução corrente são destruídos a cada iteração, e posteriormente são reotimizados utilizando uma heurística de geração de colunas. A seleção desses r blocos de veículo é realizada por três estratégias: Random Schedules, Less Frequent

Schedules e Closest Schedules, utilizadas para diversificar a busca. Tais estratégias são

escolhidas aleatoriamente, de acordo com seus respectivos pesos, ajustados dinamicamente durante o processamento. Os resultados computacionais aplicados a instâncias geradas aleatoriamente, mostram que a heurística de geração de colunas tem o melhor desempenho quando tem-se tempo computacional suficiente. Por outro lado, o LNS é a melhor alternativa quando espera-se por soluções de boa qualidade em tempo computacional relativamente curto.

Kovacs et al. (2012) resolveram o Problema de Roteamento e Programação de Técnicos de Serviço e Manutenção (Service Technician Routing and Scheduling Problem - STRSP) por meio do ALNS. O STRSP é um problema de planejamento operacional que deve ser resolvido diariamente. Assim, um conjunto de tarefas devem ser executadas por um dado conjunto de técnicos especializados em diferentes áreas e com diferentes níveis de competência. Estes técnicos podem ser agrupados em times que permanecem juntos durante todo o dia e completam todas as tarefas que são a eles atribuídas. A

Capítulo 3. Revisão Bibliográfica 38

solução inicial é construída utilizando uma heurística gulosa e os autores propõem quatro heurísticas de remoção: Random, Worst, Shaw e Cluster, e três heurísticas de inserção:

Greedy, Sequential e Regret. Ao contrário de Ropke e Pisinger (2006a), onde a heurística

de inserção é escolhida independentemente da heurística de remoção, os autores usam pontuação para os pares de heurísticas. Assim, são analisadas todas as combinações, e elas são escolhidas através do método da roleta. Os pesos são ajustados dinamicamente durante a busca. Soluções de alta qualidade em tempo computacional curto foram encontradas empregando a metodologia descrita.

Ribeiro e Laporte (2012) utilizaram a ALNS para resolver o Problema de Rotea- mento de Veículos com Capacidade Cumulativa, conhecido na literatura como Cumulative

Capacitated Vehicle Routing Problem (CCVRP). O objetivo do CCVRP consiste em mini-

mizar o somatório dos tempos de chegada aos consumidores ao invés de minimizar o custo total de roteamento. A solução inicial adotada pelos autores é construída por meio da heurística construtiva Regret-3. Sete heurísticas de remoção e três heurísticas de inserção foram implementadas: duas Remoções do tipo Shaw, baseadas nos tempos de chegada e nas distâncias, Remoção Random, Worst, Cluster, Neighbor Graph e Request Graph, e as Inserções Basic Greedy, Deep Greedy e Regret-k. Os resultados obtidos pelos autores foram aplicados a um conjunto de instância de benchmark, superando a maioria das melhores soluções conhecidas.

Ribeiro, Laporte e Mauri (2012) compararam três metaheurísticas na resolução do Problema de Roteamento de Sondas de Produção, conhecido por Workover Rig Routing

Problem (WRRP). O WRRP é uma variação do Problema de Roteamento de Veículos com

Janelas de Tempo e surge ao operar em campos petrolíferos terrestres. Neste problema, um conjunto de sondas de produção, localizadas em diferentes posições, devem atender os poços de petróleo que requerem manuntenção o mais rápido possível, uma vez que em manutenção, sua produção é interrompida por questões de segurança e a sonda de operação deve atender dentro de um determinado prazo. Dessa forma, o WRRP consiste em minimizar a perda total da produção, dada por encontrar o melhor roteamento para as sondas de forma que todos os pedidos sejam atendidos dentro de seus prazos, e também minimizar a perda do óleo. Foram comparadas as metaheurísticas Iterated Local Search (ILS), Clustering Search e a ALNS. Como métodos de remoção da ALNS, os autores implementaram duas versões da Remoção Shaw, baseadas na contribuição dos poços à FO e nas suas distâncias, respectivamente. Também foram implementadas a Remoção Random,

Worst e Route, que destrói completamente um roteamento aleatoriamente selecionado.

Para reconstruir as soluções, foram adotadas as Inserções Basic Greedy, Deep Greedy e

Regret-k. O desempenho das três abordagens foram similares nas intâncias de 50 poços.

No entanto, a ALNS se sobressaiu nas instâncias maiores.

WRRP com frotas heterogêneas em um horizonte de planejamento finito: VNS, branch-

price-and-cut (BPC), ALNS e um AG híbrido. Na ALNS implementada, as heurísticas de

remoção Shaw, Random, Worst, Cluster, Neighbor Graph e Request Graph foram utilizadas para parcialmente destruir as soluções. Para reparar as soluções destruídas, foram utilizadas as heurísticas de inserção Basic Greedy, Extensive Greedy e Regret. Para os problemas testados, o Algoritmo Genético híbrido soubressaiu-se aos demais métodos na maioria dos casos. No entanto, a ALNS também apresentou resultados melhores que o VNS e a BPC.

A ALNS também foi utulizada por Mauri et al. (2016) ao resolver o Problema de Alocação de Berços de Atracação, conhecido na literatura por Berth Allocation Problem (BAP). O BAP consiste em atribuir os navios aos berços de atracação ao longo de um cais do porto. A principal decisão a ser tomada neste problema é quando e onde os navios devem se mover, sujeita a restrições relacionadas à profundidade do local e ao tamanho do navio, e também relacionadas ao tempo de atracação dos navios, modelado como janelas de tempo. Pretende-se então minimizar o tempo total gasto pelos navios nos portos. Os modelos discretos e contínuos do BAP foram resolvidos pela ALNS. Duas versões da Remoção Shaw foram implementadas, baseadas na diferença absoluta entre o custo de dois navios na solução e no tempo de chegada dos navios, respectivamente. Além disso, foram implementadas a Remoção Random e Worst. Para reconstruir as soluções, foram adotadas as Inserções Regret-k e Deep Greedy. Os resultados alcançados pela ALNS superaram outras metodologias competitivas para o mesmo problema, com melhorias estatisticamente significativas na maioria dos casos.