Learning for routing: A guided review of recent developments and future directions

Abstract

This paper reviews the current progress in applying machine learning (ML) tools to solve NP-hard combinatorial optimization problems, with a focus on routing problems such as the traveling salesman problem (TSP) and the vehicle routing problem (VRP). Due to the inherent complexity of these problems, exact algorithms often require excessive computational time to find optimal solutions, while heuristics can only provide approximate solutions without guaranteeing optimality. With the recent success of machine learning models, there is a growing trend in proposing and implementing diverse ML techniques to enhance the resolution of these challenging routing problems. We propose a taxonomy categorizing ML-based routing methods into construction-based and improvement-based approaches, highlighting their applicability to various problem characteristics. This review aims to integrate traditional OR methods with state-of-the-art ML techniques, providing a structured framework to guide future research and address emerging VRP variants.

Accepted for publication in Transportation Research Part E: Logistics and Transportation Review

References in corpus (41)

• A Comprehensive Survey on Graph Neural Networks
• Learning Combinatorial Optimization Algorithms over Graphs
• Deep Reinforcement Learning for Multi-objective Optimization
• Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• The Reversible Residual Network: Backpropagation Without Storing Activations
• Deep Reinforcement Learning for Electric Vehicle Routing Problem with Time Windows
• Challenges and Opportunities in Quantum Optimization
• Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning
• Learning to Perform Local Rewriting for Combinatorial Optimization
• Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
• Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning
• 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
• The Transformer Network for the Traveling Salesman Problem
• Efficient Neural Neighborhood Search for Pickup and Delivery Problems
• Learning Collaborative Policies to Solve NP-hard Routing Problems
• Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems
• Predicting Drivers' Route Trajectories in Last-Mile Delivery Using A Pair-wise Attention-based Pointer Neural Network
• Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem
• Recent Advances in Vehicle Routing with Stochastic Demands: Bayesian Learning for Correlated Demands and Elementary Branch-Price-and-Cut
• Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach
• DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization
• Evaluation of OpenAI o1: Opportunities and Challenges of AGI
• Pareto Set Learning for Neural Multi-objective Combinatorial Optimization
• Collaborative electric vehicle routing with meet points
• DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
• Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt
• BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
• Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem
• Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning
• Generalization in Deep RL for TSP Problems via Equivariance and Local Search
• Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
• Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?
• Less Is More -- On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP
• Exploring Combinatorial Problem Solving with Large Language Models: A Case Study on the Travelling Salesman Problem Using GPT-3.5 Turbo
• Self-Improved Learning for Scalable Neural Combinatorial Optimization
• A GREAT Architecture for Edge-Based Graph Problems Like TSP
• Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problems
• Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routes