Paper Info
Title
A two-level diploid genetic based algorithm for solving the family traveling salesman problem.
Abstract
In this paper, we consider the Family Traveling Salesman Problem (FTSP), which is a variant of the classical Traveling Salesman Problem (TSP). Given a partition of the nodes into a predefined number of clusters, called families, the aim of the FTSP is to find a minimum cost tour visiting a given number of nodes from each family. We describe a novel solution approach for solving the FTSP obtained by decomposing the problem into two smaller subproblems: a macro-level subproblem and a micro-level subproblem, and solving them separately. The goal of the first subproblem is to provide tours visiting the families using a classical genetic algorithm and a diploid genetic algorithm, while the aim of the second subproblem is to find the minimum-cost tour, corresponding to the above mentioned tours, visiting a given number of nodes from each family. The second subproblem is solved by transforming each global tour into a traveling salesman problem (TSP) which then is optimally computed using the Concorde TSP solver. The preliminary computational results on a usually used set of benchmark instances prove that our solution approach provides competitive solutions in comparison to the existing methods for solving the FTSP.
Year
DOI
Venue
2018
10.1145/3205455.3205545
GECCO
Keywords
Field
DocType
Combinatorial optimization, traveling salesman problem, generalized traveling salesman problem, family traveling salesman problem, diploid genetic algorithms
Mathematical optimization,Computer science,Combinatorial optimization,Travelling salesman problem,Solver,Partition (number theory),Genetic algorithm
Conference
ISBN
Citations 
PageRank 
978-1-4503-5618-3
0
0.34
References 
Authors
12
3
Name
Order
Citations
PageRank
Petrica C. Pop118327.86
Oliviu Matei24311.15
Camelia-Mihaela Pintea310216.15