Hierarchical Learning-based Graph Partition for Large-scale Vehicle Routing Problems

• URL: http://arxiv.org/abs/2502.08340v1
• Date: Wed, 12 Feb 2025 12:07:09 GMT
• Title: Hierarchical Learning-based Graph Partition for Large-scale Vehicle Routing Problems
• Authors: Yuxin Pan, Ruohong Liu, Yize Chen, Zhiguang Cao, Fangzhen Lin,
• Abstract summary: We propose a versatile Hierarchical Learning-based Graph Partition (HLGP) framework to benefit the partition of CVRP instances. HLGP is tailored to benefit the partition of CVRP instances by synergistically integrating global and local partition policies.
• Score: 19.54367116789867
• License:
• Abstract: Neural solvers based on the divide-and-conquer approach for Vehicle Routing Problems (VRPs) in general, and capacitated VRP (CVRP) in particular, integrates the global partition of an instance with local constructions for each subproblem to enhance generalization. However, during the global partition phase, misclusterings within subgraphs have a tendency to progressively compound throughout the multi-step decoding process of the learning-based partition policy. This suboptimal behavior in the global partition phase, in turn, may lead to a dramatic deterioration in the performance of the overall decomposition-based system, despite using optimal local constructions. To address these challenges, we propose a versatile Hierarchical Learning-based Graph Partition (HLGP) framework, which is tailored to benefit the partition of CVRP instances by synergistically integrating global and local partition policies. Specifically, the global partition policy is tasked with creating the coarse multi-way partition to generate the sequence of simpler two-way partition subtasks. These subtasks mark the initiation of the subsequent K local partition levels. At each local partition level, subtasks exclusive for this level are assigned to the local partition policy which benefits from the insensitive local topological features to incrementally alleviate the compounded errors. This framework is versatile in the sense that it optimizes the involved partition policies towards a unified objective harmoniously compatible with both reinforcement learning (RL) and supervised learning (SL). (*Due to the notification of arXiv "The Abstract field cannot be longer than 1,920 characters", the appeared Abstract is shortened. For the full Abstract, please download the Article.)

Related papers

• Decomposition-based Unsupervised Domain Adaptation for Remote Sensing Image Semantic Segmentation [30.606689882397223]
  Unsupervised domain adaptation (UDA) techniques are vital for semantic segmentation in geosciences. Most existing UDA methods, which focus on domain alignment at the high-level feature space, struggle to simultaneously retain local spatial details and global contextual semantics. A novel decomposition scheme is proposed to guide domain-invariant representation learning.
  arXiv  Detail & Related papers  (2024-04-06T07:13:49Z)
• Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy [24.91781032046481]
  Many neural construction methods for Vehicle Routing Problems(VRPs) focus on synthetic problem instances with specified node distributions and limited scales. We design an auxiliary policy that learns from the local transferable topological features, named local policy, and integrate it with a typical construction policy to form an ensemble policy. With joint training, the aggregated policies perform cooperatively and complementarily to boost generalization.
  arXiv  Detail & Related papers  (2023-08-27T13:22:50Z)
• PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback [106.63518036538163]
  We present a novel unified bilevel optimization-based framework, textsfPARL, formulated to address the recently highlighted critical issue of policy alignment in reinforcement learning. Our framework addressed these concerns by explicitly parameterizing the distribution of the upper alignment objective (reward design) by the lower optimal variable. Our empirical results substantiate that the proposed textsfPARL can address the alignment concerns in RL by showing significant improvements.
  arXiv  Detail & Related papers  (2023-08-03T18:03:44Z)
• Hierarchical Spatio-Temporal Representation Learning for Gait Recognition [6.877671230651998]
  Gait recognition is a biometric technique that identifies individuals by their unique walking styles. We propose a hierarchical-temporal representation learning framework for extracting gait features from coarse to fine. Our method outperforms the state-of-the-art while maintaining a reasonable balance between model accuracy and complexity.
  arXiv  Detail & Related papers  (2023-07-19T09:30:00Z)
• RCD-SGD: Resource-Constrained Distributed SGD in Heterogeneous Environment via Submodular Partitioning [1.9145351898882879]
  We develop a framework for distributed training algorithms based on a novel data partitioning algorithm involving submodular optimization. Based on this algorithm, we develop a distributed SGD framework that can accelerate existing SOTA distributed training algorithms by up to 32%.
  arXiv  Detail & Related papers  (2022-11-02T02:49:48Z)
• Semi-supervised Domain Adaptive Structure Learning [72.01544419893628]
  Semi-supervised domain adaptation (SSDA) is a challenging problem requiring methods to overcome both 1) overfitting towards poorly annotated data and 2) distribution shift across domains. We introduce an adaptive structure learning method to regularize the cooperation of SSL and DA.
  arXiv  Detail & Related papers  (2021-12-12T06:11:16Z)
• An Entropy-guided Reinforced Partial Convolutional Network for Zero-Shot Learning [77.72330187258498]
  We propose a novel Entropy-guided Reinforced Partial Convolutional Network (ERPCNet) ERPCNet extracts and aggregates localities based on semantic relevance and visual correlations without human-annotated regions. It not only discovers global-cooperative localities dynamically but also converges faster for policy gradient optimization.
  arXiv  Detail & Related papers  (2021-11-03T11:13:13Z)
• HSVA: Hierarchical Semantic-Visual Adaptation for Zero-Shot Learning [74.76431541169342]
  Zero-shot learning (ZSL) tackles the unseen class recognition problem, transferring semantic knowledge from seen classes to unseen ones. We propose a novel hierarchical semantic-visual adaptation (HSVA) framework to align semantic and visual domains. Experiments on four benchmark datasets demonstrate HSVA achieves superior performance on both conventional and generalized ZSL.
  arXiv  Detail & Related papers  (2021-09-30T14:27:50Z)
• Global Aggregation then Local Distribution for Scene Parsing [99.1095068574454]
  We show that our approach can be modularized as an end-to-end trainable block and easily plugged into existing semantic segmentation networks. Our approach allows us to build new state of the art on major semantic segmentation benchmarks including Cityscapes, ADE20K, Pascal Context, Camvid and COCO-stuff.
  arXiv  Detail & Related papers  (2021-07-28T03:46:57Z)
• Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processes [0.0]
  We present a novel approach to hierarchical reinforcement learning for linearly-solvable Markov decision processes. We represent value functions on several levels of abstraction, and use the compositionality of subtasks to estimate the optimal values of the states in each partition.
  arXiv  Detail & Related papers  (2021-06-29T13:10:08Z)
• Clustered Federated Learning via Generalized Total Variation Minimization [83.26141667853057]
  We study optimization methods to train local (or personalized) models for local datasets with a decentralized network structure. Our main conceptual contribution is to formulate federated learning as total variation minimization (GTV) Our main algorithmic contribution is a fully decentralized federated learning algorithm.
  arXiv  Detail & Related papers  (2021-05-26T18:07:19Z)

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.