Menu
Home
Contact us
Stats
Categories
Calendar
Toggle Wiki
Wiki Home
Last Changes
Rankings
List pages
Orphan pages
Sandbox
Print
Toggle Image Galleries
Galleries
Rankings
Toggle Articles
Articles home
List articles
Rankings
Toggle Blogs
List blogs
Rankings
Toggle Forums
List forums
Rankings
Toggle File Galleries
List galleries
Rankings
Toggle Maps
Mapfiles
Toggle Surveys
List surveys
Stats
ITHEA Classification Structure > G. Mathematics of Computing  > G.2 DISCRETE MATHEMATICS  > G.2.1 Combinatorics 
ITHEA Classification Structure > I. Computing Methodologies  > I.2 ARTIFICIAL INTELLIGENCE  > I.2.8 Problem Solving, Control Methods, and Search 
DECOMPOSITION METHODS FOR LARGE-SCALE TSP
By: Roman Bazylevych et al. (3667 reads)
Rating: (1.00/10)

Abstract: Decomposition methods for solving large-scale Traveling Salesman Problem (TSP) are presented. Three approaches are proposed: macromodeling for clustered TSP as well as extending and “ring” methods for arbitrary points’ distribution. Four stages of the problem solving include partitioning of the input set of points into small subsets, finding the partial high quality solutions in the subsets, merging the partial solutions into the complete initial solution and optimizing the final solution. Experimental investigations as well as the comparative analysis of the results and their effectiveness estimation in terms of quality and running time were conducted. The suggested approaches provide substantial reduction in the running time in comparison with the existing heuristic algorithms. The quality loss is small. The problem instances up to 200,000 points were investigated. The TSP is extensively applied in transportation systems analysis, printed circuit boards, VLSI, SoC and NoC computer-aided design, testing and manufacturing, laser cutting of plastics and metals, protein structure research, continuous line drawings, X-ray crystallography as well as in number of other fields.

Keywords: traveling salesman problem, combinatorial NP-hard problems, decomposition, large-scale.

ACM Classification Keywords: G.2.1 Combinatorics - Combinatorial algorithms; I.2.8 Problem Solving, Control Methods, and Search - Heuristic methods.

Link:

DECOMPOSITION METHODS FOR LARGE-SCALE TSP

Roman Bazylevych, Marek Pałasiński, Roman Kutelmakh, Bohdan Kuz, Lubov Bazylevych

http://www.foibg.com/ibs_isc/ibs-26/ibs-26-p10.pdf

Print
G.2.1 Combinatorics
article: RANDOMIZED SET SYSTEMS CONSTRAINED BY THE DISCRETE TOMOGRAPHY · A NEW ALGORITM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM · ON THE STRUCTURE OF MAXIMUM INDEPENDENT SETS IN BIPARTITE GRAPHS · SOME PROPERTIES IN MULTIDIMENSIONAL MULTIVALUED DISCRETE TORUS · ON PROBLEM OF ADEQUACY OF MULTISET MATHEMATICAL MODELS · SPREADING THE MOORE - PENROSE PSEUDO INVERSE ON MATRICES EUCLIDEAN SPACES: ... · VECTORS AND MATRIXES IN GROUPING INFORMATION PROBLEM · CHOICE OF DIAGNOSTIC DECISION MAKING IN MEDICINE AND INTERVENTION MISTAKE ... · RECURRENT PROCEDURE IN SOLVING THE GROUPING INFORMATION PROBLEM IN APPLIED... · ‘FEATURE VECTORS’ IN GROUPING INFORMATION PROBLEM IN APPLIED MATHEMATICS: .. · DECOMPOSITION METHODS FOR LARGE-SCALE TSP · ON THE DISCRETIZATION OF DISTANCE GEOMETRY PROBLEMS · REGULAR INVERSIVE POLYTOPES · LOGARITHMIC DISTANCES IN GRAPHS · FUZZY SETS AS A MEAN FOR UNCERTAINTY HANDLING: MATH, APPLIED MATH, HEURISTICS · FUZZY SETS: MATH, APPLIED MATH, HEURISTICS? PROBLEMS AND INTERPRETATIONS · CROSS INTERSECTION SEQUEL OF DISCRETE ISOPERIMETRY1 · GENERATING MORE BOUNDARY ELEMENTS OF SUBSET PROJECTIONS · MULTICRITERION PROBLEMS ON THE COMBINATORIAL SET OF POLYARRANGEMENTS · CHAIN SPLIT OF PARTIALLY ORDERED SET OF K-SUBSETS · SOLVING LARGE SYSTEMS OF BOOLEAN EQUATIONS · LAGRANGEAN APPROXIMATION FOR COMBINATORIAL INVERSE PROBLEMS · MULTICRITERION PROBLEMS ON THE COMBINATORIAL SET OF POLYARRANGEMENTS · DESCRIPTION REDUCTION FOR RESTRICTED SETS OF (0,1) MATRICES 1 · DECOMPOSITION OF BOOLEAN FUNCTIONS – RECOGNIZING A GOOD SOLUTION BY TRACES · THE BOUNDARY DESCRIPTORS OF THE n-DIMENSIONAL UNIT CUBE SUBSET PARTITIONING1 · RANDOMIZED PARALLELIZATION – A NEW METHOD FOR SOLVING ... · OPTIMIZATION OF ATM TELECOMMUNICATION NETWORKS · VECTOR COMBINATORIAL PROBLEMS IN A SPACE OF COMBINATIONS ... ·
I.2.8 Problem Solving, Control Methods, and Search
article: DEVELOPMENT AND ANALYSIS OF GENETIC ALGORITHM FOR TIME SERIES FORECASTING ... · TWO-LEVEL GENETIC ALGORITHM FOR PROGRAMMABLE LOGIC DEVICES RECONFIGURATION · ADAPTIVE FUZZY PROBABILISTIC CLUSTERING OF INCOMPLETE DATA · Criteria investigations in ant colony optimization algorithm for travelling ... · CRITERIA INVESTIGATIONS IN ANT COLONY OPTIMIZATION ALGORITHM FOR TRAVELLING SALE · АЛГОРИТМ ПОСТРОЕНИЯ ВЫПУКЛОГО ПРОДОЛЖЕНИЯ · ADAPTIVE CLUSTERING OF INCOMPLETE DATA USING NEURO-FUZZY KOHONEN NETWORK · THE EFFECT OF INTRODUCTION OF THE NON-LINEAR CALIBRATION FUNCTION AT THE ... · DECOMPOSITION METHODS FOR LARGE-SCALE TSP · INFORMATIONAL-PARAMETRIC MODEL OF SIGN LANGUAGE FINGERSPELLING UNITS · CONSTRUCTION OF A REALISTIC MOVEMENT ON THE 3D HUMAN MODEL FOR STUDYING AND ... · ПРОГНОЗИРОВАНИЕ ДИНАМИКИ ПОПОЛНЕНИЯ ФОНДО� · SELF-ORGANIZING ROUTING ALGORITHM FOR WIRELESS SENSORS NETWORKS (WSN) USING ... · COMPUTER TECHNOLOGY FOR SIGN LANGUAGE MODELLING · NEURAL NETWORK BASED OPTIMAL CONTROL WITH CONSTRAINTS · LOGICAL MODELS OF COMPOSITE DYNAMIC OBJECTS CONTROL · LIMIT BEHAVIOUR OF DYNAMIC RULE-BASED SYSTEMS ·
Login
[ register | I forgot my password ]
World Clock
Powered by Tikiwiki Powered by PHP Powered by Smarty Powered by ADOdb Made with CSS Powered by RDF powered by The PHP Layers Menu System
RSS Wiki RSS Blogs rss Articles RSS Image Galleries RSS File Galleries RSS Forums RSS Maps rss Calendars
[ Execution time: 0.09 secs ]   [ Memory usage: 7.55MB ]   [ GZIP Disabled ]   [ Server load: 0.45 ]
Powered by Tikiwiki CMS/Groupware