Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais

30 De Setembro de 2015 Orientadora: Professora Doutora Dalila B. M. M. Fontes Coorientador: Professor Doutor José Fernando Gonçalves Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais ANDREIA PATRÍCIA FERREIRA SOUSA DISSERTAÇÃO DE MESTRADO EM MODELAÇÃO, ANÁLISE DE DADOS E SISTEMAS DE APOIO À DECISÃO OTIMIZAÇÃO Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 2 Nota Biográfica Andreia Patrícia Ferreira Sousa nasceu em Oliveira de Azeméis a 18 de Janeiro de 1991. Terminou o ensino secundário em Ciências Sócioeconómicas na Escola Secundária Serafim leite, em 2009. Licenciou-se em Gestão, em 2012, na Faculdade de Economia do Porto, com média final de 14 valores. Em 2012, tomou a iniciativa de ingressar no Mestrado em Modelação, Análise de Dados e Sistemas de Apoio à Decisão (MADSAD). Esse desejo implicou um novo e intenso desafio na sua vida: o de conciliar a vida profissional com a académica. Em 2015, prevê concluir o seu mestrado sob a orientação do Profª. Dr.ª. Dalila B. M. M. Fontes e coorientação do Prof. Dr. José Fernando Gonçalves. Com vista ao término do mesmo pretende apresentar a dissertação intitulada por “Um Algoritmo Genético para O Planeamento De Rotas Com Considerações Ambientais”. Iniciou a sua atividade profissional em 2012, numa mediação de seguros, UnânimeSeguros - Mediação de Seguros Lda., onde trabalhou como Assistente Comercial até Julho de 2015. Atualmente integra a equipa de Packing Support do departamento de logística da Parfois, como Analísta de Logística. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 3 Agradecimentos Em primeiro lugar quero agradecer à Professora Doutora Dalila Martins Fontes, pela sua orientação, total apoio, disponibilidade, pelo conhecimento que transmitiu, pelas opiniões e críticas, total colaboração no solucionar de dúvidas e problemas que foram surgindo ao longo deste trabalho e por todas as palavras de incentivo. Ao Professor Doutor José Fernando Gonçalves, pela sua disponibilidade em ajudar-me e por me ter proporcionado a oportunidade de desenvolver esta dissertação com a sua coorientação. Fico grata por toda a sua compreensão e pela motivação dada nos momentos certos. Quero agradecer aos meus colegas e amigos de Mestrado, em especial, ao Dinis Machado, Cláudia Dias e ao Tiago Ramos, pelo companheirismo, pela interajuda, pela motivação dada e os desabafos ouvidos. Sem eles todo este percurso não teria sido uma experiência tão enriquecedora. Às minhas amigas, que são as melhores amigas do mundo, Inês Vinhas, Catarina Brito, Daniela Ferreira, entre outras, que não menciono o nome mas que sabem quem são. Amigas que estiveram ao meu lado durante esta longa fase, obrigada pelo companheirismo, força e apoio nos momentos certos e difíceis. Obrigada por todo o incentivo que me deram, por terem aturado os meus momentos de desespero e por me terem proporcionado momentos de distração nas alturas certas, foram sempre excecionais durante todo o percurso. Por último, tendo consciência que sozinha nada disto teria sido possível, dirijo um agradecimento especial ao meu Pai, tia Zira, irmãos (ã), cunhadas(o) e sobrinhos, pelo apoio incondicional, incentivo, amizade, paciência e total ajuda na superação de obstáculos que ao longo desta caminhada surgiram. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 4 Dedicatória “Ninguém escapa ao sonho de voar, de ultrapassar os limites do espaço onde nasceu, de ver novos lugares e novas gentes. Mas saber ver em cada coisa, em cada pessoa, um objeto singular, um amigo – é fundamental. Navegar é preciso, reconhecer o valor das coisas e das pessoas, é mais preciso ainda!!!” Antonie de SaintExupéry À pessoa que me ensinou todos os valores essenciais a um ser humano e que sempre me deu força para terminar esta etapa com sucesso, à minha Mãe. Apesar de nunca poder vir a dizer-te isto pessoalmente, obrigada pela força mesmo quando eras tu que precisavas, pela preocupação diária com o decorrer do mestrado e por acreditares sempre em mim mesmo nos momentos em que vacilei e pensei em desistir. Foste a melhor pessoa que conheci, na vida, e continuas a ser o meu apoio diário na maioria das dificuldades. Por tudo isso e por seres para sempre a melhor mãe do mundo é a ti que dedico, de coração, mais esta conquista da minha vida! E porque o “essencial será sempre invisível aos olhos “. Amo-te! Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 5 Sumário O ambiente extremamente competitivo que as empresas encontram nos mercados onde atuam pressiona-as a otimizar a prestação de serviços Neste trabalho, estuda-se o transporte de mercadorias com o objetivo de diminuir os custos envolvidos tendo em conta algumas preocupações ambientais, como o nível de emissões de CO2, poluição sonora, entre outras. Mais concretamente, estuda-se a otimização de rotas desenvolvendo uma metodologia para a sua obtenção. No problema abordado considera-se o abastecimento de um conjunto de clientes a partir de um armazém central recorrendo a uma frota de veículos com capacidade limitada. Pretendem-se determinar as rotas, isto é o conjunto sequencial de clientes a visitar por cada veículo, de modo a satisfazer a procura dos clientes. Considera-se ainda que cada cliente é visitado uma única vez. De entre as soluções possíveis o principal interesse está em encontrar uma que minimize os custos totais. Preocupações ambientes são modeladas por incorporação na função objetivo dos custos incorridos com o combustível consumido e dos custos/ benefícios incorridos com a compra/venda de licenças de emissão de CO2. Este problema é NP-completo pelo que não é possível obter soluções ótimas para instâncias de tamanho razoável em tempo útil. Assim, optou-se por recorrer aos algoritmos genéticos para encontrar soluções de boa qualidade num tempo computacional aceitável. Foi desenvolvido um algoritmo genético baseado em chaves aleatórias e os resultados obtidos foram comparados com resultados recentemente publicados na literatura. Como se pode ver no Capítulo 7 os resultados obtidos nesta dissertação são em alguns casos melhores do que os publicados na literatura. De notar ainda que o tempo computacional necessário á obtenção dos resultados é inferior ao reportado na literatura (tendo em conta os computadores usados). A qualidade dos resultados obtidos aponta para a superioridade Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 6 do método proposto neste documento pelo que será interessante desenvolver e incorporar, no mesmo rotinas de pesquisa local de modo a intensificar a procura (de boas soluções) em regiões promissoras do espaço de soluções admissíveis. Palavras-Chave: Logística, Otimização, Planeamento de rotas de transporte, Preocupações ambientais, Algoritmos Genéticos. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 7 Abstract The highly competitive environment that companies face in their markets presses them to improve services. In this work, we study the problem of timely supplying customers, while minimizing costs. Environmental considerations are taken into account since the costs considered include costs with CO2 emissions, noise pollution, among others. More specifically, we study a vehicle routing problem (VRP) for which a mixed integer linear programming model is formulated and a methodology to solve it is purposed. The problem under study involves supplying a set of geographically dispersed customers from a central depot using a fleet of vehicles with limited capacity. Thus, we wish to determine the vehicle routes, i.e. sequence of customers to be visit by each vehicle, such that customers’ demand is satisfied and vehicles’ capacity is not exceed. It is also considered that each client can be visited only once. Among the possible solutions we are interested in finding one that minimizes the total cost. Environmental concerns are modeled by incorporating into the objective function the costs incurred with fuel consumption and the costs/benefits associated with purchasing/selling CO2 emission allowances. This problem is NP-complete and thus, it is not possible to obtain an optimal solution for realistic instances in a reasonable amount of time. Therefore, we propose a genetic algorithm, based on random keys, that is capable of finding good quality solutions with small computational time requirements. The algorithms performance has been tested on benchmark problems and, as it can be seen in Chapter 7, for some problems it was able to improve on literature results. In addition, the computational time requirements seem to be smaller than those reported in the literature, when the computers use are taken into account. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 8 The quality of the results obtained points to the superiority of the genetic algorithm proposed, thus it would be interesting to develop and incorporate in it some local search capabilities in order to intensify the search around good solutions. Key-words: Logistics, Optimization, Vehicle routing problem, Environmental issues, Genetic algorithms. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 9 Conteúdo 1. Introdução .............................................................................................................. 13 1.1. Motivação ......................................................................................................... 13 1.2. Objetivos .......................................................................................................... 14 1.3. Estrutura ........................................................................................................... 15 2. Revisão Bibliográfica ............................................................................................. 18 2.1. O Problema Inicial Do TSP .............................................................................. 18 2.2. O VRP - Vehicle Routing Problem .................................................................. 19 2.3. O EVRP - Environmental Vehicle Routing Problem ....................................... 23 2.4. Estudos Realizados Na Área Da Otimização De Rotas ................................... 24 3. O Problema ............................................................................................................ 31 3.1. Definição Do Problema .................................................................................... 31 3.2. Formulação Matemática ................................................................................... 34 4. Métodos De Resolução .......................................................................................... 38 4.1. Heurísticas ........................................................................................................ 39 4.2. Meta-Heurísticas .............................................................................................. 47 4.2.1. Tabu Search (TS) ...................................................................................... 47 4.2.2. Simulated Annealing (SA) ........................................................................ 47 4.2.3. Genetic Algorithms (GAs) ........................................................................ 48 5. Os GAs – Genetic Algorithms .............................................................................. 49 5.1. Conceitos Básicos ............................................................................................ 50 5.2. Técnicas De Codificação .................................................................................. 51 5.3. População ......................................................................................................... 53 5.4. Função De Fitness ............................................................................................ 53 5.5. Operadores Genéticos ...................................................................................... 53 5.5.1. Seleção ...................................................................................................... 54 Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 16 No terceiro capítulo é apresentado o problema específico a abordar, fazendo-se a descrição do mesmo e enquadrando-o no trabalho a realizar. É feita uma exposição das principais características da frota da empresa e também uma abordagem aos clientes por ela fornecidos. Após o enquadramento teórico envolvente, apresenta-se o modelo matemático que o descreve e a respetiva notação. No quarto capítulo é apresentada a metodologia, ou seja, revelam-se as ferramentas das áreas de otimização que podem ser usadas na resolução de problemas deste tipo. No quinto capítulo são aprofundados os conceitos básicos, as técnicas de codificação, as formas de reprodução, operadores genéticos e estratégias evolucionárias dos algoritmos genéticos. A descrição do algoritmo genético desenvolvido e aplicado e dos dados utilizados é feita no capítulo seis desta dissertação. As experiências computacionais e os resultados obtidos serão apresentados e debatidos no sétimo capítulo sob as perspetivas, prática e teórica. Estes conduzirão às conclusões da dissertação que se seguem no oitavo capítulo. Sendo este o derradeiro capítulo, é nele que é feita a conclusão da dissertação e sugeridos alguns pontos a respeito de possíveis trabalhos futuros sobre o tema e problema abordados nesta dissertação. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 17 O fluxograma seguinte (Figura 1) ilustra de forma sintetizada a estrutura da dissertação. Figura 1 - Fluxograma descritivo da estrutura da dissertação. 1. Introdução 2. Revisão Bibliográfica 3. O Problema 4. Métodos de Resolução 5. Os Algoritmos Genéticos 6. Especificação do Algoritmo Genético Utilizado 7. Experiências Computacionais e Resultados 8. Conclusões e Desenvolvimentos de Futuros Trabalhos Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 18 2. Revisão Bibliográfica A logística pode ser definida como o fornecimento de bens e serviços desde o ponto de produção até ao ponto de procura, afirmam Eilon, et al (1971). Bodin, et al (1983) dizem que um sistema logístico engloba todo o processo de produção que se inicia com o movimento das matérias-primas e de todos os inputs necessários para o processo de fabrico desde os fornecedores, à sua conversão em produtos acabados nas fábricas, o seu fluxo para os diversos armazéns ou centros de distribuição e, por fim, à sua distribuição para os clientes finais. Esta distribuição para ser eficaz e eficiente implica a tomada de decisão a três níveis: o estratégico, o tático e o operacional. Primeiro, é necessário determinar o número e a localização das fábricas, dos armazéns e dos centros de distribuição, o que consiste em decisões estratégicas. Ao nível tático, encontram-se os problemas relacionados com tamanho da frota e com o mix de produtos a colocar a cada armazém. Por último, as decisões operacionais estão mais relacionadas com a gestão do dia-a-dia da empresa, ou seja, a determinação das rotas e o escalonamento dos condutores pelos vários veículos. 2.1. O Problema Inicial Do TSP O TSP, em inglês Travelling Salesman Problem traduzido para o português por ‘Problema do Caixeiro-viajante’ é um dos problemas de otimização combinatória mais conhecidos e mais aplicados em diversas áreas. O início do seu estudo foi proposto por Dantzig e Ramser (1954), e desde aí o TSP foi extensivamente estudado por vários autores. Sabe-se ainda que a relação destes problemas com a programação linear foi estudada por Robinson e Koopmans (1949) e mais tarde por Heller (1953). Para descrever um problema de TSP, podemos imaginar um caixeiro-viajante que pretende visitar um conjunto de cidades, cada uma é visitada uma e uma só vez, regressando à cidade de onde partiu. Ele pretende seguir o caminho mais curto, sabendo, à partida, as distâncias entre os pares de cidades que tenciona visitar. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 19 Ainda hoje este problema é amplamente estudado, pois apesar da simplicidade da sua descrição e perceção, é um problema bastante complexo em termos de resolução, por se tratar de um problema combinatório, ou seja, é um problema para o qual o aumento da sua dimensão conduz a um aumento exponencial do tempo necessário à sua resolução. Com o evoluir das sociedades surgiram necessidades e preocupações suplementares, tais como a capacidade dos meios de transporte, a variedade da frota da empresa, a hora a que os clientes são visitados, os dias a que os clientes querem ser abastecidos, entre outras, que conduziram ao estudo de diversas variantes deste problema. Seguidamente apresentase o problema designado, em inglês, por Vehicle Routing Problem (VRP) que surgiu após a consideração de alguns aspetos acima mencionados. 2.2. O VRP - Vehicle Routing Problem O problema do planeamento de rotas, que têm como objetivos a entrega ao cliente e a consequente satisfação do mesmo, e a redução dos custos associados, é designado por Vehicle Routing Problem 4 . Por outras palavras, como definem Tavares, et al (2008), dada uma frota de veículos com diferentes capacidades, um único centro de distribuição e vários clientes que constituem os pontos de procura e de entrega, o VRP tem como objetivo encontrar o conjunto de rotas que além de minimizarem o custo total permitem satisfazer toda a procura de forma eficiente e eficaz. Ao longo dos anos várias versões deste problema têm vindo a ser estudadas. Segundo Dantzing e Ramser (1959), o VRP surge nas áreas da logística, distribuição e transporte, sendo mesmo um dos principais problemas de otimização com real aplicação, por exemplo no transporte de alunos da escola até suas casas, nas recolhas de lixo pelos vários quarteirões, nas entregas do correio, entre outros. Devido às restrições impostas pelos clientes e fornecedores, como por exemplo, tempos de entrega, capacidades do 4 Neste documento, o problema Vehicle Routing Problem é designado pela sigla VRP. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 20 veículo, velocidade, entre outros, o problema de VRP não pode ser considerado apenas como um problema geográfico. Assim, devido a todas as possíveis restrições impostas todos os recursos disponíveis serão afetos, sempre com o objetivo de reduzir os custos totais do transporte. Como cada organização tem um conjunto específico de necessidades, surgiu um conjunto de variantes deste tipo de problemas, tendo em conta as restrições impostas em cada um:  Restrições temporais (ou janelas temporais), uma das mais frequentes e mais utilizada nas entregas de correio, nos autocarros de transporte escolar e na distribuição para grandes superfícies como por exemplo super e hipermercados. Proposto por Kohl (1997), o VRPTW 5 é uma extensão do VRP onde todos os clientes devem ser satisfeitos dentro de um intervalo de tempo, Braysy, et al (2005). Tendo em conta esta restrição, quando o distribuidor chega ao cliente só pode entregar o produto caso a hora a que chegou seja pelo menos o início da janela temporal, definida pelo cliente, e não ultrapasse o fim da mesma. Se o distribuidor chegar após o limite máximo da janela temporal, a solução torna-se inviável. Já no caso em que chega antes do limite inferior da janela temporal a entrega pode ser feita, no entanto implica um tempo de espera.  Restrições de capacidade, CVRP 6 foram propostas por Breslin (1997), dando origem a um dos problemas mais comuns no planeamento de rotas. Neste problema, uma frota de veículos homogénea serve um conjunto de clientes com uma procura conhecida, a partir de um único armazém. As restrições que aqui podem surgir são, por exemplo, cada rota começa e termina no armazém, cada cliente só pode ser visitado uma única vez, pelo que a procura de cada cliente não pode ser dividida por diferentes veículos. A restrição principal deste problema é o facto de a soma da procura dos vários clientes atribuídos a cada rota não poder exceder a capacidade do veículo afeto a realizar o percurso. 5 Neste documento, o problema Vehicle Routing Problem with Time Windows será designado pela sigla VRPTW. 6 Neste documento, o problema Capacitated Vehicle Routing Problem será designado pela sigla CVRP. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 21 Pretende-se tomar decisões tendo em conta o número de veículos disponíveis na frota e as necessidades dos clientes, o tempo disponível e a distância de cada rota. O objetivo principal é minimizar os custos totais, tendo em conta a capacidade de cada veículo e a satisfação de todos os clientes.  Hjorring (1995) apresentou uma versão que considera múltiplos armazéns, MDVRP 7 . Aqui, os veículos da frota iniciam as suas rotas a partir de vários centros de distribuição, e no fim, cada camião deve retornar ao centro de distribuição onde iniciou a sua rota. Como existem vários centros de distribuição, isto implica determinar também quais os clientes que são satisfeitos por cada armazém. O objetivo tradicional deste problema é definir o conjunto de rotas que minimizam o somatório da distância percorrida pelos veículos, a partir dos vários centros de distribuição, Carlsson, et al (2007).  As restrições de periodicidade conduzem a uma outra versão do problema de VRP, o Periodic Vehicle Routing Problem 8 , onde o planeamento das rotas é feito para um determinado número de dias, por exemplo uma semana, em vez de apenas para um dia, Angelelli et al (2002). Isto é, O PVRP tem um horizonte temporal, de T dias, e existe uma procura e regularidade de entrega para cada cliente indicando quantas vezes dentro do período de T dias o cliente deve ser visitado. A solução para o PVRP consiste em encontrar os T conjuntos de rotas que conjuntamente satisfazem as restrições da quantidade procurada e regularidade. O aspeto mais importante neste tipo de problemas prende-se com a prioridade a dar a cada cliente. Este aspeto foi estudado por Christofides (1981), que apresentou uma heurística onde era dado um nível de prioridade a cada cliente e, de acordo com a prioridade atribuída, era formulado um horário de visitas para cada um deles.  A crescente preocupação com a proteção do meio ambiente conduziu a alterações significativas nos processos das empresas, quer ao nível da produção, reutilização 7 Neste documento, o problema Multiple Depots Vehicle Routing Problem será designado pela sigla MDVRP. 8 Neste documento, o problema Periodic Vehicle Routing Problem será designado pela sigla PVRP. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 22 das embalagens e dos próprios bens, como também ao nível da distribuição. Segundo Dethloff (2001), estas alterações conduziram a que os bens passassem a ser transportados também na direção inversa. Assim, o planeamento das rotas passa a incluir a distribuição de bens e também a recolha de outros para serem reciclados ou reutilizados. Neste sentido, o Vehicle Routing Problems With Pickups and Deliveries 9 é um tipo de problema de planeamento de rotas no qual os clientes requerem uma determinada quantidade a ser entregue e outra a ser recolhida, Hoff, et al (2009). Neste problema a entrega e a recolha de produtos em cada cliente, processam-se apenas por um único veículo e num determinado instante, e cada cliente só pode ser visitado uma única vez. Deste modo, é necessário garantir que a quantidade de produtos que os clientes querem devolver não excede a capacidade disponível do veículo. Restrições de entrega e recolha foram abordados pela primeira vez na literatura por Min (1989). Nesse trabalho, foi estudada a distribuição e recolha de livros entre um centro de distribuição e vinte e duas livrarias em Ohio. Para tal, existiam dois veículos com capacidade limitada e a operação de distribuição e recolha era efetuada diariamente. As livrarias foram particionadas em dois grupos e para definir as rotas que otimizam estas operações foram resolvidos dois problemas do tipo do VRP separadamente, um para cada veículo. Para todos estes tipos de problemas existem, na literatura, extensos e variados estudos que propõem algoritmos para a sua resolução. Desde algoritmos exatos, que são apenas viáveis para instâncias de pequena dimensão, o que na realidade acontece poucas vezes, até às Meta-heurísticas que chegam a soluções viáveis e satisfatórias para problemas de grande dimensão, mas sem garantia de otimalidade. 9 Neste documento, o problema Vehicle Routing Problems With Pickups and Deliveries será designado pela sigla VRPPD. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 23 2.3. O EVRP - Environmental Vehicle Routing Problem A distribuição dos produtos, ou seja, o seu transporte entre fornecedor e cliente é parte imprescindível na cadeia logística de uma empresa, e tendo em conta que o transporte prejudica a qualidade do ar local (emissões de CO2 e efeito de estufa), gera poluição sonora, consome combustível e contribui de forma significativa para o aquecimento global, cada vez mais, é tema de preocupação para a economia, saúde pública e sustentabilidade das gerações futuras. Para lidar com estas questões, surge o Environmental Vehicle Routing Problem (EVRP). Neste problema incluem-se preocupações ambientais, ecológicas e energéticas. Na realidade sabemos ser impossível eliminar por completo esses fatores enquanto estamos num processo de distribuição, no entanto, pode ser viável obviar esses fatores, implementando uma gestão que tenha em conta a utilização eficiente dos tempos de transporte, da velocidade, das emissões de CO2 e do consumo de combustível, sem sacrificar significativamente os custos. Demir, et al (2011) afirmam que as emissões de CO2 são diretamente proporcionais à quantidade de combustível consumido por um veículo, que por sua vez é dependente de uma variedade de parâmetros relacionados com o trânsito, tais como a velocidade do veículo, a carga e a aceleração. Apesar de todos estes parâmetros serem apontados na literatura, não há estudos que efetivamente os considerem, dada a inviabilidade de obtenção de dados. Alguns dos fatores que afetam a eficiência do motor estão também diretamente relacionados com as emissões de CO2, e são eles, o tipo/qualidade de combustível, a proporção de ar, a velocidade do motor e a taxa de compressão. A velocidade é considerada o fator mais importante na influência do consumo de combustível, no entanto, devido a elevada existência de estradas com grande inclinação e à circulação a velocidades bastante reduzidas, comparando com a que é permitida, devido ao trânsito e aos congestionamentos, em zonas urbanas, este fator torna-se de difícil mensuração para o estudo deste tipo de problemas e é por isso, usualmente, ignorado. A dimensão da frota é outro elemento importante, pelo que a possibilidade de escolher o veículo certo para cada tipo de encomenda a transportar é um elemento significativo na Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 24 variação do consumo de combustível. Veículos com capacidade menor e de dimensões mais reduzidas possuem motores com menor potência e por isso consomem menos combustível. O uso de um veículo pesado de maior dimensão, apesar de consumir mais combustível, pode ser uma melhor solução do que a utilização de dois veículos menores. Em casos reais esta questão é, normalmente, ignorada ou quase ignorada, pois na verdade a frota é muitas vezes constituída por poucos tipos de veículos. 2.4. Estudos Realizados Na Área Da Otimização De Rotas Um dos primeiros documentos estudados para a realização da revisão bibliográfica desta dissertação, foi escrito por Bektaş e Laporte (2011), intitulado por “The Pollution-Routing Problem”, onde o PRP é descrito com uma função objetivo ampla e mais abrangente que tem em conta não apenas a distância da rota, mas também a quantidade de emissões de CO2, consumo do combustível, duração da rota e os custos variáveis da mesma. Este estudo tem como objetivo principal chamar à atenção para uma visão diferente acerca dos custos do chamado “transporte responsável”. Os resultados sugerem que o PRP é significativamente mais difícil de resolver do que o VRP, no entanto, tem o potencial de produzir poupanças significativas no custo total. Tal deve-se ao facto do PRP incluir fatores e custos associados à realização da rota, tais como, os custos com as emissões de CO2, custos operacionais dos veículos como despesas de manutenção e reparação de avarias e custos com os motoristas, usualmente negligenciados. Segundo os autores, a necessidade deste trabalho surge por ser evidente a lacuna existente na literatura ao nível de estudo e de conclusões aplicáveis ao PRP. Na verdade, a maioria dos estudos efetuados não integra adequadamente os fatores ambientais, em particular, as emissões de CO2. O seu objetivo principal passa por descrever uma abordagem para reduzir as necessidades energéticas na definição das rotas com base num modelo de emissões que tem em conta uma série de fatores, incluindo carga e velocidade. O problema fundamental considerado por Bektas e Laport (2011) é formalmente definido como a construção de rotas para um conjunto de veículos conseguir dar resposta á procura de todos os clientes, sendo que todos os veículos saem e retornam ao mesmo armazém, nenhum veículo transporta carga a mais do que a sua capacidade e cada cliente é visitado Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 25 dentro de sua respetiva janela de tempo. O objetivo global é o de minimizar o custo total que é composto pelo custo das emissões, custos operacionais do veículo e custo com os motoristas. A formulação do problema é feita através de um modelo de programação não-linear inteira onde as não linearidades estão associadas ao cálculo do custo das emissões de CO2 e do tempo de condução. Posteriormente é realizado um procedimento para linearizar ambos os termos não-lineares através da discretização das variáveis. O problema linearizado é então resolvido utilizando o CPLEX 12.1. Para tornar o método mais eficiente, os autores executam o branch-and-cut em paralelo. Foi imposto um tempo limite de computação de três horas e todas as experiências foram realizadas num servidor com velocidade de 3 GHz e 1GB de RAM. As experiências computacionais reportadas foram inicialmente realizadas recorrendo a problemas gerados pelos autores. Estes dividem-se em três classes de problemas com 10, 15 e 20 cidades e cada classe inclui 10 instâncias onde as procuras seguem uma distribuição uniforme discreta no intervalo [130, 150]. Nestes problemas é considerado apenas um único veículo de capacidade limitada e que os clientes podem ser satisfeitos em qualquer altura, ou seja, não são incluídas janelas temporais. A resolução destes problemas permitiu concluir que minimizar apenas as emissões de CO2 não é suficiente no que diz respeito à minimização de custos totais. Os autores fizeram experiências adicionais considerando variantes dos problemas acima referidos onde foram incorporadas outras características tais como vários veículos com características diferentes, janelas temporais associadas aos clientes e vários padrões de procura. Estas experiências permitiram retirar as seguintes conclusões: i) minimizar a carga transportada por camião implica um menor consumo de combustível, particularmente quando não existem janelas de tempo; ii) a utilização de uma frota heterogénea ou mista de veículos, conduz a um menor consumo de combustível e uma maior taxa de utilização da capacidade do veículo; iii) o potencial de redução do consumo de energia aumenta com a variação dos valores da procura, particularmente quando um pequeno número de clientes é responsável pela maior parte da procura. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 32 As taxas de consumo de combustível, apresentadas acima, são calculadas com base no trabalho de Xiao et al (2012), isto é, assumindo Y = 0.0000793X0,026, onde Y e X são a taxa de consumo de combustível (l/km) e o peso do veículo (em ton), respetivamente. Aqui X assume-se como sendo a capacidade do veículo, Q . É assumido que o consumo de combustível aumenta de forma linear com a distância percorrida. Tipo 1: Y = 0.0000793(16000) - 0,026. Tipo 2: Y = 0.0000793(19000) - 0,026. Tipo 3: Y = 0.0000793(26000) - 0,026. Neste problema o cliente só pode ser abastecido uma e uma única vez, no entanto os veículos podem passar pelo local do cliente sem o abastecer, desde que isso leve a um melhor trajeto. Pretende-se então determinar as rotas, isto é o conjunto sequencial de clientes a visitar, a efetuar de modo a satisfazer a procura de cada cliente. Assim, a cada rota é alocado um conjunto de encomendas, bem como o veículo da frota disponível para as transportar. Cada veículo pode fazer mais do que uma rota e as rotas efetuadas por um mesmo veículo têm uma duração total limitada a um dia de trabalho, ou seja, 8 horas, não se considerando relevante para os resultados do algoritmo considerar os intervalos estabelecidos no Código de Trabalho de apenas 10 minutos no período da manhã e da tarde. A Figura 3 ilustra uma solução possível para um problema de VRP, com um armazém e distribuição e dez clientes. Figura 3 - Problema de VRP. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 33 De entre as soluções possíveis estamos interessados em encontrar uma que minimize os custos totais incorridos. Os custos a considerar incluem: custos de transporte, custos com combustível e custos com emissões de CO2. Os custos designados por custos de transporte (𝑉𝑘), referem-se aos custos operacionais que são proporcionais à distância percorrida (𝐷𝑖𝑗). Como estes custos incluem custos tais como, custos com o motorista e custos de manutenção do veículo, são dependentes do tipo de veículo que está a ser utilizado. O custo de combustível está associado à distância percorrida entre cada ponto de paragem. De acordo com o relatório mensal sobre os combustíveis da Entidade Nacional para o mercado dos combustíveis (ENMC) de Março, o Gasóleo Rodoviário, em Portugal, apresentou um preço de 1,186€, como se pode verificar na imagem abaixo. Figura 4 - Preço do combustível, Fonte: Comissão Europeia. Por fim, associado ao custo das emissões de CO2 está a quantidade de emissões de CO2 e a velocidade do veículo utilizado, no entanto, não vamos ter em conta esta última, pois estamos a tratar de transportes urbanos e não conseguimos controlar se os camionistas cumprem ou não os limites de velocidade e o trânsito citadino exige o “ para – arranca “, entre outros fatores. No que diz respeito a quantidade de CO2 emitidos pelo veículo, é Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 34 necessário ter em conta que se a emissão for superior ao limite máximo permitido, temos de comprar licenças de emissão no mercado de emissões e caso contrário poderemos vende-las. Surge a necessidade de conhecermos o preço de venda e de compra as licenças e o limite máximo de emissões permitidas. Para cada tipo de veículo, as emissões de carbono são calculadas usando os dados na Figura 5, apresentada abaixo. O custo unitário da emissão de carbono é definido em 25$/ton. O limite superior (𝐴𝐸) para as emissões de carbono para cada instância é definido como a quantidade usada na 1ª solução admissível obtida pelo seguinte método, uma vez que não é possível estimá-las. Figura 5 - Método de cálculo das emissões de CO2. Fonte: Kwon, et al (2013), Heterogeneous fixed fleet vehicle routing considering carbon emission. 3.2. Formulação Matemática Neste capítulo apresenta-se o modelo de programação matemática para o problema definido anteriormente onde a forma de tratar as emissões de CO2 é baseada na proposta por Kwon, et al (2013). Considera-se uma rede G = (𝑉, A ), onde o conjunto de vértices 𝑉= (v0, v1, …., 𝑉 R) representa o armazém (𝑣 0 ) e os R clientes. A cada cliente está associada uma encomenda que se caracteriza pelo seu peso (𝑃𝑖) e o tempo necessário para efetuar a sua entrega (𝑇𝑖). O conjunto de arcos A = ( ( vi,vj ) , vi, vj ε V, 𝑖 ≠ 𝑗 ) representa as várias ligações existentes entre os clientes. Ao conjunto dos arcos está associado uma matriz de distâncias entre cada par de vértices (𝐷𝑖𝑗). O número de veículos usados para efetuar o serviço não pode ultrapassar o número de veículos na frota (𝑁 = 𝑁1+ 𝑁2+ ⋯+ 𝑁𝑘). Estes veículos, que não são todos iguais, são Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 35 caracterizados pela sua capacidade ( QK, 𝑘 =1,2,…,K ) e o consumo médio de combustível (𝐶𝑀𝑐𝑘, 𝑘 =1,2, …, 𝐾) Assim, pretendemos determinar um conjunto de rotas, que minimize o custo total e satisfaça os clientes e as restrições do sistema. Uma vez que uma rota é uma sequência de clientes, definimos as variáveis 𝑥𝑖𝑗𝑘, que tomam o valor 1 se o veículo 𝑘 passar no arco (𝑖 ,j ) e 0 caso contrário. E as variáveis 𝑦𝑖𝑗𝑘 que representam a carga que o veículo 𝐾 transporta no arco (𝑖 ,j ). Sendo assim, a) Índices 𝑖 - Local visitado; j - Local a visitar; 𝑘 - Tipo de veículo, k=1,2…Mk , onde nk é o número de tipos de veículos; l – 1, …, Nk, onde Nk é o número de veículos do tipo k. b) Parâmetros 𝐷𝑖𝑗 - Distância entre os pontos 𝑖 e 𝑗; 𝑄𝑘 - Capacidade do veículo do tipo 𝐾; 𝑃𝑖 - Procura do cliente no ponto 𝑖; 𝑃𝑟 - Preço do combustível; 𝑉𝑘 - Custo variável operacional dos veículos do tipo 𝑘 por unidade de distância; 𝐸𝑘Quantidade de emissões de CO2 emitidas pelos veículos do tipo 𝑘 por unidade de distância (g/km); 𝑇𝑖 - Tempo de entrega no cliente 𝑖; 𝑀 - Número muito grande; 𝐾 - Tipos de veículos; 𝑁𝑘 - Número de veículos do tipo 𝑘; 𝐶𝑀𝑐𝑘 - Consumo médio de combustível por veículo do tipo 𝑘; 𝐴𝐸 – Limite superior para as emissões de CO2. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 36 c) Variáveis De Decisão 𝑧𝑘 - Toma o valor 1 se o veículo 𝑘 é utilizado e 0 caso contrário; 𝑠𝑖 𝑘 - Toma o valor 1 se o veículo 𝑘 abastece o cliente 𝑖, 0 caso contrário; 𝑥𝑖𝑗𝑘 - Toma o valor 1 se o veículo 𝑘 passar no arco (𝑖, 𝑗), 0 caso contrário; 𝑦𝑖𝑗𝑘 - Representa a carga que o veículo transporta no arco (𝑖 , 𝑗). d) Função Objetivo A função objetivo consiste em minimizar o custo total do transporte, que é composto pelo custo do transporte, custo do combustível e custo de emissões de CO2 (3.1). Minimizar ∑𝑉𝑘𝑧𝑘 𝑁 𝑘=1 + ∑ ∑ ∑ 𝐷𝑖𝑗 𝑁 𝑘=1 𝑅 𝑗=1 𝑅 𝑖=1 × 𝐶𝑀𝑐𝑘 × 𝑃𝑟 × 𝑥𝑖𝑗𝑘 + [−(𝐴𝐸 − ∑ ∑ ∑ 𝐸𝑘 𝑀 𝑗=1 𝑀 𝑖=1 𝑁 𝑘=1 × 𝐷𝑖𝑗 × 𝑥𝑖𝑗𝑘) 𝑃𝑐𝑜𝑚𝑝𝑟𝑎/𝑣𝑒𝑛𝑑𝑎] (3.1) e) Restrições Sujeito a: Satisfação Da Procura Dos Clientes 𝑦𝑖𝑗𝑘 ≤ 𝑀 × 𝑥𝑖𝑗𝑘, ∀𝑖,𝑗,𝑘; (3.2) 𝑦𝑖𝑗𝑘 ≤ 𝑀 × 𝑧𝑘, ∀𝑖,𝑗, 𝑘; (3.3) ∑𝑠𝑖 𝑘 𝑁 𝑘=1 = 1, ∀𝑖; (3.4) ∑𝑦𝑖𝑗𝑘 𝑅 𝑗=1 = ∑𝑦𝑗𝑖𝑘 𝑅 𝑗=1 − 𝑃𝑖 × 𝑠𝑖𝑘 , ∀𝑖,𝑘; (3.5) ∑𝑦𝑗𝑖𝑘 𝑅 𝑗=1 ≥ 𝑠𝑖𝑘 × 𝑃𝑖 , ∀𝑖,𝑘. (3.6) Frota Disponível 𝑦𝑖𝑗 𝑘≤ 𝑄𝑘 , ∀ 𝑖,𝑗,𝑘. (3.7) Rota ∑𝑥𝑖0𝑘 = ∑𝑥0𝑗𝑘 , 𝑅 𝑗=1 𝑅 𝑖=1 ∀𝑘; (3.8) Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 37 ∑𝑥𝑖𝑗𝑘 𝑅 𝑗=1 =∑𝑥𝑖𝑗𝑘 , ∀𝑖,𝑘 𝑅 𝑖=1 . (3.9) Tempo ∑𝑇𝑖 𝑠𝑖 𝑘 + ∑ ∑ 𝑇𝑖𝑗 𝑘 𝑅 𝑗=1 𝑅 𝑖=1 𝑅 𝑖=1 × 𝑥𝑖𝑗𝑘 × 𝐷𝑖𝑗 ≤ 8 , ∀𝑘. (3.10) A função objetivo (3.1) consiste em minimizar o custo total. As equações (3.2) e (3.3) garantem que o veículo 𝑘 só transporta carga no arco (𝑖, 𝑗) se o veículo 𝑘 é utilizado e passa no arco (𝑖, 𝑗). Na equação (3.4) garante-se que o cliente é abastecido uma única vez. Na equação (3.5) garantimos, para todos os veículos, que a carga que sai do nó i é igual à que entra menos a que é eventualmente entregue ao cliente 𝑖. Na equação (3.6) garantimos que se o veículo 𝑘 abastece o cliente 𝑖 então a carga entra em 𝑖 é suficiente para o abastecer. O conjunto de restrições dadas pelas equações de (3.2) a (3.6) dizem respeito à satisfação da procura dos clientes. A restrição (3.7) diz respeito à capacidade de cada veículo, que em nenhum ponto da rota pode ser excedida. As restrições (3.8) e (3.9) garantem as condições da rota, ou seja, que o número de vezes que cada veículo entra em cada nó é igual ao número de vezes que o veículo sai desse mesmo nó. A equação (3.10) garante que o tempo total da rota, i.e. a soma do tempo necessário para proceder à entrega das encomendas associadas a esta rota com o tempo de condução da mesma não ultrapassa o limite de 8 horas definido para cada rota (horário de trabalho dos motoristas). Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 38 4. Métodos De Resolução Segundo Hillier e Lieberman (2006), o desenvolvimento de um modelo de otimização de um problema real requer a concretização de cinco etapas: Figura 6 - Etapas do desenvolvimento de um modelo de otimização de um problema real. Neste capítulo serão abordados os vários procedimentos existentes para a obtenção de soluções. Durante vários anos foram desenvolvidos diversos métodos numa tentativa de se encontrar a melhor solução possível. De seguida apresentam-se as várias técnicas para obtenção de soluções encontradas na literatura, as quais se dividem em dois tipos: 1. Abordagens Exatas - A solução procurada é aquela que alcança a melhor solução possível satisfazendo todas as restrições de modo a garantir que a solução identificada é uma ótima. No entanto, os métodos exatos requerem demasiados recursos computacionais pelo que são para problemas combinatórios, como é o caso do problema abordado neste trabalho, demasiado demorados e apenas viáveis para problemas de pequena dimensão. 2. Heurísticas - Para a resolução de problemas de otimização de rotas existem diversas heurísticas. Neste ponto da dissertação, serão abordadas diversas heurísticas, que poderão ser utilizadas para a resolução e otimização do problema. No entanto, para a escolha da heurística a utilizar, terá de ser analisado o problema com algum detalhe, para que a escolha recaia na mais indicada para o problema em questão. Definição do problema Formulação matemática do problema Procedimento e obtenção de soluções Validação Aplicação Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 39 4.1. Heurísticas Qualquer um dos métodos apresentados de seguida tem vantagens e desvantagens. Determinados métodos, irão ser capazes de retornar uma solução muito boa para o problema, enquanto outros apenas irão retornar mínimos/máximos locais, podendo assim não ser a solução ótima global do problema. Estes algoritmos recorrem a uma estruturação matemática do problema e tipicamente produzem soluções possíveis e próximas do ótimo, não garantindo o ótimo, segundo Bodin et al (1983), podem ser classificadas em três tipos: 4.1.1. Heurísticas Construtivas permitem construir gradualmente uma solução possível, usualmente, fazem-no a partir da matriz de distância ou de tempo entre os vários pontos. Vizinho mais próximo A solução é construída através da adição do ponto mais próximo, individualmente à solução final. O critério utilizado para a sua adição é a distância entre dois pontos, sendo que o ponto escolhido para ser adicionado será o mais próximo do selecionado anteriormente. •Vizinho mais próximo - Juntar o cliente mais próximo/ MAIOR ENCOMENDA/MAIOR TEMPO ; •Heurística da inserção mais próxima - Juntar o cliente mais próximo da rota na melhor posição; •Heurística da inserção mais afastada - Juntar o cliente mais afastado da rota na melhor posição; •Algoritmo de Savings de Clark and Wright (poupança) - Juntar o cliente que tráz mais poupança à rota. Heurísticas Construtivas (constroi uma rota possivel adicionando um cliente de cada vez). Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 40 Figura 7 – Exemplo do algoritmo do vizinho mais próximo. Heurística da inserção mais próxima Nesta heurística podemos encontrar três fases principais. Partindo de uma seleção, onde o ponto de partida é o armazém, identifica-se o cliente mais próximo (do armazém) que é inserido na solução em computação (tendo de sugerir sempre). Seguidamente, procurase o cliente mais próximo do anteriormente inserido, neste caso o cliente mais próximo do cliente 1 é o cliente 2 (imagem do centro acima). Este procedimento é repetido até todos os clientes estarem inseridos na rota para poderem ser satisfeitos. Heurística da inserção mais afastada Segundo Carravilha e Oliveira (2010), para se construir uma solução através da heurística de inserção mais distante devem ser utilizados os mesmos passos descritos na heurística de inserção mais próxima, diferindo apenas na fase da seleção, pois em vez de pretendermos escolher o ponto que minimiza o custo/distância, pretende-se a sua maximização. Algoritmo de Savings de Clarke and Wright O Algoritmo de Savings proposto por Clarke e Wright, (1964), pode ser definido como a maximização da poupança da combinação de duas sub-rotas existentes. O algoritmo de Savings tem com solução inicial tantas rotas como clientes, ou seja, para cada cliente é Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 41 estabelecida uma rota que parte do armazém para o cliente e regressa ao armazém. Depois iterativamente considera-se juntar todos os pares de rotas possíveis, colocando para cada um a poupança obtida da seguinte junção onde Cij é o custo entre os dois clientes, 0 o armazém e Sij as distâncias: Sij = C0i + Cj0 – Cij, São escolhidas para se juntar, as rotas associadas à maior poupança. Este procedimento repete-se até que haja apenas uma rota, ou em casos com limitações, como por exemplo de carga, ou tempo de computação, ou ambos, não seja possível haver mais junções. Figura 8 – Exemplo de um problema inicial VRP. Considere um problema onde se abastecem n clientes (nós 2 a 5) de um armazém (nó 1), (ver Figura 8). De acordo com este algoritmo a solução inicial é a dada na figura abaixo. Figura 9 – Exemplo de uma solução inicial e custos do VRP, De acordo com o algoritmo de Clarke and Wright (1964). Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 48 4.2.3. Genetic Algorithms Os algoritmos genéticos, do Inglês Genetic Algorithms (GAs), são métodos de pesquisa estocástica baseados na Teoria da Evolução Natural das Espécies, criados por Holland, (1975) nos anos 60. Basicamente, o que um algoritmo genético faz é criar uma população de possíveis respostas para o problema a ser tratado (inicialização) para depois submetelas ao processo de evolução. De acordo com a literatura os GAs 13 apresentam uma boa performance quando aplicados neste tipo de problemas e por isso vamos aplica-los nesta dissertação. Algumas das vantagens em se utilizar os Algoritmos Genéticos, enunciadas por Linden, (2006), são:  São robustos e aplicáveis a uma grande variedade de problemas, apresentando um bom desempenho para uma grande escala de problemas;  Não usam apenas informação local, logo, não ficam necessariamente presos, a ótimos locais como determinados métodos de procura. Esta característica é uma das mais interessantes dos algoritmos genéticos e faz com que eles sejam técnicas extremamente adequadas para funções de comportamento complexo;  São de fácil implementação e proporcionam maior flexibilidade no tratamento do problema a ser resolvido; 13 Neste documento Algoritmos Genéticos são também designados por GAs ou Genetic Algorithms. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 49 5. Os GAs – Genetic Algorithms Os Algoritmos Genéticos são inspirados no processo de evolução natural e utilizados para resolver problemas reais de otimização. Segundo Fernandes (2005), eles procuram a melhor solução para os problemas, utilizando um processo iterativo de procura da melhor solução. Diferentemente dos métodos tradicionais de procura da solução ótima, os GAs apresentam algumas peculiaridades que lhes conferem a possibilidade de explorar espaços de procura mais complexos de forma robusta, como, trabalharem com uma codificação das possíveis soluções (genótipos) e não com as próprias soluções (fenótipos); manipularem simultaneamente um conjunto (população) de soluções candidatas; utilizarem informações de custo e recompensa e por fim empregarem regras de transição probabilísticas. A procura inicia-se através de uma população inicial, que combinando os melhores representantes desta população, obtém uma nova, que passa a substituir a anterior. A cada nova iteração é gerada uma nova população que apresenta novas e melhores soluções para o problema em questão, culminando com a sua convergência para pelo menos um ótimo local. O fluxograma da figura abaixo representa um Algoritmo Genético. Figura 17 – Fluxograma de um Algoritmo Genético. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 50 A técnica utilizada para codificar os cromossomas varia conforme o tipo do problema. Pode ser utilizada uma cadeia de strings de bits para representar os cromossomas ou podese utilizar uma variável numérica contínua que armazena o seu próprio valor real, entre outros. Estes cromossomas passam por uma função de avaliação chamada função fitness, que representa a performance do cromossoma como representação de uma solução para o problema original. 5.1. Conceitos Básicos Geração É o resultado da aplicação do estado de Seleção ate à criação de um novo individuo que se junta a uma população. População Conjunto de indivíduos que compõe uma geração. Indivíduo Representação (genótipo) da solução (fenótipo) de um determinado problema (ambiente), por exemplo através de um vetor ou matriz. Função de Fitness Função de avaliação, que mede a adaptabilidade do indivíduo ao ambiente. Seleção Processo de escolha que usualmente seleciona os indivíduos mais aptos (que apresentam uma maior fitness), para participarem no processo de reprodução. Reprodução Processo pelo qual indivíduos mais aptos, ou seja, com melhores valores da função fitness, têm a chance de perpetuar seu material genético, ou pelo menos parte deste material, através da aplicação dos operadores genéticos de crossover. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 51 Mutação Alterações no código genético e assim nas características das espécies. Tem como objetivo permitir maior variabilidade genética na população, impedindo que a procura fique estagnada num mínimo local. Critério de Paragem Caracterizado pela obtenção de uma solução satisfatória ou pelo término do tempo computacional no número de gerações ou outra critério pré-estabelecido Fogel, (1995). Termos Biológicos Termos Computacionais Cromossoma Indivíduo Gene Caractere Alelo Valor do caractere Lócus Posição do caractere Genótipo Representação do indivíduo Fenótipo Interpretação do vetor de caracteres Tabela 1 – Quadro comparativo entre a linguagem biológica e a linguagem computacional. 5.2. Técnicas De Codificação Um ponto importante a ser observado na utilização de um GAs para a resolução de um problema é a forma como é feita a representação das possíveis soluções, ou seja, qual a estrutura de dados que será utilizada para compor o cromossoma. Através de uma boa codificação garante-se que os algoritmos atuarão de forma adequada. Dentro da terminologia da genética, estas codificações/representações que serão manipuladas pelos GAs são chamadas genótipos. Às soluções propriamente ditas (ou genótipos descodificados) dá-se o nome de fenótipos. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 52 Representação Binária (Binary encoding) No caso da representação binária, a codificação é direta quando as possíveis soluções já são de natureza binária. Caso contrário, procura-se transformar as possíveis soluções para o problema em um número binário ou numa sequência de números binários. Candidato à solução Codificação (genótipo) A 1000 B 1001 C 0010 D 0100 Tabela 2 – Exemplos de codificação binária. A forma mais comum de codificação é exatamente a construção de uma solução binária de comprimento L em que cada elemento denotaria (0) a ausência, ou (1) a presença de uma determinada característica. Desta forma, se L assumir o valor 10, tem-se 210= 1024 possíveis representações para soluções candidatas, o que constitui o espaço de procura do Algoritmo. Esta codificação tornou-se popular por ser simples e abrangente. Através de uma cadeia binária é possível a representação de diversos tipos de fenótipos, tais como, valores inteiros e reais, matrizes, grafos, árvores, entre outros. Representação de Permutação (Permutation encoding) Esta forma de representação é particularmente utilizada em problemas de ordenação. Neste tipo de representação, cada cromossoma é uma sequência de números reais. Tabela 3 – Exemplos de permutation encoding. Existem outras formas de representação, que também são passiveis de ser utilizadas dependendo do problema que estamos a considerar. O método de representação deve ser Cromossoma A 135624798 Cromossoma B 857723149 Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 53 escolhido tendo em conta que irá ser utilizada uma estrutura de dados o mais próxima possível da representação real, garantir que todos os genótipos correspondem a soluções viáveis e ainda se possível garantir que os operadores genéticos garantem a viabilidade. 5.3. População O tamanho da população inicial e das populações subsequentes é um aspeto importante a ser considerado para o sucesso do processo evolutivo, pois é possível comprometer a evolução dos indivíduos caso a quantidade escolhida seja muito grande ou muito pequena. Esta medida, exceto em casos muito particulares, deve ser estabelecida empiricamente e de acordo com a disponibilidade de recursos computacionais Goldberg, (1989) e Holland, (1975). Deve considerar-se sempre a possibilidade da população ser dividida em subpopulações e aplicar-se diferentes formas de reprodução e de operadores para cada uma delas. 5.4. Função De Fitness A função de avaliação (fitness) é calculada para cada indivíduo. Este valor está associado a quão adaptado está o indivíduo ao ambiente com o qual ele interage. Em termos computacionais, esta medida indica o quão bem um candidato à solução (indivíduo) é capaz de resolver o problema (ambiente). Na generalidade dos problemas ela é a função objetivo modificada, do problema. É muito importante a correta definição e compreensão desta medida de adaptação, para que o processo evolutivo seja capaz de fornecer uma solução que atenda aos objetivos em questão, Goldberg (1989). 5.5. Operadores Genéticos Segundo Holland (1975), existem três técnicas utilizadas para criar filhos diferentes dos pais. A técnica de seleção, de cruzamento e de mutação. Elas estão intimamente relacionadas com o modelo básico de um algoritmo genético, pois as três permitem a evolução da população. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 54 5.5.1. Seleção A função de seleção de um algoritmo consiste em escolher os elementos da população que farão parte do processo de reprodução, isto é, selecionar os pais dos indivíduos que estarão presentes na nova população. Esta escolha, geralmente, deve ser feita para que os membros da população mais adaptados ao meio ambiente, ou seja, aqueles que apresentam um melhor valor da função fitness, tenham maior chance de reprodução. Tipos de seleção Existem várias técnicas de seleção, na literatura, dentro das quais destacam-se:  Seleção por ranking (rank selection): os indivíduos da população são ordenados de acordo com seu valor de adequação e a possibilidade de escolha é atribuída de acordo com a posição que ocupam. Este método pode levar à convergência excessiva.  Seleção por torneio (tournament selection): Grupos de soluções são escolhidos sucessivamente e as mais adaptadas (maior valor de função fitness) dentro de cada um desses grupos são selecionadas, Goldberg, (1989) e Geyer (1997).  Seleção uniforme: Todos indivíduos possuem a mesma probabilidade de serem selecionados. Obviamente que esta forma de seleção possui uma probabilidade muito baixa de dar origem a uma população melhor do qua aquela sobre a qual atuamos; 5.5.2. Cruzamento Os operadores genéticos de cruzamento são os responsáveis pelas transformações sofridas pela população, já que a sua função é combinar os cromossomas dos pais, para gerar os cromossomas filhos. O operador de cruzamento tem como objetivo propagar os esquemas mais adequados na população. Para isto, a determinação dos pontos de corte são fundamentais, pois vão determinar quais esquemas sobreviverão ao processo de reprodução. Vejamos alguns tipos de cruzamento: Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 55 1. Cruzamento num ponto O cruzamento num ponto consiste em dividir os cromossomas selecionados num ponto da sua cadeia, onde este ponto é escolhido aleatoriamente. Após isso, copiamos uma parte do cromossoma de cada pai, para gerar os cromossomas dos novos filhos. A Figura 18 demonstra um exemplo deste método de cruzamento. Figura 18 – Exemplos de cruzamento num ponto. 2. Cruzamento Uniforme Segundo Syswerda (1991), o cruzamento uniforme consiste em gerar cada gene do descendente, copiando o correspondente gene de um dos pais, onde este gene é escolhido de acordo com uma “mascara de Cruzamento” gerada aleatoriamente. No processo de criação do cromossoma, Percorre-se todas as posições da máscara analisando seus valores, quando o valor da posição corrente for 1, o gene do primeiro pai referente, referente a mesma posição da máscara é copiado, caso o valor da mascara for 0, será copiado o gene do segundo pai. No término do processo esta gerado o novo descendente, como se pode ver no exemplo a seguir. Figura 19 – Exemplo de cruzamento uniforme. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 56 5.5.3. Mutação A mutação é o fator fundamental para garantir a biodiversidade e introduzir aleatoriedade na população. Apesar de normalmente aplicada com uma probabilidade bastante inferior à de cruzamento, ela é tida por uma série de autores como o operador mais importante para o processo evolutivo, chegando em alguns casos extremos a ser utilizada como o único operador de transformação. O operador de mutação possui também um papel fundamental no que diz respeito à necessidade de evitar a convergência prematura, que ocorre quando a população se estabiliza com uma média de adaptação pouco adequada por causa da pressão evolutiva e baixa diversidade. Isto geralmente dá-se com o surgimento de um super-individuo que domina o processo seletivo e, uma vez incapaz de gerar filhos melhores, transmite as suas características por toda a população. As mutações mais utilizadas são, a troca de bit em codificações binárias (ver Figura 20), troca de posição de dois elementos (ver Figura 21), e a diminuição ou soma de um pequeno número em codificações reais (ver Figura 22). Cromossoma A 1 0 1 1 0 0 1 1 Cromossoma Mutado 1 1 1 1 0 0 1 1 Figura 20 - Troca de um bit. Cromossoma B 1 2 3 4 5 6 7 8 9 Cromossoma Mutado 1 8 3 4 5 6 7 2 9 Figura 21 -Troca de Posição. Cromossoma C (1.29 5.68 2.96 4.11 5.55) Cromossoma Mutado (1.29 5.68 2.73 4.22 5.55) Figura 22 - Soma ou subtração de um pequeno valor. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 57 5.6. Estratégias Evolucionárias A estratégia evolucionária tem por base a escolha das soluções que vão formar a próxima população. Podemos ter em conta apenas o pensamento de “só os mais fortes sobrevivem” e escolher apenas os indivíduos com maior aptidão para fazerem parte da nova população, independentemente de serem soluções recém-geradas. Por outro lado podemos ter em consideração outro tipo de estratégias e, por exemplo, atribuir uma probabilidade a um indivíduo de ser selecionado para a próxima população e depois escolher tendo em conta a sua aptidão, assim se consegue uma maior diversidade na próxima população e ainda temos em conta o facto de soluções consideradas más poderem ter partes boas. As três estratégias mais utilizadas são: 1Geracional Neste método nenhuma solução passa de forma automática da população atual para a próxima população. Todas as soluções da nova população são geradas através de processos de mutação e reprodução. No entanto este método tem a desvantagem de corrermos o risco de perdermos boas soluções e características da população inicial, bem como as melhores soluções obtidas. 2Elitista As chamadas “soluções de elite”, ou seja, as soluções com maior valor na função de aptidão são copiadas automaticamente para a próxima população. Estas soluções de elite são uma pequena percentagem, as melhores soluções encontradas. As restantes soluções são geradas através de processos de mutação e reprodução. Por vezes é necessário reforçar a utilização das operações de mutação de forma a evitar a convergência excessiva. 3Steady State; Apenas uma solução nova é gerada por mutação ou reprodução e incluída na população nova. As restantes soluções são as já existentes na população atual. A nova solução gerada Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 64 Se observamos o exemplo da figura anterior verificamos que o primeiro gene do cromossoma filho (0.30) foi resulta do cromossoma do primeiro progenitor. Isto deve-se ao facto de o valor gerado para o primeiro gene (0.58) ser inferior à probabilidade de escolha (0.7) definida. O operador de mutação em vez de utilizar a mutação gene a gene com baixa probabilidade emprega o conceito de imigração. Em cada geração são gerados novos membros a partir da mesma distribuição utilizada para a geração da população inicial (MUT). Este processo visa evitar a convergência prematura de uma população. A Figura 27 exemplifica o processo de transição de uma geração para a seguinte: Figura 27 - Transição de geração. 6.3. Exemplo De Construção De Uma Solução De seguida apresenta-se um exemplo para ilustrar com se obtém uma solução a partir de um cromossoma fornecido pelo algoritmo genético. 6.3.1. Dados Do Problema No exemplo ilustrativo assume-se que existem 10 clientes e uma frota de camiões constituída por dois tipos de capacidade, um de 20 e outro de 25 toneladas. A procura de cada cliente (em toneladas) é a apresentada na tabela seguinte Slide - 12 Cruzamento Gerados Aleatóriamente Geração Actual Geração Seguinte Copia Melhores TOPO MUT Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 65 Clientes 1 2 3 4 5 6 7 8 9 10 Procura (em toneladas) 2 5 7 8 6 7 4 5 3 6 Tabela 4 - Dados do exemplo. Em face das capacidades dos dois tipos de camião disponíveis (20 e 25 toneladas) e da procura total dos 10 clientes que é igual a 53 toneladas pode-se determinar que o número mínimo de camiões necessários são 3. O número máximo necessário de camiões seria, numa situação extrema, igual ao número de clientes, isto é, 10. Contudo, no exemplo iremos assumir um valor mais razoável igual a 5 camiões. 6.3.2. Cromossoma Fornecido Pelo BRKGA O cromossoma será constituído por 15 genes tendo em conta que assumimos que o número máximo de camiões será 5 e que o número de clientes é igual a 10. Para efeitos do exemplo iremos assumir que o BRKGA nos fornece o seguinte cromossoma. Tipos de Camião Ordem pela qual os clientes serão afetos às rotas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Genes 0,70 0,20 0,35 0,66 0,23 0,45 0,80 0,86 0,35 0,22 0,55 0,42 0,54 0,62 0,81 Tabela 5 – Cromossoma. 6.3.3. Descodificação Do Tipo De Camião Usado Em Cada Rota A descodificação do tipo de camião a utilizar em cada rota é obtida através da expressão (6.1) e consiste em multiplicar o valor de cada gene pelo número de tipos de camião disponíveis (que é 2 neste caso) e arredondar para o inteiro superior. Se o valor arredondado for 1, é escolhido o camião do tipo 1 com capacidade de 20 toneladas, se o valor obtido for 2, é utilizado o veículo do tipo 2 de 25 toneladas. A tabela abaixo mostra os cálculos efetuados. Rota 1 2 3 4 5 Gene 0,7 0,2 0,35 0,66 0,23 Valor expressão (6.1) INT( 0,7 x 2) = 2 INT( 0,2 x 2) =1 INT( 0,35 x 2) = 1 INT( 0,66 x 2) =2 INT( 0,23 x 2) = 1 Tipo de Veiculo a utilizar Tipo 2 = 25 toneladas Tipo 1 = 20 toneladas Tipo 1 = 20 toneladas Tipo 2= 25 toneladas Tipo 1 = 20 toneladas Tabela 6 - Descodificação das rotas Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 66 6.3.4. Descodificação Da Sequencia De Atribuição Dos Clientes Às Rotas A sequência pela qual os clientes serão afetados às rotas obtém-se ordenando os índices dos clientes por ordem crescente do valor dos seus genes. A tabela seguinte indica que os clientes serão atribuídos às rotas pela seguinte ordem: 5, 4, 7, 1, 8, 6, 9, 2, 10 e 3. Sequência de atribuição dos clientes às rotas 5 4 7 1 8 6 9 2 10 3 Genes por ordem crescente 0,22 0,35 0,42 0,45 0,54 0,6 0,62 0,8 0,81 0,86 Tabela 7 – Sequência de atribuição dos clientes à rota. 6.3.5. Construção da Solução Os clientes serão afetados às rotas de acordo a sequencia com a sequência especificada no ponto 6.4 (5, 4, 7, 1, 8, 6, 9, 2, 10 e 3). Construção da Rota 1 Conforme definido no ponto 6.3 na rota 1 será usado um camião com capacidade igual a 25 toneladas. Os clientes serão afetados na sequência proposta enquanto a capacidade do camião não for excedida. Clientes 5 4 7 8 6 Toneladas 6 8 4 5 7 Total 6 14 18 25 32 > 25 Parar Tabela 8 - Rota 1. Construção da Rota 2 Conforme definido no ponto 6.3 na rota 2 será usado um camião com capacidade igual a 20 toneladas. Os clientes serão afetados na sequência proposta enquanto a capacidade do camião não for excedida. Clientes 6 9 6 Toneladas 7 7 7 Total 7 14 21 > 20 Parar Tabela 9 - Rota 2. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 67 Construção da Rota 3 Conforme definido no ponto 6.3 na rota 3 será usado um camião com capacidade igual a 20 toneladas. Os clientes serão afetados na sequência proposta enquanto a capacidade do camião não for excedida. Clientes 2 10 3 Toneladas 7 6 7 Total 7 13 20 Tabela 10 - Rota 3. 6.3.6. Solução Final A solução final será a seguinte: Rotas Tipo de Camião Clientes Rota 1 1 Cap = 25 ton. 5 4 7 8 Rota 2 2 Cap = 20 ton. 6 9 Rota 3 2 Cap = 20 ton. 2 10 3 Tabela 11 - Solução final do exemplo. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 68 7. Experiências Computacionais Neste capítulo são descritos os dados utilizados: fontes e características das instâncias. Posteriormente, apresentam-se as soluções obtidas, analisando a performance do algoritmo desenvolvido. Por fim compararam-se as soluções encontradas com as reportadas na literatura e discutem-se as implicações de cada uma. O que se pretende avaliar é a qualidade dos resultados obtidos, ao nível da minimização dos custos totais da empresa com a aplicação de rotas de transporte eco-eficientes. A componente que diz respeito ao transporte eco-eficiente é parte integrante do custo total de transporte na função objetivo desenvolvida no capítulo três desta dissertação. 7.1. Dados Com vista a obter dados representativos do problema foram usados os dados propostos no documento escrito por Kwon, et al (2013) e intitulado por Heterogeneous fixed fleet vehicle routing considering carbon emission, com as seguintes características: Figura 28 - Instâncias de benchmark. Fonte: Kwon, et al (2013), Heterogeneous fixed fleet vehicle routing considering carbon emission. O problema estudado por Kwon et al tem apenas um armazém de onde saem todos os veículos e a onde regressam sempre no final da sua rota. É assumida uma frota de veículos heterogéneos de diferentes capacidades e níveis de emissão de carbono que estão disponíveis no armazém. É também assumido que o tamanho da frota é fixo, que cada veículo pode efetuar no máximo uma rota e cada cliente tem uma procura não negativa Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 69 que deve ser satisfeita. As distâncias entre cada par de pontos (clientes e armazém) são conhecidas. O problema consiste em determinar a rota de cada veículo usado, tendo em conta as suas capacidades e as necessidades dos clientes de modo a minimizar a soma dos custos variáveis de operação e dos custos líquidos de comércio de emissões de carbono. Para resolver este problema foram usadas três versões de um Tabu Search, cujo desempenho foi avaliado recorrendo a instâncias obtidas por modificação de instâncias de problemas benchmark (ver Figura 28). As instâncias foram originalmente geradas por Taillard, (1999) para o HVRP (Heterogeneous Vehicle Routing Problem) pelo que foi necessário gerar as emissões de carbono para cada tipo de veículo (ver capítulo 3, Figura 5) e o custo unitário líquido das referidas emissões (definido como US $ 25/ton). Relativamente ao limite superior permitido para estas emissões (AE) foi definido como a quantidade calculada para a solução obtida quando o custo das emissões de carbono é ignorado. As principais diferenças entre estes problemas e os que originalmente pensávamos resolver referem-se as emissões de CO2. Os custos destas emissões são incorporados na função objetivo, mas não se tem em conta o valor permitido. Assim, não se faz a análise de compra (caso se exceda o limite AE) e/ou venda (caso as emissões totais sejam inferiores a AE) de emissões no mercado de emissões (ver Capítulo 3). 7.2. Configuração Do BRKGA A população tem um número de cromossomas igual a 15 vezes o número de clientes. O valor dos parâmetros TOPO e MUT são iguais a 15% e a 20% do número de cromossomas na população, respetivamente. A probabilidade de escolher um gene do cromossoma de melhor qualidade é igual a 0.7. O critério de paragem do BRKGA foi 100 gerações. 7.3. Resultados Experimentais O algoritmo BRKGA foi implementado em linguagem de programação C++ e foi corrido 10 vezes para cada problema num computador com um processador Intel Core i7- Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 70 2630QM @2.0GHZ CPU e com o Sistema operativo Fedora release 21. Os resultados obtidos são apresentados na tabela seguinte. Problemas BRKGA Custo mínimo Custo médio Tempo (s) Custo mínimo T13 1994,76 2185,2 0,3 T14 994,56 1050,65 0,3 T15 1213,04 1280,51 0,5 T16 1542,53 1705 0,9 T17 1764,49 1923,23 1,5 T18 3065,19 3286,77 1,1 T19 1647,76 1860,36 14,3 T20 2592,43 2853,4 5,6 Tabela 12 – Resultados Experimentais do Algoritmo BRKGA. Para posteriormente se proceder a comparações de performance entre os dois algoritmos, começa-se por explicar como foram geradas as soluções do algoritmo aplicado no estudo de Kwon et al (2013). O algoritmo utilizado no estudo referido é um Tabu-Search que foi implementado em 3 versões diferentes, variando o método de geração de vizinhança. Os autores desenvolveram duas formas de gerar vizinhança: insertion e swap. Com estes duas foram criadas três versões (ver Figura 29): i) Insertion; ii) swap; iii) Hybrid que combina as duas primeiras. Ao analisar a Figura 29, verifica-se que os movimentos são feitos entre soluções vizinhas envolvendo menores quantidades de emissão de CO2 (E) sem ter em conta a distância de deslocação (D). Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 71 Figura 29 - Métodos de geração de vizinhança. Fonte: Kwon, et al (2013), Heterogeneous fixed fleet vehicle routing considering carbon emission. Considere-se um problema com 10 clientes, em que uma solução constituída por duas rotas representadas pelos vetores Rp e Rq, respetivamente. O método de inserção obtém novas soluções da seguinte forma. Primeiro é selecionado um nó no vetor Rq (cliente a ser removido da rota representada por Rq), seguidamente é selecionada uma posição no vetor Rp onde esse cliente é inserido. Se a nova solução (conjunto das duas rotas) apresentar menor valor de emissões de CO2, então essa solução é aceite; caso contrário a solução é rejeitada (ver Figura 29 (a)). No método de troca selecionam-se dois nós (clientes), um em cada rota, que são trocados. Tal como no caso do método de inserção, se a solução resultante apresentar menor valor de emissões de CO2, então essa solução é aceite; caso contrário a solução é rejeitada (ver Figura 29 (b)). O terceiro e último método, o método híbrido, gera novas soluções selecionando aleatoriamente, em cada iteração, o Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 72 método de inserção ou o método de troca. A melhor solução vizinha obtida, em qualquer um dos métodos, é posteriormente melhorada recorrendo a heurísticas 3-opt 14 . Desta forma, são geradas as soluções apresentadas na tabela abaixo, num computador de processador intel core i-7-2600 @3.40GHZ. Tabela 13 – Resultados computacionais do TSI,TSS e TSH. Analisando a tabela conclui-se que o TS-Hybrid obtém a melhor solução para todos os problemas exceto para o problema T14, para o qual a melhor solução é obtida pelo TSIsertion. Quanto à média das 10 soluções obtidas para cada problema, uma vez mais o TSHybrid apresenta os melhores resultados, com a exceção do problema T14, para qual desta vez o melhor desempenho é obtido pelo TS-Swap. A comparação entre o TSInsertion e o TS-Swap permite verificar que quanto à melhor solução cada um dos métodos é melhor que o outro em 4 problemas. No entanto, a performance do TSInsertion é mais variável já que em apenas 2 casos a média das 10 soluções obtidas é melhor do que a média para o TS-Swap. Assim sendo, pode-se concluir que a forma de gerar a vizinhança tem impacto na qualidade das soluções obtidas, pelo que expectavelmente o TS-Hybrid obtém melhores resultados, já que combina as outras duas estratégias de geração de vizinhança. Relativamente ao tempo computacional necessário à obtenção destas soluções o TSInsertion é mais rápido que os outros dois e de entre estes o TS-Hybrid é um pouco mais demorado. 14 Uma heurística 3-opt consiste em remover 3 ligacões de uma rota e refaze-la usando outras ligacões. Problemas TS – INSERTION(TSI) TS – SWAP(TSS) TS – HYBRID(TSH) Custo mínimo Custo médio Tempo (s) Custo mínimo Custo médio Tempo (s) Custo mínimo Custo médio Tempo (s) T13 2925,06 2925,06 0,1 2253.97 2284,7 0,3 1994,76 2205,05 0,3 T14 994,56 1069,45 0,2 1035.38 1045,79 0,3 1007,63 1087,85 0,2 T15 1588,85 1737,26 0,2 1401.78 1569,6 0,4 1213,04 1315,78 0,4 T16 1542,53 1808,43 0,3 1943.50 2006,98 0,2 1380,58 1502,94 0,7 T17 1850,76 1944,8 0,6 1764.49 1870,47 1,9 1596,5 1735,85 1,6 T18 3609,65 3668,25 0,2 3419.40 3484,57 0,3 3065,19 3268,97 0,4 T19 2017,57 2221,39 4,8 2040.78 2202,39 13,4 1647,76 1825,63 12,4 T20 2592,43 2945,23 1,6 3300.83 3300,83 0,7 2091,12 2304,74 3,5 Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 73 O algoritmo BRKGA não apresenta sempre os melhores resultados, no entanto, parece ser mais rápido, dado que o processador do outro computador era melhor do que o utilizado nas experiências computacionais para o BRKGA. Quando comparado com o TS-Insertion e relativamente às melhores soluções o BRKGA apresenta soluções melhores para 5 problemas e iguais para os restantes 3. No entanto, o BRKGA é mais robusto uma vez que a média das soluções obtidas é sempre melhor. Quando comparado com o TS-Swap, pode-se verificar que o BRKGA encontra, para 7 dos 8 problemas considerados, uma melhor solução. Quanto à média apenas não é melhor para um problema, pelo que mais uma vez apresenta melhor robustez. O TS-Hybrid encontra melhor solução do que o BRKGA para 3 problemas e pior para 1, já relativamente à média o numero de problemas em que cada um supera o outro é igual. Assim, mais uma vez BRKGA evidência maior robustez. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 80  Kwon, Y. J., Choi, Y. J., & Lee, D. H. (2013). Heterogeneous fixed fleet vehicle routing considering carbon emission. Transportation Research Part D: Transport and Environment, 23, 81-89.  Karp, R. M. (1975). On the computational complexity of combinatorial problems. Neworks, (5):45-68.  Kirkpatrick, S., Gelatt, C. e Vecchi, M., (1983), Optimization by simulated annealing, Science, 220, 671.  Koopmans, T. C. (1949). Optimum utilization of the transportation system.Econometrica: Journal of the Econometric Society, 136-146.  Kohl, N., & Madsen, O. B. (1997). An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation. Operations Research, 45 (3), 395-406.  Lins, S. e Kernigham, B (1973). An Effective Heuristic Algorithm for the Traveling Salesman Problem, Operations Research, 21, 498-516.  Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. Y. (2014). Survey of green vehicle routing problem: Past and future trends. Expert Systems with Applications, 41 (4), 1118-1138.  Min, H., (1989), The multiple vehicle routing problem with simultaneous delivery and pickup points, Transportation Research Part A, 23 (5), 377.  Mitchell, M. (1996). Computation in cellular automata: A selected review.Nonstandard Computation, 95-140.  Magalhães, M. S. M. M. (2011). Optimização de Rotas, (p. 1-31). Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 81  Oliveira, E. D. A. S., & Poldi, K. C. UMA INTRODUÇÃO AO PROBLEMA DE CORTE DE ESTOQUE COM DATA DE ENTREGA. Programação e Livro de Resumos, (p. 1-186).  Paksoy, T., O¨ zceylan, E., Weber, G. W., Barsoum, N., Weber, G. W., & Vasant, P. (2010, February). A multi objective model for optimization of a green supply chain network. In AIP Conference Proceedings (p. 311).  Pisinger, D., & Ropke, S. (2005). A general heuristic for vehicle routing problems. Copenhaga: Department of Computer Science, University of Copenhagen.  Paksoy, T., & Özceylan, E. (2013). Environmentally conscious optimization of supply chain networks. Journal of the Operational Research Society, 65 (6), 855872.  Piecyk, M. I., & McKinnon, A. C. (2010). Forecasting the carbon footprint of road freight transport in 2020. International Journal of Production Economics,128 (1), 31-42.  Robinson, J. (1949). On the Hamiltonian game (a traveling salesman problem)(No. RAND/RM-303). RAND PROJECT AIR FORCE ARLINGTON VA.  Salimifard, K., Shahbandarzadeh, H., & Raeesi, R. (2012). Green transportation and the role of operation research. In Int. Conf. Traffic Transp. Eng.(ICTTE 2012) (pp. 74-79).  Spears, W. M., Dejong K.A., 1991. On the Virtues of parameterized uniform crossover, in: Procedings of the Fourth International Conference on Genetic Algorithms, (pp. 230-236). Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 82  Shaw, P. (1998). Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems, Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP '98), M. Maher and J.-F. Puget (eds.), Springer-Verlag, 417-431.  Syswerda, G. (1991). Schedule optimization using genetic algorithms. Handbook of genetic algorithms.  Syswerda, G. (1989) Uniform crossover in genetic algorithms. In [43], 2–9.  Tavares, G., Zsigraiova, Z., Semiao, V., & Carvalho, M. d. (2008). A case study of fuel savings through optimization of MSW transportation routes. In Management of Environmental Quality: An international Journal (pp. 444-454).  Taha, M., Fors, M. N., & Shoukry, A. A. (2014). An exact solution for a class of green vehicle routing problem. In International Conference on Industrial Engineering and Operations Management (p. 7-9).  Taillard, É. D. (1999). A heuristic column generation method for the heterogeneous fleet VRP. Revue française d'automatique, d'informatique et de recherche opérationnelle. Recherche opérationnelle, 33 (1), 1-14.  Xiao, Y., Zhao, Q., Kaku, I., & Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem.Computers & Operations Research, 39(7), 1419-1431. Um Algoritmo Genético Para O Planeamento De Rotas Com Considerações Ambientais 83 Sites  Sistema europeu de negociação de CO2, http://www.sendeco2.com , acedido em 15 de Março de 2015.  INÊS B. (2014), “Veículos anteriores a 2000 proibidos de circular na Baixa de Lisboa a partir de Novembro”, http://www.publico.pt/local/noticia/veiculosanteriores-a-2000-proibidos-de-circular-na-baixa-de-lisboa-a-partir-de novembro-1670161, acedido em Março de 2015.  http://www.enmc.pt/pt-PT/atividades/mercado-de-combustiveis/precos-dereferencia, acedido em Março de 2015.  http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances, acedido em Junho de 2015.