Página 1 dos resultados de 368 itens digitais encontrados em 0.011 segundos

Um melhor limite inferior para o problema do caixeiro viajante assimétrico baseado no problema da afectação; An improved lower bound for the asymmetric traveling salesman problem based on the assignment problem

Ramires, Ana; Soares, João
Fonte: APDIO - Associação Portuguesa de Investigação Operacional Publicador: APDIO - Associação Portuguesa de Investigação Operacional
Tipo: Artigo de Revista Científica
POR
Relevância na Pesquisa
86.56%
Neste artigo explicamos como obter um limite inferior para o valor óptimo do problema do caixeiro viajante assimétrico melhor do que o que advém do problema de afectação através da resolução sucessiva de problemas de afectação. O algoritmo que propomos é um método de primeira ordem baseado na função de penalidade exponencial cujas direcções de deslocamento são definidas com base numa relaxação disjuntiva que propomos ser de dois tipos, uma baseada em ciclos e a outra baseada em cliques.; In this article we decribe how to compute a lower bound for the asymmetric traveling salesman problem that dominates the bound that comes from the assignment relaxation, through the solving of a sequence of assignment problems. The algorithm that we propose is a first-order method based on the exponential penalty function. Directions of movement are derived from a disjunctive relaxation that we proposed as being one of two possible classes, one based on cycles, the other based on cliques.

Rede neural recorrente com perturbação simultânea aplicada no problema do caixeiro viajante; Recurrent neural network with simultaneous perturbation applied to traveling salesman problem

Benini, Fabriciu Alarcão Veiga
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 15/12/2008 PT
Relevância na Pesquisa
96.7%
O presente trabalho propõe resolver o clássico problema combinatorial conhecido como problema do caixeiro viajante. Foi usado no sistema de otimização de busca do menor caminho uma rede neural recorrente. A topologia de estrutura de ligação das realimentações da rede adotada aqui é conhecida por rede recorrente de Wang. Como regra de treinamento de seus pesos sinápticos foi adotada a técnica de perturbação simultânea com aproximação estocástica. Foi elaborado ainda uma minuciosa revisão bibliográfica sobre todos os temas abordados com detalhes sobre a otimização multivariável com perturbação simultânea. Comparar-se-á também os resultados obtidos aqui com outras diferentes técnicas aplicadas no problema do caixeiro viajante visando propósitos de validação.; This work proposes to solve the classic combinatorial optimization problem known as traveling salesman problem. A recurrent neural network was used in the system of optimization to search the shorter path. The structural topology linking the feedbacks of the network adopted here is known by Wang recurrent network. As learning rule to find the appropriate values of the weights was used the simultaneous perturbation with stochastic approximation. A detailed bibliographical revision on multivariable optimization with simultaneous perturbation is also described. Comparative results with other different techniques applied to the traveling salesman are still presented for validation purposes.

Análise de similaridades de modelagem no emprego de técnicas conexionistas e evolutivas da inteligência computacional visando à resolução de problemas de otimização combinatorial: estudo de caso - problema do caixeiro viajante.; Similarity analysis for conexionist and evolutionary tecniques of the computational intelligence fild focused on the resolution of combinatorial optimization problems: case study - traveling salesman problem.

Fernandes, David Saraiva Farias
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 08/06/2009 PT
Relevância na Pesquisa
96.56%
Este trabalho realiza uma análise dos modelos pertencentes à Computação Neural e à Computação Evolutiva visando identificar semelhanças entre as áreas e sustentar mapeamentos entre as semelhanças identificadas. Neste contexto, a identificação de similaridades visando à resolução de problemas de otimização combinatorial resulta em uma comparação entre a Máquina de Boltzmann e os Algoritmos Evolutivos binários com população composta por um único indivíduo pai e um único indivíduo descendente. Como forma de auxiliar nas análises, o trabalho utiliza o Problema do Caixeiro Viajante como plataforma de ensaios, propondo mapeamentos entre as equações da Máquina de Boltzmann e os operadores evolutivos da Estratégia Evolutiva (1+1)-ES.; An analysis between the Evolutionary Computation and the Neural Computation fields was presented in order to identify similarities and mappings between the theories. In the analysis, the identification of similarities between the models designed for combinatorial optimization problems results in a comparison between the Boltzmann Machine and the Two-Membered Evolutionary Algorithms. In order to analyze the class of combinatorial optimization problems, this work used the Traveling Salesman Problem as a study subject...

Uso de meta-aprendizado na recomendação de meta-heurísticas para o problema do caixeiro viajante; Using meta-learning on the recommendation of meta-heuristics for the traveling salesman problem

Kanda, Jorge Yoshio
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 07/12/2012 PT
Relevância na Pesquisa
96.62%
O problema do caixeiro viajante (PCV) é um problema clássico de otimização que possui diversas variações, aplicações e instâncias. Encontrar a solução ótima para muitas instâncias desse problema é geralmente muito difícil devido o alto custo computacional. Vários métodos de otimização, conhecidos como meta-heurísticas (MHs), são capazes de encontrar boas soluções para o PCV. Muitos algoritmos baseados em diversas MHs têm sido propostos e investigados para diferentes variações do PCV. Como não existe um algoritmo universal que encontre a melhor solução para todas as instâncias de um problema, diferentes MHs podem prover a melhor solução para diferentes instâncias do PCV. Desse modo, a seleção a priori da MH que produza a melhor solução para uma dada instância é uma tarefa difícil. A pesquisa desenvolvida nesta tese investiga o uso de abordagens de meta-aprendizado para selecionar as MHs mais promissoras para novas instâncias de PCV. Essas abordagens induzem meta-modelos preditivos a partir do treinamento das técnicas de aprendizado de máquina em um conjunto de meta-dados. Cada meta-exemplo, em nosso conjunto de meta-dados, representa uma instância de PCV descrita por características (meta-atributos) do PCV e pelo desempenho das MHs (meta-atributo alvo) para essa instância. Os meta-modelos induzidos são usados para indicar os valores do meta-atributo alvo para novas instâncias do PCV. Vários experimentos foram realizados durante a investigação desta pesquisa e resultados importantes foram obtidos; The traveling salesman problem (TSP) is a classical optimization problem that has several variations...

Aplicações de meta-heuristica genetica e fuzzy no sistema de colonia de formigas para o problema do caixeiro viajante; Aplications of genetic and fuzzy metaheusistic in the ant colony system for the traveling salesman problem

Marcia Braga de Carvalho
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 27/07/2007 PT
Relevância na Pesquisa
86.58%
Dentre as várias técnicas heurísticas e exatas existentes para a resolução de problemas combinatórios, os algoritmos populacionais de otimização por colônia de formigas e genéticos têm se destacado devido à sua boa performance. Em especial os algoritmos de colônia de formigas são considerados atualmente como uma das técnicas mais bem sucedidas para a resolução de vários problemas combinatórios, dentre eles o problema do caixeiro viajante. Neste trabalho é apresentado um algoritmo híbrido que trabalha com as meta-heurísticas de sistema de colônia de formigas e genético conjuntamente aplicados no problema do caixeiro viajante simétrico. Além disso, apresentamos uma proposta para o algoritmo de formigas quando temos incertezas associadas aos parâmetros do problema. Os resultados obtidos com as metodologias propostas apresentam resultados satisfatórios para todas as instâncias utilizadas; Amongst the several existing heuristical and accurate techniques for the resolution of combinatorial problems, the population algorithms ant colony optimization and genetic have been detached due to their good performance. In special the ant colony algorithms are considered currently as one of the techniques most succeeded for the resolution of some combinatorial problems...

Algoritmos heuristicos para o prize collecting traveling salesman problem

Wesley Elias Ribeiro
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 03/12/1997 PT
Relevância na Pesquisa
66.82%
Esta dissertação trata do Problema do Caixeiro Viajante Coletor de Prêmios (Prize Collecting Traveling Salesman Problem-PCTSP). Este problema é uma generalização do bastante conhecido Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP), em que o caixeiro viajante não precisa visitar, necessariamente, todas as cidades, mas um número suficiente delas para a obtenção de um prêmio mínimo. Além disso, sua função objetivo é dada pela minimização do comprimento da rota adicionada às penalidades pagas por cidades não visitadas. A formulação do PCTSP foi feita com base em uma aplicação prática do problema, o escalonamento de equipamentos em uma indústria siderúrgica. O presente trabalho apresenta um estudo de algoritmos heurísticos disponíveis na literatura do problema. São, então, apresentadas novas heurísticas de construção e melhoria de soluções desenvolvidas para o PCTSP, e é efetuada uma comparação com o algoritmo de melhor garantia de desempenho encontrado na literatura. Este trabalho também compreende o desenvolvimento de um Time Assíncrono para o PCTSP. Times Assíncronos compreendem uma abordagem meta-heurística já aplicada com sucesso a diversos outros problemas de Otimização Combinatória. Seu princípio básico é a combinação sinérgica de diversos algoritmos (agentes)...

Grupos de visitação na AMAN : um estudo de caso do problema do caixeiro viajante; Groups visiting the Military Academy of Agulhas Negras : a case study of the travelling salesman problem

Rogerio Carvalho Mendes Tavora
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 07/01/2011 PT
Relevância na Pesquisa
86.64%
Comemorando os 200 anos de Academia Militar no Brasil a partir de março de 2011, estão previstas várias implementações e melhorias na estrutura de visitação da AMAN que, consequentemente, vão gerar um aumento substancial no número de grupos visitantes no ano de seu bicentenário. Diante dos fatos percebe-se a necessidade de um modelo matemático eficiente cuja finalidade seja permitir aos grupos visitantes percorrerem trajetos otimizados, ou seja, que passem pelos pontos principais de visitação no menor tempo e distância possíveis. O modelo matemático a ser adotado neste trabalho é o Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP), um clássico da Otimização Combinatória pertencente `a classe de problemas NP - difícil, que já possui eficientes algoritmos desenvolvidos. Serão utilizadas heurísticas próprias para a resolução do TSP com o intuito de se obter numericamente itinerários ótimos de visitação, considerando os diferentes grupos visitantes e suas dificuldades de acesso, dentre outras particularidades.; Celebrating 200 years of the Military Academy in Brazil from March 2011, provides a lot of implementations and improvements in the structure of visitation of AMAN, consequently, will generate substantial growth in the number of visiting groups in the year of its bicentennial. Given the facts we see the need for an efficient mathematical model whose purpose is to allow visitors to wander paths optimized groups...

O problema do caixeiro viajante com restrições de empacotamento tridimensional; The traveling salesman problem with three-dimensional loading constraints

Pedro Henrique Del Bianco Hokama
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 14/10/2011 PT
Relevância na Pesquisa
96.72%
Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática.; We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem...

Re-engineering and optimization of material collection and distribution in hospitals

Figueiredo, João André Saleiro
Fonte: Universidade do Minho Publicador: Universidade do Minho
Tipo: Trabalho de Conclusão de Curso
Publicado em //2013 ENG
Relevância na Pesquisa
66.68%
Dissertação de mestrado integrado em Engenharia e Gestão Industrial; The recent economical climate brought the search for efficiency into priority in the different sectors of economic activities. The healthcare sector needs many resources to accomplish proper functioning and its management and organization can become a complicated task. Operations Research tools can be an added value when treating these tasks by giving reliable results and freeing working time for these tasks’ performers. This dissertation was developed as the final project for Mestrado Integrado em Engenharia e Gestão Industrial from Universidade do Minho. The project was developed in the logistics department of Hospital de Braga. The main goal of this project was the analysis of the current practice for internal material distribution and to propose improvements for efficiency. The project focused on the internal transportation of documents, which revealed to be an area that would benefit from improvements. The project was mainly the creation of a routing system that would make the task of collecting and delivering documents inside the hospital more efficient than the current practice. In this dissertation, several working methodologies were formulated...

Scheduling and Routing in Transportation and Distribution Systems: Formulations and New Relaxations

Gavish, Bezalel ; Graves, Stephen C.
Fonte: University of Rochester Publicador: University of Rochester
Tipo: Trabalho em Andamento
ENG
Relevância na Pesquisa
66.72%
New formulations are presented for the traveling salesman problem, and their relationship to previous formulations is investigated. The new formulations are extended to include a variety of transportation scheduling problems, such as the multi-traveling salesman problem, the delivery problem, the school bus problem, and the dial-a-bus problem. A Benders decomposition procedure is applied to the new formulations and the resulting computational procedure is seen to be identical to previous methods for solving the traveling salesman problem. The new formulations are also shown to have a dual relationship with an earlier formulation due to Miller, Tucker and Zemlin. Three Lagrangean relaxations are proposed for the new formulation, one of which is shown to be identical to the I-tree relaxation suggested by Held and Karp. New possibilities are indicated for developing new branch and bound procedures for scheduling and routing in transportation systems.

On the Integrality Gap of the Subtour Relaxation of the Traveling Salesman Problem for Certain Fractional 2-matching Costs

Fast, Caleb
Fonte: Universidade Rice Publicador: Universidade Rice
Relevância na Pesquisa
96.56%
This thesis provides new bounds on the strength of the subtour relaxation of the Traveling Salesman Problem (TSP) for fractional 2-matching cost instances whose support graphs have no fractional cycles larger than five vertices. This work provides insight for improving approximation heuristics for the TSP and into the structure of solutions produced by the subtour relaxation. Guided by a T-join derived from the subtour relaxation, I form a tour by adding edges to the subtour relaxation. By this constructive process, I prove that the optimal solution of the TSP is within 4/3, 17/12, or strictly less than 3/2 of the optimal solution of the subtour relaxation. Thus, this thesis takes a step towards proving the 4/3 conjecture for the TSP and the development of a 4/3 approximation algorithm for the TSP. These developments would provide improved approximations for applications such as DNA sequencing, route planning, and circuit board testing.

Algoritmos de feixe para programação linear inteira mista.

Santos, Ana Maria Ramires Príncipe dos
Fonte: Universidade Portucalense Publicador: Universidade Portucalense
Tipo: Tese de Doutorado
Publicado em //2004 POR
Relevância na Pesquisa
66.9%
Modelos de optimização são muito comuns na literatura das áreas da Investigação Operacional e das Ciências de Gestão. Neste trabalho, abordamos a resolução de uma classe de modelos de optimização conhecidos por modelos de programação linear disjuntiva, que se caracterizam por serem problemas de programação linear cuja região de admissibilidade é união de poliedros. Quase todos os problemas de optimização com- binatória (como o problema do caixeiro viajante, por exemplo) podem ser modelados como problemas de programação linear disjuntiva. Problemas de programação linear disjuntiva (incluindo muitos dos problemas de op- timização combinatória) são melhor resolvidos por métodos do tipo enumerativo (de- nominados branch-and-bound), eventualmente combinados com métodos de planos cortantes (denominados branch-and-cut). No caso de problemas de optimização combi- natória, os cortes mais e cazes são os que constituem facetas do poliedro associado. No caso de problemas sem estrutura identi cável, os cortes mais profundos propostos em [17] são vistos, em geral, como uma boa opção. Contudo, a sua caracterização obriga à resolução de um adequado problema de optimização cuja resolução algébrica obriga à duplicação de estruturas de dados. Em geral...

A study of flow-based models for the electric vehicle routing problem

Santos, Daniel Rebelo dos
Fonte: Universidade de Lisboa Publicador: Universidade de Lisboa
Tipo: Dissertação de Mestrado
Publicado em //2015 ENG
Relevância na Pesquisa
66.67%
Tese de mestrado em Estatística e Investigação Operacional, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2015; Em anos recentes tem-se visto um aumento do uso de veículos eléctricos por parte de empresas que possuem frotas de veículos. Um veículo eléctrico exibe um comportamento bastante distinto de um veículo usual já que não pode funcionar durante largos períodos de tempo e necessita de recarregar a sua bateria de acordo com um processo frequente e bastante demorado. Além disso, a carga transportada por um veículo elétrico influencia a quantidade de energia gasta, algo que também ocorre com veículos usuais mas que não pode ser negligenciado no caso de um veículo elétrico pois o carregamento da bateria é, como foi referido, um processo demorado e que, portanto, quer-se que seja realizado o menor número de vezes possível. A introdução de veículos elétricos também conduz a outro tipo de aspectos a considerar relativamente à topologia da rede de estradas e clientes subjacente ao problema. Uma rua a subir implica um maior consumo de energia por parte de um veículo elétrico, enquanto que uma rua a descer pode até permitir a recuperação de energia. Além disso, temos também de considerar um conjunto novo de vértices...

A comprehensive benchmark set and heuristics for the traveling thief problem

Polyakovskiy, S.; Bonyadi, M.R.; Wagner, M.; Michalewicz, Z.; Neumann, F.
Fonte: ACM Publicador: ACM
Tipo: Conference paper
Publicado em //2014 EN
Relevância na Pesquisa
76.39%
Real-world optimization problems often consist of several NP-hard optimization problems that interact with each other. The goal of this paper is to provide a benchmark suite that promotes a research of the interaction between problems and their mutual influence. We establish a comprehensive benchmark suite for the traveling thief problem (TTP) which combines the traveling salesman problem and the knapsack problem. Our benchmark suite builds on common benchmarks for the two sub-problems which grant a basis to examine the potential hardness imposed by combining the two classical problems. Furthermore, we present some simple heuristics for TTP and their results on our benchmark suite.; Sergey Polyakovskiy, Mohammad Reza Bonyadi, Markus Wagner, Zbigniew Michalewicz, Frank Neumann

A New Exact Algorithm for Traveling Salesman Problem with Time Complexity Interval (O(n^4), O(n^3*2^n))

Li, Yunpeng
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
66.92%
Traveling salesman problem is a NP-hard problem. Until now, researchers have not found a polynomial time algorithm for traveling salesman problem. Among the existing algorithms, dynamic programming algorithm can solve the problem in time O(n^2*2^n) where n is the number of nodes in the graph. The branch-and-cut algorithm has been applied to solve the problem with a large number of nodes. However, branch-and-cut algorithm also has an exponential worst-case running time. In this paper, a new exact algorithm for traveling salesman problem is proposed. The algorithm can be used to solve an arbitrary instance of traveling salesman problem in real life and the time complexity interval of the algorithm is (O(n^4), O(n^3*2^n)). It means that for some instances, the algorithm can find the optimal solution in polynomial time although the algorithm also has an exponential worst-case running time. In other words, the algorithm tells us that not all the instances of traveling salesman problem need exponential time to compute the optimal solution. The algorithm of this paper can not only assist us to solve traveling salesman problem better, but also can assist us to deepen the comprehension of the relationship between NP-complete and P. Therefore...

Parallel Genetic Algorithm to Solve Traveling Salesman Problem on MapReduce Framework using Hadoop Cluster

Er, Harun Rasit; Erdogan, Nadia
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/01/2014
Relevância na Pesquisa
66.78%
Traveling Salesman Problem (TSP) is one of the most common studied problems in combinatorial optimization. Given the list of cities and distances between them, the problem is to find the shortest tour possible which visits all the cities in list exactly once and ends in the city where it starts. Despite the Traveling Salesman Problem is NP-Hard, a lot of methods and solutions are proposed to the problem. One of them is Genetic Algorithm (GA). GA is a simple but an efficient heuristic method that can be used to solve Traveling Salesman Problem. In this paper, we will show a parallel genetic algorithm implementation on MapReduce framework in order to solve Traveling Salesman Problem. MapReduce is a framework used to support distributed computation on clusters of computers. We used free licensed Hadoop implementation as MapReduce framework.; Comment: The International Journal of Soft Computing and Software Engineering [JSCSE], Vol. 3, No. 3, Special Issue. The Proceeding of International Conference on Soft Computing and Software Engineering 2013

The Approximation Ratio of the Greedy Algorithm for the Metric Traveling Salesman Problem

Brecklinghaus, Judith; Hougardy, Stefan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 23/12/2014
Relevância na Pesquisa
66.68%
We prove that the approximation ratio of the greedy algorithm for the metric Traveling Salesman Problem is $\Theta(\log n)$. Moreover, we prove that the same result also holds for graphic, Euclidean, and rectilinear instances of the Traveling Salesman Problem. Finally we show that the approximation ratio of the Clarke-Wright savings heuristic for the metric Traveling Salesman Problem is $\Theta(\log n)$.

Application of particle swarm optimization for traveling salesman problem to lossless compression of color palette images

Van Hook, Joshua; Sahin, Ferat; Arnavut, Ziya
Fonte: IEEE Publicador: IEEE
Tipo: Proceedings
EN_US
Relevância na Pesquisa
96.58%
This paper investigates optimal color indexing for the compression of color palette images. This work enhances the recent Traveling Salesman Problem (TSP) based re-indexing technique with Particle Swarm Optimization (PSO). In this work, color re-indexing is done by solving the problem as a TSP using PSO. The proposed technique, yields better compression gains than the recent work that used a Cross Entropy (CE) based TSP for re-indexing.; Conference Proceedings from the System of Systems Engineering, 2008 conference. Please see www.ieee.org for more information.

A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem

Kawashima,Makswell Seyiti; Rangel,Socorro; Litvinchev,Igor; Infante,Luis
Fonte: DYNA Publicador: DYNA
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/06/2015 EN
Relevância na Pesquisa
96.56%
In this paper we explore the multi-commodity flow formulation for the Asymmetric Traveling Salesman Problem (ATSP) to obtain dual bounds. The procedure employed is a variant of a relax and cut procedure proposed in the literature that computes the Lagrangean multipliers associated to the subtour elimination constraints preserving the optimality of the multipliers associated to the assignment constraints. The results obtained by the computational study are encouraging and show that the proposed algorithm generated good dual bounds for the ATSP with a low execution time.

A network branch and bound approach for the traveling salesman model

Munapo,Elias
Fonte: South African Journal of Economic and Management Sciences Publicador: South African Journal of Economic and Management Sciences
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/01/2013 EN
Relevância na Pesquisa
86.56%
This paper presents a network branch and bound approach for solving the traveling salesman problem. The problem is broken into sub-problems, each of which is solved as a minimum spanning tree model. This is easier to solve than either the linear programming-based or assignment models.