Paper Info
Title
Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
Abstract
We introduce a new combinatorial optimization problem, which is a generalization of the Traveling Salesman Problem (TSP) and which we call Traveling Salesman Problem of Second Order (2-TSP). It is motivated by an application in bioinformatics, especially the Permuted Variable Length Markov model. We propose seven elementary heuristics and two exact algorithms for the 2-TSP, some of which are generalizations of similar algorithms for the Asymmetric Traveling Salesman Problem (ATSP), some of which are new ideas. Finally we experimentally compare the algorithms for random instances and real instances from bioinformatics. Our experiments show that for the real instances most heuristics lead to optimum or almost-optimum solutions, and for the random instances the exact algorithms need less time than for the real instances.
Year
DOI
Venue
2008
10.1007/978-3-540-85097-7_20
COCOA
Keywords
Field
DocType
random instance,second order,elementary heuristics,heuristics lead,real instance,experimental study,permuted variable length markov,new idea,new combinatorial optimization problem,exact algorithm,salesman problem,markov model,traveling salesman problem,assignment problem,discrete mathematics
Traveling purchaser problem,Bottleneck traveling salesman problem,Combinatorics,Computer science,Algorithm,Combinatorial optimization,Cross-entropy method,Travelling salesman problem,Christofides algorithm,2-opt,Lin–Kernighan heuristic
Conference
Volume
ISSN
Citations 
5165
0302-9743
12
PageRank 
References 
Authors
0.60
13
2
Name
Order
Citations
PageRank
Gerold Jäger111314.66
P. Molitor221118.50