Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
Solving Traveling Salesman Problem by Marker Method  [PDF]
Masoumeh Vali
Mathematics , 2013,
Abstract: In this paper we use marker method and propose a new mutation operator that selects the nearest neighbor among all near neighbors solving Traveling Salesman Problem.
Towards Efficiently Solving Quantum Traveling Salesman Problem  [PDF]
Debabrata Goswami,Harish Karnick,Prateek Jain,Hemanta K. Maji
Physics , 2004,
Abstract: We present a framework for efficiently solving Approximate Traveling Salesman Problem (Approximate TSP) for Quantum Computing Models. Existing representations of TSP introduce extra states which do not correspond to any permutation. We present an efficient and intuitive encoding for TSP in quantum computing paradigm. Using this representation and assuming a Gaussian distribution on tour-lengths, we give an algorithm to solve Approximate TSP (Euclidean) within BQP resource bounds. Generalizing this strategy for any distribution, we present an oracle based Quantum Algorithm to solve Approximate TSP. We present a realization of the oracle in the quantum counterpart of PP.
Solving the Traveling Salesman Problem Using Hydrological Cycle Algorithm  [PDF]
Ahmad Wedyan, Jacqueline Whalley, Ajit Narayanan
American Journal of Operations Research (AJOR) , 2018, DOI: 10.4236/ajor.2018.83010
Abstract: In this paper, a recently developed nature-inspired optimization algorithm called the hydrological cycle algorithm (HCA) is evaluated on the traveling salesman problem (TSP). The HCA is based on the continuous movement of water drops in the natural hydrological cycle. The HCA performance is tested on various geometric structures and standard benchmarks instances. The HCA has successfully solved TSPs and obtained the optimal solution for 20 of 24 benchmarked instances, and near-optimal for the rest. The obtained results illustrate the efficiency of using HCA for solving discrete domain optimization problems. The solution quality and number of iterations were compared with those of other metaheuristic algorithms. The comparisons demonstrate the effectiveness of the HCA.
Analysis and Counterexamples Regarding Yatsenko's Polynomial-Time Algorithm for Solving the Traveling Salesman Problem  [PDF]
Christopher Clingerman,Jeremiah Hemphill,Corey Proscia
Computer Science , 2008,
Abstract: Yatsenko gives a polynomial-time algorithm for solving the traveling salesman problem. We examine the correctness of the algorithm and its construction. We also comment on Yatsenko's evaluation of the algorithm.
Alternative Method for Solving Traveling Salesman Problem by Evolutionary Algorithm  [PDF]
Zuzana ?i?ková,Ivan Brezina,Juraj Pekár
International Scientific Journal of Management Information Systems , 2008,
Abstract: This article describes the application of Self Organizing Migrating Algorithm (SOMA) to the well-known optimization problem - Traveling Salesman Problem (TSP). SOMA is a relatively new optimization method that is based on Evolutionary Algorithms that are originally focused on solving non-linear programming problems that contain continuous variables. The TSP has model character in many branches of Operation Research because of its computational complexity; therefore the use of Evolutionary Algorithm requires some special approaches to guarantee feasibility of solutions. In this article two concrete examples of TSP as 8 cities set and 25 cities set are given to demonstrate the practical use of SOMA. Firstly, the penalty approach is applied as a simple way to guarantee feasibility of solution. Then, new approach that works only on feasible solutions is presented.
An improved genetic algorithm with a local optimization strategy and an extra mutation level for solving traveling salesman problem  [PDF]
Keivan Borna,Vahid Haji Hashemi
Computer Science , 2014, DOI: 10.5121/ijcseit.2014.4405
Abstract: The Traveling salesman problem (TSP) is proved to be NP-complete in most cases. The genetic algorithm (GA) is one of the most useful algorithms for solving this problem. In this paper a conventional GA is compared with an improved hybrid GA in solving TSP. The improved or hybrid GA consist of conventional GA and two local optimization strategies. The first strategy is extracting all sequential groups including four cities of samples and changing the two central cities with each other. The second local optimization strategy is similar to an extra mutation process. In this step with a low probability a sample is selected. In this sample two random cities are defined and the path between these cities is reversed. The computation results show that the proposed method also finds better paths than the conventional GA within an acceptable computation time.
An Algorithm for Solving a Multi-city Traveling Salesman Problem Based on Learning of Hopfield Network

JIN Haihe,CHEN Jian,TANG Zheng,ZHENG Guoqi,

系统工程理论与实践 , 2003,
Abstract: This paper proposes an algorithm of solving the multi-city traveling salesman problem based on Hopfield network learning. The algorithm uses the Hopfield network learning as basal arithmetic operators, to look for the optimal or better solution by dividing up, calculation and linking the group of cities with the given rules. The algorithm is applied to a 100-city traveling salesman problem, and its effectiveness is confirmed by simulation. This algorithm is free from limitation of the city number; and speedup can be implemented by parallel operation; and hardware can be achieved easily because of simplicity and clarity in algorithm.
Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems  [PDF]
Sandor P. Fekete,Henk Meijer,Andre Rohe,Walter Tietze
Computer Science , 2002,
Abstract: We consider geometric instances of the Maximum Weighted Matching Problem (MWMP) and the Maximum Traveling Salesman Problem (MTSP) with up to 3,000,000 vertices. Making use of a geometric duality relationship between MWMP, MTSP, and the Fermat-Weber-Problem (FWP), we develop a heuristic approach that yields in near-linear time solutions as well as upper bounds. Using various computational tools, we get solutions within considerably less than 1% of the optimum. An interesting feature of our approach is that, even though an FWP is hard to compute in theory and Edmonds' algorithm for maximum weighted matching yields a polynomial solution for the MWMP, the practical behavior is just the opposite, and we can solve the FWP with high accuracy in order to find a good heuristic solution for the MWMP.
Applying the Method for Solving Traveling Salesman Problem Based on Backtracking Algorithm to Order Picking  [PDF]
Jie Zhu, Ying Huang, Lijuan Xu
Open Journal of Optimization (OJOp) , 2016, DOI: 10.4236/ojop.2016.52010
Abstract: In the distribution center, the way of order picking personnel to pick goods has two kinds: single picking and batch picking. Based on the way of the single picking and assumed warehouse model, in order to reduce the walking path of order picking, the order picking problem is transformed into the traveling salesman problem in this paper. Based on backtracking algorithm, the order picking path gets optimized. Finally verifing the optimization method under the environment of VC++6.0, order picking path in the warehouse model get optimized, and compared with the traditional order picking walking paths. The results show that in small and medium-sized warehouse, the optimization method proposed in this paper can reduce order picking walking path and improve the work efficiency as well as reduce the time cost.
S. Kantsedal,M. Kostikova,I. Skrypina
Аvtomob?lnyi Transport , 2012,
Abstract: Lytle’s algorithm is described as proposed for an accurate solution of the salesman Problem. Statistical characteristics of solution duration with lytle’s algorithm of some problems and of their modifications are specified. On the basis of the results obtained the limits for the algorithm practical specification in the preparation of the route network are given.
Page 1 /100
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.