CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention

• URL: http://arxiv.org/abs/2412.00346v1
• Date: Sat, 30 Nov 2024 04:11:36 GMT
• Title: CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
• Authors: Han Li, Fei Liu, Zhi Zheng, Yu Zhang, Zhenkun Wang,
• Abstract summary: This paper introduces a Constraint-Aware Dual-Attention Model (CaDA) for vehicle routing problems.<n>CaDA incorporates a constraint prompt that efficiently represents different problem variants.<n>It features a dual-attention mechanism with a global branch for capturing broader graph-wide information.
• Score: 21.554370739508528
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Vehicle Routing Problems (VRPs) are significant Combinatorial Optimization (CO) problems holding substantial practical importance. Recently, Neural Combinatorial Optimization (NCO), which involves training deep learning models on extensive data to learn vehicle routing heuristics, has emerged as a promising approach due to its efficiency and the reduced need for manual algorithm design. However, applying NCO across diverse real-world scenarios with various constraints necessitates cross-problem capabilities. Current NCO methods typically employ a unified model lacking a constraint-specific structure, thereby restricting their cross-problem performance. Current multi-task methods for VRPs typically employ a constraint-unaware model, limiting their cross-problem performance. Furthermore, they rely solely on global connectivity, which fails to focus on key nodes and leads to inefficient representation learning. This paper introduces a Constraint-Aware Dual-Attention Model (CaDA), designed to address these limitations. CaDA incorporates a constraint prompt that efficiently represents different problem variants. Additionally, it features a dual-attention mechanism with a global branch for capturing broader graph-wide information and a sparse branch that selectively focuses on the most relevant nodes. We comprehensively evaluate our model on 16 different VRPs and compare its performance against existing cross-problem VRP solvers. CaDA achieves state-of-the-art results across all the VRPs. Our ablation study further confirms that each component of CaDA contributes positively to its cross-problem learning performance.

Related papers

• TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problems [43.89334324926175]
  TuneNSearch is a hybrid transfer learning and local search approach for addressing different variants of vehicle routing problems (VRP) We first pre-train a reinforcement learning model on the multi-depot VRP, followed by a short fine-tuning phase to adapt it to different variants. Results show that TuneNSearch outperforms many existing state-of-the-art models trained for each VRP variant, requiring only one-fifth of the training epochs.
  arXiv  Detail & Related papers  (2025-03-16T21:34:11Z)
• Towards Constraint-Based Adaptive Hypergraph Learning for Solving Vehicle Routing: An End-to-End Solution [4.965709007367529]
  Vehicle routing problems are characterized by vast solution spaces and intricate constraints. This study introduces a novel end-to-end framework that combines constraint-oriented hypergraphs with reinforcement learning.
  arXiv  Detail & Related papers  (2025-03-13T14:42:44Z)
• IC/DC: Surpassing Heuristic Solvers in Combinatorial Optimization with Diffusion Models [6.260482448679642]
  We present IC/DC, a learning-based optimization framework that operates without any supervision. IC/DC is specialized in addressing problems involving two distinct sets of items, and it does not need problem-specific search processes to generate valid solutions. We train our model in a self-supervised way to minimize the cost of the solution while adhering to the problem-specific constraints.
  arXiv  Detail & Related papers  (2024-10-15T06:53:30Z)
• AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation [88.50256898176269]
  We develop a pixel-level AUC loss function and conduct a dependency-graph-based theoretical analysis of the algorithm's generalization ability. We also design a Tail-Classes Memory Bank to manage the significant memory demand.
  arXiv  Detail & Related papers  (2024-09-30T15:31:02Z)
• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
  Combinatorial optimization (CO) is the fundamental problem at the intersection of computer science, applied mathematics, etc. In this paper, we design a family of non-autoregressive neural networks to solve CO problems under positive linear constraints. We validate the effectiveness of this framework in solving representative CO problems including facility location, max-set covering, and traveling salesman problem.
  arXiv  Detail & Related papers  (2024-09-06T14:58:31Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  We propose an adaptive Graph Attention Sampling with the Edges Fusion framework to solve vehicle routing problems. Our proposed model outperforms the existing methods by 2.08%-6.23% and shows stronger generalization ability.
  arXiv  Detail & Related papers  (2024-05-21T03:33:07Z)
• 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)
• Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization [18.298695520665348]
  Vehicle routing problems (VRPs) can be found in numerous real-world applications. In this work, we make the first attempt to tackle the crucial challenge of cross-problem generalization. Our proposed model can successfully solve VRPs with unseen attribute combinations in a zero-shot generalization manner.
  arXiv  Detail & Related papers  (2024-02-23T13:25:23Z)
• A General Framework for Learning from Weak Supervision [93.89870459388185]
  This paper introduces a general framework for learning from weak supervision (GLWS) with a novel algorithm. Central to GLWS is an Expectation-Maximization (EM) formulation, adeptly accommodating various weak supervision sources. We also present an advanced algorithm that significantly simplifies the EM computational demands.
  arXiv  Detail & Related papers  (2024-02-02T21:48:50Z)
• Pointer Networks with Q-Learning for Combinatorial Optimization [55.2480439325792]
  We introduce the Pointer Q-Network (PQN), a hybrid neural architecture that integrates model-free Q-value policy approximation with Pointer Networks (Ptr-Nets) Our empirical results demonstrate the efficacy of this approach, also testing the model in unstable environments.
  arXiv  Detail & Related papers  (2023-11-05T12:03:58Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)

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.