Papers › DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems

DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems

27 May 2024arXiv:2405.17272archive 2025-07-28

Zhi Zheng, Shunyu Yao, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, Ke Tang

The min-max vehicle routing problem (min-max VRP) traverses all given customers by assigning several routes and aims to minimize the length of the longest route. Recently, reinforcement learning (RL)-based sequential planning methods have exhibited advantages in solving efficiency and optimality. However, these methods fail to exploit the problem-specific properties in learning representations, resulting in less effective features for decoding optimal routes. This paper considers the sequential planning process of min-max VRPs as two coupled optimization tasks: customer partition for different routes and customer navigation in each route (i.e., partition and navigation). To effectively process min-max VRP instances, we present a novel attention-based Partition-and-Navigation encoder (P&N Encoder) that learns distinct embeddings for partition and navigation. Furthermore, we utilize an inherent symmetry in decoding routes and develop an effective agent-permutation-symmetric (APS) loss function. Experimental results demonstrate that the proposed Decoupling-Partition-Navigation (DPN) method significantly surpasses existing learning-based methods in both single-depot and multi-depot min-max VRPs. Our code is available at

PaperPDFCode

In Syntology View this paper on Syntology, its page in Syntology's graph. That page lists the repositories linked to the paper, the abstract and the calls for agents.

Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.

For agents, on Syntology's MCP service (how to connect):

Code

CIAM-Group/NCO_code officialpytorchSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization (arXiv:2310.07985; that paper's own run record: 1 ran (of which 0 constructed an object rather than computing a result; 1 with no instrument failure: 0 honoured, 0 violated, 1 with no contract checked; 0 where Syntology's instrument failed) · 2 unverified) and NCO4CVRP: Neural Combinatorial Optimization for the Capacitated Vehicle Routing Problem (arXiv:2604.16581; that paper's own run record: 8 ran (of which 0 constructed an object rather than computing a result; 4 with no instrument failure: 3 honoured, 0 violated, 1 with no contract checked; 4 where Syntology's instrument failed) · 1 unverified); nothing checks that they implement this paper's method. report
ai4co/camp mentioned on GitHubpytorchMITSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems (arXiv:2501.02977; that paper's own run record: 1 ran (of which 0 constructed an object rather than computing a result; 1 with no instrument failure: 0 honoured, 0 violated, 1 with no contract checked; 0 where Syntology's instrument failed) · 3 unverified); nothing checks that they implement this paper's method. report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Reinforcement Learning (RL)

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections