Como forma de comparar as rotas realizadas pela empresa com as elaboradas por softwares de otimização, numa primeira fase foi escolhida uma semana de trabalho e listados os clientes que foram satisfeitos na segunda-feira, 18 clientes. Depois com recurso à ferramenta Google Maps foram retiradas
as coordenadas da JPZ e dos 18 clientes, sendo de seguida coladas num ficheiro de texto as mesmas como mostra a Figura 25.
Figura 25 - Coordenadas da localização da empresa e dos 18 clientes
Com recurso ao site oficial do NEOS Server (https://neos-server.org/neos/) foi submetido o ficheiro anterior com as coordenadas, mais concretamente, na plataforma NEOS Server utilizou-se o solver designado por “Concorde” que é disponibilizado pelo NEOS SERVER para solucionar o problema do caixeiro viajante.
Deste passo resultou a rota presente na Figura 26 que aparenta não ser uma solução otimizada, dado que facilmente se consegue fazer ligações entre vértices com menos distâncias do que as que se observam na figura.
Figura 26 - Mapa resultante da instância da Figura 25 no NEOS Server
Como intenção de explicar o sucedido, pesquisou-se a forma como são trabalhados os dados inseridos no Concorde. Foi possível compreender que é utilizada uma função de arredondamento (“nint”), que arredonda os valores inseridos com casas decimais para um valor inteiro. Concluiu-se que as coordenadas X foram arredondadas para “-8” e as coordenadas Y para “41”. Na prática resultou na sobreposição dos vértices e consequentemente todas as distâncias entre os vértices foram assumidas como nulas. Deste modo a solução apresentada na Figura 26 é uma solução ótima alternativa porque todas as distâncias são nulas.
Para contornar a situação do arredondamento e tendo em conta que quer as coordenadas X, quer as Y diferiam apenas nas casas decimais, somou-se “8” a cada coordenada X e subtrai-se “41” a cada coordenada Y dos 19 vértices ficando apenas com seis casas decimais. De seguida multiplicou-se cada valor por “10000” para que se pudesse diferenciar cada coordenada suficientemente bem para o NEOS Server. As coordenadas daqui resultantes estão presentes na Figura 27.
41. 25 41.3 41.35 41.4 45 41. 41.5 41.55 41.6 41.65 -8.65 -8.6 -8.55 -8.5 -8.45 -8.4 -8.35 -8.3 -8.25 -8.2 -8.15 1 14 6 4 18 10 8 13 19 2 7 16 11 12 15 17 5 3 9 · lis t o f cities with 2-d co ordin ates · -- dim en sion =1 9
Figura 27 - Coordenadas da instância de 19 vértices modificadas
Pela análise da Figura 27 é possível verificar que mesmo após as coordenadas serem submetidas no NEOS Server, estas vão diferir bastante entre si não havendo o risco de o arredondamento para valores inteiros resultar em coordenas iguais. A solução obtida é apresentada graficamente na Figura 28.
Figura 28 - Rota resultante da submissão das coordenadas dos 19 vértices modificadas.
Observando a Figura 28, conclui-se facilmente que é a rota otimizada. Todos os clientes são visitados e a distância total percorrida entre vértices aparenta ser a menor possível. O NEOS Server informa que a distância total da rota é 16958, que ao dividir-se pelos 10000 anteriormente multiplicados nas coordenadas, temos 1,6958.
Para calcular a distância entre vértices, o Concorde no NEOS Server utiliza a distância euclidiana simétrica. Embora não seja a distância real das estradas disponíveis, esta aproximação, permite obter em poucos segundos a solução da instância que irão ajudar a tirar algumas conclusões.
A fórmula utilizada para calcular a distância entre dois pontos é então a do Teorema de Pitágoras, sendo equivalente a (2).
𝑑2 = 𝑎2+ 𝑏2 (2)
Tendo dois pontos e imaginando um terceiro, de forma a que os três formem um triângulo retângulo, o cálculo da distância entre os dois pontos reside em calcular o valor da hipotenusa do triângulo (Vitor Nunes, n.d.). Ao resolver o Teorema de Pitágoras em ordem à hipotenusa temos a fórmula para calcular a distância entre dois pontos (3). Sendo 𝑑, a distância entre os vértices 𝑎 e 𝑏 e as coordenadas dos vértices 𝑎 e 𝑏 representadas por (𝑥𝑎, 𝑦𝑎) e (𝑥𝑏, 𝑦𝑏), respetivamente.
𝑑 = √(𝑥𝑏− 𝑥𝑎)2+ (𝑦
𝑏− 𝑦𝑎)2 (3)
Recorreu-se também ao NEOS Server para estudar o problema do caixeiro viajante múltiplo (mTSP) que deriva do problema do caixeiro viajante (TSP). Ou seja, é semelhante ao TSP mas em vez de se utilizar 1 caixeiro viajante são utilizados 𝑚 caixeiros viajantes para se proceder à visita dos vértices (Oliveira, 2015).
Com base na instância dos 18 clientes satisfeitos na segunda-feira, apresentada anteriormente, e com o objetivo de modelar o 2-TSP (utilização de “dois caixeiros viajantes”), repetiu-se no final as coordenadas do armazém para assim se obter duas rotas como mostra a Figura 29 à esquerda.
Ainda na Figura 29 à direita é possível observar o resultado do problema MTSP submetido. Neste temos 3 colunas, a primeira corresponde ao vértice de partida de uma aresta, a segunda ao vértice de chegada e a terceira à distância dessa mesma aresta. Cada linha da solução obtida corresponde assim a uma aresta. O NEOS Server desconta uma unidade à numeração original dos vértices e, dado que a solução começa na segunda linha, a solução inicia então com a aresta “0 19” que corresponde a ir do vértice 1 ao 20.
O mTSP é conhecido por não balancear os comprimentos das rotas, o que origina a que não possa ser utilizado na sua maioria quando o objetivo é este. O resultado obtido não foi de agrado, pois o NEOS Server gerou duas rotas, em que a primeira no fundo se cinge a ir do armazém ao armazém (dado que o vértice 1 e 20 são os mesmos) e a segunda, que visita todos os clientes da instância. O expectável seria que o NEOS Server gera-se uma rota com os clientes mais a norte de Guimarães (ex.: Barcelos) e outra rota com os que estão mais a sul de Guimarães (ex.: Porto).
Este processo foi repetido algumas vezes, acrescentando de forma gradual as coordenadas do armazém. As soluções ótimas obtidas continuaram a não ser satisfatórias.
O propósito de recorrer ao m-TSP foi o de encontrar o valor mínimo de custo da instância em estudo para mais tarde se enquadrar/comparar com as soluções heurísticas do VRP.
Com o auxílio do Google Maps obteve-se o custo mínimo de partir do armazém da JPZ, visitar todos os clientes e regressar, ou seja, calculou-se a distância mínima para percorrer o caminho ótimo obtido para o problema do caixeiro viajante. A distância total é de 262,49 quilómetros, sendo necessárias 4 horas e 39 minutos para a viagem (sem contar com o tempo necessário para realizar as descargas de mercadoria nos respetivos clientes).
Após analisados os resultados apresentados pelo NEOS Server para o problema do Caixeiro Viajante para os 18 clientes (um dia de trabalho), era importante comparar estes mesmos resultados com os que se obteriam num outro programa de otimização.