A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem
This paper proposes a hybrid genetic algorithm for solving the Multiple Traveling Salesman Problem (mTSP) to minimize the length of the longest tour. The genetic algorithm utilizes a TSP sequence as the representation of each individual, and a dynamic programming algorithm is employed to evaluate the individual and find the optimal mTSP solution for the given sequence of cities. A novel crossover operator is designed to combine similar tours from two parents and offers great diversity for the population. For some of the generated offspring, we detect and remove intersections between tours to obtain a solution with no intersections. This is particularly useful for the min-max mTSP. The generated offspring are also improved by a self-adaptive random local search and a thorough neighborhood search. Our algorithm outperforms all existing algorithms on average, with similar cutoff time thresholds, when tested against multiple benchmark sets found in the literature. Additionally, we improve the best-known solutions for $21$ out of $89$ instances on four benchmark sets.
Code (0)
등록된 구현이 없습니다.
Tasks
DiversityTraveling Salesman ProblemSimilar Papers 제목 키워드 기반
A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone
There are emerging transportation problems known as the Traveling Salesman Problem with Drone (TSPD) and the Flying Sidekick Traveling Salesman Problem (FSTSP) that involve using a drone in conjunction with a truck for p…
Decision MakingTraveling Salesman ProblemParallel Genetic Algorithm to Solve Traveling Salesman Problem on MapReduce Framework using Hadoop Cluster
Traveling Salesman Problem (TSP) is one of the most common studied problems in combinatorial optimization. Given the list of cities and distances between them, the problem is to find the shortest tour possible which visi…
Combinatorial OptimizationTraveling Salesman ProblemReinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem
In this paper, we propose a new method called the Reinforced Hybrid Genetic Algorithm (RHGA) for solving the famous NP-hard Traveling Salesman Problem (TSP). Specifically, we combine reinforcement learning with the well-…
DiversityQ-Learningreinforcement-learningReinforcement Learning+2Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem
The Multiple Traveling Salesman Problem (mTSP) extends the Traveling Salesman Problem to m tours that start and end at a common depot and jointly visit all customers exactly once. In the min-max variant, the objective is…
Reinforcement LearningAn improved genetic algorithm with a local optimization strategy and an extra mutation level for solving traveling salesman problem
The Traveling salesman problem (TSP) is proved to be NP-complete in most cases. The genetic algorithm (GA) is one of the most useful algorithms for solving this problem. In this paper a conventional GA is compared with a…
Traveling Salesman Problem