LMask: Learn to Solve Constrained Routing Problems with Lazy Masking
Summary: arXiv:2505.17938v2 Announce Type: replace-cross
Abstract
Routing problems are canonical combinatorial optimization tasks with wide-ranging applications in logistics, transportation, and supply chain management. However, solving these problems becomes significantly more challenging when complex constraints are involved. In this paper, we propose LMask, a novel learning framework that utilizes dynamic masking to generate high-quality feasible solutions for constrained routing problems.
Introduction
Routing problems, such as the Traveling Salesman Problem (TSP), are fundamental challenges in operations research and artificial intelligence. These problems often become more intricate due to the presence of constraints that must be satisfied. Traditional methods for solving routing problems can struggle with these complexities, leading to suboptimal solutions. Our research introduces LMask, a new approach designed to effectively tackle these constrained routing challenges through innovative techniques.
Key Features of LMask
LMask stands out due to several key features that enhance its effectiveness in solving constrained routing problems:
- LazyMask Decoding: This novel decoding method refines feasibility masks lazily, allowing for a more efficient search process. By incorporating a backtracking mechanism, LMask can better explore feasible solutions without exhaustive searches.
- Refinement Intensity Embedding: To address potential representation ambiguities caused by backtracking, LMask utilizes refinement intensity embedding. This technique encodes the search trace into the model, improving the quality of the solutions generated.
- Backtracking Budget: LMask sets a backtracking budget during the decoding process to reduce sampling costs. This budget helps maintain computational efficiency while still striving for high-quality outputs.
- Penalty for Constraint Violations: To counteract the infeasibility that may arise from the set budget, LMask incorporates penalties for constraint violations in its loss function during training. This ensures that the model learns to prioritize feasible solutions.
Theoretical Guarantees
One of the significant advancements of LMask is its theoretical underpinning. We provide guarantees for both the validity and probabilistic optimality of our approach. These guarantees reinforce the reliability of LMask in generating feasible solutions even in complex scenarios.
Experimental Results
To validate the effectiveness of LMask, we conducted extensive experiments on two well-known routing problems:
- Traveling Salesman Problem with Time Windows (TSPTW): LMask demonstrated superior performance in generating feasible routes within specified time constraints.
- Traveling Salesman Problem with Draft Limits (TSPDL): The results indicated that LMask outperformed existing neural methods, achieving state-of-the-art feasibility rates and solution quality.
Conclusion
LMask presents a promising new approach for solving constrained routing problems through innovative techniques such as LazyMask decoding and refinement intensity embedding. Our findings indicate that LMask not only excels in feasibility but also in solution quality, making it a valuable tool for applications in logistics and supply chain management.