TLDR: This paper introduces DRLHQ, a novel deep reinforcement learning approach to solve Capacitated Location-Routing Problems (CLRPs) and Open CLRPs (OCLRPs) in an end-to-end manner. By reformulating these complex optimization problems as a Markov Decision Process and employing a heterogeneous querying attention mechanism with dynamic masking, DRLHQ simultaneously handles facility location and vehicle routing decisions. Experimental results show DRLHQ provides superior solution quality and better generalization compared to existing traditional and DRL-based methods on various datasets.
The world of logistics and supply chain management constantly grapples with complex challenges, none more intricate than the Capacitated Location-Routing Problems (CLRPs). These problems demand simultaneous decisions on where to establish facilities (like warehouses or depots) and how to efficiently route vehicles to serve customers, all while adhering to various capacity constraints. Traditionally, these two critical decisions—location and routing—have often been tackled separately, leading to less-than-optimal outcomes because their interdependencies are overlooked.
A recent research paper, titled “An End-to-End Learning Approach for Solving Capacitated Location-Routing Problems,” introduces a groundbreaking solution using deep reinforcement learning (DRL). Authored by Chang-Hao Miao, Yun-Tian Zhang, Tong-Yu Wu, Fang Deng, and Chen Chen, this work presents DRL with heterogeneous query (DRLHQ), a novel method designed to solve both CLRP and its variant, the Open CLRP (OCLRP), in a unified, end-to-end fashion. This is a significant step forward, as it marks the first time an end-to-end learning approach has been proposed for CLRPs.
The Challenge of CLRPs
CLRPs are notoriously difficult to solve because they belong to a class of problems known as NP-hard combinatorial optimization problems. This means that as the number of facilities and customers increases, the computational time required to find an optimal solution grows exponentially. Traditional methods, such as exact algorithms and heuristics, often struggle with large-scale instances. Exact methods can be computationally expensive, while heuristic methods, though faster, often rely on handcrafted rules and expert domain knowledge, limiting their adaptability and solution quality.
Previous attempts to apply deep reinforcement learning to CLRPs typically broke the problem down into two sequential sub-problems: first locating facilities, then planning routes. However, this sequential approach fails to capture the strong links between location and routing decisions, leading to suboptimal solutions.
DRLHQ: A Unified Approach
The DRLHQ method addresses these limitations by reformulating CLRPs as a Markov Decision Process (MDP). This allows the model to consider facility location and vehicle routing decisions simultaneously within a single framework. The core of DRLHQ lies in its encoder-decoder structure, enhanced by several innovative components:
-
Heterogeneous Querying Attention Mechanism: This novel mechanism dynamically adapts to different decision-making stages. When a vehicle route (subtour) is completed, it constructs a ‘location query’ to decide the next depot to open. During an ongoing route, it uses a ‘routing query’ to select the next customer to visit. This adaptive querying helps the model better understand and manage the intricate relationships between location and routing decisions.
-
Dynamic Masking Mechanism: To ensure that the solutions generated are feasible and adhere to all constraints (like vehicle and depot capacities, and ensuring each customer is visited once), DRLHQ employs a dynamic masking mechanism. This mechanism intelligently masks out invalid choices at each step of the decision-making process, preventing the model from making illegal moves.
-
Enhanced Inference Strategies: The researchers also refined existing techniques like instance augmentation, extending it to a more general form that accounts for rotational invariance in problem instances. Additionally, they integrated a simulation-based beam search (SBS) as a post-hoc search strategy to further improve solution quality.
Impressive Results and Generalization
The effectiveness of DRLHQ was rigorously tested on both synthetic and benchmark datasets for CLRP and OCLRP. The experimental results were compelling: DRLHQ consistently outperformed traditional exact solvers (like Gurobi) and heuristic methods (such as ILS, SAH, and TBSA), especially on larger problem scales where traditional methods struggled to find high-quality solutions within reasonable time limits. For instance, on CLRP100 instances, DRLHQ delivered high-quality solutions in under a second, while Gurobi took significantly longer and yielded inferior results.
Furthermore, DRLHQ demonstrated superior generalization performance. It maintained its effectiveness when applied to larger problem scales (up to 200 customer nodes) using models trained on smaller datasets, and also performed exceptionally well on cross-distribution benchmark datasets, which have different node distributions, customer demands, and depot characteristics compared to the synthetic training data. This indicates the model’s robustness and applicability to real-world scenarios.
Also Read:
- Optimizing Complex Cyber-Physical Systems with Logic-Informed Reinforcement Learning
- Optimizing Retail Pricing: How Graph Attention Enhances Multi-Agent Reinforcement Learning
Impact and Future Directions
This research provides a robust, end-to-end learning approach for solving complex location-routing problems, offering significant potential for applications in supply-chain management, emergency response, and disaster relief. By integrating location and routing decisions, DRLHQ promises more efficient and cost-effective logistical operations.
The authors plan to extend this work by applying DRLHQ to even more complex variants of routing problems, enhancing its generalization across different problem sizes and distributions, and incorporating uncertain factors often present in real-world applications. For more in-depth technical details, you can refer to the full paper available at arXiv:2511.02525.
