Introduction
The Vehicle Routing Problem with Two-Dimensional Loading (2L-CVRP) is a complex combinatorial optimization problem that integrates routing with rectangular item packing. The addition of Last-In-First-Out (LIFO) constraints further complicates the problem, as items must be accessible without rearranging the load. Standard exact solvers rely on Column Generation (CG), where the primary computational bottleneck is the "Pricing Problem"—the repeated generation and feasibility checking of potential routes against packing constraints.
The Neural Column Generation Framework
To address this bottleneck, the authors propose Neural Column Generation (NCG). This framework integrates a machine learning model as a fast feasibility "gatekeeper" within the CG loop. To maintain mathematical exactness, the system includes mechanisms to handle classification errors. False positives (infeasible routes labeled as feasible) are corrected via "false-positive cuts" in the Master Problem. False negatives (feasible routes labeled as infeasible) are mitigated by a secondary check to ensure the global optimum remains reachable.
Neural Network Architecture
The predictive model is specifically designed to reflect the physical structure of the problem.
The architecture uses Multi-Head Attention to process items for a single customer, as their internal loading order is flexible. Conversely, a Gated Recurrent Unit (GRU) processes the sequence of customer stops to capture the strict dependencies imposed by LIFO constraints. Data augmentation through item shuffling ensures the model learns permutation invariance for items within a single stop.
Results and Discussion
The NCG approach was evaluated on standard benchmarks from Iori et al. (2007). The model achieved approximately 95% accuracy in feasibility prediction.
Empirical results demonstrate that NCG delivered a median performance improvement of 29.79% over state-of-the-art exact solvers. Notably, the NCG framework successfully solved instance 2304, a previously open problem in the literature that had caused memory overflows in prior solvers.
Conclusion
By combining neural networks with classical optimization, NCG offers a scalable path for solving complex logistics problems. This "filter" philosophy provides the best of both worlds: the speed of machine learning and the mathematical guarantees of exact solvers. Future work may extend this to 3D loading or more complex temporal constraints.
Summary updated