Carla Sofia Problema do Caixeiro Viajante – Resolução e de ... · O Problema do Caixeiro Viajante (PCV) pode ser entendido como o problema de um vendedor que deseja visitar um

Universidade de Aveiro 2008

Departamento de Matemática

Carla Sofia de Assunção Gomes Costa

Problema do Caixeiro Viajante – Resolução e Depuração

Universidade de Aveiro 2008

Departamento de Matemática

Carla Sofia de Assunção Gomes Costa

Problema do Caixeiro Viajante – Resolução e Depuração

Dissertação apresentada à Universidade de Aveiro para cumprimento dos requisitos necessários à obtenção do grau de Mestre em Matemática e Aplicações - Especialização em Matemática Empresarial e Tecnológica, realizada sob a orientação científica do Doutor Sérgio Barreto, Professor Adjunto do Instituto Superior de Contabilidade e Administração da Universidade de Aveiro e co-orientação científica da Doutora Paula Rama, Professora Auxiliar do Departamento de Matemática da Universidade de Aveiro.

Dedicatória

Aos meus pais.

Ao Rui, meu marido.

O júri

Presidente: Professora Doutora Tatiana Tchemisova Cordeiro

Professora Auxiliar da Universidade de Aveiro

Vogais: Professor Doutor Tatiana Francisco José Ferreira Silva Professor Auxiliar da Universidade dos Açores

Professor Doutor Sérgio dos Santos Barreto

Professora Adjunto do Instituto Superior de Contabilidade e Administração da Universidade de Aveiro

Professora Doutora Paula Cristina Roque da Silva Rama Professora Auxiliar da Universidade de Aveiro

Agradecimentos

Ao Professor Sérgio Barreto, que orientou de uma forma muito paciente este trabalho. Agradeço toda a sua disponibilidade e compreensão ao longo destes meses, assim como a forma com que me conduziu neste trabalho e os conhecimentos que me transmitiu. À Professora Paula Rama, pela sua co-orientação e apoio nesta investigação. Aos meus pais, pelo constante incentivo, por todo o interesse e investimento que ao longo destes anos têm feito na minha formação, mas acima de tudo, por todo o amor e apoio que sempre me deram. Ao Rui, meu marido, o grande amor da minha vida. Obrigado por tudo, desde a paciência e compreensão, ao incentivo e contribuição prática neste trabalho. Com toda a certeza que, sem o seu incansável apoio não estaria a escrever estas linhas. Obrigado.

Palavras-chave

PCV, formulações, sub-ciclos.

Resumo

O Problema do Caixeiro Viajante (PCV) pode ser entendido como o problema de um vendedor que deseja visitar um conjunto de cidades, passando exactamente uma vez por cada uma e voltando ao ponto de partida no final do seu percurso.

O PCV está classificado como NP- Completo, o que faz com que seja de muito difícil resolução. A grande dificuldade na obtenção da solução óptima deste tipo de problemas, deve-se ao elevado número de restrições que cresce exponencialmente com o número de clientes.

Neste trabalho, começamos por introduzir o problema com exemplos bastante simples, onde são exibidos métodos heurísticos para a sua resolução. De seguida, é feita uma abordagem mais formal, onde são apresentados vários resultados que permitem reduzir substancialmente o número de restrições. Posteriormente, é feito um estudo de várias instâncias do problema, de forma a averiguar o comportamento das restrições de eliminação de sub-ciclos e o modo como estas se influenciam mutuamente. A grande parte dos testes efectuados neste trabalho apontam para a existência de uma forte redundância, do ponto de vista prático, na maior parte das restrições de eliminação de sub- -ciclos. Assim, os resultados obtidos indicam que apenas uma pequena percentagem das restrições de eliminação de sub-ciclos é necessária para a obtenção da solução óptima do problema.

Keywords

TSP, formulations, sub-cycle.

Abstract

The Travelling Salesman Problem (TSP) can be seen as a problem

of a salesman that wants to visit a set of cities, passing by each city exactly one time and returning to the starting point at the end of his tour.

The TSP is classified as a NP-Complete problem, which makes it a very hard to solve. The major difficulty in obtaining the optimal solution of this kind of problems is in the large number of constraints, that grows exponentially with the number of clients.

In this work, we start by introducing the problem through simple examples, where heuristic methods to obtain a solution are presented. Next, we take a more formal approach, where several results that allow for a considerable reduction on the number of constraints are presented. An analysis of several instances of the problem is then performed, with the objective of analysing the behaviour of the sub-cycle elimination constraints and the way they mutually interfere. The majority of the tests presented in this work indicate that there exists high redundancy, from a practical point of view, in most of the sub-cycle elimination constraints. Therefore, the results indicate that only a small percentage of the sub- -cycle elimination constraints is necessary to obtain the optimal solution for the problem.

PCV – Resolução e Depuração

1

ÍNDICE 1. Introdução …………………………………………………………………..……………4

1.1. Objectivos do trabalho ………………………………………………………......4

1.2. Estrutura do trabalho …………………………………………………………….5

2. O Problema do Caixeiro Viajante (PCV) …………………………………………….6

2.1. PCV: Origem e contextualização ………………………………………………6

2.2. Evolução histórica da resolução do PCV………………………………………7

3. Métodos de resolução do PCV: heurísticos e exactos ……………………..…..12

3.1. Exemplo de um problema ilustrativo do PCV …………………………….....13

3.1.1. Resolução usando o método do vizinho mais próximo ………………..14

3.1.2. Resolução usando um método de inserção …………………………….15

4. Formalização do Problema do Caixeiro Viajante…………………………..…….17

4.1. Algumas noções básicas sobre grafos ………………………………………17

4.2. Formulações matemáticas do PCV………………...…….…………………..21

Formulação 1 (Dantzig, Fulkerson e Johnson, 1954)………………….21

Formulação 2 (Dantzig, Fulkerson e Johnson, 1954) …………………25

Formulação 3 (Miller, Tucker e Zemlin, 1960) …………………………31

Formulação 4 (Barreto, 2004)……………………………………………35

5. Estudo e resolução iterativa de várias instâncias do PCV ……………………37

6. Relação e condicionamento entre restrições de eliminação de sub-ciclos ..45

6.1. Análise da matriz de restrições do PCV……………………………………...45

6.2. Interligação das restrições de eliminação de sub-ciclos……………………51

6.2.1. Influência das restrições de eliminação de sub-ciclos com 4 nós na

eliminação de sub-ciclos com 3 nós…………………………….……….52

6.2.2. Influência das restrições de eliminação de sub-ciclos com 5 nós na

eliminação de sub-ciclos com 3 e 4 nós…………,.……………………..58

7. Conclusão ……………………………………………………………..………………..61

8. Bibliografia……………...……………………………………………………………...62

9. Anexos ………………………………..…………………………………………..........64


2

LISTA DE FIGURAS

2.1. Jogo Icosiano………………………………………………………………………………….7

2.2. Solução gráfica da instância do PCV constituído por 49 cidades………………………9

2.3. Evolução da resolução do PCV desde 1954 até 2004………………………………...…9

2.4. Ilustração gráfica do World TSP…………………………………………………………..11

3.1. Localização geográfica das cidades……………………………………………………...13

4.1. Exemplo de um grafo……………………………………………………………………….17

4.2. Grafo simples………………………………………………………………………………..18

4.3. Grafo completo de seis vértices…………………………………………………………...19

4.4. Exemplo de um grafo……………………………………………………………………….19

4.5. Exemplo de um grafo orientado e não simétrico………………………………………...20

4.6. Exemplo de um grafo orientado e simétrico……………………………………………..20

4.7. Exemplo de um grafo não orientado (simétrico)…………………………………………21

4.8. Exemplo de dois sub-ciclos num grafo…………………………………………………...32

4.9. Ilustração de eliminação de sub-ciclos num grafo………………………………………33

5.1. Solução óptima da instância do PCV……………………………………………………..37

5.2. Solução da instância do PCV obtida apenas com as restrições de afectação………38


5.4. Solução da instância do PCV obtida com a adição da nova restrição………………..40

5.5. Solução da instância do PCV obtida com a adição das duas novas restrições……..40




6.1. Matriz de restrições de um PCV com 6 clientes…………………………………………47

6.2. Matriz de restrições do PCV com o acrescento das variáveis de folga……………….49

6.3. Esquema representativo do estudo da interligação de restrições……………………..52

6.4. Grafo completo com 4 nós………………………………………………………………....52

6.5. Sub-ciclos possíveis com 3 nós………………………...…………………………………53

6.6. Sub-ciclos possíveis com 4 nós………………….………………………………………..53

6.7. Grafo completo com 5 nós…………………………………………………………………58

6.8. Esquema conclusivo do estudo efectuado ……………..……………………………….59


3

LISTA DE TABELAS 3.1. Distância entre cidades…………………………………………………………………….13

3.2. Ciclos hamiltonianos possíveis entre as cidades………………………………………..14

3.3. Ordenação crescente do peso das arestas………………………………………………15

4.1. Ilustração de soluções impossíveis no PCV……………………………………………..23

4.2. Descrição dos subconjuntos de N………………………………………………………...24

4.3. Sub-ciclos possíveis com 3 nós num grafo com 7 nós…………………………………26

4.4. Sub-ciclos possíveis com 4 nós num grafo com 7 nós…………………………………26

4.5. Restrições de eliminação de sub-ciclos com 3 nós……………………………………..26

4.6. Restrições de eliminação de sub-ciclos com 4 nós……………………………………..27

4.7. Restrições de conectividade para sub-ciclos com 3 nós……………………………….28

4.8. Número de restrições de eliminação de sub-ciclos……………………………………..36

5.1. Número de restrições da instância do PCV……………………………………………...39

5.2. Resolução e análise de várias instâncias do PCV………………………………………44

6.1. Restrições de um PCV com 6 clientes…………………………………………………...46

6.2. Restrições do PCV com o acréscimo das variáveis de folga…………………………..48

6.3. Característica da matriz de restrições de alguns PCV………………………………….50

6.4. Formas distintas de satisfazer, no máximo, a restrição (1)…………………………….54

6.5. Restrições de eliminação de sub-ciclos com 4 nós num grafo com 5 nós……………55





6.10. Análise das escolhas admissíveis da restrição (6)…………..…………….…………..59


4

1. INTRODUÇÃO

O sector dos transportes é, sem dúvida, uma componente essencial da economia, e

de toda a sociedade em geral. Este fornece suporte à produção, ao comércio e

actividades de consumo, assegurando a movimentação rápida e eficaz, disponibilizando

em tempo apropriado matéria-prima, produto acabado e passageiros. Deste modo, os

transportes representam uma parcela significativa do custo de inúmeros produtos, bem

como da despesa nacional de qualquer país. Isto leva a uma forte e crescente

preocupação por parte das mais diversas empresas de diferentes sectores, na procura de

soluções que lhes permitam efectuar os seus serviços com a qualidade desejada, no

menor período de tempo e com o menor custo possível, de forma a rentabilizar os seus

recursos e a maximizar os lucros.

É neste contexto que, nos dias que correm, podemos enquadrar o Problema do

Caixeiro Viajante (PCV). Este é um problema que, desde há muitos anos, tem sido

objecto de estudo de muitos investigadores das mais diversas áreas científicas, dada a

sua grande e variada aplicação. Informalmente, o PCV consiste em encontrar o trajecto

de menor custo que permita a visita a todos os clientes (ou cidades) de uma determinada

rede, passando exactamente uma vez por cada um, de forma a economizar recursos e/ou

tempo.

Hoje em dia, o PCV é já tratado em dimensões gigantescas, em instâncias que

englobam milhões de clientes (cidades), sempre com o recurso a computadores de

elevada capacidade de processamento. Neste trabalho, além de uma contextualização e

descrição deste tipo de problema, serão resolvidas várias instâncias que, dada a

complexidade matemática e computacional do problema, serão significativamente mais

pequenas das que se adequam à realidade, de forma a clarificar a sua resolução, e

consequentemente facilitar a sua compreensão.

1.1. OBJECTIVO DO TRABALHO

O objectivo deste trabalho é expor de forma simples e clara o PCV, assim como

descrever de forma sequencial a resolução de vários exemplos e mostrar as dificuldades

existentes na obtenção da solução óptima, nomeadamente para problemas de grande

dimensão. São resolvidas várias instâncias do PCV e analisadas várias das suas

características e particularidades, com o objectivo de se obterem algumas conclusões


5

acerca do seu comportamento e, posteriormente, é feita uma generalização para

problemas de dimensão superior aos que são abordados neste trabalho.

Este texto pode ser dividido em fases, que se encontram estruturadas da seguinte

forma:

- O que é, para que serve e como se resolve um PCV;

- Mostrar, através da resolução de vários exemplos, que é difícil obter a solução

exacta usando todas as restrições, mas que, na verdade, é possível obter a solução

óptima com apenas uma percentagem muito pequena de restrições relativamente ao

conjunto inicial;

- Investigar o conjunto de restrições de eliminação de sub-ciclos e avaliar possíveis

redundâncias neste conjunto.

1.2. ESTRUTURA DO TRABALHO

Este trabalho encontra-se organizado e distribuído em 7 capítulos, incluindo esta

introdução. No capítulo 2, é feita uma breve referência à origem e contextualização

histórica do PCV, assim como um retrato da evolução verificada ao longo das últimas

décadas nos métodos de resolução do mesmo.

No capítulo 3, é apresentado um exemplo ilustrativo do PCV que, posteriormente, é

resolvido por dois métodos heurísticos distintos, sem recurso a qualquer programa

computacional.

No capítulo 4, encontram-se algumas noções básicas acerca de grafos, cujo

conhecimento e interiorização são relevantes para a compreensão deste estudo.

Posteriormente, são apresentadas e descritas diferentes formulações matemáticas para o

PCV.

No capítulo 5, são resolvidas, de forma sequencial, várias instâncias do PCV,

recorrendo às formalizações matemáticas apresentadas no capítulo anterior.

No capítulo 6, é feita uma análise a algumas características das restrições de

eliminação de sub-ciclos com o objectivo de se retirar algumas conclusões para a

simplificação da resolução deste tipo de problemas.

Finalmente, no capítulo 7 são apresentadas as conclusões e recomendações

resultantes da pesquisa e do estudo efectuados.


6

2. O PROBLEMA DO CAIXEIRO VIAJANTE (PCV)

2.1. PCV: ORIGEM E CONTEXTUALIZAÇÃO

O Problema do Caixeiro Viajante (PCV) é um dos problemas mais famosos de

Optimização Combinatória. Como já referido, o PCV consiste em encontrar o trajecto de

menor custo que permita a visita a todos os clientes de uma determinada rede, passando

exactamente uma vez por cada um. Este trabalho será focado no PCV simétrico, isto é,

dadas duas cidades A e B, o custo associado à ligação de A para B é exactamente o

mesmo custo associado à ligação de B para A.

Apesar da sua formulação simples, este é um problema que continua a captar a

atenção e o interesse de muitos investigadores das mais diversas áreas, entre as quais

Matemática, Investigação Operacional, Física e Biologia. Este amplo interesse no PCV

deve-se em grande parte, não só à simples formulação já referida, mas também às suas

diversas aplicações. De facto, inúmeros problemas reais podem ser modelados e

tratados como uma variante do PCV, como por exemplo problemas de produção, que

consistem na criação da sequência de um dado número de tarefas numa máquina de

forma a minimizar o tempo total de execução das mesmas. Um outro conjunto de

exemplos típicos de aplicação do PCV são os problemas de construção de rotas de

veículos1, de forma a minimizar os custos de distribuição e/ou o tempo despendido.

A origem deste problema não está precisamente estabelecida, no entanto, segundo

Goldbarg e Luna [9], a sua génese deve-se a William Rowan Hamilton2, que desenvolveu

um sistema de álgebra não comutativa – o Cálculo Icosiano – que pode ser interpretado

em termos de caminhos sobre um grafo descrito por um dodecaedro regular. Hamilton,

em 1859, construiu um puzzle a que chamou o Jogo Icosiano (Figura 2.1). Neste jogo,

cada um dos vértices (ou nós) do dodecaedro tinha escrito o nome de uma importante

cidade e o desafio que se colocava ao jogador era o de encontrar um caminho

percorrendo as arestas do dodecaedro de modo a passar exactamente uma vez por cada

uma das cidades e regressar ao ponto de partida.

1 Informações mais detalhadas sobre rotas de veículos aplicadas ao transporte escolar podem ser consultadas em [15]. 2 William Rowan Hamilton (1805-1865): matemático, físico e astrónomo irlandês. Fez contribuições importantes no desenvolvimento da óptica, dinâmica e álgebra. A sua descoberta mais importante, na área da Matemática, foi a dos Quaterniões. Em Física, foi muito conhecido pelo seu trabalho em mecânica analítica, que veio a ser muito influente nas áreas da mecânica quântica e da teoria quântica de campos.


7

O PCV é um problema classificado como NP-Completo. Segundo Cormen [5], esta

classe é constituída pelos problemas para os quais ainda não foi descoberto qualquer

algoritmo capaz de os resolver em tempo polinomial e, por outro lado, ainda ninguém foi

capaz de provar a sua inexistência. Dito de outra forma, significa que o PCV possui

ordem de complexidade exponencial, isto é, o esforço computacional para a sua

resolução aumenta exponencialmente com o número de nós a serem visitados.

Deste modo, apesar dos imensos estudos efectuados com o objectivo de encontrar

formas rápidas e eficazes de obter a solução para este tipo de problemas em tempo útil,

até hoje, tal não foi possível. Este facto leva a que, na maior parte dos casos, os métodos

de obtenção de solução aplicados a problemas reais sejam heurísticos, isto é, não

garantem a obtenção da solução óptima do problema do ponto de vista matemático.

2.2. EVOLUÇÃO HISTÓRICA DA RESOLUÇÃO DO PCV

Apesar da origem deste problema ser atribuída a Hamilton, o PCV foi difundido pela

primeira vez, em 1920, em Viena, pelo matemático Karl Menger3 que o divulgou pelos

seus companheiros universitários. Em 1930, o problema reapareceu no seio da

comunidade matemática em Princeton. Já na década de 40, foi estudado por vários

3 Karl Menger (1902-1985): matemático de sucesso da sua época. Filho do famoso economista Carl Menger, obteve o seu doutoramento na Universidade de Viena, trabalhando em várias áreas da matemática, nomeadamente em álgebra e geometria. Menger deu um grande contributo para o desenvolvimento da teoria de jogos.

Figura 2.1: Jogo Icosiano.


8

estatísticos, nomeadamente Mahalanobis4 (1940) e Jessen5 (1942) com vista a

aplicações no sector agrícola. Este problema foi ainda difundido na RAND Corporation6

pelo matemático Flood7, onde ganhou uma grande popularidade, passando mesmo a ser

considerado o protótipo dos problemas difíceis da Optimização Combinatória. Nesta

altura, a análise de todos os trajectos possíveis, um a um, começava a ser posta de

parte, dado que à medida que o número de clientes/cidades aumenta, o número de

trajectos possíveis também aumenta de forma muito significativa, tornando esta análise

completamente impraticável em tempo útil.

A grande evolução na resolução do PCV deve-se a George Dantzig, Ray Fulkerson e

Selmer Johnson que, em 1954, publicaram um artigo, entitulado Solution of a large-scale

Traveling-Salesman Problem [8] (que é hoje considerado um clássico) onde descrevem

um método de resolução do problema, ao mesmo tempo que demonstram graficamente o

poder desse método com a resolução de uma instância do PCV constituída por 49

cidades, o que representava um grande número na altura.

Para construir essa instância, escolheram uma cidade de cada um dos 48 estados dos

E.U.A. (o Alaska e o Hawaii apenas se tornaram estados em 1959) juntamente com

Washington D.C..

4 Prasanta Chandra Mahalanobis (1893-1972): cientista e estatístico indiano, considerado por muitos, um renascentista. Obteve a sua graduação com distinção em Física, no King’s College, em Cambridge. Publicou, em conjunto em outros professores, vários artigos relevantes na área de Estatística. Foi o fundador do Instituto Indiano de Estatística e contribuiu para estudos de amostras de grande escala. 5 Raymond Jessen (1910-2003): prestigiado estatístico que desde sempre teve um grande gosto e interesse pela actividade agrícola, obtendo, em 1937, uma licenciatura em Economia Agrícola. Foi encorajado por vários professores a prosseguir os seus estudos, conciliando as suas reconhecidas potencialidades estatísticas com o seu interesse pela agricultura. O resultado foi a sua Tese de Doutoramento, na qual criou a ideia de amostragem por áreas, desenvolvendo-a e utilizando-a para estimar factos acerca de explorações agrícolas. O doutoramento foi atribuído em 1943, conquistando de seguida um lugar de professor na Universidade do Estado de Iowa. Ao longo da sua carreira, direccionou sempre os seus trabalhos nas possíveis aplicações no sector agrícola. 6 RAND Corporation (Research ANd Development): instituição sem fins lucrativos, criada em

1948, cujo principal objectivo era o de, através de pesquisas e análises aprofundadas, ajudar a melhorar a política e a tomada de decisões dos responsáveis pelas Forças Armadas dos E.U.A.. Ao longo dos anos, esta instituição tem sofrido uma grande expansão, trabalhando quer com outros governos, quer com fundações privadas, organizações comerciais e internacionais. Tem sempre em vista uma análise objectiva e uma consequente obtenção de soluções eficazes para as questões com que se depara, de forma a auxiliar estas instituições a enfrentar os desafios políticos, sociais e económicos com que se deparam constantemente. 7 Merrill Flood: matemático americano, reconhecido pelo contributo dado para a base do Dilema do Prisioneiro (célebre problema da Teoria de Jogos), durante o período que colaborou com a RAND Corporation.


9

Figura 2.28: Solução gráfica da instância do PCV constituída por 49 cidades.

A figura 2.2 ilustra a solução encontrada para este problema. Este artigo foi, sem dúvida,

o grande impulsionador do desenvolvimento da resolução deste tipo de problemas.

Já na década de 70, mais especificamente em 1977, Grotschel9 encontrou um

percurso óptimo para um problema constituído por 120 cidades da Alemanha Ocidental.

Nos trinta anos seguintes verificou-se um enorme progresso na resolução deste tipo de

problemas, como podemos ver no gráfico seguinte (Figura 2.3) que ilustra de forma clara

tal avanço.

Figura 2.310: Evolução da resolução do PCV desde 1954 até 2004.

8 Imagem retirada de http://www.tsp.gatech.edu/history/pictorial/dfj.html (confirmado em 20.09.08) 9 Martin Grotschel: Professor no Instituto de Matemática da Universidade Técnica de Berlim, Alemanha. As suas principais áreas de investigação são a Optimização, Matemáticas Discreta e Pesquisa Operacional. Há mais de três décadas que publica artigos de grande relevo nestas áreas. Informação mais detalhada pode ser consultada em http://www.zib.de/groetschel/. 10 Imagem retirada de http://www.tsp.gatech.edu/methods/progress/progress.htm (confirmado em 21.09.08).

Nº de

cidades

Ano


10

Em 1973, Lin e Kernighan [12] propuseram um problema constituído por 318 nós

(problema conhecido por lin318), que foi resolvido, pela primeira vez, em 1980, por

Crowder e Padberg [6]. Em 1987, Padberg e Rinaldi [14] apresentaram um método de

resolução para uma instância constituída por 532 cidades dos Estados Unidos da

América (problema conhecido por att532). Ainda nesse mesmo ano, propuseram e

resolveram uma nova instância do PCV composta por 2392 nós (problema conhecido por

pr2392).

Applegate11, Bixby12, Chvátal13 e Cook14 deram um grande contributo na resolução de

instâncias do PCV. Em 1994, resolveram uma instância composta por 7397 cidades

(problema que ficou conhecido por pla7397). Em 1998, resolveram uma instância de

elevada dimensão constituída por 13 509 cidades, todas elas com pelo menos 500

habitantes, dos E.U.A. (problema conhecido por usa1350915). Já em 2001, resolvem um

problema de ainda maior dimensão, constituído por 15 112 cidades da Alemanha

(problema conhecido por d15112).

Em 2004, a mesma equipa de investigadores juntamente com Helsgaun16 resolveu

uma instância do PCV constituída por 24 978 cidades da Suécia (problema conhecido por

sw24978).

De forma sucinta, é esta a evolução ilustrada no gráfico (Figura 2.3), que é, na

verdade, surpreendente. No entanto, nos quatro anos seguintes, houve um avanço

gigantesco neste estudo. Os últimos dados conhecidos, apontam para o estudo de uma

instância do PCV constituída por 1 904 711 localidades (vilas e cidades povoadas) de

todo o mundo, daí este ser denominado por World TSP17. O melhor trajecto conhecido

para solucionar este problema foi encontrado por Helsgaun, em Julho de 2008, cujo

comprimento é de 7 515 948 301. No entanto, já em Setembro de 2003, havia 11 David Applegate: Professor Associado no Departamento de Matemática Aplicada e Computacional da Universidade de Rice, E.U.A. e investigador no AT&T Labs. É considerado um dos cientistas lideres no campo da Optimização. 12 Robert Bixby: Professor e Investigador na área de Gestão no Departamento de Matemática Aplicada e Computacional da Universidade de Rice, E.U.A..É considerado um marco na área da Optimização. 13 Vasek Chvátal: Professor no Departamento de Ciências dos Computadores da Universidade de Rutgers, E.U.A.. 14 William Cook: Professor no Departamento de Matemática Aplicada e Computacional da Universidade de Rice, E.U.A.. 15 Informação detalhada sobre este problema em http://www.crpc.rice.edu/CRPC/newsletters/sum98/news_tsp.html (informação confirmada em 21.09.08) 16 Keld Helsgaun: Professor associado no Departamento de Ciências dos Computadores da Universidade de Roskilde, Dinamarca. As suas principais áreas de investigação são Inteligência Artificial e Optimização Combinatória. 17 Toda a informação de forma detalhada sobre este problema pode ser encontrada no site http://www.tsp.gatech.edu/world/index.html (informação confirmada em 10.09.08)


11

conseguido chegar a um dos melhores trajectos conhecidos, com um comprimento de 7

517 285 610.

No momento presente, o melhor limite inferior para o comprimento de um percurso

deste problema é o de 7 512 218 268. Este limite mostra que o percurso obtido por

Helsgaun tem, no máximo, um comprimento 0.04987% maior do que o comprimento do

percurso correspondente à solução óptima do problema. Ou seja, o resultado obtido por

Helsgaun é, assim, muito próximo do óptimo, o que é surpreendente tendo em conta a

enorme dimensão do problema. A Figura 2.4 ilustra de forma clara a dimensão e

densidade deste problema. São, assim, evidentes os investimentos e esforços que têm

sido feitos, ao longo das últimas décadas, no sentido de melhorar os métodos de

resolução para este tipo de problemas, estando a fasquia cada vez mais elevada.

Figura 2.4: Ilustração gráfica do World TSP.


12

3. MÉTODOS DE RESOLUÇÃO DO PCV: HEURÍSTICOS E EXACTOS

Segundo Laporte [11], os métodos utilizados para a obtenção de solução do PCV

podem ser divididos em dois grupos: os métodos exactos e os métodos heurísticos.

Os métodos exactos são aqueles que possibilitam a obtenção da solução óptima do

problema e baseiam-se, normalmente, em procedimentos de enumeração implícita em

árvore, como é o caso do método Branch & Bound18, para o qual têm sido propostas

diferentes funções limitadoras. No entanto, dadas as várias limitações destes métodos,

nomeadamente a elevada capacidade computacional necessária para a resolução de

instâncias com um elevado número de nós, a atenção é cada vez mais dirigida para os

métodos heurísticos.

Estes métodos permitem a obtenção de soluções aproximadas, porém com maior

rapidez e em problemas de grande dimensão. Heurísticas são procedimentos de

obtenção de solução que, na maior parte das vezes, se baseiam numa abordagem

intuitiva, na qual a estrutura particular do problema possa ser considerada e explorada de

forma inteligente para a obtenção da solução adequada. Tal facto leva a que, na maioria

dos casos, as heurísticas propostas sejam bastante específicas para o problema em

causa, o que impossibilita a obtenção de boas soluções para problemas com

características ou restrições um pouco distintas das dos problemas para as quais foram

desenvolvidas.

De forma a facilitar a compreensão deste tipo de problemas, apresentamos um

exemplo simples de um PCV, com um número reduzido de cidades que o Caixeiro

Viajante tem de visitar. Para determinar o melhor trajecto a percorrer, vamos recorrer a

dois métodos heurísticos distintos.

18 Branch and bound é um algoritmo geral para encontrar soluções óptimas de problemas de optimização em programação linear inteira. Este método consiste numa enumeração sistemática de todos os candidatos a solução do problema, onde grandes subconjuntos de candidatos sem sucesso são descartados em massa, através do uso de limites superior e inferior estimados da variável que está a ser optimizada. O método foi inicialmente proposto em 1960, por A. H. Land e A. G. Doig para problemas de programação linear.


13

3.1. Exemplo de um problema ilustrativo do PCV

Exemplo 3.1.1: Um vendedor de uma empresa do sector metalúrgico pretende visitar

seis dos seus clientes, instalados na Península Ibérica. Para tal, pretende determinar o

melhor percurso a efectuar, tendo em conta exclusivamente as distâncias entre as várias

cidades em causa.

Na Tabela 3.1, temos as distâncias (em Km) entre as várias cidades a serem visitadas

pelo vendedor. No mapa (Figura 3.1), podemos observar um esquema representativo das

respectivas localizações.

Évora Elvas Faro Salamanca Madrid

Lisboa 133 208 277 472 628

Évora -- 85 173 390 606

Elvas -- -- 363 306 422

Faro -- -- -- 709 723

Salamanca -- -- -- -- 208

Figura 3.119: Localização geográfica das cidades.

19 O mapa da Figura 3.1 e as distâncias apresentadas na Tabela 3.1 foram obtidos através do software Google Earth.

Tabela 3.1: Distância entre cidades.


14

3.1.1. RESOLUÇÃO USANDO O MÉTODO DO VIZINHO MAIS PRÓXIMO

Este método consiste em, dado um conjunto de cidades que o Caixeiro Viajante tem

de visitar, começar por escolher (aleatoriamente) uma cidade para iniciar o percurso. De

seguida, seguir para a mais próxima e assim sucessivamente até voltar à cidade inicial.

No entanto, nem sempre é possível escolher a cidade mais próxima, pois esta pode já ter

sido visitada e a sua escolha iria possibilitar a formação de um sub-ciclo, isto é, iria

terminar o percurso antes que todas as cidades tivessem sido visitadas.

Aplicando este algoritmo, para as seis cidades apresentadas, temos os seguintes

resultados:

Percursos Total (Km) Lisboa � Évora � Elvas � Salamanca � Madrid � Faro � Lisboa 1732

Faro � Évora � Elvas � Lisboa � Salamanca � Madrid � Faro 1869

Évora � Elvas � Lisboa � Faro � Salamanca � Madrid � Évora 1993

Elvas � Évora � Lisboa � Faro � Salamanca � Madrid � Elvas 1834

Salamanca � Madrid � Elvas � Évora � Lisboa � Faro � Salamanca 1834

Madrid � Salamanca � Elvas � Évora � Lisboa � Faro � Madrid 1732

Na Tabela 3.2, podemos encontrar os dois percursos que seriam os mais económicos

(tendo apenas em conta a distância entre as cidades), um com início em Lisboa, outro

com início em Madrid. É importante realçar que este método apenas nos fornece a

melhor solução em cada etapa, o que pode não conduzir à solução óptima global. No

entanto, este é um processo a que várias vezes se recorre neste tipo de problemas dado

que reduz de forma significativa o número de percursos a analisar. Note-se que, com

apenas 6 cidades, temos um total de 602!5

= percursos nas condições pretendidas. De

uma forma geral, para o PCV simétrico, no caso de existirem n cidades para visitar, o

número de trajectos nas condições desejadas, isto é, trajectos que permitem ao Caixeiro

Viajante visitar todas as cidades da sua rota, sem repetir qualquer uma delas e regressar

à cidade inicial, é dado por ( )2

!1n − .

Tabela 3.2: Ciclos hamiltonianos possíveis entre as cidades.


15

Deste modo, este algoritmo reduz o número de possibilidades para o número de

cidades a visitar, não sendo no entanto um método sempre eficaz.

3.1.2. RESOLUÇÃO USANDO UM MÉTODO DE INSERÇÃO

Os métodos de inserção partem de um trajecto inicial composto por apenas 2 cidades,

acrescentando-se, de seguida e de forma sequencial, todas as outras cidades que ainda

não haviam sido incluídas no trajecto. Segundo Laporte [11], essa selecção sucessiva

pode atender a diversos critérios, nomeadamente: a cidade mais próxima do trajecto, ou

a mais distante; aquela cidade que forma o maior ângulo com duas cidades já incluídas

no trajecto; a cidade que proporciona o menor acréscimo de distância total ao percurso

parcial já construído.

Neste caso, vamos usar um algoritmo de inserção baseado na ordenação do peso

(distância) das arestas. Começamos por ordenar as arestas por ordem crescente do

respectivo peso. O objectivo é a construção de um percurso nas condições anteriormente

descritas que inclua as arestas de menor peso, tendo em conta as seguintes restrições:

- não se inclui um nova aresta incidente num vértice já visitado por duas arestas;

- não se fecha um ciclo enquanto existirem nós não visitados.

Por ordem crescente, a ordenação das arestas é dada por:

85 Évora �� Elvas

133 Lisboa �� Évora

173 Évora � Faro

208 Madrid �� Salamanca

208 Lisboa � Elvas

277 Lisboa �� Faro

306 Salamanca �� Elvas

363 Faro � Elvas

390 Évora � Salamanca

422 Madrid � Elvas

472 Lisboa � Salamanca

506 Madrid � Évora

628 Madrid � Lisboa

709 Faro � Salamanca

723 Madrid �� Faro

Tabela 3.3: Ordenação crescente do peso das arestas.


16

Tomemos, para iniciar o algoritmo, a aresta de menor peso, que liga Évora a Elvas. De

seguida, inclua-se na solução a segunda aresta de menor peso, que liga Lisboa a Évora,

dado que esta não corrompe qualquer uma das condições impostas. No entanto, já a

terceira aresta não pode ser incluída, pois tal implicaria que se voltasse a uma cidade já

visitada. Portanto, segue-se para a quarta aresta, que pode ser incluída no percurso. O

mesmo não acontece com a quinta aresta, pois a sua inclusão formaria um circuito que

não incluía algumas das cidades a serem visitadas. Procedendo com este raciocínio,

chegamos à conclusão que o percurso obtido por este método (representado a bold) é

igual ao primeiro percurso obtido pelo método do vizinho mais próximo, com um total de

1732 km de distância a percorrer.

Os dois métodos apresentados levam-nos à conclusão de que a distância mínima que

o Caixeiro Viajante tem de percorrer é a de 1732 km, seguindo o caminho apresentado.

No entanto, apesar destes dois métodos heurísticos nos induzirem que esta é a solução

óptima do problema, ainda não podemos garantir efectivamente que assim seja.

Ao longo deste trabalho, iremos recorrer à análise de vários exemplos semelhantes ao

anterior, tendo como objectivo estudar qual a melhor forma para obter a solução óptima

do problema de um modo o mais eficaz possível. Iremos começar por formalizar

matematicamente o PCV de forma a prosseguir com o seu estudo e depuração.


17

4. FORMALIZAÇÃO DO PROBLEMA DO CAIXEIRO VIAJANTE (PCV)

4.1. ALGUMAS NOÇÕES BÁSICAS SOBRE GRAFOS

Para dar seguimento ao estudo do PCV, é necessário definir formalmente alguns

conceitos e noções que vão ser frequentemente utilizados ao longo deste trabalho.

Definição 4.1.1: Um grafo consiste em dois conjuntos finitos e disjuntos, V (de vértices

ou nós) e A (de arestas ou ligações) e uma função ψ dita de incidência definida em A tais

que:

i. V≠∅

ii. para cada a ∈ A, ψ(a) é um par de elementos de V (não necessariamente

distintos).

Definição 4.1.2: Dois vértices dizem-se adjacentes, se existe a ∈ A, tal que ψ(a)=uv.

Definição 4.1.3: Uma aresta que liga um vértice com ele próprio chama-se lacete ou

laço.

Definição 4.1.4: Se dois vértices estão ligados por mais do que uma aresta, então as

arestas que os ligam chamam-se arestas múltiplas.

Exemplo 4.1.1: Consideremos o seguinte grafo G, onde { }5,4,3,2,1V = e

{ }i,h,gf,e,d,c,b,aA = .

P

h

f

g

e d b

c

a

1 2 3

4 5 i

G

Figura 4.1: Exemplo de um grafo.


18

Neste caso, temos que, por exemplo:

- os vértices 1 e 2 são adjacentes dado que existe uma aresta, c, que os une;

- as arestas a e b dizem-se arestas múltiplas dado que têm os mesmos vértices como

extremidades;

- a aresta g diz-se um lacete dado que liga o vértice 3 a ele próprio.

Definição 4.1.5: Um grafo simples é um grafo sem lacetes e sem arestas múltiplas.

Exemplo 4.1.2: Se ao grafo G, do exemplo anterior, retirarmos uma das arestas que liga

os vértices 1 e 4, e o lacete incidente no vértice 3, obtemos o grafo simples, H.

Nota: De forma a simplificar a notação, nos exemplos seguintes não serão utilizadas

letras para identificar as arestas, usando apenas os números para os vértices (ou nós).

Definição 4.1.6: Um grafo completo com n vértices é um grafo simples em que

quaisquer dois vértices são adjacentes e representa-se por Kn.

Definição 4.1.7: O grau do vértice v é o número de arestas que incidem em v e designa-

se por g(v).

Definição 4.1.8: Um grafo diz-se regular (de grau k) se todos os vértices tiverem o

mesmo grau (igual a k).

Exemplo 4.1.3: Considere-se, por exemplo, K6, grafo completo de seis vértices. Todos os

vértices têm grau 5, logo K6 é um exemplo de um grafo regular de grau 5.

h

f

e d b

c 1 2 3

4 5 i

H

Figura 4.2: Grafo simples.


19

Definição 4.1.9: Dado um grafo G, um passeio em G é uma sucessão finita, não vazia,

de vértices (ou nós) adjacentes. Diz-se um passeio fechado se começa e termina no

mesmo vértices, e aberto, caso contrário.

Definição 4.1.10: Um caminho é um passeio sem repetição de vértices.

Definição 4.1.11: Um ciclo é um passeio fechado, sem repetição de vértices, com a

excepção do primeiro e do último.

Definição 4.1.12: O comprimento do caminho v0…vk é k, igual ao número de arestas.

Exemplo 4.1.4: Consideremos o grafo G da Figura 4.4:

5

4

1 2

3

6

G

Figura 4.3: Grafo completo de seis vértices (ou nós).

Figura 4.4: Exemplo de um grafo.


20

Vejamos alguns exemplos, em G, de:

- um passeio aberto: 1 2 3 4 2;

- um passeio fechado: 1 2 3 4 2 1;

- um caminho: 1 6 5 4;

- um ciclo: 1 6 5 4 2 1.

Definição 4.1.13: Seja G um grafo. Um caminho hamiltoniano em G é um caminho

(passeio sem repetição de vértices) que contém todos os vértices de G. No caso de ser

fechado, tal caminho diz-se um ciclo hamiltoniano.

Nota: Se a um ciclo hamiltoniano retirarmos uma aresta obtemos um caminho

hamiltoniano.

Definição 4.1.14: Um grafo G é um grafo hamiltoniano se admitir um ciclo hamiltoniano.

Note-se que o grafo G do exemplo 4.1.4, é um grafo hamiltoniano, pois este contém um

ciclo hamiltoniano (1 2 3 4 5 6 1).

Definição 4.1.15: Um grafo diz-se dirigido ou orientado quando o sentido das ligações

entre os vértices é considerado, isto é, as arestas possuem uma direcção. Neste caso, as

arestas passam a denominar-se por arcos.

Definição 4.1.16: Um grafo simétrico é um grafo onde existem arestas dirigidas de um

vértice para o outro em ambos os sentidos.

Um grafo não orientado é sempre simétrico.

Exemplo 4.1.5: Vejamos as seguintes figuras de modo a esclarecer os conceitos das

definições 4.1.15 e 4.1.16.

1 2

4 3

Figura 4.5: Exemplo de um grafo orientado e não simétrico.

1 2

4 3

Figura 4.6: Exemplo de um grafo orientado e simétrico.


21

4.2. FORMULAÇÕES MATEMÁTICAS DO PCV

A formalização matemática do PCV requer a definição formal de alguns conjuntos e

parâmetros fundamentais: { }n...,,2,1N = representa o conjunto com n clientes do

plano; ijc , representa o custo associado à ligação entre os clientes Nj,i ∈ e, por

último, ijx , representa o número de vezes que é usada a ligação entre o cliente i e o

cliente j (são designadas por variáveis de decisão).

Dantzig, Fulkerson e Johnson [8] foram os pioneiros na formalização do PCV, quando

em 1954, publicaram um artigo onde fazem uma análise detalhada deste problema e o

formalizam matematicamente, em programação linear binária, da seguinte forma:

Formulação 1:

{ } )3.1(ji,Nj,i,1,0x

)2.1(3n|S|3,NS,1|S|x

)1.1(Ng,2xx:asujeito

xcZMin

ij

ji,Sj,iij

gi,Ni jg,Njgjig

ji,Nj,iijij

<∈∈

−≤≤⊂−≤

∈=+

=

∑

∑ ∑

∑

<∈

<∈ <∈

<∈

1 2

4 3

Figura 4.7: Exemplo de um grafo não orientado (simétrico).


22

A função objectivo (z) representa o custo total do percurso do Caixeiro Viajante. Note-

se que se o custo for de uma unidade monetária por cada unidade de comprimento, a

função objectivo irá traduzir o valor da distância percorrida pelo Caixeiro Viajante. As

restrições (1.1), designadas por restrições de afectação, estabelecem que cada cliente é

visitado exactamente uma vez, tendo em conta as restrições (1.3), que atribuem o valor 0

para arestas que não sejam incluídas na solução e o valor 1 caso contrário. As restrições

(1.2) têm como objectivo o impedimento de sub-ciclos que não contenham todos os

clientes.

As restrições de integralidade juntamente com as restrições de afectação não

permitem a formação de sub-ciclos com menos de 3 nós. Pois, como estamos a estudar

PCV simétrico e todos os nós têm grau 2, não é permitida a existência de nós isolados

nem de arestas múltiplas. Isto justifica a indicação 3n|S|3,NS −≤≤⊂ , nas restrições

(1.2).

Deste modo, no caso de termos menos de 6 clientes, as restrições necessárias são

apenas as restrições de afectação, pois estas impõem imediatamente a inexistência de

sub-ciclos. Já vimos que para 3n ≤ , não há possibilidade de formação de sub-ciclos.

Portanto, basta-nos analisar a possibilidade de existência de sub-ciclos com 3 nós, no

caso de termos 4 ou 5 clientes. Em ambos os casos, tal não é possível, pois, para n=4, a

existência de um sub-ciclo com 3 nós, implicaria a existência de 1 nó isolado; por outro

lado, no caso de n=5, implicaria a existência de um sub-ciclo com 2 nós ou de nós

isolados.


23

Na Tabela 4.1, podemos ver algumas ilustrações dos casos referidos.

Número de nós Situações que não podem acontecer

n=3

n=4

n=5

Assim, concluímos que para PCVs com menos de seis clientes, não é necessário

incluir restrições de eliminação de sub-ciclos. Portanto, as restrições de eliminação de

sub-ciclos têm relevância em PCVs constituídos por pelo menos seis clientes.

Segundo Barreto [2], dado um PCV com n clientes, o número de restrições de

eliminação de sub-ciclos, que cresce exponencialmente com o número de clientes, é

dado por 2nn2 2n −−− .

De forma a ganharmos alguma intuição sobre esta expressão, concretizemos um

exemplo de um PCV com 7 clientes, que pode então ser representado por um grafo com

7 nós. Neste caso, { }7,6,5,4,3,2,1N = . Sem ter em conta a fórmula apresentada,

vejamos qual o número de restrições de eliminação de sub-ciclos necessário para a

resolução do problema segundo a Formulação 1.

Comecemos por construir o conjunto das partes de N, )N(P , isto é, o conjunto

constituído por todos os subconjuntos de N, cujo cardinal é 2n. Como 7n = , temos um

total de 128 subconjuntos de N, que se encontram descritos na Tabela 4.2.

Tabela 4.1: Ilustração de soluções impossíveis no PCV.


24

Nº de nós

Descrição dos subconjuntos de N Nº total

0 φ 1

1 { } { } { } { } { } { } { }7,6,5,4,3,2,1 7

2 { } { } { } { } { } { } { } { } { } { } { } { } { } { }{ } { } { } { } { } { } { }7,6,7,5,6,5,7,4,6,4,5,4,7,3

,6,3,5,3,4,3,7,2,6,2,5,2,4,2,3,2,7,1,6,1,5,1,4,1,3,1,2,1 21

3

{ } { } { } { } { } { } { } { } { } { }{ } { } { } { } { } { } { } { } { } { }{ } { } { } { }{ } { } { } { } { } { }{ } { } { } { } { }7,6,5,7,6,4,7,5,4,6,5,4,7,6,3

,7,5,3,6,5,3,7,4,3,6,4,3,5,4,3,7,6,2,7,5,2,6,5,2,7,4,2,6,4,2

,5,4,2,7,3,2,6,3,2,5,3,2,4,3,2,7,6,1,7,5,1,6,5,1,7,4,1,6,4,1

,5,4,1,7,3,1,6,3,1,5,3,1,4,3,1,7,2,1,6,2,1,5,2,1,4,2,1,3,2,1

35

4

{ } { } { } { } { } { } { } { }{ } { } { } { } { } { } { } { }{ } { } { } { } { } { } { } { }{ } { } { } { } { } { } { }{ } { } { } { }7,6,5,4,7,6,5,3,7,6,4,3,7,5,4,3

,6,5,4,3,7,6,5,2,7,6,4,2,7,5,4,2,6,5,4,2,7,6,3,2,7,5,3,2,

6,5,3,2,7,4,3,2,6,4,3,2,5,4,3,2,7,6,5,1,7,6,4,1,7,5,4,1,,6,5,4,1

,7,6,3,1,7,5,3,1,6,5,3,1,7,4,3,1,6,4,3,1,5,4,3,1,7,6,2,1,7,5,2,1

,6,5,2,1,7,4,2,1,6,4,2,1,5,4,2,1,7,3,2,1,6,3,2,1,5,3,2,1,4,3,2,1

35

5

{ } { } { }{ } { } { } { }{ } { } { } { } { } { } { }{ } { } { } { } { } { } { }7,6,5,4,3,7,6,5,4,2,7,6,5,3,2,7,6,4,3,2,7,5,4,3,2,6,5,4,3,2,7,6,5,4,1

,7,6,5,3,1,7,6,4,3,1,7,5,4,3,1,6,5,4,3,1,7,6,5,2,1,7,6,4,2,1,7,5,4,2,1

,6,5,4,2,1,7,6,3,2,1,7,5,3,2,1,6,5,3,2,17,4,3,2,1,6,4,3,2,1,5,4,3,2,1 21

6 { } { } { } { } { }{ } { }7,6,5,4,3,2,7,6,5,4,3,1

,7,6,5,4,2,1,7,6,5,3,2,1,7,6,4,3,2,1,7,5,4,3,2,1,6,5,4,3,2,1 7

7 { }7,6,5,4,3,2,1 1

Total 128

Como temos um grafo com 7 nós, temos de considerar os subconjuntos NS ⊆ tal que

4|S|3 ≤≤ , obtendo um total de 70 subconjuntos (consultar Tabela 4.2). Os subconjuntos

com 1, 2, 5 e 6 elementos são no total 56, que pode ser escrito como 72+7. Temos, ainda,

mais 2 subconjuntos que se referem ao conjunto vazio e ao próprio conjunto N. Então,

desta forma, para obtermos o número de restrições teríamos de retirar ao número total de

subconjuntos de N, que é de 128, um total de 582772 =++ , o que equivale a efectuar

o cálculo 702772 27 =−−− , o que vai de encontro ao pretendido.

Tabela 4.2: Descrição dos subconjuntos de N.


25

Uma outra possível formulação para o PCV, também proposta por Dantzig et al. [8],

pode ser obtida pela substituição das restrições (1.2) por restrições do tipo:

A formalização do PCV usando as restrições de conectividade, é a seguinte:

Formulação 2:

Note-se que, nesta formulação, existem restrições de conectividade que se repetem.

Vejamos um exemplo simples de forma a consolidarmos este facto.

Exemplo 4.1: Consideremos uma instância do PCV constituída por 7 clientes, a qual

pode ser representada por um grafo com 7 nós. Como nos vamos centrar apenas nas

restrições do problema, não é necessário especificar um problema em concreto.

A existência de 7 nós implica a existência de 21 variáveis de decisão (xij) (note-se que

para um problema com n clientes, o número de variáveis de decisão é dado por 2n C ,

dado que se tratam de PCV simétricos). Dada a existência de 7 nós, temos 7 restrições

de afectação (1.1 e 2.1, respectivamente, Formulação 1 e 2) e, como já vimos, temos

apenas de nos preocupar com a existência de sub-ciclos com 3 e 4 nós. Temos um total

de 35 sub-ciclos possíveis com 3 nós e também 35 sub-ciclos possíveis com 4 nós (note-

-se que dado um problema com n nós, o número de sub-ciclos com k nós é dado por

kn C ), que podemos ver especificados na Tabela 4.3. e na Tabela 4.4, respectivamente.

∑∈∈

−≤≤⊂≥Sj,Si

ij .3n|S|3,NS,1x

{ } )3.2(ji,Nj,i,1,0x

)2.2(3n|S|3,NS,1x


xcZMin

ij

Sj,Siij

gi,Ni jg,Njgjig

ji,Nj,iijij

<∈∈

−≤≤⊂≥

∈=+

=

∑

∑ ∑

∑

∈∈

<∈ <∈

<∈


26

Portanto, segundo a Formulação 1, temos um total de 70 restrições de eliminação de

sub-ciclos necessárias para a obtenção da solução óptima do problema. Seguindo a

ordem (por coluna) apresentada na Tabela 4.3, vejamos na Tabela 4.5, as 35 restrições

de eliminação de sub-ciclos com 3 nós.

2xxx 231312 ≤++ 2xxx 561615 ≤++ 2xxx 672726 ≤++

2xxx 241412 ≤++ 2xxx 571715 ≤++ 2xxx 453534 ≤++

2xxx 251512 ≤++ 2xxx 671716 ≤++ 2xxx 463634 ≤++

2xxx 261612 ≤++ 2xxx 342423 ≤++ 2xxx 473734 ≤++

2xxx 271712 ≤++ 2xxx 352523 ≤++ 2xxx 563635 ≤++

2xxx 341413 ≤++ 2xxx 362623 ≤++ 2xxx 573735 ≤++

2xxx 351513 ≤++ 2xxx 372723 ≤++ 2xxx 673736 ≤++

2xxx 361613 ≤++ 2xxx 452524 ≤++ 2xxx 564645 ≤++

2xxx 371713 ≤++ 2xxx 462624 ≤++ 2xxx 574745 ≤++

2xxx 451514 ≤++ 2xxx 472724 ≤++ 2xxx 674746 ≤++

2xxx 461614 ≤++ 2xxx 562625 ≤++ 2xxx 675756 ≤++

2xxx 471714 ≤++ 2xxx 572725 ≤++

123 134 146 234 246 345 367

124 135 147 235 247 346 456

125 136 156 236 256 347 457

126 137 157 237 257 356 467

127 145 167 245 267 357 567

1234 1246 1345 1367 2345 2367 3456

1235 1247 1346 1456 2346 2456 3457

1236 1256 1347 1457 2347 2457 3467

1237 1257 1356 1467 2356 2467 3567

1245 1267 1357 1567 2357 2567 4567

Tabela 4.3: Sub-ciclos possíveis com 3 nós num grafo com 7 nós.

Tabela 4.4: Sub-ciclos possíveis com 4 nós num grafo com 7 nós.

Tabela 4.5: Restrições de eliminação de sub-ciclos com 3 nós.


27

Vejamos, agora, na Tabela 4.6 as 35 restrições que permitem eliminar todos os sub-

ciclos com 4 nós possíveis num grafo com 7 nós (descritos na Tabela 4.4).

3xxxxxx 342423141312 ≤+++++ 3xxxxxx 674746171614 ≤+++++

3xxxxxx 352523151312 ≤+++++ 3xxxxxx 675756171615 ≤+++++

3xxxxxx 362623161312 ≤+++++ 3xxxxxx 453534252423 ≤+++++

3xxxxxx 372723171312 ≤+++++ 3xxxxxx 463634262423 ≤+++++

3xxxxxx 452524151412 ≤+++++ 3xxxxxx 473734272423 ≤+++++

3xxxxxx 462624161412 ≤+++++ 3xxxxxx 563635262523 ≤+++++

3xxxxxx 472724171412 ≤+++++ 3xxxxxx 573735272523 ≤+++++

3xxxxxx 562625161512 ≤+++++ 3xxxxxx 673736272623 ≤+++++

3xxxxxx 572725171512 ≤+++++ 3xxxxxx 564645262524 ≤+++++

3xxxxxx 672726171612 ≤+++++ 3xxxxxx 574745272524 ≤+++++

3xxxxxx 453534151413 ≤+++++ 3xxxxxx 674746272624 ≤+++++

3xxxxxx 463634161413 ≤+++++ 3xxxxxx 675756272625 ≤+++++

3xxxxxx 473734171413 ≤+++++ 3xxxxxx 564645363534 ≤+++++

3xxxxxx 563635161513 ≤+++++ 3xxxxxx 574745373534 ≤+++++

3xxxxxx 573735171513 ≤+++++ 3xxxxxx 674746373634 ≤+++++

3xxxxxx 673736171613 ≤+++++ 3xxxxxx 675756373635 ≤+++++

3xxxxxx 564645161514 ≤+++++ 3xxxxxx 675756474645 ≤+++++

3xxxxxx 574745171514 ≤+++++

Vejamos, agora, o caso da Formulação 2.

Atentemos no primeiro sub-ciclo com 3 nós considerado na Tabela 4.3, sendo este o

sub-ciclo 123. Neste caso, temos { }3,2,1S = e { }7,6,5,4S = . Para eliminarmos o conjunto

S, segundo a Formulação 2, temos de considerar a seguinte restrição:

Tabela 4.6: Restrições de eliminação de sub-ciclos com 4 nós.

.1xxxxxxxxxxxx 373635342726252417161514 ≥+++++++++++


28

Note-se que a restrição de conectividade que obriga à eliminação de S é a mesma

restrição de conectividade que provoca a eliminação de S . Portanto, já não iremos

considerar o caso contrário, dada a sua repetição.

Vejamos, então, de forma detalhada na Tabela 4.7 todas as restrições de

conectividade necessárias segundo a Formulação 2.

{ } { }7,6,5,4S;3,2,1S ==

1xxxxxxxxxxxx 373635342726252417161514 ≥+++++++++++

{ } { }7,6,5,3S;4,2,1S ==

1xxxxxxxxxxxx 474645342726252317161513 ≥+++++++++++

{ } { }7,6,4,3S;5,2,1S ==

1xxxxxxxxxxxx 575645352726242317161413 ≥+++++++++++

{ } { }7,5,4,3S;6,2,1S ==

1xxxxxxxxxxxx 675646362725242317151413 ≥+++++++++++

{ } { }6,5,4,3S;7,2,1S ==

1xxxxxxxxxxxx 675747372625242316151413 ≥+++++++++++

{ } { }7,6,5,2S;4,3,1S ==

1xxxxxxxxxxxx 474645243736352317161512 ≥+++++++++++

{ } { }7,6,4,2S;5,3,1S ==

1xxxxxxxxxxxx 575645253736342317161412 ≥+++++++++++

{ } { }7,5,4,2S;6,3,1S ==

1xxxxxxxxxxxx 675646263735342317151412 ≥+++++++++++

{ } { }6,5,4,2S;7,3,1S ==

1xxxxxxxxxxxx 675747273635342316151412 ≥+++++++++++

{ } { }7,6,3,2S;5,4,1S ==

1xxxxxxxxxxxx 575635254746342417161312 ≥+++++++++++

{ } { }7,5,3,2S;6,4,1S ==

1xxxxxxxxxxxx 675636264745342417151312 ≥+++++++++++


29

{ } { }6,5,3,2S;7,4,1S ==

1xxxxxxxxxxxx 675737274645342416151312 ≥+++++++++++

{ } { }7,4,3,2S;6,5,1S ==

1xxxxxxxxxxxx 674636265745352517141312 ≥+++++++++++

{ } { }6,4,3,2S;7,5,1S ==

1xxxxxxxxxxxx 674737275645352516141312 ≥+++++++++++

{ } { }5,4,3,2S;7,6,1S ==

1xxxxxxxxxxxx 574737275646362615141312 ≥+++++++++++

{ } { }7,6,5,1S;4,3,2S ==

1xxxxxxxxxxxx 474645143736351327262514 ≥+++++++++++

{ } { }7,6,4,1S;5,3,2S ==

1xxxxxxxxxxxx 575645153736341327262412 ≥+++++++++++

{ } { }7,5,4,1S;6,3,2S ==

1xxxxxxxxxxxx 675646163735341327252412 ≥+++++++++++

{ } { }6,5,4,1S;7,3,2S ==

1xxxxxxxxxxxx 675747173635341326252412 ≥+++++++++++

{ } { }7,6,3,1S;5,4,2S ==

1xxxxxxxxxxxx 575635154746341427262312 ≥+++++++++++

{ } { }7,5,3,1S;6,4,2S ==

1xxxxxxxxxxxx 675636164745341427252312 ≥+++++++++++

{ } { }6,5,3,1S;7,4,2S ==

1xxxxxxxxxxxx 675737174645341426252312 ≥+++++++++++

{ } { }7,4,3,1S;6,5,2S ==

1xxxxxxxxxxxx 674636165745351527242312 ≥+++++++++++

{ } { }6,4,3,1S;7,5,2S ==

1xxxxxxxxxxxx 674737175645351526242312 ≥+++++++++++

{ } { }5,4,3,1S;7,6,2S ==

1xxxxxxxxxxxx 574737175646361625242312 ≥+++++++++++


30

{ } { }7,6,2,1S;5,4,3S ==

1xxxxxxxxxxxx 575625154746241437362313 ≥+++++++++++

{ } { }7,5,2,1S;6,4,3S ==

1xxxxxxxxxxxx 675626164745241437352313 ≥+++++++++++

{ } { }6,5,2,1S;7,4,3S ==

1xxxxxxxxxxxx 675727174645241436352313 ≥+++++++++++

{ } { }7,4,2,1S;6,5,3S ==

1xxxxxxxxxxxx 674626165745251537342313 ≥+++++++++++

{ } { }6,4,2,1S;7,5,3S ==

1xxxxxxxxxxxx 674727175645251536342313 ≥+++++++++++

{ } { }5,4,2,1S;7,6,3S ==

1xxxxxxxxxxxx 574727175646261635342313 ≥+++++++++++

{ } { }7,3,2,1S;6,5,4S ==

1xxxxxxxxxxxx 673626165735251547342414 ≥+++++++++++

{ } { }6,3,2,1S;7,5,4S ==

1xxxxxxxxxxxx 673727175635251546342414 ≥+++++++++++

{ } { }5,3,2,1S;7,6,4S ==

1xxxxxxxxxxxx 573727175636261645342414 ≥+++++++++++

{ } { }4,3,2,1S;7,6,5S ==

1xxxxxxxxxxxx 473727174636261645352515 ≥+++++++++++

Dada a existência de repetição dentro do conjunto das restrições de conectividade,

podemos afirmar que, comparativamente às restrições de eliminação de sub-ciclos, estas

são em menor número, em particular metade. Por outro lado, apesar do menor número

de restrições, verificamos que cada restrição de conectividade implica um número

significativamente maior de ocorrências, aumentando a complexidade em cada restrição.

Já foram efectuados vários estudos no sentido de provar a existência de diferenças

entre estes dois tipos de restrições, não se chegando, no entanto, à conclusão sobre qual

Tabela 4.7: Restrições de conectividade para sub-ciclos com 3 nós.


31

seria o mais eficiente. Em Barreto et al [3] podemos encontrar um estudo prático, onde

são resolvidos vários problemas recorrendo aos dois tipos de restrições e,

posteriormente, é feita uma comparação. Na maior parte dos casos, a solução obtida é

exactamente a mesma, sendo, contudo verificadas diferenças notórias ao nível do tempo

de resolução e do número de iterações para a obtenção da solução óptima. No entanto,

essas diferenças vão-se alternando consoante os problemas, não levando à

predominância de um tipo de restrição sobre o outro.

Assim sendo, a nível prático e experimental, existem diferenças entre as restrições de

eliminação de sub-ciclos e as restrições de conectividade, não estando, no entanto,

provado qual dos dois tipos de restrições é o mais eficiente.

Apesar de, neste trabalho, nos centrarmos no PCV simétrico, é importante referir a

formulação criada por Miller, Tucker e Zemlin [13], que deram um grande contributo nesta

área, desenvolvendo uma formulação para o PCV orientado. Os autores partiram de um

problema mais geral (tendo como uma possível instância o PCV usual). Na sua

generalização, existem n cidades a serem visitadas, indexadas de 1,…,n, sendo a cidade

de partida indexada por 0. Durante o seu percurso, o caixeiro viajante deve regressar

exactamente t vezes à cidade inicial, incluindo o seu último regresso. O viajante deve

visitar no máximo p cidades no seu percurso.

Notemos, assim, que para 1t = e np ≥ , estamos perante o PCV usual, mas para grafos

orientados. A formulação pode ser formalizada da seguinte forma:

Formulação 3 (para PCV não simétricos):

)4.3(eirasint0x

)3.3(nji1,1pxpuu

)2.3(Ni,1x

)1.3(Nj,1x:asujeito

xcZMin

ij

ijji

n

ij0j

ij

n

ji0i

ij

iji0 nj

ij

≥

≤≠≤−≤+−

∈=

∈=

=

∑

∑

∑∑

≠=

≠=

≠≤ ≤


32

onde ijc representa a distância entre as cidades i e j; p representa o número mínimo de

cidades que o caixeiro-viajante tem de visitar no seu percurso ( np ≥ );

)Ni(ui ∈ representam números reais arbitrários. Note-se que as restrições (3.1) e (3.2)

obrigam a que as variáveis ijx tomem o valor 0 ou 1.

Até aqui, apresentámos três diferentes tipos de formalização do PCV, sendo a última

do PCV não simétrico, sobre o qual, como já referimos, não vamos dirigir o nosso estudo.

Um dos objectivos deste trabalho é o de avaliar e analisar as restrições do PCV, de forma

a estudar a interacção entre estas, como actuam na resolução do problema e qual a sua

importância na obtenção da solução óptima. Como tal, a partir deste momento, vamos

focar o nosso estudo na Formulação 1, na qual surgem as restrições de eliminação de

sub-ciclos, pois parece-nos ser a formulação mais simples, dado que cada restrição de

eliminação de sub-ciclos envolve um número menor de variáveis do que as restrições de

conectividade. Analisemos então com mais detalhe o funcionamento da Formulação 1.

Assim sendo, suponha-se que a aplicação da Formulação 1 ao grafo G, relaxando as

restrições de afectação, conduziu ao resultado demonstrado na Figura 4.8, onde

podemos observar dois possíveis sub-ciclos em G

Notemos que a eliminação do sub-ciclo A, constituído por 3 nós, vai provocar a

eliminação do sub-ciclo B, constituído por 8 nós, dado que A terá de absorver, no mínimo,

mais 1 nó, pois não pode perder algum dos que já possui dado que não é permitida a

formação de sub-ciclos com 2 nós.

Deste modo, a eliminação de sub-ciclos com 3 nós gera automaticamente a

eliminação de sub-ciclos com 8 nós (Figura 4.9).

Figura 4.8: Exemplo de dois sub-ciclos num grafo.

A

B


33

Consideremos então o caso de A apenas ter absorvido um nó. Vamos obter um novo

sub-ciclo agora com 4 nós. Procedendo deste modo, ao eliminarmos qualquer sub-ciclo

com 4 nós, eliminamos automaticamente a possibilidade de existência de sub-ciclos com

7 nós, dado que estes terão de absorver pelo menos mais 1 dos nós do grafo (não pode

perder algum dos nós que já possuía dado que a existência de sub-ciclos com 3 nós já foi

restringida).

Esquematizando este procedimento, temos:

Eliminação de sub-ciclos Eliminação de sub-ciclos

Com 3 nós Com 8 (=11-3) nós






Com k nós Com n-k nós

Neste caso, em que temos um grafo com 11 nós, verificamos que, para garantir a

inexistência de sub-ciclos, necessitamos apenas de adicionar as restrições de eliminação

de sub-ciclos com 3, 4 e 5 nós, pois todos os outros casos já estão automaticamente

eliminados com a inclusão destas restrições. Tal facto, reduz drasticamente o número de

restrições a considerar no problema.

Este estudo leva-nos assim ao seguinte resultado:

Figura 4.9: Ilustração da eliminação de sub-ciclos num grafo.

A

B


34

Teorema (Barreto, 2004):

Considere-se o Problema do Caixeiro Viajante como foi descrito na Formulação 1. A

não existência de sub-ciclos em qualquer sub-conjunto S:

≤≤⊂

2n

|S|3,NS garante a

não existência de sub-ciclos em N.

Prova (Barreto [1]):

Como já referido, as restrições de integralidade e as restrições de afectação (que

obrigam a que todos os vértices tenham grau 2), não permitem a formação de sub-ciclos

com menos de 3 nós, o que justifica o facto de se considerar S: .|S|3,NS ≤⊂

Pretendemos agora provar que :

Nemciclossub2n

|S|,NS:Semciclossub −∃⇒

≤⊂−∃

Ou, de forma equivalente,

>⊂−∃⇒

≤⊂−∃

2n

|T|,NT:Temciclossub2n

|S|,NS:Semciclossub

Usando a lei da conversão, é ainda equivalente a,

≤⊂−∃⇒

>⊂−∃

2n

|S|,NS:Semciclossub2n

|T|,NT:Temciclossub .

A prova desta última implicação é equivalente à prova da primeira.

Consideremos, então, a existência de um sub-ciclo em T:

>⊂

2n

|T|,NT . Devido às

restrições de afectação e integralidade, os nós de TNS −= têm obrigatoriamente de se

agrupar em sub-ciclos (um ou mais). Assim, como

≤∧⊂

2n

|S|NS , resulta que a

implicação é verdadeira.


35

Como consequência, podemos reescrever formalmente o PCV simétrico da seguinte

forma:

Formulação 4:

Este teorema proporciona assim uma redução efectiva do número de restrições do

PCV relativamente à Formulação 1. Vejamos um exemplo para o constatarmos de forma

mais explícita.

Consideremos, por exemplo, um PCV com 15 clientes. Assim, segundo a Formulação

1 do PCV, as restrições de eliminação de sub-ciclos serão da forma:

O número total deste tipo de restrições encontra-se detalhado na Tabela 4.8.

{ } )3.4(ji,Nj,i,1,0x

)2.4(2n

|S|3,NS,1|S|x


xcZMin

ij

ji,Sj,iij

gi,Ni jg,Njgjig

ji,Nj,iijij

<∈∈

≤≤⊂−≤

∈=+

=

∑

∑ ∑

∑

<∈

<∈ <∈

<∈

∑<∈

≤≤⊂−≤ji,Sj,i

ij 12|S|3,NS,1|S|x


36

Observamos que, apesar de não termos um número muito elevado de nós, apenas 15,

teríamos de considerar, pela Formulação 1, um total de 32 526 restrições de eliminação

de sub-ciclos. Este é já um número bastante elevado, o que torna a resolução do

problema bastante pesada computacionalmente.

Por outro lado, considerando a Formulação 4, resultante do teorema anterior, as

restrições de eliminação de sub-ciclos são da forma

Segundo esta formulação, temos apenas de considerar as restrições de eliminação de

sub-ciclos constituídos desde 3 a 7 nós, o que equivale a exactamente metade do

número de restrições a considerar na Formulação 1, ou seja, 16 263.

Este resultado, reduz, de forma bastante significativa o número necessário de

restrições de eliminação de sub-ciclos no PCV simples.

Número de nós Número de restrições de

eliminação de sub-ciclos

3 455C315 =

4 1365C415 =

5 3003C515 =

6 5005C615 =

7 6435C715 =

8 6435C815 =

9 5005C915 =

10 3003C1015 =

11 1365C1115 =

12 455C1215 =

Total 32526

∑<∈

≤≤⊂−≤ji,Sj,i

ij 7|S|3,NS,1|S|x

Tabela 4.8: Número de restrições de eliminação de sub-ciclos.


37

5. ESTUDO E RESOLUÇÃO ITERATIVA DE VÁRIAS INSTÂNCIAS DO PCV

Vejamos, agora, a resolução detalhada de alguns exemplos do PCV, recorrendo à

Formulação 4, dado que se trata da formalização apresentada que exige, à partida, uma

menor complexidade. Nos exemplos seguintes, o peso de cada aresta corresponde à

distância euclidiana entre os seus extremos.

Na resolução de todas as instâncias do PCV apresentadas no decorrer deste trabalho

foi utilizado um computador do tipo PC20 e recorreu-se ao software Xpress-IVE, versão

1.18.01, que utiliza o Xpress-Mosel 2.0.0 e o Xpress-Optimizer versão 18.00.01.

Exemplo 5.1: Consideremos a instância 1 do PCV, que se encontra no Anexo 1,

constituída por 6 clientes.

Como já vimos, a existência de 6 clientes implica a existência de 15 variáveis de

decisão (xij), de 6 restrições de afectação (4.1) e a necessidade de inclusão das

restrições de eliminação de sub-ciclos com 3 nós, o que corresponde a um total de 20

restrições do tipo (4.2). Então, no total, para garantir a obtenção da solução óptima do

problema necessitamos de 26 restrições (excluindo as restrições de binariedade das

variáveis de decisão).

A solução do problema com as 26 restrições referidas é a seguinte (Figura 5.1):

20 Modelo SONY VAIO VGN-C1Z/B. Processador: INTEL® Core™ 2 Duo T5500, 1.66 GHz. Memória RAM: 1 GB.

Figura 5.1: Solução óptima da instância do PCV.


38

Vejamos agora uma resolução sequencial do mesmo problema. Comecemos por

resolver o problema incluindo apenas as restrições de afectação. A solução obtida é

composta por dois sub-ciclos, ambos com 3 nós (Figura 5.2).

Para impedir a formação dos dois sub-ciclos apresentados, basta-nos uma restrição

que imponha que o número de ligações permitidas entre os clientes 3, 4 e 6 seja no

máximo duas, pois tal implicará que uma das três ligações usadas entre eles seja

quebrada, tendo de se ligar a um dos clientes do outro sub-ciclo, o que automaticamente

também o desfaz. Note-se que poderíamos ter feito o mesmo raciocínio partindo do sub-

ciclo formado pelos clientes 1, 2 e 5. Com apenas esta restrição, além das restrições de

afectação obtemos a solução óptima do problema.

É importante salientar que não estava garantido à partida que o acrescento desta

restrição resultaria imediatamente na solução óptima, pois apesar de eliminar os dois

sub-ciclos representados (Figura 5.2), poderia originar a criação de novos sub-ciclos.

De uma forma geral, a ideia de resolução sequencial deste tipo de problemas, pode

resumir-se em três passos:

- Numa primeira iteração, resolve-se um sub-problema obtido do problema inicial,

mas apenas com as restrições de afectação;

- Numa segunda fase, as restrições omitidas na fase anterior, são acrescentadas

à medida que forem sendo corrompidas e o problema é novamente optimizado;

- O processo continua até que não existam mais restrições corrompidas.

Vejamos agora um exemplo de um PCV com 8 clientes.

Figura 5.2: Solução da instância do PCV obtida apenas com as restrições de afectação.


39

Exemplo 5.2: Consideremos a instância 7 do PCV, que se encontra no Anexo 1,

constituída por 8 clientes.

Como temos 8 clientes, temos um total de 28 variáveis de decisão. Na Tabela 5.1,

temos o número de restrições necessário para obter a solução óptima logo na primeira

iteração.

Restrições Quantidade

Afectação 8

Eliminação de sub-ciclos com 3 nós 56

Eliminação de sub-ciclos com 4 nós 70

Total 134

De facto, com apenas 8 clientes, já temos um número considerável de restrições a ter

em conta para a obtenção da solução óptima do problema.

Vejamos, de forma análoga ao exemplo anterior, se é possível resolver o problema

recorrendo a um número menor de restrições. Ou seja, se é possível obter a solução

óptima do problema original partindo de um problema análogo, considerando apenas um

subconjunto de restrições.

Incluindo apenas as oito restrições de afectação, a solução do problema é constituída

por dois sub-ciclos de 4 nós (Figura 5.3).

Seguindo o raciocínio do exemplo anterior para a eliminação de sub-ciclos, basta-nos

acrescentar uma restrição que imponha que o número máximo de ligações existentes

entre os clientes 1, 2, 3 e 6 (ou 4, 5, 7 e 8) seja três.

Tabela 5.1:Número de restrições da instância do PCV.



40

No entanto, com o acrescento desta nova restrição e resolvendo o problema

resultante, obtemos novamente dois sub-ciclos, um de 3 nós e um de 5 nós (Figura 5.4).

Acrescentemos, então, a restrição que obriga a que pelo menos uma das arestas do

sub-ciclo de 3 nós seja quebrada, ligando-se ao sub-ciclo de 5 nós.

Após nova restrição, voltamos a obter um sub-ciclo com 3 nós e um sub-ciclo com 5

nós (Figura 5.5).

Procedendo do mesmo modo que no passo anterior, isto é, acrescentando a restrição

que obriga à eliminação do sub-ciclo com 3 nós, obtemos a solução óptima do problema

(Figura 5.6).

Figura 5.6: Solução óptima da instância do PCV.

Figura 5.4: Solução da instância do PCV obtida com a adição da nova restrição.

Figura 5.5: Solução da instância do PCV obtida com a adição das 2 novas restrições.


41

Foram, então, necessárias quatro iterações para a obtenção da solução óptima do

problema, requerendo um total de onze restrições, isto é, três novas restrições além das

restrições de afectação. Assim, tal como no caso anterior, verificámos que é possível

obter a solução óptima com um número consideravelmente menor de restrições do que

aquelas que seriam necessárias à partida.

Note-se que, por exemplo, no caso de termos um PCV com 10 clientes, teríamos um

total de 582 restrições de eliminação de sub-ciclos de forma a garantir a obtenção da

solução óptima. De facto, verificamos que um pequeno aumento no número de clientes

gera um crescimento exponencial do número das restrições a considerar inicialmente.

Antes de partirmos para um estudo mais intensivo de vários problemas deste tipo,

vamos resolver o problema que serviu de introdução a este trabalho, onde o Caixeiro

Viajante tinha de visitar as seis cidades mencionadas da Península Ibérica (Capítulo 3,

página 13).

Assim tal como no exemplo 5.1, este é um problema com 6 nós, que correspondem às

seis cidades em causa e 15 variáveis de decisão que correspondem às ligações

existentes entre as mesmas. Resolvendo o problema apenas com as restrições de

afectação, a solução obtida é constituída por dois sub-ciclos com 3 nós (Figura 5.7).


306

208

422

133

277

173


42

Acrescentando a restrição que impossibilita a formação do sub-ciclo constituído pelas

cidades de Lisboa, Évora e Faro, obtemos a solução óptima:

Verificamos, assim, que a solução obtida pelos dois métodos heurísticos corresponde

à solução óptima do problema, onde o Caixeiro Viajante deve seguir o percurso ilustrado,

percorrendo um total de 1732 Km.

Seguidamente, serão apresentados e analisados os resultados do estudo e resolução,

de forma iterativa, de vários exemplos de PCVs, constituídos por um número variável de

clientes. Para cada exemplo é apresentado o número de variáveis de decisão, assim

como o número de restrições consideradas segundo a Formulação 4 do PCV. Seguindo

um procedimento análogo aos exemplos apresentados, começou-se por resolver o

problema apenas com as restrições de afectação e anotar o número de sub-ciclos iniciais

da respectiva solução.

Posteriormente, e de forma sequencial, foram-se acrescentando restrições com o

objectivo de eliminar os sub-ciclos que se iam formando ao longo da resolução.

Figura 5.8: Solução óptima da instância do PCV

133

277

306

208

85

723


43

Podemos, assim, observar e comparar o número de restrições necessário, para a

obtenção da solução óptima do respectivo problema, segundo a resolução feita neste

estudo e a Formulação 4 do PCV. Essa comparação pode ser observada na última

coluna da Tabela 5.2, onde constatamos que, mesmo para problemas constituídos por

apenas seis clientes, apenas aproximadamente 26% das restrições são usadas e, à

medida que o número de clientes vai aumentando, a percentagem de restrições usadas

na obtenção na solução óptima vai diminuindo drasticamente. Note-se que, em

problemas constituídos por 13 clientes (o que transportando para a realidade e

associando a rotas de transportes, não é um número muito elevado), temos um total de

4017 restrições, sendo este já um número bastante considerável. Para este número de

clientes, nos exemplos estudados, apenas aproximadamente 0,5% das restrições foram

necessárias para a obtenção da solução óptima do problema.

Após esta análise, dado que foi possível obter a solução óptima dos problemas

originais resolvendo problemas análogos em que um elevado número de restrições foi

retirado, é natural criar a seguinte conjectura:

CONJECTURA: No PCV, grande parte das restrições de eliminação de sub-ciclos da

Formulação 4 são, do ponto de vista prático, desnecessárias.

O grande problema que se coloca é como determinar, à priori, perante um PCV, qual o

número de restrições suficientes para resolver um problema de optimização deste tipo, e

posteriormente, quais as restrições indispensáveis de entre o grande conjunto de

restrições considerado inicialmente no estudo do PCV.

A resposta a esta questão seria um grande avanço neste estudo, dado que permitiria

tornar muito mais rápida e eficiente a resolução deste tipo de problemas

computacionalmente. No entanto, esta é uma questão que ainda se encontra em aberto.


44


45

6. RELAÇÃO E CONDICIONAMENTO ENTRE RESTRIÇÕES DE ELIMINAÇÃO DE

SUB-CICLOS

Dado todo o estudo efectuado até esta fase do trabalho, torna-se claro, que muitas

das restrições de eliminação de sub-ciclos são, do ponto de vista prático, provavelmente

redundantes, isto é, não são efectivamente necessárias para obter a solução óptima do

problema. Uma das particularidades que nos poderá dar alguma indicação sobre quais as

restrições realmente necessárias para a obtenção da solução óptima será, por exemplo,

a característica da matriz de restrições.

6.1. ANÁLISE DA MATRIZ DE RESTRIÇÕES DO PCV

A matriz de restrições do PCV é inicialmente constituída por m linhas, que

correspondem às restrições de afectação e às restrições de eliminação de sub-ciclos, e

por p colunas, que correspondem às variáveis de decisão. Note-se que esta é uma matriz

que contém apenas entradas com valor um, no caso de haver ligação entre os dois

clientes em questão, e valor zero, caso contrário.

É importante realçar que a constituição desta matriz não depende das coordenadas

dos clientes em causa nas várias instâncias do PCV. Isto é, a matriz de restrições do

PCV não depende dos custos associados a cada uma das ligações.

Exemplo 6.1: Consideremos, novamente, uma instância do PCV constituída por 6

clientes. De forma a tornar clara e simples a construção da matriz de restrições do

problema, observemos na Tabela 6.1, as restrições de afectação e as restrições de

eliminação de sub-ciclos necessárias para a obtenção da solução óptima, segundo a

Formulação 4.


46

Assim, para uma instância com 6 clientes, temos as seguintes restrições:

2xxxxx 1615141312 =++++ 2xxx 451514 ≤++

2xxxxx 2625242312 =++++ 2xxx 461614 ≤++

2xxxxx 3635342313 =++++ 2xxx 561615 ≤++

2xxxxx 5645342414 =++++ 2xxx 342423 ≤++

2xxxxx 5645352515 =++++ 2xxx 352523 ≤++

2xxxxx 5646362616 =++++ 2xxx 362623 ≤++

2xxx 231312 ≤++ 2xxx 452524 ≤++

2xxx 241412 ≤++ 2xxx 462624 ≤++

2xxx 251512 ≤++ 2xxx 562625 ≤++

2xxx 261612 ≤++ 2xxx 453534 ≤++

2xxx 341413 ≤++ 2xxx 463634 ≤++

2xxx 351513 ≤++ 2xxx 563635 ≤++

2xxx 361613 ≤++ 2xxx 564645 ≤++

Então, com base na Tabela 6.1, vamos construir a matriz de restrições, A, para o

problema. A matriz21 A é composta por 26 linhas (número total de restrições) e por 15

colunas (número de variáveis de decisão). Tendo em conta a Tabela 6.1 e a definição

acima referida, a matriz de restrições de um PCV com 6 clientes é a seguinte:

21 Considera-se um problema possível com soluções admissíveis e, consequentemente, com um sistema de restrições compatível. Assim sendo, a característica da matriz completa é igual à característica da matriz do sistema e podemos assim desprezar os termos independentes.

Tabela 6.1: Restrições de um PCV com 6 clientes.


47

12 13 14 15 16 23 24 25 26 34 35 36 45 46 56

Em termos matemáticos, a característica dá-nos informação acerca do número de

linhas (ou colunas) linearmente independentes. Vamos, deste modo, analisar se o cálculo

da característica22 da matriz nos fornece algum tipo de informação que indicie a

existência de redundância entre as restrições de eliminação de sub-ciclos.

22

É necessário ter em conta que, antes de passar ao cálculo da característica da matriz de restrições, é necessário acrescentar a todas as desigualdades (restrições de eliminação de sub- -ciclos) as respectivas variáveis de folga de forma a transformá-las em igualdades.

Figura 6.1: Matriz de restrições de um PCV com 6 clientes.

=

1 1 1 0 0 0 0 0 0 0 0 00 0 0

1 0 0 1 1 0 0 0 0 0 0 0 0 0 0

0 1 0 1 0 1 0 0 0 0 0 00 0 0

0 0 1 0 1 1 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 1 1 0 0 0 0 0 0 0

0 1 0 0 0 0 1 0 1 0 0 0 0 0 0

0 0 1 0 0 0 0 1 1 0 0 0 0 0 0

0 0 0 1 0 0 1 0 0 1 0 0 0 0 0

0 0 0 0 1 0 0 1 0 1 0 0 0 0 0

0 0 0 0 0 1 0 0 1 1 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 1 1 0 0 0

0 1 0 0 0 0 0 0 0 0 1 0 1 00

0 0 1 0 0 0 0 0 0 0 0 1 1 0 0

0 0 0 10 0 0 0 0 0 1 0 0 1 0

0 0 00 1 0 0 0 0 0 0 1 0 1 0

0 0 0 0 0 1 0 0 0 00 0 1 1 0

0 0 0 0 0 0 1 0 0 0 1 0 0 0 1

0 0 0 0 0 00 1 0 0 0 1 0 0 1

0 0 0 0 0 0 0 0 1 0 0 0 1 0 1

0 0 0 0 0 0 0 0 0 1 0 00 1 1

1 1 0 1 0 0 1 0 0 0 1 0 0 0 0

1 0 1 0 1 0 0 1 0 0 0 1 0 0 0

0 1 1 0 0 1 0 0 1 00 0 1 0 0

0 0 01 1 1 0 0 0 1 0 0 0 1 0

0 0 0 0 0 0 1 1 1 1 0 0 00 1

0 0 0 0 00 0 0 0 0 1 1 1 1 1

A

Restrições

de afectação

Restrições de

eliminação de

sub-ciclos com 3 nós


48

Exemplo 6.2: Considerando a matriz de restrições apresentada no exemplo 6.1., vamos

proceder ao cálculo da sua característica. No entanto, note-se que das 26 restrições

apresentadas, apenas 6 são equações, logo temos que transformar as 20 restrições de

eliminação de sub-ciclos em equações através do acrescento de variáveis de folga.

Procedendo desta forma, passamos a ter a restrições:

2xxxxx 1615141312 =++++ 2yxxx 8451514 =+++

2xxxxx 2625242312 =++++ 2yxxx 9461614 =+++

2xxxxx 3635342313 =++++ 2yxxx 10561615 =+++

2xxxxx 5645342414 =++++ 2yxxx 11342423 =+++

2xxxxx 5645352515 =++++ 2yxxx 12352523 =+++

2xxxxx 5646362616 =++++ 2yxxx 13362623 =+++

2yxxx 1231312 =+++ 2yxxx 14452524 =+++

2yxxx 2241412 =+++ 2yxxx 15462624 =+++

2yxxx 3251512 =+++ 2yxxx 16562625 =+++

2yxxx 4261612 =+++ 2yxxx 17453534 =+++

2yxxx 5341413 =+++ 2yxxx 18463634 =+++

2yxxx 6351513 =+++ 2yxxx 19563635 =+++

2yxxx 7361613 =+++ 2yxxx 20564645 =+++

Assim, vamos ter uma matriz com 26 linhas mas com 15+20=35 colunas (uma nova

coluna por cada variável de folga acrescentada a cada inequação).

Tabela 6.2: Restrições do PCV com o acrescento das variáveis de folga.


49

A matriz resultante é a seguinte:

A característica23 desta matriz é de 26. Assim, sendo a característica igual ao número

de restrições não podemos, por esta via, concluir sobre a eventual existência de

restrições redundantes. Pelo contrário, confirma-se a total interligação entre todas as

restrições.

23 A característica foi calculada através do programa MatLab, versão 2006B.

=

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0

0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1

00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1

A1

Figura 6.2: Matriz de restrições do PCV com o acrescento das variáveis de folga.


50

Vejamos, então, o que acontece com a característica da matriz de restrições para

PCVs com um número variável de clientes. Na Tabela 6.3, podemos observar as

características da matriz de restrições de alguns PCVs constituídos desde 4 até 10

clientes.

Nota: Nas somas colocadas entre parênteses na terceira coluna, a primeira parcela

representa o número de colunas inicial (variáveis de decisão), e a segunda parcela

representa o número de variáveis de folga acrescentadas.

Observando a Tabela 6.3, é natural conjecturar que o número de restrições

linearmente independentes num PCV com n clientes é igual ao número de restrições, que

correspondem às linhas da matriz. Assim, como a característica da matriz é igual ao

número de restrições, concluímos que a característica da matriz de restrições não nos

trará informação adicional sobre a existência de restrições redundantes, pelo contrário,

confirma a total independência linear entre as restrições.

Esta conclusão, conjugada com a conjectura apresentada no capítulo 5, gera um

paradoxo. Por um lado, teoricamente, todas as restrições são indispensáveis, por outro,

na prática, apenas uma pequena parte é necessária para a resolução. Esta aparente

contradição indicia que podem existir relações e propriedades ainda desconhecidas neste

tipo de sistemas.

Nº de clientes Nº de restrições

(linhas)

Nº de variáveis

(colunas)

Característica

da matriz

4 4 6 4

5 5 10 5

6 26 35 (15+20) 26

7 42 56 (21+35) 42

8 134 154 (28+126) 134

9 219 246 (36+210) 219

10 592 627 (45+582) 592

Tabela 6.3: Característica da matriz de restrições de alguns PCVs.


51

6.2. INTERLIGAÇÃO DAS RESTRIÇÕES DE ELIMINAÇÃO DE SUB-CICLOS

Focando novamente a atenção na conjectura apresentada no capítulo 5, será legítimo

supor que a eliminação de sub-ciclos com um determinado número de nós poderá

desencadear a eliminação de outros sub-ciclos. Como tal, vamos fazer um estudo nesse

sentido, novamente com o intuito de comprovar a existência de interligação entre as

várias restrições de eliminação de sub-ciclos.

É importante realçar que nesta análise, apenas nos basearemos em grafos com 4 e 5

nós, tendo sempre em conta, como já foi referido, que não seria necessária a inclusão

deste tipo de restrições para a obtenção da solução óptima. No entanto, o uso de grafos

com um número reduzido de nós permite uma melhor visualização e consequente

compreensão do problema.

Vamos começar por analisar num grafo com 4 nós, de que forma as restrições de

eliminação de sub-ciclos com 4 nós condicionam a existência de sub-ciclos com 3 nós,

isto é, pretendemos determinar em que medida a existência de sub-ciclos com 3 nós na

solução do problema, é influenciada quando eliminamos todos os sub-ciclos com 4 nós.

Seguidamente, será feito um raciocínio análogo num grafo com 5 nós.

Por fim, iremos estudar também, num grafo de 5 nós, qual o grau de impedimento da

formação de sub-ciclos com 3 e 4 nós, quando acrescentamos a restrição de eliminação

de sub-ciclos com 5 nós.


52

Esquematizando este raciocínio, de forma a torná-lo mais claro, pretendemos

completar o esquema da Figura 6.3 com a correspondente avaliação quantificada.

GRAFO COM 4 NÓS GRAFO COM 5 NÓS

Figura 6.3: Esquema representativo do estudo da interligação de restrições.

6.2.1. INFLUÊNCIA DAS RESTRIÇÕES DE ELIMINAÇÃO DE SUB-CICLOS COM 4 NÓS NA

ELIMINAÇÃO DE SUB-CICLOS COM 3 NÓS

Consideremos um grafo completo com 4 nós, ou seja, um grafo simples em que todos

os nós estão ligados. Deste modo, temos 4 nós e 6 arestas, como podemos ver na Figura

6.4 .

Figura 6.4: Grafo completo com 4 nós.

Eliminação de


Eliminação de


Eliminação de


Eliminação de


Eliminação de


? % ? %

? %

? %


53

Neste grafo, é possível formar quatro sub-ciclos com 3 nós ( 34 C ): (1,2,3), (1,2,4);

(1,3,4) e (2,3,4) (Figura 6.5);

e três sub-ciclos com 4 nós: (1,2,3,4), (1,3,2,4) e (1,2,4,3) (Figura 6.6).

Para impedir a formação dos 3 sub-ciclos com 4 nós, basta acrescentar uma restrição,

dado que todos os sub-ciclos são formados pelos mesmos nós. A restrição é a seguinte:

)1(.3xxxxxx 342423141312 ≤+++++

Analise-se com mais detalhe como actua esta restrição. Temos 6 arestas

intervenientes, das quais podem ser escolhidas, no máximo, 3. Logo, existem 20C36 =

formas distintas de actuar nessa escolha, considerando a permanência de 3 arestas.

Iremos sempre considerar o caso em que permanecem o número máximo de arestas

possíveis em cada restrição, dado que, para os casos em que tal não acontece, menor é

a probabilidade de formação de sub-ciclos, ou seja, nos casos em que duas, uma, ou

mesmo zero arestas integram a solução, menor é a probabilidade de se formarem sub-

ciclos no grafo. Vamos, assim, centrar o nosso estudo na análise do pior caso.

Figura 6.5: Sub-ciclos possíveis com 3 nós.

Figura 6.6: Sub-ciclos possíveis com 4 nós.


54

Na Tabela 6.4, podemos observar todas essas possibilidades.

x12 x13 x14 x23 x24 x34 Resultado

1 1 1 XX 1 1 1 (1,2,3) 1 1 1 X 1 1 1 X 1 1 1 X 1 1 1 (1,2,4) 1 1 1 X 1 1 1 XX 1 1 1 X 1 1 1 X 1 1 1 X 1 1 1 X 1 1 1 (1,3,4) 1 1 1 X 1 1 1 XX 1 1 1 X 1 1 1 X 1 1 1 X 1 1 1 XX 1 1 1 (2,3,4)

Notação: XX - existe um vértice com grau superior a 2;

X - o caminho não fecha, não formando assim um ciclo.

É fundamental ter em conta que toda esta análise se enquadra no estudo do PCV,

logo é condição imposta pelas restrições de afectação que todos os nós do grafo tenham

grau 2. Como tal, das 20 escolhas possíveis, 4 implicam a existência de nós com grau

superior a 2 (escolhas assinaladas com XX na Tabela 6.4). Assim, passamos a ter

apenas um espaço de resultados composto por 16 escolhas distintas. No entanto, note-

se que existem outros casos (nomeadamente, os que não formam sub-ciclos com 3 nós)

em que existem nós com grau 1, isto é, não satisfazem as restrições de afectação.

Contudo, como este é um estudo teórico, não vamos excluir estas opções. Deste modo,

vamos considerar como escolhas admissíveis, todas aquelas que não implicam a

existência de nós com grau superior a 2.

Tabela 6.4: Formas distintas de satisfazer, ao máximo, a restrição (1).


55

Portanto, das 16 escolhas admissíveis neste caso, existem 4 que geram a formação

de sub-ciclos com 3 nós, como podemos ver assinalado na Tabela 6.4. Assim, temos 12

possibilidades distintas que não geram a formação de sub-ciclos com 3 nós e que

satisfazem as condições impostas na formulação do PCV.

Deste modo, considerando as ocorrências com igual probabilidade, temos que, ao

eliminarmos a existência de sub-ciclos com 4 nós, existem 75% (12/16) de probabilidade

de serem também eliminados os sub-ciclos com 3 nós.

Façamos agora um raciocínio análogo para um grafo completo com 5 nós. Neste caso,

temos 5 possibilidades distintas de formação de subconjuntos com 4 nós ( 45 C ). Como

vimos no exemplo anterior, cada subconjunto com 4 nós, pode originar 3 sub-ciclos

distintos, no entanto, basta uma restrição para impedir a sua formação. As respectivas

restrições podem ser observadas na Tabela 6.5.

Subconjuntos com 4 nós Restrição de eliminação dos sub-

ciclos possíveis

1234 )1(3xxxxxx 342423141312 ≤+++++

1235 )2(3xxxxxx 352523151312 ≤+++++

1245 )3(3xxxxxx 452524151412 ≤+++++

1345 )4(3xxxxxx 453534151413 ≤+++++

2345 )5(3xxxxxx 453534252423 ≤+++++

Como vimos, para cada restrição apresentada na Tabela 6.5, existem 6 arestas

intervenientes, das quais podemos seleccionar 3, no máximo, o que origina as 20

possibilidades diferentes de escolha, já referidas. Note-se que a primeira restrição é igual

à apresentada e já analisada no caso anterior (Tabela 6.4).

Vamos, então, analisar as possibilidades em cada uma das restantes restrições

apresentadas.

Tabela 6.5: Restrições de eliminação de sub-ciclos com 4 nós num grafo com 5 nós.


56








57








58

Verificamos, através da análise pormenorizada das Tabelas 6.4, 6.6, 6.7, 6.8 e 6.9

que, das 16 escolhas admissíveis em cada uma das respectivas restrições, 12 não

possibilitam a formação de sub-ciclos com 3 nós e satisfazem as condições impostas,

como já havia sido concluído no caso anterior. Deste modo, considerando o sistema

composto pelas 5 restrições apresentadas, vamos ter 60 escolhas admissíveis que não

geram sub-ciclos com 3 nós. Assim, num grafo com 5 nós, ao eliminarmos os sub-ciclos

com 4 nós, temos novamente 75% (60/80) de probabilidade de eliminar os sub-ciclos com

3 nós, tal como acontecia no caso de um grafo com 4 nós.

6.2.2. INFLUÊNCIA DAS RESTRIÇÕES DE ELIMINAÇÃO DE SUB-CICLOS COM 5 NÓS NA

ELIMINAÇÃO DE SUB-CICLOS COM 3 E 4 NÓS

Analogamente ao estudo anterior, façamos agora uma análise para a eliminação de

sub-ciclos com 5 nós, de forma a termos alguma informação acerca do seu impacto na

eliminação de sub-ciclos com 3 e 4 nós.

Consideremos, então, um grafo completo com 5 nós.

Para eliminarmos todos os sub-ciclos possíveis com 5 nós neste grafo (Figura 6.7),

basta-nos considerar a seguinte restrição

Temos um total de 10 arestas intervenientes na restrição, das quais podemos escolher,

no máximo 4, logo teremos 210C410 = formas distintas de fazer essa escolha.

Figura 6.7: Grafo completo com 5 nós.

)6(.4xxxxxxxxxx 45353425242315141312 ≤+++++++++

1

2

3

4 5


59

Com base na Tabela A.2.1 do Anexo 2, chegamos à conclusão que existem 126

escolhas que implicam a existência de nós com grau superior a 2, impossibilitadas à

partida pelas restrições de afectação, logo passamos a ter um total de 84 escolhas

admissíveis. Dessas, temos o seguinte:

Possibilidades Número

Não permitem a formação de sub-ciclos 59

Permitem a formação de sub-ciclos com 3 nós 10

Permitem a formação de sub-ciclos com 4 nós 15

Total 84

Atendendo à Tabela 6.10, observamos que, ao eliminarmos os sub-ciclos com 5 nós

no grafo, temos aproximadamente 88% (74/84) de probabilidade de eliminar sub-ciclos

com 3 nós e aproximadamente 82% (69/84) de probabilidade de eliminar sub-ciclos com

4 nós.

Em forma de resumo, com base na análise efectuada, estamos em condições de

completar o esquema (Figura 6.8), de forma a consolidarmos toda a informação obtida.

GRAFO COM 4 NÓS GRAFO COM 5 NÓS

Tabela 6.10: Análise das escolhas admissíveis da restrição (6).

Eliminação de


Eliminação de


Eliminação de


Eliminação de


Eliminação de


75 % 82 %

75 %

88 %

Figura 6.8: Esquema representativo do estudo efectuado.


60

Os elevados valores percentuais obtidos neste estudo (Figura 6.8) vêm confirmar o

que toda a experiência prática realizada ao longo deste trabalho nos demonstrou. Ou

seja, estes resultados vão de encontro à conjectura enunciada no capítulo 5, que

pressupõe a existência de uma forte interligação entre as restrições de eliminação de

sub-ciclos. De facto, ao longo de toda a análise efectuada e de todos os exemplos

práticos resolvidos, sempre foi possível obter a solução óptima do problema com um

número de restrições muito inferior ao considerado inicialmente pela respectiva

formulação do PCV. Tudo isto aponta para que as restrições de eliminação de sub-ciclos

com um determinado número de nós influenciem a eliminação de sub-ciclos com um

cardinal diferente. No entanto, a grande questão que continua a prevalecer é a de qual o

conjunto de restrições de eliminação de sub-ciclos que é, de facto, necessário para a

obtenção da solução óptima do problema. Apesar de todos os esforços nesse sentido,

esta é uma questão que ainda se encontra sem resposta.

No entanto, é necessário frisar que este é um estudo teórico, onde são assumidas

determinadas características, que em termos práticos não se verificam, nomeadamente,

o facto de as ocorrências terem a mesma probabilidade em todas as possibilidades.


61

7. CONCLUSÃO

Neste trabalho foi feito um estudo, de forma gradual, do Problema do Caixeiro

Viajante. O problema foi introduzido de um modo simples e informal e, posteriormente,

foram apresentadas várias formulações matemáticas para o mesmo, propostas por

diversos autores. Focando a atenção numa das formulações apresentadas, foram

apresentados resultados que permitiram o seu melhoramento, facilitando a resolução do

problema, provando-se assim a existência de uma formulação com a mesma eficácia

mas que apenas necessita de metade das restrições de eliminação de sub-ciclos. Toda a

análise posterior foi centrada nessa formulação, sendo resolvidas várias instâncias do

PCV de forma a se poder analisar o comportamento das restrições de eliminação de sub-

ciclos e a sua importância na obtenção da solução óptima do problema.

O estudo efectuado levou-nos a conjecturar que muitas das restrições de eliminação

de sub-ciclos são provavelmente desnecessárias, pois todas as instâncias foram

resolvidas com um número de restrições bastante inferior ao número exigido por qualquer

uma das formalizações apresentadas.

De forma a averiguar a existência da provável interligação entre estas restrições,

analisámos de que forma as restrições de eliminação de sub-ciclos com 5 nós

influenciam a eliminação de sub-ciclos com 3 e 4 nós, assim como as restrições de

eliminação de sub-ciclos de 4 nós influenciam a eliminação de sub-ciclos com 3 nós. Em

todos os casos, obtivemos resultados que, sob certas condições de equiprobabilidade,

apontam para a existência de uma forte interligação, isto é, ao eliminarmos, por exemplo,

os sub-ciclos com 5 nós num grafo, temos uma grande probabilidade de impedir a

formação de sub-ciclos com 3 e 4 nós. Estes resultados vão de encontro a toda a

experiência prática realizada ao longo deste trabalho, onde é notória a existência de

redundância entre estas restrições. Por exemplo, é possível obter a solução óptima de

um PCV com 13 clientes usando apenas aproximadamente 0.5% das restrições de

eliminação de sub-ciclos.

Através da obtenção de valores numéricos que vêm confirmar a existência de uma

forte redundância entre as restrições de eliminação de sub-ciclos, este trabalho fomenta

estudos futuros com o objectivo de eliminar esta redundância, reduzindo drasticamente o

número de restrições deste tipo o que, consequentemente, levará a uma redução do

custo computacional da resolução do PCV.


62

8. BIBLIOGRAFIA

[1] Barreto, S. Análise e Modelização de Problemas de Localização-Distribuição. Tese de

Doutoramento, Departamento de Economia, Gestão e Engenharia Industrial,

Universidade de Aveiro, 2004.

[2] Barreto, S. Uma contribuição para a simplificação do Problema do Caixeiro Viajante

Universidade de Aveiro, 2003 (Documento não publicado).

[3] Barreto, S., Ferreira, C., Paixão, J. Formulações de compromisso para um Problema

de Localização-Distribuição com capacidade. Apresentação integrada no Seminário de

Investigação Operacional da Faculdade de Engenharia da Universidade do Porto, Abril de

2004 (Documento não publicado).

[4] Bondy, J., Murty, U. Graph theory with applications. North Holland, New York, 1976.

[5] Cormen, Thomas H. et al. Algoritmos: teoria e prática. 2ªEdição, Rio de Janeiro:

Elsevier, 2002.

[6] Crowder, H., Padberg, M. Solving large-scale symmetric travelling salesman roblems

to optimality. Management Science 26 (1980) S. 495-509

[7] Cunha, Bonasser, Abrahão Experimentos Computacionais com Heurísticas de

Melhorias para o Problema do Caixeiro Viajante. Trabalho apresentado no XVI

Congresso da Associação Nacional de Pesquisa e Ensino em Transportes e publicado

nos anais do evento. Departamento de Engenharia e Transportes, Escola Politécnica da

Universidade de São Paulo, 2002.

[8] Dantzig, G., Fulkerson, R., Johnson, S. Solution of a large-scale Traveling-Salesman

Problem. Operations Research, volume 2, número1, 1954.

[9] Goldbarg, Luna Optimização Combinatória e Programação Linear: Modelos e

Algoritmos. Editora Campus, 1999.


63

[10] Land, A. H., Doig, A. G. An Automatic method of solving discrete programming

problems. Econometrica, volume 28, número 3. Julho, 1960.

[11] Laporte, G. The Traveling Salesman Problem: An overview of exact and approximate

algorithms. European Journal of Operacional Research nº 59,1992.

[12] Lin, S., Kernighan, B. W. An Effective Heuristic Algorithm for the Traveling-Salesman

Problem. Operations Research, Vol. 21, pp. 498-516, Março-Abril 1973.

[13] Miller, C. E., Tucker, A. W., Zemlint, R. A. Integer Programming Formulation of

Traveling Salesmam Problems. 1960.

[14] Padberg, M., Rinaldi, G. Optimization of a 532-city Symmetric Traveling Salesman

Problem by Branch and cut. Operations Research Letters, Vol. 6, pp 1-7, 1987

[15] Souza, L. V. Técnicas de roteirização de veículos aplicadas ao transporte escolar.

Tese de Mestrado, Universidade Federal do Paraná, Brasil, 1997.

Endereços consultados:

http://www.portalcomputacao.com.br/conhecimento/pcv.html#desc24

http://www.tsp.gatech.edu/

http://en.wikipedia.org/wiki/Branch_and_bound


64

9. ANEXOS

ANEXO 1

DESCRIÇÃO DOS FICHEIROS DE DADOS

Neste anexo são apresentados os ficheiros de dados sobre quais os testes

computacionais foram efectuados. Todos os ficheiros, uns directamente outros com

algumas adaptações, foram recolhidos de [1].

Cada instância do PCV encontra-se numerada de acordo com a ordem de surgimento

no trabalho. Em cada instância, é identificado o número dos clientes que a constitui e as

respectivas coordenadas (abcissa e ordenada).

FICHEIROS DE DADOS A1.1. Instâncias constituídas por seis clientes

INSTÂNCIA 1 Cliente Abcissa Ordenada

1 151 254 2 159 261 3 130 254 4 128 252 5 163 247 6 146 246


1 295 272 2 301 258 3 309 260 4 217 274 5 218 278 6 282 267


65

A1. 2. Instâncias constituídas por sete clientes


1 218 382 2 218 358 3 201 370 4 214 371 5 224 370 6 210 382 7 104 354


1 283 406 2 279 399 3 271 401 4 264 414 5 277 439 6 290 434 7 319 433


1 45 35 2 59 15 3 5 6 4 10 17 5 21 10 6 5 64 7 30 15


1 547064 268520 2 543480 259490 3 543480 529420 4 532728 276990 5 550032 260610 6 565824 278670 7 541520 263760


66

A1.3. Instâncias constituídas por oito clientes


1 295 272 2 301 258 3 309 260 4 217 274 5 218 278 6 282 267 7 242 249 8 230 262


1 188 357 2 152 349 3 215 389 4 212 394 5 188 393 6 207 406 7 184 410 8 207 392


1 20 20 2 20 50 3 30 30 4 30 70 5 40 50 6 50 30 7 50 70 8 60 50


67


1 37 52 2 49 49 3 52 64 4 20 26 5 40 30 6 21 47 7 17 63 8 31 62


1 44 13 2 26 13 3 11 28 4 7 43 5 17 64 6 41 46 7 55 34 8 35 16


1 329 252 2 318 252 3 329 224 4 267 213 5 275 192 6 303 201 7 208 217 8 326 181


1 146 208 2 164 208 3 141 206 4 147 193 5 164 193 6 129 189 7 155 185 8 139 182


68

A.1.4. Instâncias constituídas por dez clientes


1 119 340 2 129 349 3 126 347 4 125 346 5 116 355 6 126 335 7 125 355 8 119 357 9 115 341

10 153 351


1 51 21 2 42 41 3 31 32 4 5 25 5 12 42 6 36 16 7 52 41 8 27 23 9 17 33

10 13 13


1 22 22 2 36 26 3 21 45 4 45 35 5 55 20 6 33 34 7 50 50 8 55 45 9 26 59

10 40 66


69

INSTÂNCIA 17

Cliente Abcissa Ordenada 1 40 25 2 42 7 3 24 12 4 23 3 5 11 14 6 6 38 7 2 48 8 8 56 9 13 52

10 6 68


1 3915 1225 2 4145 1176 3 4170 1206 4 3926 1275 5 3965 1169 6 4266 1261 7 4242 1226 8 4234 1120 9 4376 1358

10 4364 1276


1 74 41 2 118 34 3 88 42 4 95 30 5 75 40 6 117 33 7 83 42 8 97 33 9 112 34

10 99 29


70

A.1.5. Instâncias constituídas por 11 clientes


1 298 427 2 309 445 3 307 464 4 336 475 5 320 439 6 321 437 7 322 437 8 323 433 9 324 433

10 323 429 11 314 435


1 293 421 2 296 418 3 261 384 4 297 410 5 315 407 6 314 406 7 321 391 8 321 398 9 314 394

10 313 378 11 304 382


1 43 26 2 31 76 3 22 53 4 26 29 5 50 40 6 55 50 7 54 10 8 60 15 9 47 66

10 30 60 11 30 50


71

INSTÂNCIA 23

Cliente Abcissa Ordenada 1 30 61 2 22 54 3 45 54 4 39 47 5 28 39 6 36 36 7 32 35 8 33 32 9 27 28

10 32 28 11 11 27

A.1.6. Instâncias constituídas por 13 clientes


1 62 42 2 42 57 3 16 57 4 8 52 5 7 38 6 27 68 7 30 48 8 43 67 9 58 48

10 58 27 11 37 69 12 38 46 13 46 10


1 15 56 2 29 39 3 54 38 4 55 57 5 67 41 6 10 70 7 6 25 8 65 27 9 40 60

10 70 64 11 64 4 12 36 6 13 30 20


72


1 123 46 2 95 39 3 118 34 4 111 32 5 90 39 6 81 35 7 84 34 8 76 37 9 107 35

10 122 38 11 80 40 12 121 39 13 93 45


1 1300 770 2 1182 956 3 895 920 4 1265 1020 5 1171 960 6 1087 735 7 1118 1036 8 883 1058 9 1003 1004

10 1296 758 11 90 993 12 692 1930 13 67 661


73

ANEXO 2

Neste anexo, encontra-se a tabela com as 210 possibilidades de satisfazer, no

máximo, a restrição (6) que surge no capítulo 6, secção 6.3.

x12

x13 x14 x15 x23 x24 x25 x34 x35 x45 Res.

1 1 1 1 0 0 0 0 0 0 XX

1 1 1 0 1 0 0 0 0 0 XX

1 1 1 0 0 1 0 0 0 0 XX

1 1 1 0 0 0 1 0 0 0 XX

1 1 1 0 0 0 0 1 0 0 XX

1 1 1 0 0 0 0 0 1 0 XX

1 1 1 0 0 0 0 0 0 1 XX

1 1 0 1 1 0 0 0 0 0 XX

1 1 0 1 0 1 0 0 0 0 XX

1 1 0 1 0 0 1 0 0 0 XX

1 1 0 1 0 0 0 1 0 0 XX

1 1 0 1 0 0 0 0 1 0 XX

1 1 0 1 0 0 0 0 0 1 XX

1 1 0 0 1 1 0 0 0 0 XX

1 1 0 0 1 0 1 0 0 0 XX

1 1 0 0 1 0 0 1 0 0 XX

1 1 0 0 1 0 0 0 1 0 XX

1 1 0 0 1 0 0 0 0 1 123

1 1 0 0 0 1 1 0 0 0 XX

1 1 0 0 0 1 0 1 0 0 1342

1 1 0 0 0 1 0 0 1 0 X

1 1 0 0 0 1 0 0 0 1 X

1 1 0 0 0 0 1 1 0 0 X

1 1 0 0 0 0 1 0 1 0 1352

1 1 0 0 0 0 1 0 0 1 X

1 1 0 0 0 0 0 1 1 0 XX

1 1 0 0 0 0 0 1 0 1 X

1 1 0 0 0 0 0 0 1 1 X

1 0 1 1 1 0 0 0 0 0 XX

1 0 1 1 0 1 0 0 0 0 XX

1 0 1 1 0 0 1 0 0 0 XX

1 0 1 1 0 0 0 1 0 0 XX

1 0 1 1 0 0 0 0 1 0 XX

1 0 1 1 0 0 0 0 0 1 XX


74

1 0 1 0 1 1 0 0 0 0 XX

1 0 1 0 1 0 1 0 0 0 XX

1 0 1 0 1 0 0 1 0 0 1432

1 0 1 0 1 0 0 0 1 0 X

1 0 1 0 1 0 0 0 0 1 X

1 0 1 0 0 1 1 0 0 0 XX

1 0 1 0 0 1 0 1 0 0 XX

1 0 1 0 0 1 0 0 1 0 124

1 0 1 0 0 1 0 0 0 1 XX

1 0 1 0 0 0 1 1 0 0 X

1 0 1 0 0 0 1 0 1 0 X

1 0 1 0 0 0 1 0 0 1 1452

1 0 1 0 0 0 0 1 1 0 X

1 0 1 0 0 0 0 1 0 1 XX

1 0 1 0 0 0 0 0 1 1 X

1 0 0 1 1 1 0 0 0 0 XX

1 0 0 1 1 0 1 0 0 0 XX

1 0 0 1 1 0 0 1 0 0 X

1 0 0 1 1 0 0 0 1 0 1532

1 0 0 1 1 0 0 0 0 1 X

1 0 0 1 0 1 1 0 0 0 XX

1 0 0 1 0 1 0 1 0 0 X

1 0 0 1 0 1 0 0 1 0 X

1 0 0 1 0 1 0 0 0 1 1542

1 0 0 1 0 0 1 1 0 0 125

1 0 0 1 0 0 1 0 1 0 XX

1 0 0 1 0 0 1 0 0 1 XX

1 0 0 1 0 0 0 1 1 0 X

1 0 0 1 0 0 0 01 0 1 X

1 0 0 1 0 0 0 0 1 1 XX

1 0 0 0 1 1 1 0 0 0 XX

1 0 0 0 1 1 0 1 0 0 XX

1 0 0 0 1 1 0 0 1 0 XX

1 0 0 0 1 1 0 0 0 1 XX

1 0 0 0 1 0 1 1 0 0 XX

1 0 0 0 1 0 1 0 1 0 XX

1 0 0 0 1 0 1 0 0 1 XX

1 0 0 0 1 0 0 1 1 0 XX

1 0 0 0 1 0 0 1 0 1 X


75

1 0 0 0 1 0 0 0 1 1 X

1 0 0 0 0 1 1 1 0 0 XX

1 0 0 0 0 1 1 0 1 0 XX

1 0 0 0 0 1 1 0 0 1 XX

1 0 0 0 0 1 0 1 1 0 X

1 0 0 0 0 1 0 1 0 1 XX

1 0 0 0 0 1 0 0 1 1 X

1 0 0 0 0 0 1 1 1 0 X

1 0 0 0 0 0 1 1 0 1 X

1 0 0 0 0 0 1 0 1 1 XX

1 0 0 0 0 0 0 1 1 1 345

0 1 1 1 1 0 0 0 0 0 XX

0 1 1 1 0 1 0 0 0 0 XX

0 1 1 1 0 0 1 0 0 0 XX

0 1 1 1 0 0 0 1 0 0 XX

0 1 1 1 0 0 0 0 1 0 XX

0 1 1 1 0 0 0 0 0 1 XX

0 1 1 0 1 1 0 0 0 0 1423

0 1 1 0 1 0 1 0 0 0 X

0 1 1 0 1 0 0 1 0 0 XX

0 1 1 0 1 0 0 0 1 0 XX

0 1 1 0 1 0 0 0 0 1 XX

0 1 1 0 0 1 1 0 0 0 X

0 1 1 0 0 1 0 1 0 0 XX

0 1 1 0 0 1 0 0 1 0 X

0 1 1 0 0 1 0 0 0 1 XX

0 1 1 0 0 0 1 1 0 0 143

0 1 1 0 0 0 1 0 1 0 X

0 1 1 0 0 0 1 0 0 1 X

0 1 1 0 0 0 0 1 1 0 XX

0 1 1 0 0 0 0 1 0 1 XX

0 1 1 0 0 0 0 0 1 1 1453

0 1 0 1 1 1 0 0 0 0 X

0 1 0 1 1 0 1 0 0 0 1523

0 1 0 1 1 0 0 1 0 0 XX

0 1 0 1 1 0 0 0 1 0 XX

0 1 0 1 1 0 0 0 0 1 X

0 1 0 1 0 1 1 0 0 0 X

0 1 0 1 0 1 0 1 0 0 X


76

0 1 0 1 0 1 0 0 1 0 153

0 1 0 1 0 1 0 0 0 1 X

0 1 0 1 0 0 1 1 0 0 X

0 1 0 1 0 0 1 0 1 0 XX

0 1 0 1 0 0 1 0 0 1 XX

0 1 0 1 0 0 0 1 1 0 XX

0 1 0 1 0 0 0 1 0 1 1543

0 1 0 1 0 0 0 0 1 1 XX

0 1 0 0 1 1 1 0 0 0 XX

0 1 0 0 1 1 0 1 0 0 XX

0 1 0 0 1 1 0 0 1 0 XX

0 1 0 0 1 1 0 0 0 1 X

0 1 0 0 1 0 1 1 0 0 XX

0 1 0 0 1 0 1 0 1 0 XX

0 1 0 0 1 0 1 0 0 1 X

0 1 0 0 1 0 0 1 1 0 XX

0 1 0 0 1 0 0 1 0 1 XX

0 1 0 0 1 0 0 0 1 1 XX

0 1 0 0 0 1 1 1 0 0 X

0 1 0 0 0 1 1 0 1 0 X

0 1 0 0 0 1 1 0 0 1 254

0 1 0 0 0 1 0 1 1 0 XX

0 1 0 0 0 1 0 1 0 1 XX

0 1 0 0 0 1 0 0 1 1 X

0 1 0 0 0 0 1 1 1 0 XX

0 1 0 0 0 0 1 1 0 1 X

0 1 0 0 0 0 1 0 1 1 XX

0 1 0 0 0 0 0 1 1 1 XX

0 0 1 1 1 1 0 0 0 0 X

0 0 1 1 1 0 1 0 0 0 X

0 0 1 1 1 0 0 1 0 0 X

0 0 1 1 1 0 0 0 1 0 X

0 0 1 1 1 0 0 0 0 1 145

0 0 1 1 0 1 1 0 0 0 1524

0 0 1 1 0 1 0 1 0 0 XX

0 0 1 1 0 1 0 0 1 0 X

0 0 1 1 0 1 0 0 0 1 XX

0 0 1 1 0 0 1 1 0 0 X

0 0 1 1 0 0 1 0 1 0 XX


77

0 0 1 1 0 0 1 0 0 1 XX

0 0 1 1 0 0 0 1 1 0 1534

0 0 1 1 0 0 0 1 0 1 XX

0 0 1 1 0 0 0 0 1 1 XX

0 0 1 0 1 1 1 0 0 0 XX

0 0 1 0 1 1 0 1 0 0 XX

0 0 1 0 1 1 0 0 1 0 X

0 0 1 0 1 1 0 0 0 1 XX

0 0 1 0 1 0 1 1 0 0 X

0 0 1 0 1 0 1 0 1 0 235

0 0 1 0 1 0 1 0 0 1 X

0 0 1 0 1 0 0 1 1 0 XX

0 0 1 0 1 0 0 1 0 1 XX

0 0 1 0 1 0 0 0 1 1 X

0 0 1 0 0 1 1 1 0 0 XX

0 0 1 0 0 1 1 0 1 0 X

0 0 1 0 0 1 1 0 0 1 XX

0 0 1 0 0 1 0 1 1 0 XX

0 0 1 0 0 1 0 1 0 1 XX

0 0 1 0 0 1 0 0 1 1 XX

0 0 1 0 0 0 1 1 1 0 X

0 0 1 0 0 0 1 1 0 1 XX

0 0 1 0 0 0 1 0 1 1 XX

0 0 1 0 0 0 0 1 1 1 XX

0 0 0 1 1 1 1 0 0 0 XX

0 0 0 1 1 1 0 1 0 0 234

0 0 0 1 1 1 0 0 1 0 X

0 0 0 1 1 1 0 0 0 1 X

0 0 0 1 1 0 1 1 0 0 X

0 0 0 1 1 0 1 0 1 0 XX

0 0 0 1 1 0 1 0 0 1 XX

0 0 0 1 1 0 0 1 1 0 XX

0 0 0 1 1 0 0 1 0 1 X

0 0 0 1 1 0 0 0 1 1 XX

0 0 0 1 0 1 1 1 0 0 X

0 0 0 1 0 1 1 0 1 0 XX

0 0 0 1 0 1 1 0 0 1 XX

0 0 0 1 0 1 0 1 1 0 X

0 0 0 1 0 1 0 1 0 1 XX


78

0 0 0 1 0 1 0 0 1 1 XX

0 0 0 1 0 0 1 1 1 0 XX

0 0 0 1 0 0 1 1 0 1 XX

0 0 0 1 0 0 1 0 1 1 XX

0 0 0 1 0 0 0 1 1 1 XX

0 0 0 0 1 1 1 1 0 0 XX

0 0 0 0 1 1 1 0 1 0 XX

0 0 0 0 1 1 1 0 0 1 XX

0 0 0 0 1 1 0 1 1 0 XX

0 0 0 0 1 1 0 1 0 1 XX

0 0 0 0 1 1 0 0 1 1 2354

0 0 0 0 1 0 1 1 1 0 XX

0 0 0 0 1 0 1 1 0 1 2345

0 0 0 0 1 0 1 0 1 1 XX

0 0 0 0 1 0 0 1 1 1 XX

0 0 0 0 0 1 1 1 1 0 2435

0 0 0 0 0 1 1 1 0 1 XX

0 0 0 0 0 1 1 0 1 1 XX

0 0 0 0 0 1 0 1 1 1 XX

0 0 0 0 0 0 1 1 1 1 XX

Tabela A.2.1: Possibilidades para satisfazer, no máximo, a restrição (6).

Notação: XX - existe um vértice com grau superior a 2;

X - o caminho não fecha, não formando assim um ciclo;

Documents

Carla Sofia Problema do Caixeiro Viajante – Resolução e de ... · O Problema do Caixeiro Viajante (PCV) pode ser entendido como o problema de um vendedor que deseja visitar um