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

Zhi Zheng, Shunyu Yao, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, Ke Tang
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:61559-61592, 2024.

Abstract

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-zheng24m, title = {{DPN}: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems}, author = {Zheng, Zhi and Yao, Shunyu and Wang, Zhenkun and Xialiang, Tong and Yuan, Mingxuan and Tang, Ke}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {61559--61592}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/zheng24m/zheng24m.pdf}, url = {https://proceedings.mlr.press/v235/zheng24m.html}, abstract = {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} }
Endnote
%0 Conference Paper %T DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems %A Zhi Zheng %A Shunyu Yao %A Zhenkun Wang %A Tong Xialiang %A Mingxuan Yuan %A Ke Tang %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-zheng24m %I PMLR %P 61559--61592 %U https://proceedings.mlr.press/v235/zheng24m.html %V 235 %X 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
APA
Zheng, Z., Yao, S., Wang, Z., Xialiang, T., Yuan, M. & Tang, K.. (2024). DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:61559-61592 Available from https://proceedings.mlr.press/v235/zheng24m.html.

Related Material