Um Algoritmo de Roteamento para Vistoria dos Estádios da Eurocopa 2016

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

Um Algoritmo de Roteamento para Vistoria dos Est´adios da Eurocopa 2016 1 ´ Carlos H. P. Liberalino1 , Francisco C. de L. Junior , Gelson L. do Nascimento2 , 1 2 ´ ´ Jos´e E. B. Junior , Serafim do Nascimento Junior 1

Programa de P´os-graduac¸a˜ o em Ciˆencia da Computac¸a˜ o Universidade do Estado do Rio Grande do Norte (UERN) Rua Almino Afonso, 478 – Centro – 59.610-210 – Mossor´o – RN – Brasil 2

Programa de P´os-graduac¸a˜ o em Ciˆencia da Computac¸a˜ o ´ Universidade Federal Rural do Semi-Arido (UFERSA) Av. Francisco Mota, 572 – Costa e Silva – 59625-900 – Mossor´o – RN – Brasil {charlesbat,fclimajr,gelsonlopes.san,jose.etiene,serafim.snj}@gmail.com

Abstract. Holding soccer events requires too much responsibility of their organizing committees. An important task to be carried out before the beginning and after the end of these events is the inspection of the stadiums where the games are going to be hosted. This paper presents an optimal routing algorithm that finds and calculates the minimum cost route in order to help an inspection company to inspect stadiums rapidly and economically. The algorithm was implemented by utilizing the Branch & Bound paradigm to solve the travelling salesman problem. After applying it to the inspection of stadiums of the UEFA Euro 2016, it was possible to conclude by the results that the proposed algorithm is efficient and effective and, thus, it is very useful for carrying out inspections. Resumo. A realizac¸a˜ o de eventos de futebol requer muita responsabilidade de seus organizadores. Uma tarefa primordial a ser realizada nestes eventos e´ a vistoria dos est´adios sediadores dos jogos, pois garante a seguranc¸a dos usu´arios. Este artigo apresenta um algoritmo de roteamento o´ timo que encontra e calcula o caminho de custo m´ınimo que uma empresa de vistoria pode utilizar para tornar mais econˆomica e r´apida a execuc¸a˜ o desta tarefa. O algoritmo foi implementado utilizando o paradigma Branch & Bound para solucionar o problema do caixeiro viajante. Ap´os aplic´a-lo ao problema de vistoria dos est´adios da Eurocopa 2016, os resultados permitem concluir que o algoritmo e´ eficiente e eficaz e, portanto, e´ de grande utilidade para realizac¸a˜ o de vistorias.

1. Introduc¸a˜ o A Eurocopa e´ o principal campeonato de futebol europeu entre as selec¸o˜ es dos pa´ıses associados a` Uni˜ao das Federac¸o˜ es Europeias de Futebol (UEFA). O evento e´ realizado a cada quatro anos desde 1960 e a cada copa, um dos pa´ıses se torna a sede do evento. Originalmente, a Eurocopa era chamada de Copa das Nac¸o˜ es Europeias, ent˜ao a partir de 1968 o Campeonato Europeu de Futebol passou a se chamar apenas Eurocopa [UEFA 2016]. Este ano, a Eurocopa foi sediada na Franc¸a dentre os dias 10 de junho e 10 de julho. As cidades que sediar˜ao os jogos s˜ao apresentadas na Figura 1.

47

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

Figura 1. Cidades-sede da Eurocopa 2016 (EURO, 2016).

De acordo com [UEFA 2016], a base da estrutura organizacional da Eurocopa e´ realizada pela pr´opria sediadora do evento em parceria com a federac¸a˜ o de futebol do pa´ıs sede. Antes da realizac¸a˜ o dos jogos, a UEFA envia uma equipe de vistoria que, conforme [Buriol 2000], tem o intuito de realizar uma verificac¸a˜ o geral em todos os est´adios onde ir˜ao ocorrer os jogos do evento, tais como: sistema estrutural, impermeabilizac¸a˜ o, vedac¸a˜ o e revestimento, esquadrias, cobertura, instalac¸o˜ es hidrossanit´arias, instalac¸o˜ es el´etricas e combate a incˆendio. Como mencionado anteriormente, a vistoria consiste em passar por todos os est´adios em que ocorrem os jogos da Eurocopa. Desta maneira, nota-se que h´a um grande gasto de tempo e dinheiro durante a realizac¸a˜ o deste processo. Com base nesta problem´atica, este trabalho tem o objetivo de apresentar e propor um algoritmo para encontrar o roteamento o´ timo do percurso realizado por uma determinada empresa de vistoria entre as cidades que sediar˜ao os jogos da Eurocopa 2016, visando a minimizac¸a˜ o dos gastos e tempo de realizac¸a˜ o desta tarefa. Para atingir este objetivo, foi implementado um algoritmo que resolve o problema do caixeiro viajante utilizando-se o paradigma Branch and Bound (B&B) para determinac¸a˜ o do caminho de custo m´ınimo que uma empresa de vistoria pode utilizar e, assim, otimizar recursos e tornar mais econˆomica e r´apida a vistoria dos est´adios da Eurocopa 2016, seja antes do in´ıcio dos jogos seja ap´os o t´ermino. Neste artigo, apresentamos o algoritmo desenvolvido aplicado ao problema de vistoria dos est´adios. Este trabalho est´a organizado de acordo com as seguintes sec¸o˜ es: a sec¸a˜ o 2 apresenta a fundamentac¸a˜ o te´orica necess´aria para a implementac¸a˜ o do algoritmo; a sec¸a˜ o 3 denota alguns trabalhos relacionados que utilizam abordagens semelhantes as deste trabalho; a sec¸a˜ o 4 descreve os materiais e m´etodos utilizados para implementac¸a˜ o do algoritmo; a sec¸a˜ o 5 demonstra os resultados obtidos com a aplicac¸a˜ o do algoritmo sobre o problema de vistoria dos est´adios da Eurocopa 2016; e, finalmente, a sec¸a˜ o 6 apresenta as conclus˜oes.

48

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

2. Referencial Te´orico Com o intuito de realizar a tarefa de vistoria dos est´adios da maneira mais otimizada poss´ıvel, e´ necess´ario realizar um estudo sobre quais procedimentos devem ser tomados para se implementar um algoritmo que retorne o caminho de custo m´ınimo assim como seu custo para, desta maneira, se efetuar tal func¸a˜ o. Sendo assim, nesta sec¸a˜ o apresentamos o estudo que foi necess´ario para se obter o embasamento te´orico requerido para implementac¸a˜ o do algoritmo. 2.1. Roteamento de ve´ıculos Consoante [da Cunha 2000], o termo roteamento, do Inglˆes “routing”, e´ definido como um processo de determinac¸a˜ o de um ou mais rotas ou sequˆencias de paradas a serem cumpridas por ve´ıculos de uma frota objetivando visitar um conjunto de pontos geograficamente distribu´ıdos, em locais pr´e-determinados, que necessitam de atendimento. Os problemas de roteirizac¸a˜ o reais de acordo com [Dumitrescu and St¨utzle 2003] s˜ao definidos por trˆes principais fatores: decis˜oes, objetivos e restric¸o˜ es. Onde as decis˜oes se dizem a respeito do grupo de v´ertices a serem visitados, e envolvendo tamb´em a programac¸a˜ o e o sequenciamento das visitas. Como objetivos principais, o processo de roteamento visa proporcionar um servic¸o de alto n´ıvel, por´em mantendo os custos operacionais e de capitais t˜ao baixos quanto poss´ıvel. Por outro lado, devem-se obedecer as restric¸o˜ es geradas pelos problemas. Podemos reformular o problema de roteamento de ve´ıculos de forma simples, como um conjunto de ve´ıculos V idˆenticos, onde podemos represent´a-los pelo conjunto V ={1, 2, ..., n}, onde os mesmos necessitam realizar entregas ou prestar servic¸os em uma determinada regi˜ao, sendo assim seu ponto de partida sendo sua central. Os diversos pontos a serem visitados junto com a central s˜ao representados pelo conjunto C, que s˜ao os v´ertices de um grafo G=(C, A), onde A e´ o conjunto de arestas do grafo, representando a distˆancia entre os v´ertices [dos Reis 2007]. 2.2. Caixeiro Viajante O Problema do Caixeiro Viajante (PCV) consiste na problem´atica onde existe um caixeiro viajante e este quer encontrar o menor caminho para percorrer um conjunto de cidades que s˜ao atendidas por este caixeiro. Em outras palavras, o caixeiro conhece um conjunto de N cidades que se conectam umas com as outras, se encontra em uma delas e seu objetivo e´ passar, somente uma vez, por todas as cidades retornando a cidade de origem [Dorigo and St¨utzle 2004], formando assim um ciclo hamiltoniano. A sua origem e´ creditada a William Rowan Hamilton, pois inventou um jogo cujo objetivo era trac¸ar uma rota visitando um conjunto de cidades (v´ ertices), onde o trajeto se iniciava e terminava na mesma cidade, sem repetir a mesma visita a` uma cidade a qual j´a se tinha passado anteriormente. O ciclo Hamiltoniano construiu uma soluc¸a˜ o para o jogo de Hamilton [Guedes et al. 2009]. Segundo [Rodrigues et al. 2000], a formulac¸a˜ o matem´atica para o caso sim´etrico do caixeiro viajante, isto e´ , onde Cij = Cj i para todo i, j pertencente a V , e´ apresentada na Figura 2. A parte (1) da formulac¸a˜ o representa o custo total do circuito; as partes (2) e (3) s˜ao as restric¸o˜ es que forc¸am a chegada e a sa´ıda do caixeiro viajante exatamente uma vez

49

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

˜ matematica ´ Figura 2. Formulac¸ao do problema do caixeiro viajante.

de cada cidade, respectivamente; a parte (4) tem como objetivo impedir a formac¸a˜ o de subcircuitos e a (5) retrata a seguinte condic¸a˜ o: se Xij = 1, o trecho (rota) de i para j se encontra no circuito; caso contr´ario, se Xij = 0, o trecho n˜ao est´a. 2.3. Branch and Bound Uma boa forma intuitiva de se obter uma soluc¸a˜ o o´ tima para o PCV seria testar por ´ exaust˜ao todas as possibilidades. Por´em, como o PCV e´ um problema N P -Arduo, logo a abordagem exaustiva se torna invi´avel. No entanto, existem diversas outras estrat´egias baseadas em programac¸a˜ o inteira que podem garantir a obtenc¸a˜ o de uma soluc¸a˜ o o´ tima para o problema. Estas abordagens algor´ıtmicas, chamadas de exatas, garantem a obtenc¸a˜ o do resultado o´ timo e ainda provam a soluc¸a˜ o o´ tima obtida num tempo de execuc¸a˜ o finito ou provam que a soluc¸a˜ o vi´avel n˜ao existe. Como um exemplo de m´etodos exatos baseado em programac¸a˜ o inteira, podemos citar o m´etodo Branch & Bound [Dumitrescu and St¨utzle 2003]. Contudo, ainda nota-se que h´a algumas vantagens e desvantagens quanto a aplicac¸a˜ o de algoritmos exatos na soluc¸a˜ o de problemas que envolvem otimizac¸a˜ o combinat´oria. A vantagem dos algoritmos exatos que utilizam programac¸a˜ o inteira e´ que eles permitem provar e encontrar soluc¸o˜ es o´ timas, obtidas quando o algoritmo tem sucesso na sua execuc¸a˜ o. [Dumitrescu and St¨utzle 2003]. A desvantagem e´ o fato de que, para muitos problemas, o tamanho da instˆancia que pode ser solucionada encontra-se limitado pelo seu custo computacional, que e´ muito elevado, pois o tempo de processamento est´a em func¸a˜ o do n´umero de possibilidades e, sendo assim, cresce com o tamanho da instˆancia [Prestes 2006].

3. Trabalhos Relacionados Entre todos os problemas de otimizac¸a˜ o combinat´oria, o problema do caixeiro (PCV) e´ um dos problemas mais amplamente estudados. Embora a vers˜ao de otimizac¸a˜ o deste problema e´ N P -dif´ıcil, t´ecnicas de soluc¸a˜ o pr´atica n˜ao requerem otimizac¸a˜ o. E muitas

50

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

diferentes heur´ısticas de aproximac¸a˜ o de algoritmos s˜ao utilizados para resolver este problema [Matei and Pop 2010]. Na literatura encontramos v´arias aplicac¸o˜ es utilizando o problema do caixeiro viajante. Podemos citar uma empresa de produc¸a˜ o de jornais, onde estes jornais s˜ao distribu´ıdos em v´arios locais diferentes. Para isto, o funcion´ario respons´avel por fazer a distribuic¸a˜ o dos jornais, tem que encontrar uma rota de menor custo entre as cidades atendidas e ao final retornar a sua empresa [Zaeri et al. 2007] H´a tamb´em um aplicativo onde o caixeiro viajante e´ utilizado para encontrar a menor rota para pontos de sa´ude, tais como: postos de sa´ude, hospitais e outros. Uma aplicac¸a˜ o que tem apresentado resultados satisfat´orios, pois permite que o tempo gasto no atendimento seja minimizado [Hoffmann et al. ]. Em outra situac¸a˜ o, tem-se a utilizac¸a˜ o do caixeiro viajante para a colocac¸a˜ o de pontos estrat´egicos das bases policiais, e assim posicionando em pontos que minimizem a rota destes policiais, permitindo assim uma abrangˆencia maior da pol´ıcia (Gurgel et al., 2010). Percebe-se que ao longo do tempo surgiram v´arios algoritmos que proporcionam melhorias para a sociedade. Em outras palavras, estes algoritmos otimizam as ferramentas tecnol´ogicas e, consequentemente, problemas do nosso cotidiano. Outro exemplo de algoritmo e´ o Branch & Bound para soluc¸a˜ o do PCV. [dos Reis 2007], apresenta uma soluc¸a˜ o do problema fazendo uma alocac¸a˜ o o´ tima de medidores de energia el´etrica, no qual isso e´ aplicado dentro de uma rede de transmiss˜ao el´etrica de potˆencia. Para a sua implementac¸a˜ o foi utilizado o software Matlab, e tem a func¸a˜ o de minimizar o custo total do sistema, fazendo assim um monitoramento e, desta forma, determinando o n´umero o´ timo e tamb´em a localizac¸a˜ o dos monitores, com suas restric¸o˜ es sob as observac¸o˜ es da rede. Outro caso que vale a pena citar e´ o algoritmo de roteamento de ve´ıculos, apresentado em [Arsie et al. 2009]. Nele, e´ considerada uma classe dinˆamica de problemas de roteamento de ve´ıculos, em que um n´umero de agentes m´oveis no plano deve visitar pontos alvo gerados ao longo do tempo por um processo estoc´astico. Desta forma, fornecendo estrat´egias de coordenac¸a˜ o de movimento, a fim de minimizar o tempo esperado entre o aparecimento de um ponto de destino e o tempo que e´ visitado por um dos agentes.

4. Materiais e M´etodos Nesta sec¸a˜ o s˜ao apresentados os materiais e m´etodos que foram necess´arios para implementar o algoritmo apresentado neste artigo. 4.1. Modelagem do Problema Inicialmente foi realizada a coleta de dados por meio da obtenc¸a˜ o dos valores referentes as distˆancias (em Km) entre as cidades-sede da Eurocopa 2016. A ferramenta utilizada para execuc¸a˜ o desta tarefa foi a Google Maps. Os dados obtidos foram tabulados como pode ser visto na Figura 3. A partir da tabela apresentada na Figura 3, foi poss´ıvel criar um grafo G = (V, A), apresentado na Figura 4, para melhorar a visualizac¸a˜ o do problema. Para isto, a ferramenta GraphViz foi utilizada. Neste grafo, o conjunto V de v´ertices representam as cidades-sede e, consequentemente, o conjunto A de arestas representam as distˆancias entre duas cidades distintas.

51

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

ˆ Figura 3. Distancias entre as cidades-sede da Eurocopa 2016.

ˆ Figura 4. Grafo que representa as distancias entre as cidades.

4.2. Algoritmo proposto Para solucionar o problema de vistoria especificado anteriormente foi implementado um algoritmo de roteamento de ve´ıculos utilizando o paradigma Branch & Bound para soluc¸a˜ o do problema do caixeiro viajante. Onde o mesmo, resumidamente, segue o seguinte procedimento: dada uma matriz de adjacˆencia, e´ gerada uma estrutura de a´ rvore de decis˜ao, em que se percorre todos os seus n´os de forma sistem´atica e, assim, procurando evitar caminhos com soluc¸o˜ es invi´aveis ou piores das rotas j´a encontradas [Machado et al. ]. Esta estrat´egia pode ser visualizada atrav´es do pseudoc´odigo apresentado a seguir: A priori, faz-se um relaxamento para adaptac¸a˜ o do problema transformando a matriz num problema Branch & Bound. Diante desta situac¸a˜ o, para verificar se o algoritmo est´a correto, e´ apresentada a corretude dele a seguir. Como o algoritmo e´ iterativo, a sua corretude e´ verificada por meio do invariante de lac¸o. • Invariante: retorna-se uma lista (referente ao percurso o´ timo) com o caminho de custo m´ınimo armazenado sendo que cada um de seus elementos representam uma cidade onde a vistoria deve ser feita. • Antes do lac¸o: como n˜ao se saiu da cidade inicial, a lista referente ao percurso o´ timo n˜ao teve nenhum elemento adicionado referente ao caminho. Logo, ela e´ nula.

52

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

Algorithm 1 Inicio do algoritmo Definir um valor inicial para o melhor custo (custo m´ınimo) do caminho; Inicializar a fila de prioridades; Gerar o primeiro n´o com o caminho parcial [1] e calcular seu limite inferior; Inserir este n´o na fila de prioridades F P ; Enquanto n˜ao esvazia a fila de prioridades F P ; Remova o primeiro elemento dentro da fila de prioridades F P e atribua ele ao n´o pai; Se o limite inferior < melhor custo do caminho; Defina o n´ıvel do n´o para o n´ıvel do n´o pai + 1; Se este n´ıvel e´ igual a n − 1 (isto e´ , n ser o n´umero de cidades); Adicione 1 para o fim do caminho e calcule o custo do caminho inteiro; Se este custo < custo do melhor caminho; Defina o custo da melhor rota (caminho) e o melhor caminho adequadamente; Sen˜ao (isto e´ , o n´ıvel n˜ao e´ igual a n − 1 ); Para todo i tal que 2 = i ≤ n e i n˜ao est´a no caminho do pai; Copie o caminho do pai para o novo n´o; Adicione i para o fim deste caminho; Calcule o limite inferior para este n´o; Se o limite inferior e´ menor do que o custo da melhor rota; Insira este novo n´o na fila de prioridades; Fim do algoritmo

• Durante o lac¸o: a cada iterac¸a˜ o do lac¸o, trac¸a-se a rota de um novo caminho na a´ rvore. Caso o novo caminho tenha o menor custo do que o caminho j´a anteriormente obtido, esta nova rota e´ aderida e adicionada na lista referente ao percurso o´ timo. Logo, o caminho aderido anteriormente e´ podado. Caso o caminho seja invi´avel (pior do que o caminho j´a anteriormente obtido) este caminho e´ podado. Em seguida, inicia-se uma busca a um novo caminho e tudo se repete sucessivamente. • Ap´os o lac¸o: ao t´ermino do lac¸o, haver´a uma lista que indica o caminho com a soluc¸a˜ o o´ tima, isto e´ , o caminho de custo m´ınimo. Como visto anteriormente, o algoritmo demonstra-se estar correto. Para verificar a sua complexidade, vemos que no pior caso a a´ rvore de subproblemas ser´a completamente expandida. Sabendo que a cada expans˜ao dos n´os, a quantidade de subproblemas di-minui fatorialmente, isto e´ : na 1a expans˜ao: (n − 1) n´os; na 2a expans˜ao: (n − 2) n´os; na 3a expans˜ao: (n − 3) n´os; at´e a e-n´esima: (n − n). Logo, conclui-se que a complexidade do algoritmo, no pior caso, e´ O(n!). 4.3. Ferramentas utilizadas O algoritmo foi implementado utilizando a linguagem de programac¸a˜ o C auxiliada pelo ambiente de desenvolvimento Dev-C++ e utilizando-se o compilador minGW, sob o sistema operacional Windows 7.

53

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

5. Resultados Os resultados foram obtidos aplicando-se o algoritmo sobre a matriz de adjacˆencia referente ao problema de vistoria dos est´adios da Eurocopa 2016. Foi suposto que a empresa de vistoria se encontra na cidade de Bord´eus, cidade de origem do percurso. Para que a vistoria seja feita da maneira mais econˆomica e r´apida poss´ıvel, o caminh˜ao da empresa precisa percorrer todas as demais cidades e, por fim, retornar a sua cidade de origem. Desta maneira, aplicando o algoritmo proposto neste trabalho para solucionar este problema, obtivemos os seguinte resultados apresentados na Figura 5.

Figura 5. Cronograma com os dados pa-ra a vistoria

Como podemos observar na Figura 5, o algoritmo retorna que o custo total m´ınimo da menor rota, saindo de Bord´eus, e´ de 2908 km. Ademais, ele tamb´em apresenta o percurso que deve ser seguido saindo de Bord´eus, passando pelas demais cidades um u´ nica vez e, finalmente, retornando para a cidade inicial do percurso. Estas informac¸o˜ es auxiliam um determinada empresa de vistoria a executar esta tarefa de maneira mais r´apida e econˆomica. O grafo apresentado na Figura 6 representa melhor o percurso o´ timo que foi retornado pelo algoritmo.

6. Conclus˜ao Diante do problema de vistoria dos est´adios da Eurocopa deste ano, que consiste na necessidade de uma empresa fazer a inspec¸a˜ o de cada um dos est´adios-sede dos jogos, neste artigo uma soluc¸a˜ o tanto para este problema quanto para problemas similares e´ proposta. O algoritmo de roteamento de ve´ıculos apresentado neste trabalho utiliza o paradigma Branch & Bound para solucionar o Problema do Caixeiro Viajante. Ao aplicar o algoritmo para o problema de vistoria da Eurocopa 2016, os resultados obtidos apontam que o algoritmo apresenta uma soluc¸a˜ o o´ tima para encontrar o caminho de custo m´ınimo. Com isto, pode-se concluir que ele resolve o problema das vistorias nos est´adios de maneira eficiente e eficaz. Portanto, pode ser utilizado para qualquer problema que envolva o c´alculo de caminhos de custo m´ınimo.

54

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

Figura 6. Grafo com o caminho de custo m´ınimo de-terminado pelo algoritmo proposto

Como trabalhos futuros, pretende-se desenvolver um sistema de organizac¸a˜ o de eventos de futebol e, consequentemente, adicionar o algoritmo proposto neste trabalho a ele. Com o intuito de atingir este objetivo, ser˜ao implementadas mais funcionalidades ao algoritmo. Uma delas ser´a a inserc¸a˜ o de perfis de torcedores para gerar um cronograma mostrando todas as informac¸o˜ es referentes aos jogos que o torcedor deseja assistir. Tamb´em como proposta de trabalho futuro, visa-se otimizar o algoritmo proposto o tornando capaz de se trabalhar com m´ultiplas equipes de vistoria por meio da criac¸a˜ o de rotas.

Referˆencias Arsie, A., Savla, K., and Frazzoli, E. (2009). Efficient routing algorithms for multiple vehicles with no explicit communications. IEEE Transactions on Automatic Control, 54(10):2302–2317. Buriol, L. S. (2000). Algoritmo memetico para o problema do caixeiro viajante assimetrico como parte de um framework para algoritmos evolutivos. da Cunha, C. B. (2000). Aspectos pr´aticos da aplicac¸a˜ o de modelos de roteirizac¸a˜ o de ve´ıculos a problemas reais. Transportes, 8(2). Dorigo, M. and St¨utzle, T. (2004). Ant colony optmization, massachusetts institute of technology. dos Reis, D. C. S. (2007). Um algoritmo branch and bound para o problema da alocac¸ao otima de monitores de qualidade de energia el´etrica em redes de transmissao. Juiz de Fora, MG. Dumitrescu, I. and St¨utzle, T. (2003). Combinations of local search and exact algorithms. In Workshops on Applications of Evolutionary Computation, pages 211–223. Springer. Guedes, A. d. C. B., Leite, J. N. F., and Aloise, D. J. (2009). Um algoritmo gen´etico com infecc¸a˜ o viral para o problema do caixeiro viajante. Revista PublICa, 1(1).

55

EPOCA 2016 - IX Escola Potiguar de Computação e suas Aplicações

Hoffmann, E. H., Aebi, K. W. Z., and Bortoleto, S. Sistema de roteirizac¸a˜ o urba a: Aplicac¸a˜ o a sa´ude p´ublica. Machado, F. C., de Queiroz, T. A., Resende, M. G., Morabito, R., and Miyazawa, F. K. Problema do caixeiro viajante com coleta e entrega de objetos com base retangular. Matei, O. and Pop, P. (2010). An efficient genetic algorithm for solving the generalized traveling salesman problem. In Intelligent Computer Communication and Processing (ICCP), 2010 IEEE International Conference on, pages 87–92. IEEE. ´ N. (2006). Uma an´alise experimental de abordagens heur´ısticas aplicadas ao Prestes, A. problema do caixeiro viajante. PhD thesis, Universidade Federal do Rio Grande do Norte. Rodrigues, M. A. P. et al. (2000). Problema do caixeiro viajante: Um algoritmo para resoluc¸ao de problemas de grande porte baseado em busca local dirigida. UEFA (2016). UEFA EURO 2016 France: Le Rendez-Vous. Dispon´ıvel em: . Acesso em: 01 jul. 2016. Zaeri, M. S., Shahrabi, J., Pariazar, M., and Morabbi, A. (2007). A combined spatial cluster analysis - traveling salesman problem approach in location-routing problem: A case study in iran. In 2007 IEEE International Conference on Industrial Engineering and Engineering Management, pages 1599–1602.

56