An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem

• URL: http://arxiv.org/abs/2403.07028v1
• Date: Mon, 11 Mar 2024 02:17:42 GMT
• Title: An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem
• Authors: Runze Guo, Feng Xue, Anlong Ming, Nicu Sebe
• Abstract summary: 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.
• Score: 67.92544792239086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, neural networks (NN) have made great strides in combinatorial optimization. However, they face challenges when solving the capacitated arc routing problem (CARP) which is to find the minimum-cost tour covering all required edges on a graph, while within capacity constraints. In tackling CARP, NN-based approaches tend to lag behind advanced metaheuristics, since they lack directed arc modeling and efficient learning methods tailored for complex CARP. In this paper, we introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics while exhibiting superior efficiency. First, we propose the direction-aware attention model (DaAM) to incorporate directionality into the embedding process, facilitating more effective one-stage decision-making. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy for subsequent reinforcement fine-tuning. It proves particularly valuable for solving CARP that has a higher complexity than the node routing problems (NRPs). Finally, a path optimization method is proposed to adjust the depot return positions within the path generated by DaAM. Experiments illustrate that our approach surpasses heuristics and achieves decision quality comparable to state-of-the-art metaheuristics for the first time while maintaining superior efficiency.

Related papers

• CHARME: A chain-based reinforcement learning approach for the minor embedding problem [16.24890195949869]
  We propose a novel approach utilizing Reinforcement Learning (RL) techniques to address the minor embedding problem, named CHARME. CHARME includes three key components: a Graph Neural Network (GNN) architecture for policy modeling, a state transition algorithm ensuring solution validity, and an order exploration strategy for effective training. In details, CHARME yields superior solutions compared to fast embedding methods such as Minorminer and ATOM.
  arXiv  Detail & Related papers  (2024-06-11T10:12:10Z)
• 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)
• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization [15.842155380912002]
  This work proposes a novel Instance-Conditioned Adaptation Model (ICAM) for better large-scale generalization of neural optimization. In particular, we design a powerful yet lightweight instance-conditioned Routing adaptation module for the NCO model. We develop an efficient three-stage reinforcement learning-based training scheme that enables the model to learn cross-scale features without any labeled optimal solution.
  arXiv  Detail & Related papers  (2024-05-03T08:00:19Z)
• CGD: Constraint-Guided Diffusion Policies for UAV Trajectory Planning [26.10588918124538]
  A successful strategy to reduce computation time involves using Imitation Learning (IL) to develop fast neural network (NN) policies from experts. Although the resulting NN policies are effective at quickly generating trajectories similar to those from the expert, their output does not explicitly account for dynamic feasibility. We propose Constraint-Guided Diffusion (CGD), a novel IL-based approach to trajectory planning.
  arXiv  Detail & Related papers  (2024-05-02T21:50:26Z)
• Optimizing Inventory Routing: A Decision-Focused Learning Approach using Neural Networks [0.0]
  We formulate and propose a decision-focused learning-based approach to solving real-world IRPs. This approach directly integrates inventory prediction and routing optimization within an end-to-end system potentially ensuring a robust supply chain strategy.
  arXiv  Detail & Related papers  (2023-11-02T04:05:28Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Solving the vehicle routing problem with deep reinforcement learning [0.0]
  This paper focuses on the application of RL for the Vehicle Routing Problem (VRP), a famous problem that belongs to the class of NP-Hard problems. In a second phase, the neural architecture behind the Actor and Critic has been established, choosing to adopt a neural architecture based on the Convolutional neural networks. Experiments performed on a wide range of instances show that the algorithm has good generalization capabilities and can reach good solutions in a short time.
  arXiv  Detail & Related papers  (2022-07-30T12:34:26Z)
• Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
  Entanglement routing establishes remote entanglement connection between two arbitrary nodes. We propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks.
  arXiv  Detail & Related papers  (2021-11-15T14:07:22Z)
• Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner with Evolution-Based Optimization [49.207538634692916]
  We propose a new algorithm for circuit routing, named Ranking Cost, to form an efficient and trainable router. In our method, we introduce a new set of variables called cost maps, which can help the A* router to find out proper paths. Our algorithm is trained in an end-to-end manner and does not use any artificial data or human demonstration.
  arXiv  Detail & Related papers  (2021-10-08T07:22:45Z)

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.