Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

5-2025

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). Additionally, we decompose the synchronized training into individual training of each component to circumvent the instability issue. Furthermore, we point out the importance of viewing the subproblems encountered during the partition process as individual training instances. Extensive experiments conducted on various CVRP benchmarks demonstrate the effectiveness and generalization of the HLGP framework. The source code is available at https://github.com/panyxy/hlgp_cvrp.

Keywords

Combinatorial Optimization Problem, Hierarchical Learning, Vehicle Routing Problem

Discipline

Artificial Intelligence and Robotics

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Sustainability

Publication

AAMAS '25: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent System, Detroit, USA, May 19-23

First Page

1604

Last Page

1612

ISBN

9798400714269

Identifier

10.5555/3709347.3743795

Publisher

ACM

City or Country

New York

Download

Share

COinS