No presente caso foram exploradas três diferentes vizinhanças denominadas InvertSol, Insert&Saving e 2 Shift, respectivamente.
Como primeira etapa de busca foi escolhido o InvertSol cujo procedimento inverte o sentido do percurso da rota, preservando o sentido de menor custo. Trata se de um procedimento (Quadro 8) simples e barato de inversão de sequência de cidades em toda a solução.
Quadro 8 – Pseudocódigo do procedimento ! do VND
Algoritmo 8 – Procedimento inverteSolucao( )
1 inverteSolucao(sol)
2 sol* ⃪ sol 3 aux ⃪ sol
4 para i de 1 até nCid faça
5 aux.carro[i] = sol.carro[nCid6i] 6 aux.rota[i] = sol.rota[nCid6i] 7 fim para 8 se f(sol) < f(sol*) 9 sol* ⃪ sol 10 fim se 11 sol ⃪ aux 12 fim para 13 retorna(sol*)
Apesar de pe inversão mudaram se a possibilitando se assim o de taxas de aluguéis é ass
A Figura 13 inversão. A solução inicial a rota de 100 e realiza a estas trocas uma penalida ciclo do alugador corresp resultante do procedimen Observa se que o valor também permanecem os serão de aluguel e de de sofrem alteração e como n
(a) Solução Inicia
Rota: 0 10 12 1 11 6 9 8 7 Trocas: 0 12= 8, 12 9= 11, 9
Valor da Solução =
Figura 13 – Ilustração do pro
Na segunda et aplicada a estrutura de procedimento procura ins rota diminua. Considerand que reste pelo menos um
O procedimento designado na rota e exam cidades da rota, substituin rota entre dois carros já d rota de menor custo, entã encontrada. O procedimen considerados para a inserç
e permanecerem os mesmo pontos de tr se as cidades de aluguel e entrega d sim o encontro de melhores resultados, visto
é assimétrica.
ilustra o resultado da solução após a inicial, mostrada na Figura 13(a), possui um va
liza ao todo 3 trocas ao longo do caminho nalidade de 26 unidades de valor, portanto o orresponde a 126. A Figura 13(b) demonst
dimento de busca InvertSol aplicado a so valor da rota permanece o mesmo, os pon s mesmos, porém ocorre à inversão em de devolução dos veículos. Consequenteme omo no caso, diminuem o valor total da soluçã
o Inicial (b) Solução Invert
7 5 2 4 3= 100 0= 7, Taxas= 26 ção = 126 Rota: 0 3 4 2 5 7 8 9 6 11 Trocas: 0 9= 4, 9 12= 6, 12 0= Valor da Solução = o procedimento ! do VND
da etapa de busca local realizada no algori de vizinhança Insert&Saving descrita no ra inserir um carro na rota de forma que o c
erando S uma solução que possui pelo meno s um carro ainda não alugado em S.
imento Insert&Saving escolhe aleatoriamente u examina a possibilidade de inseri lo em ca stituindo um carro já existente, ou ocupando
s já designados. Se um desses dois casos , então a solução é reescrita segundo a nova dimento continua até que não existam mais ca inserção.
de troca, com a ga dos veículos, visto que a matriz ós a operação de um valor referente inho, pagando por nto o valor total do onstra a solução a solução inicial. s pontos de troca o em quais pontos ntemente as taxas solução final. Invertida 1 12 10= 100 0= 3, Taxas= 13 ção = 113 algoritmo VND foi no Quadro 9. O e o custo total da menos um carro e
ente um carro não em cada uma das ando um trecho da asos produzir uma nova configuração ais carros a serem
Quadro 9 – Pseudocódigo do procedimento " # ! do VND
Algoritmo 9 – Procedimento Insert&Saving do VND
1 insert&Saving(sol)
2 sol* ⃪ sol 3 aux ⃪ sol
4 quantAlugueis ⃪ QuantCarros(sol)
5 para i de 1 até nCar2quantAlugueis faça 6 iCar ⃪ proximoCarro(sol)
7 para cada j ∊ sol faça
8 sol ⃪ insereNovoCarro(iCar) 9 se f(sol) < f(sol*) 10 sol* ⃪ sol 11 fim se 12 fim para 13 sol ⃪ aux 14 fim para 15 retorna(sol*)
No algoritmo do Quadro 9 o procedimento quantCarros( ) conta na solução corrente a quantidade de carros que está sendo utilizada. No laço representado entre os passos 5 a 12, o algoritmo testa a inserção dos carros não utilizados na solução descoberta no procedimento proximoCarro( ). A inserção é testada no passo 8, insereNovoCarro(), explorando todas as posições possíveis nos trechos de cada carro. A busca insert&Saving do VND opera apenas nas informações referentes aos carros, sem alterar a ordem das cidades do percurso.
Em uma terceira etapa, a busca explora a vizinhança 2 Shift testando movimentos de troca simples na sequência das cidades pertencentes ao percurso de um determinado veículo, na procura de melhores soluções. O pseudocódigo (Quadro 10) demonstra o procedimento de busca shift aplicado ao VND.
O procedimento 2 Shift examina os caminhos de cada carro, dentro do tour geral, realizando os deslocamentos (shifts) entre uma cidade da rota e sua vizinha, para todas as cidades da rota. Os caminhos dos carros são examinados em sequência. Cada vez que uma melhoria é alcançada, a solução S é atualizada.
Os conteúdos das posições j e j+1 são trocados (cidade e carro correspondente) no procedimento fazTroca(Sol,j). Todas as trocas são consideradas.
Um procedimento de reparação provavelmente será necessário para reparar a solução caso o procedimento 2 Shift transforme Sol em uma solução inviável. Neste caso, a inviabilidade é verificada quando um carro é alugado mais de uma vez.
Quadro 10 – Pseudocódigo do procedimento 2&S do VND
Algoritmo 10 – Procedimento 2 Shift do VND
1 aplica2Shift(sol)
2 sol* ⃪ sol 3 aux ⃪ sol
4 para cada j ∊ Sol faça 5 sol ⃪ fazTroca(Sol,j) 6 sol ⃪ repararSolucao(sol) 7 se f(sol) < f(sol*) 8 sol* ⃪ sol 9 fim se 10 sol ⃪ aux 11 fim para 12 retorna(sol*)
Como na heurística 2 Shift a restrição de não repetição do aluguel do veículo pode ser violada, a solução é corrigida pela função reparadora repararSolucao(sol). O problema do carro repetido é resolvido pela substituição da segunda ocorrência pelo carro imediatamente anterior utilizado na sequência. As cidades repetidas são substituídas aleatoriamente pelas cidades esquecidas na solução. Os carros designados para estas cidades incluídas na solução permanecem os mesmos depois da substituição.
5.5 Experimentos Computacionais
A presente seção apresenta experimentos computacionais no sentido de validar o algoritmo VND proposto, e o faz através de uma comparação de desempenho com o algoritmo GRASP apresentado no capítulo anterior.
Os testes preliminares para afinação de parâmetros do Algoritmo VND proposto foram executados sobre um conjunto de 20 instâncias CaRSLIB, com um número de cidades na faixa de 14 a 300 e 2 a 5 veículos.
Foi definido para o parâmetro máximo de iterações (maxIter = 100) com um critério de parada adicional estabelecendo que o algoritmo pare depois de 30% do número máximo de iterações sem melhoria da melhor solução corrente (0.30*maxIter).
O gráfico da Figura 14 ilustra o comportamento da média das soluções em 8 instâncias do conjunto de teste para o parâmetro maxiter variando entre 50 a 150. Conclui se que o parâmetro maxIter possui desempenho mais eficiente com a regulagem no valor de 100 unidades.
Figura 14 – Gráfico do compo
5.5.1 Resultados