DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917686048456704 |
|---|---|
| author | Zheng, Zhi Yao, Shunyu Wang, Zhenkun Tong, Xialiang Yuan, Mingxuan Tang, Ke |
| author_facet | Zheng, Zhi Yao, Shunyu Wang, Zhenkun Tong, Xialiang Yuan, Mingxuan Tang, Ke |
| contents | 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 |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_17272 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems Zheng, Zhi Yao, Shunyu Wang, Zhenkun Tong, Xialiang Yuan, Mingxuan Tang, Ke Machine Learning Artificial Intelligence 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 |
| title | DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2405.17272 |