Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning

Abstract

In this work, we introduce Graph Pointer Networks (GPNs) trained using reinforcement learning (RL) for tackling the traveling salesman problem (TSP). GPNs build upon Pointer Networks by introducing a graph embedding layer on the input, which captures relationships between nodes. Furthermore, to approximate solutions to constrained combinatorial optimization problems such as the TSP with time windows, we train hierarchical GPNs (HGPNs) using RL, which learns a hierarchical policy to find an optimal city permutation under constraints. Each layer of the hierarchy is designed with a separate reward function, resulting in stable training. Our results demonstrate that GPNs trained on small-scale TSP50/100 problems generalize well to larger-scale TSP500/1000 problems, with shorter tour lengths and faster computational times. We verify that for constrained TSP problems such as the TSP with time windows, the feasible solutions found via hierarchical RL training outperform previous baselines. In the spirit of reproducible research we make our data, models, and code publicly available.

References in corpus (5)

• Learning Combinatorial Optimization Algorithms over Graphs
• Neural Combinatorial Optimization with Reinforcement Learning
• Data-Efficient Hierarchical Reinforcement Learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Attention, Learn to Solve Routing Problems!

Cited by in corpus (18)

• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Location-routing Optimisation for Urban Logistics Using Mobile Parcel Locker Based on Hybrid Q-Learning Algorithm
• Route Planning for Last-Mile Deliveries Using Mobile Parcel Lockers: A Hybrid Q-Learning Network Approach
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• CLARE: A Semi-supervised Community Detection Algorithm
• Predicting Drivers' Route Trajectories in Last-Mile Delivery Using A Pair-wise Attention-based Pointer Neural Network
• Attention-based UAV Trajectory Optimization for Wireless Power Transfer-assisted IoT Systems
• Hybrid Pointer Networks for Traveling Salesman Problems Optimization
• Learning for routing: A guided review of recent developments and future directions
• Generalization in Deep RL for TSP Problems via Equivariance and Local Search
• Learning Vehicle Routing Problems using Policy Optimisation
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning
• Curriculum learning for multilevel budgeted combinatorial problems
• A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem
• Bilevel Learning Model Towards Industrial Scheduling
• Learning Combinatorial Node Labeling Algorithms
• Fast Approximate Solutions using Reinforcement Learning for Dynamic Capacitated Vehicle Routing with Time Windows