An End-to-End Learning Approach for Solving Capacitated Location-Routing Problems

Researchers propose DRLHQ, a deep reinforcement learning approach with heterogeneous query attention mechanisms to solve capacitated location-routing problems (CLRPs) and their open variants. This marks the first end-to-end learning framework for CLRPs, demonstrating superior performance over traditional and DRL-based baselines on benchmark datasets.

This research addresses a fundamental challenge in combinatorial optimization where location placement and vehicle routing decisions must be made simultaneously under capacity constraints. The paper introduces an innovative deep reinforcement learning solution that reformulates CLRPs as a Markov decision process, enabling the model to handle the complex interdependencies between location and routing choices through a novel heterogeneous querying attention mechanism.

Capacitated location-routing problems represent a significant class of real-world optimization challenges relevant to logistics, supply chain management, and facility planning. Traditional exact methods struggle with problem scalability, while previous DRL applications focused primarily on vehicle routing without addressing the simultaneous location decision component. The emergence of transformer-based architectures and attention mechanisms has created new opportunities for handling such interdependent decisions more effectively.

The practical implications extend across industries dependent on network optimization. Logistics companies, e-commerce platforms, and public service organizations could benefit from improved solutions that reduce operational costs while maintaining service quality. The framework's generalization capabilities across both synthetic and real benchmark datasets suggest potential for practical deployment across diverse problem instances and scales.

The research direction matters for the broader AI optimization community as it demonstrates how specialized attention mechanisms can be tailored to specific problem structures. Future work likely involves extending this approach to dynamic variants, larger problem instances, and real-world constraints such as time windows and heterogeneous vehicle types. The end-to-end learning paradigm may inspire similar approaches for other classical combinatorial optimization problems.

• →DRLHQ introduces the first end-to-end deep reinforcement learning framework specifically designed for capacitated location-routing problems.
• →A heterogeneous querying attention mechanism dynamically adapts to different decision-making stages, handling complex interdependencies between location and routing choices.
• →The approach outperforms both traditional optimization methods and existing DRL baselines on benchmark datasets.
• →The reformulation as a Markov decision process provides a general modeling framework adaptable to other DRL-based optimization methods.
• →Superior generalization performance suggests practical applicability across diverse problem instances and scales.