Learning to Optimize: Joint Routing and Flow Allocation on Sparse Non-Euclidean Networks

Research Problem

Modern logistics, particularly container liner shipping, requires the simultaneous optimization of cyclic vessel routing and cargo flow allocation. Unlike idealized Euclidean models, real-world industrial networks are sparse, directed, and non-Euclidean. These systems must also manage cross-cycle service—where cargo is picked up in one voyage and delivered in another—while adhering to strict capacity limits and soft due-date commitments. Traditional exact methods like mixed-integer programming struggle with the computational complexity of these constraints, while existing reinforcement learning solvers are typically designed for fully connected, planar networks and fail to handle the complexities of sparse, cyclic logistics.

The DCGA Approach

The authors propose the Double-Channel Graph Attention (DCGA) framework to address these challenges. The core innovation is a dual-channel architecture that separates physical network reachability from supply-demand service logic during feature extraction, preventing the representational collapse often seen in complex, sparse graphs. To ensure feasibility, the model uses a simulator-coupled, constraint-informed decoder. This decoder employs step-wise hard masks to enforce operational constraints, such as capacity and route validity, without requiring computationally expensive post-hoc repairs. By using an origin-destination (OD)-indexed action space, the model naturally handles cross-cycle service and optional cargo fulfillment.

DCGA demonstrates state-of-the-art performance on the LinerLib maritime benchmark. It consistently outperforms traditional mathematical optimization (e.g., Gurobi), advanced metaheuristics (e.g., LKH3, ALNS), and existing neural routing solvers. The performance gap between DCGA and other methods widens as the problem size increases, highlighting the model's scalability. Furthermore, DCGA achieves seconds-level inference, making it highly suitable for real-time, large-scale industrial decision-making. Extensive ablation studies confirm that the double-channel architecture and the constraint-guided decoding mechanism are both essential for the model's superior performance.