O método de construção de uma solução para o problema de roteamento de veículo com serviços de coleta e entrega é baseado no algoritmo proposto por Dethloff [2001]. A heurística baseada em inserção (IBH, do inglês Insertion-Based Heuristic), utiliza o conceito "Inserção Mais Barata". Inicialmente, o algoritmo deve escolher um consumidor (semente) e define uma nova rota: depósito −→ semente −→ depósito. Posteriormente, é analisada a inserção de cada consumidor restante em cada posição viável da rota atual. Cada uma dessas alternativas é avaliada de acordo com alguns critérios de inserção.
Neste trabalho foram utilizados dois critérios de inserção: critério de inserção viável mais barato (MB) e critério de inserção viável mais próximo (MP). Para cada critério de inserção, foram utilizadas duas estratégias de inserção: sequencial (S) e paralela (P).
O algoritmo 5.5 apresenta o pseudocódigo do algoritmo proposto por Penna et al. [2013]. O algoritmo primeiramente estima o número de veículos a ser utilizado para satisfazer as de- mandas dos consumidores (linha 1). Posteriormente, dada esta estimativa, são criadas rotas vazias (linhas 6–9). Cada rota vazia é inicializada com um consumidor selecionado aleatori- amente de uma lista de candidatos (linhas 10–14). Em seguida, seleciona-se aleatoriamente um critério de inserção e uma estratégia de inserção para geração de uma solução (linhas 15– 21). Se a solução retornada é inviável o procedimento é repetido até que um número máximo de repetições (MaxNumT entativas) pré-estabelecido seja alcançado. Quando isso ocorre,
o procedimento é repetido considerando um veículo a mais para geração da solução (linhas 22–28). Quando uma solução viável é encontrada, esta solução é retornada.
Nas subseções 5.4.1.1 5.4.1.2, 5.4.1.3 são apresentados os detalhes dos procedimentos de estimativa do número de veículos, estratégia e critério de inserção, respectivamente, aplicados ao algoritmo de geração da solução inicial.
Algoritmo 5.5 Algoritmo para gerar uma solução inicial [Penna et al., 2013]
1: v ← Estimar Número Veículos(); 2: repita
3: N umT entativas ← 0;
4: ConsumidoresCandidatos ← Criar Lista Consumidores Candidatos(); 5: Rotas ← Criar Conjunto de Rotas();
{Criar v rotas vazias};
6: para i = 1 até v faça
7: Rotai ← Criar Rota Vazia(); 8: Rotas ← Rotai;
9: fim para
{Selecionar aleatoriamente v consumidores da lista de candidatos};
10: para i = 1 até v faça
11: ci ← Selecionar Aleatoriamente(ConsumidoresCandidatos); 12: Rotai ← ci;
13: ConsumidoresCandidatos ← ConsumidoresCandidatos − ci; 14: fim para
{Selecionar aleatoriamente um critério de inserção e uma estratégia de inserção}
15: CriterioInsercao ← Selecionar aleatoriamente({M B, M P });
16: EstrategiaInsercao ← Selecionar aleatoriamente({S, P }); 17: se EstrategiaInsercao = S então
18: solucao ← Sequencial(v, ConsumidoresCandidatos, CriterioInsercao);
19: senão
20: solucao ← P aralela(v, ConsumidoresCandidatos, CriterioInsercao);
21: fim se
22: se solucao é inviável então
23: N umT entativas ← N umT entativas + 1;
24: se N umT entativas = M axN umT entativas então
25: v ← v + 1; 26: fim se
27: fim se
28: até solucao viável
29: retornar solucao;
5.4.1.1 Estimativa do Número de Veículos
A estimativa do número de veículos permite que o algoritmo de geração de solução inicial alcance uma solução de melhor qualidade, onde poucos veículos são utilizados. Pode-se veri- ficar nos trabalhos da literatura que, ao reduzir o número de veículos, o custo de transporte
também é reduzido para problemas de roteamento de veículos capacitado, bem como para os problemas de roteamento de veículos com serviços de coleta e entrega. A proposta dessa esti- mativa é que um menor número de veículos seja utilizado de forma que eles possam atender as demandas dos consumidores.
O algoritmo 5.6 apresenta o pseudocódigo do procedimento de estimativa do número de veículos. Primeiramente considera-se a utilização de um único veículo e, então, um consumidor é selecionado aleatoriamente, dado uma lista de consumidores candidatos que ainda não foram adicionados a solução parcial, para ser incluído na rota deste veículo.
A inclusão do consumidor na rota é dada pela inserção mais barata, onde todas as po- sições da rota são avaliadas e a inserção na posição que retornar menor custo é executada. Enquanto houver consumidores na lista de consumidores candidatos este procedimento é re- petido. Quando nenhum consumidor da lista puder ser inserido na rota atual, uma nova rota é gerada e o procedimento continua.
Algoritmo 5.6 Algoritmo para estimar número de veículos
1: ConsumidoresCandidatos ← Criar Lista Consumidores Candidatos();
2: Rota ← CriarRotaV azia();
3: c ← Selecionar Aleatoriamente(ConsumidoresCandidatos);
4: Remover c da lista ConsumidoresCandidatos; 5: enquanto |ConsumidoresCandidatos| > 0 faça
6: para cada consumidor c ∈ ConsumidoresCandidatos faça
7: para cada posição p ∈ Rota faça
8: custoc,p ← Calcula custo da rota caso o consumidor c seja inserido na posição
p da Rota;
9: fim para
10: fim para
11: se não nenhum consumidor c ∈ ConsumidoresCandidatos puder ser inserido a Rota sem que a capacidade do veículo seja extrapolada então
12: Rotas ← Rota;
13: Rota ← CriarRotaV azia();
14: senão
15: menorCustocmin,pmin ← M IN {custoc,p};
16: Inserir consumidor cmin na posição pmin da Rota; 17: Remover c da lista ConsumidoresCandidatos; 18: fim se
19: fim enquanto
20: retornar Rotas;
5.4.1.2 Critério de Inserção
Os critérios de inserção utilizados neste trabalho baseiam-se na heurística de inserção, a qual foi proposta por Dethloff [2001] para solucionar o problema de roteamento de veículos com coleta e entrega simultâneas.
Segundo Dethloff [2001], dada uma lista de consumidores candidatos a serem inseridos na solução, uma simples abordagem gulosa (gc) irá analisar o custo da inserção de um consumidor c, pertencente a esta lista, considerando apenas o aumento do custo de transporte da rota R após a inserção do consumidor c entre os consumidores i e j.
gc = Cic+ Ccj− Cij, ∀c ∈ Lista de Consumidores Candidatos ∧ ∀(i, j) ∈ R (5.1)
Quando o procedimento de inserção é baseado apenas no custo de transporte (gc), o critério de inserção é denominado: critério de inserção viável mais barato (MB).
Assim, calculado o custo de transporte, aquela inserção que retorne o menor custo é aplicada. Este procedimento é feito para todos os consumidores da lista de consumidores candidatos e em todas as posições viáveis da rota.
Esse critério de inserção é extremamente simples e não verifica alguns aspectos, como:
1. O efeito de uma inserção viável na carga de um veículo, ou seja, o grau de liberdade para futuras inserções.
2. Consumidores localizados remotamente podem ser deixados para serem inseridos em estágios de inserção tardios, resultando em um distância trafegada desfavorável.
Dessa forma, um outro critério de inserção é utilizado neste trabalho: critério de inserção viável mais próximo (MP). Este critério calcula a distância do consumidor para o depósito, evitando que consumidores localizados remotamente sejam inseridos de forma tardia. Assim sendo, o custo final de uma inserção de um consumidor na rota é dado pela soma ponderada do critério guloso e do critério de inserção viável mais próximo.
gc = (Cic+ Ccj− Cij) − γ(C0c+ Cc0), ∀c ∈ Lista de Consumidores Candidatos ∧ ∀(i, j) ∈ R (5.2) O critério referente ao efeito de inserção de um consumidor na carga do veículo não foi implementado neste trabalho devido ao seu custo computacional.
5.4.1.3 Estratégia de Inserção
Duas estratégias de inserção foram implementadas neste trabalho, sendo que o foco de uma delas é na rota e o foco da outra é nos consumidores candidatos. Dada uma rota, a primeira estratégia, denominada estratégia sequencial, avalia o custo de inserir cada consumidor da lista
de consumidores candidatos na rota dado o critério de inserção selecionado (seção 5.4.1.2). Em seguida, ele seleciona outra rota e repete o procedimento.
A outra estratégia, denominada estratégia paralela, avalia o custo de inserção de cada consumidor da lista de consumidores candidatos em cada posição viável de cada rota. A inserção que retornar menor custo é, então, aplicada. O custo é obtido de acordo com os critérios de inserção mencionados anteriormente. Este procedimento é repetido até que todos os consumidores do problema estejam inseridos na solução.
A primeira estratégia considera uma única rota a cada inserção de consumidor da lista de candidatos, enquanto a segunda considera todas as rotas para inserir os consumidores. Assim sendo, as soluções retornadas pela estratégia sequencial são mais balanceadas.
Os algoritmos 5.7 e 5.8 apresentam o pseudocódigo das duas estratégias de seleção. Algoritmo 5.7 Algoritmo de Inserção Sequencial
Entrada: CriterioInsercao, conjunto Rotas
1: γ ← 0;
2: se CriterioInsercao = M P então
3: γ ← Definir valor da ponderação;
4: fim se
5: enquanto |ConsumidoresCandidatos| > 0 ∧ ∃c ∈ ConsumidoresCandidatos que pode ser adicionado ao conjunto Rotas faça
6: para cada rota i ∈ Rotas faça
7: para cada consumidor c ∈ ConsumidoresCandidatos faça
8: para cada posição viável p ∈ Rotai faça
9: custoc,p ← Calcular o custo de inserção do consumidor c na posição p da
rota i dado o critério de inserção selecionado;
10: fim para
11: fim para
12: menorCustocmin,pmin ← M IN {custoc,p};
13: Inserir consumidor cmin na posição pmin da rota i;
14: Remover consumidor cmin da lista ConsumidoresCandidatos; 15: fim para
16: fim enquanto