Learning to Handle Complex Constraints for Vehicle Routing Problems

• URL: http://arxiv.org/abs/2410.21066v1
• Date: Mon, 28 Oct 2024 14:26:54 GMT
• Title: Learning to Handle Complex Constraints for Vehicle Routing Problems
• Authors: Jieyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, Jie Zhang,
• Abstract summary: Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. Recent neural methods excel in constructing solutions based on feasibility masking, but struggle with handling complex constraints. We propose a novel Proactive Infeasibility Prevention framework to advance the capabilities of neural methods towards more complex VRPs.
• Score: 26.354311541533754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. While recent neural methods excel in constructing solutions based on feasibility masking, they struggle with handling complex constraints, especially when obtaining the masking itself is NP-hard. In this paper, we propose a novel Proactive Infeasibility Prevention (PIP) framework to advance the capabilities of neural methods towards more complex VRPs. Our PIP integrates the Lagrangian multiplier as a basis to enhance constraint awareness and introduces preventative infeasibility masking to proactively steer the solution construction process. Moreover, we present PIP-D, which employs an auxiliary decoder and two adaptive strategies to learn and predict these tailored masks, potentially enhancing performance while significantly reducing computational costs during training. To verify our PIP designs, we conduct extensive experiments on the highly challenging Traveling Salesman Problem with Time Window (TSPTW), and TSP with Draft Limit (TSPDL) variants under different constraint hardness levels. Notably, our PIP is generic to boost many neural methods, and exhibits both a significant reduction in infeasible rate and a substantial improvement in solution quality.

Related papers

• LMask: Learn to Solve Constrained Routing Problems with Lazy Masking [4.693576188349811]
  We propose LMask, a novel learning framework that utilizes dynamic masking to generate high-quality feasible solutions for constrained routing problems.<n>LMask achieves state-of-the-art feasibility rates and solution quality, outperforming existing neural methods.
  arXiv  Detail & Related papers  (2025-05-23T14:15:26Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space. We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
  arXiv  Detail & Related papers  (2025-03-01T21:25:21Z)
• Constrained Reinforcement Learning with Smoothed Log Barrier Function [27.216122901635018]
  We propose a new constrained RL method called CSAC-LB (Constrained Soft Actor-Critic with Log Barrier Function) It achieves competitive performance without any pre-training by applying a linear smoothed log barrier function to an additional safety critic. We show that with CSAC-LB, we achieve state-of-the-art performance on several constrained control tasks with different levels of difficulty.
  arXiv  Detail & Related papers  (2024-03-21T16:02:52Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Capsa: A Unified Framework for Quantifying Risk in Deep Neural Networks [142.67349734180445]
  Existing algorithms that provide risk-awareness to deep neural networks are complex and ad-hoc. Here we present capsa, a framework for extending models with risk-awareness.
  arXiv  Detail & Related papers  (2023-08-01T02:07:47Z)
• Neural Fields with Hard Constraints of Arbitrary Differential Order [61.49418682745144]
  We develop a series of approaches for enforcing hard constraints on neural fields. The constraints can be specified as a linear operator applied to the neural field and its derivatives. Our approaches are demonstrated in a wide range of real-world applications.
  arXiv  Detail & Related papers  (2023-06-15T08:33:52Z)
• Travel the Same Path: A Novel TSP Solving Strategy [0.0]
  We consider the imitation learning framework, which helps a deterministic algorithm making good choices whenever it needs to. We demonstrate a strong generalization ability of a graph neural network trained under the imitation learning framework.
  arXiv  Detail & Related papers  (2022-10-12T03:56:37Z)
• Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation [0.4014524824655105]
  Vehicle Routing Problems (VRPs) in real-world applications often come with various constraints. We propose a Reinforcement Learning based method to solve soft-constrained VRPs. We apply the method on three common types of VRPs, the Travelling Salesman Problem with Time Windows (TSPTW), the Capacitated VRP (CVRP) and the Capacitated VRP with Time Windows (CVRPTW)
  arXiv  Detail & Related papers  (2022-07-20T12:51:06Z)
• Penalized Proximal Policy Optimization for Safe Reinforcement Learning [68.86485583981866]
  We propose Penalized Proximal Policy Optimization (P3O), which solves the cumbersome constrained policy iteration via a single minimization of an equivalent unconstrained problem. P3O utilizes a simple-yet-effective penalty function to eliminate cost constraints and removes the trust-region constraint by the clipped surrogate objective. We show that P3O outperforms state-of-the-art algorithms with respect to both reward improvement and constraint satisfaction on a set of constrained locomotive tasks.
  arXiv  Detail & Related papers  (2022-05-24T06:15:51Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  We propose Deep Policy Dynamic Programming (D PDP) to combine the strengths of learned neurals with those of dynamic programming algorithms. D PDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP) and the vehicle routing problem (VRP) and show that the neural policy improves the performance of (restricted) DP algorithms.
  arXiv  Detail & Related papers  (2021-02-23T15:33:57Z)
• Local Propagation in Constraint-based Neural Network [77.37829055999238]
  We study a constraint-based representation of neural network architectures. We investigate a simple optimization procedure that is well suited to fulfil the so-called architectural constraints.
  arXiv  Detail & Related papers  (2020-02-18T16:47:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.