paper-with-me

홈 › Papers

Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning

2025-01-01 · Qi Li, Zhiguang Cao, Yining Ma, Yaoxin Wu, Yue-Jiao Gong

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).

📄 PDF Abstract BibTeX arXiv:2501.00884

Code (1)

LiQisResearch/KDD--RF-MA3S 공식 구현 pytorch

Tasks

DecoderDeep Reinforcement LearningDiversity

Similar Papers 제목 키워드 기반

On Learning Paradigms for the Travelling Salesman Problem

2019-10-16 · Chaitanya K. Joshi, Thomas Laurent, Xavier Bresson

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

2015-04-10 · Hassan Ismkhan, Kamran Zamanifar

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

2023-10-23 · Ted Pilcher

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

2016-04-14 · Aziz Ouaarab, B. Ahiod, Xin-She Yang

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 Optimization

Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem

2017-06-21 · A. V. Eremeev, Yu. V. Kovalenko

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…