A New Three-Level Tree Data Structure for Representing TSP Tours in the Lin-Kernighan Heuristic(Optimization,<Special Section>Nonlinear Theory and its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• Lin-Kernighan (LK) is the most powerful local search for the Traveling Salesman Problem (TSP). The choice of data structure for tour representation plays a vital role in LK's performance. Binary trees are asymptotically the best tour representation but they perform empirically best only for TSPs with one million or more cities due to a large overhead. Arrays and two-level trees are used for smaller TSPs. This paper proposes a new three-level tree data structure for tour representation. Although this structure is asymptotically not better than the binary tree structure, it performs empirically better than the conventional structures for TSPs having from a thousand to three million cities.

• 社団法人電子情報通信学会の論文
• 2007-10-01

著者

• Nguyen H

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

• NGUYEN Hung

  Graduate School of Engineering, University of Miyazaki

• YOSHIHARA Ikuo

  Faculty of Engineering, University of Miyazaki

• YAMAMORI Kunihito

  Faculty of Engineering, University of Miyazaki

• YASUNAGA Moritoshi

  Graduate School of Systems and Information Engineering, University of Tsukuba

• 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

• Yoshihara Ikuo

  Faculty Of Engineering Miyazaki University

• Kamimai Yoshiyuki

  Faculty Of Engineering University Of Miyazaki

• Yamamori Kunihito

  Faculty Of Engineering Miyazaki University

• Nguyen Hung

  Graduate School Of Engineering Miyazaki University

関連論文

• Characteristics of International Grain Price Movements under the High Oil Prices : Toward Policy Implications
• 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)
• 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
• A Physiology Activity Value Prediction of Functional Foods Using Bayes Classifier
• An Efficient Job Scheduling Algorithm for Grid Environment with Communication Delay
• GA-based University Timetabling for Constraint Satisfaction
• Estimating Physiology Activity of Functional Foods with Self-Organizing Map
• Evaluation of Edge Assembly Crossover for Hybrid GA
• Timetabling for University Classes using Genetic Algorithm
• A High-Signal-Integrity PCB Trace Composed of Multiple Segments for GHz VLSI Packaging: Its Prototyping and Performance Analysis

もっと見る 閉じる

スポンサーリンク