Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning
Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution. To discover diverse yet high-quality solutions for Multi-Solution TSP (MSTSP), we propose a novel deep reinforcement learning based neural solver, which is primarily featured by an encoder-decoder structured policy. Concretely, on the one hand, a Relativization Filter (RF) is designed to enhance the robustness of the encoder to affine transformations of the instances, so as to potentially improve the quality of the found solutions. On the other hand, a Multi-Attentive Adaptive Active Search (MA3S) is tailored to allow the decoders to strike a balance between the optimality and diversity. Experimental evaluations on benchmark instances demonstrate the superiority of our method over recent neural baselines across different metrics, and its competitive performance against state-of-the-art traditional heuristics with significantly reduced computational time, ranging from $1.3\times$ to $15\times$ faster. Furthermore, we demonstrate that our method can also be applied to the Capacitated Vehicle Routing Problem (CVRP).
Code (1)
Tasks
DecoderDeep Reinforcement LearningDiversitySimilar Papers 제목 키워드 기반
On Learning Paradigms for the Travelling Salesman Problem
We explore the impact of learning paradigms on training deep neural networks for the Travelling Salesman Problem. We design controlled experiments to train supervised learning (SL) and reinforcement learning (RL) models …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Study of Some Recent Crossovers Effects on Speed and Accuracy of Genetic Algorithm, Using Symmetric Travelling Salesman Problem
The Travelling Salesman Problem (TSP) is one of the most famous optimization problems. The Genetic Algorithm (GA) is one of metaheuristics that have been applied to TSP. The Crossover and mutation operators are two impor…
A self-adaptive genetic algorithm for the flying sidekick travelling salesman problem
This paper presents a novel approach to solving the Flying Sidekick Travelling Salesman Problem (FSTSP) using a state-of-the-art self-adaptive genetic algorithm. The Flying Sidekick Travelling Salesman Problem is a combi…
Random-Key Cuckoo Search for the Travelling Salesman Problem
Combinatorial optimization problems are typically NP-hard, and thus very challenging to solve. In this paper, we present the random key cuckoo search (RKCS) algorithm for solving the famous Travelling Salesman Problem (T…
Combinatorial OptimizationGenetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem
We propose a new genetic algorithm with optimal recombination for the asymmetric instances of travelling salesman problem. The algorithm incorporates several new features that contribute to its effectiveness: (i) Optimal…