litlas
Log inCreate account

Attention, Learn to Solve Routing Problems!

Authors: Wouter Kool, Herke van Hoof, Max Welling - International Conference on Learning Representations, ICLR 2018 cited by 1,676

The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention layers with benefits over the Pointer Network and we show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function. We significantly improve over recent learned heuristics for the Travelling Salesman Problem (TSP), getting close to optimal results for problems up to 100 nodes. With the same hyperparameters, we learn strong heuristics for two variants of the Vehicle Routing Problem (VRP), the Orienteering Problem (OP) and (a stochastic variant of) the Prize Collecting TSP (PCTSP), outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms.

Simple StatisticalGradient-Following…Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement LearningNo free lunch theoremsfor optimizationNo free lunch theorems for optimizationDeep learningDeep learningPointer NetworksPointer NetworksHuman-level controlthrough deep…Human-level control through deep reinforcement learningDeep Residual Learningfor Image RecognitionDeep Residual Learning for Image RecognitionLayer NormalizationLayer NormalizationNeural CombinatorialOptimization with…Neural Combinatorial Optimization with Reinforcement LearningA Note on LearningAlgorithms for Quadrati…A Note on Learning Algorithms for Quadratic Assignment with Graph Neural NetworksMastering the game of Gowithout human knowledgeMastering the game of Go without human knowledgeAutomaticdifferentiation in…Automatic differentiation in PyTorchLearning the MultipleTraveling Salesmen…Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling NetworksLearning the MultipleTraveling Salesmen…Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling NetworksHow to Evaluate MachineLearning Approaches for…How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman ProblemMachine Learning forCombinatorial…Machine Learning for Combinatorial Optimization: a Methodological Tour d'HorizonMulti-Vehicle RoutingProblems with Soft Time…Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning ApproachEnd-to-End ConstrainedOptimization Learning…End-to-End Constrained Optimization Learning: A SurveyMaximum Entropy WeightedIndependent Set Pooling…Maximum Entropy Weighted Independent Set Pooling for Graph Neural NetworksGraph Neural NetworkGuided Local Search for…Graph Neural Network Guided Local Search for the Traveling Salesperson ProblemDAN: DecentralizedAttention-based Neural…DAN: Decentralized Attention-based Neural Network to Solve the MinMax Multiple Traveling Salesman ProblemFast Approximations forJob Shop Scheduling: A…Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning MethodUDC: A Unified NeuralDivide-and-Conquer…UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization ProblemsDistance-aware AttentionReshaping: Enhance…Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing ProblemsMulti-Start TeamOrienteering Problem fo…Multi-Start Team Orienteering Problem for UAS Mission Re-Planning with Data-Efficient Deep Reinforcement LearningAttention, Learn toSolve Routing Problems!Attention, Learn to Solve Routing Problems!Earlier referencesFocus paperCiting papersOlderNewer

Click a node to pin it, click the empty canvas to go back to this paper, or hover to preview. Open a node’s page from its title.