A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic

スポンサーリンク

概要

• 論文の詳細を見る

• Abstract The Lin-Kernighan (LK) heuristic is one of the most effective and efficient algorithms for the Traveling Salesman Problem (TSP). However, the LK heuristic is quite complicated and has many choices for implementing it. Especially, the data structure for tour representation plays an important role in the LK's performance. Traditionally, binary trees (including splay trees) are asymptotically the best tour representation. Empirically, however, they are utilized only for solving problems with more than one million cities due to the large overhead. Arrays are suitable for solving problems having up to a thousand cities and two-level trees are used for the problems with a thousand to a million cities. This paper proposes three-level trees as a new data structure. Although this structure is asymptotically not better than the existing ones, it perform empirically better than the existing ones in the range being investigated in this study (from 10(3乗) to 10(6.5乗) cities).

• 宮崎大学の論文

著者

• Nguyen H

  Graduate School Of Engineering University Of Miyazaki:(present Office)frontier Science Research Cent

• YASUNAGA Moritoshi

  Graduate School of Systems and Information Engineering, University of Tsukuba

• Nguyen Hung

  Department of Computer Science and Systems Engineering, Graduate School of Engineering, Miyazaki Uni

• Yoshihara Ikuo

  Department of Computer Science and Systems Engineering, Faculty of Engineering, Miyazaki University

• Yamamori Kunihito

  Department of Computer Science and Systems Engineering, Faculty of Engineering, Miyazaki University

• Yasunaga Moritoshi

  Institute of Information Sciences and Electronics, Tsukuba University

• Yasunaga Moritoshi

  Graduate School Of Systems And Information Engineering University Of Tsukuba

• Yasunaga Moritoshi

  Institute Of Information Sciences And Electronics Tsukuba University

• Yasunaga Moritoshi

  The Institute Of Information Sciences And Electronics University Of Tsukuba

• Yasunaga Moritoshi

  Institute Of Information Science And Electronics University Of Tsukuba

• Yoshihara Ikuo

  Department Of Computer And Science And Systems Engineering Miyazaki University

• Kamimai Yoshiyuki

  Faculty Of Engineering University Of Miyazaki

• Yamamori Kunihito

  Department Of Computer And Science And Systems Engineering Miyazaki University

関連論文

• A New Three-Level Tree Data Structure for Representing TSP Tours in the Lin-Kernighan Heuristic(Optimization,Nonlinear Theory and its Applications)
• A New Data Structure for Lin-Kernighan Traveling Salesman Heuristic
• Greedy Genetic Algorithms for Symmetric and Asymmetric TSPs (特集 進化的計算)
• A GA-based method for multiple protein sequence alignment
• A parallel greedy GA for symmetric and asymmetric TSPs
• Directed Edge Recombination and Hybrid Genetic Algorithm for Asymmetric Traveling Salesman Problems
• Extracting Transcription Regulatory Elements in Dictyostelium Discoideum
• Finding Characteristic Patterns Embedded in Non-transcribed Region of Dictyostelium Discoideum by Computed Moire
• Feature Extraction from Non-transcribed Region of Dictyostelium Discoideum using Moire Picture
• The Kernel-Based Pattern Recognition System Designed by Genetic Algorithms(Special Issue on Function Integrated Information Systems)
• The Evolutionary Algorithm-Based Reasoning System(Special Issue on Function Integrated Information Systems)
• Optimal Camera Layout to Take Pictures for Indoor Landscape Using GA
• Development of Exon Region Extracting Method by GMDH and GA from DNA Sequences
• GMDH-GA Hybrid Model Extracting Exon Region from DNA Sequences
• Construction of GMDH-based Prediction model using GA
• GP-Based Method for Extracting Exons from DNA Sequence
• Evaluation of GP-based time series prediction
• Segmentation and GA-based Optimization of Transmission-Line on Printed Circuit Board
• English Pronunciation Reasoning by NN Considering Frequency Distribution of Phonemes
• Multi-Modal Neural Networks for Symbolic Sequence Pattern Classification(Biocybernetics, Neurocomputing)
• Prediction of Protein Secondary Structure Based on a Multi-modal Neural Network: with Modified Profiles of MSA and PSSM
• Development of a multi-modal nueral network for predicting protein secondary structure
• Research on identifying intron-exon boundaries in DNA sequences
• Design of Passive Suspension System of Railway Vehicles via Control Theory
• Performance Evaluation of Neural Network Hardware Using Time-Shared Bus and Integer Representation Architecture
• Optimization of Discrete Camera Position for Taking All Scenery Inside Buildings by GA
• Performance of Parallel Back-Propagation Algorithm on PC Cluster System
• Identification of Exon-Intron Boundary by Hidden Markov Model and Evaluation with the Human Genome
• High-speed Generation of Logic Function to Identify Exon-Intron Boundaries by Parallel GP
• Minimizing the Number of Cameras to Take Pictures of All the Indoor Landscapes Based on GA
• GA-based University Timetabling for Constraint Satisfaction
• Evaluation of Edge Assembly Crossover for Hybrid GA
• Mosaic Face Image Recognition on Multi-Layer Neural Network
• Comparison with defect compensation methods for freed-forward neural networks
• Model Building Method for Time Series with High Complexity Using Genetic Programming
• Timetabling for Satisfying Professors' Requirements and Students' Desires using Genetic Algorithm
• Timetabling for University Classes using Genetic Algorithm
• Improved edge recombination operators for genetic algorithms
• A High-Signal-Integrity PCB Trace Composed of Multiple Segments for GHz VLSI Packaging: Its Prototyping and Performance Analysis

もっと見る 閉じる

スポンサーリンク