Towards Omni-generalizable Neural Methods for Vehicle Routing Problems

Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:42769-42789, 2023.

Abstract

Learning heuristics for vehicle routing problems (VRPs) has gained much attention due to the less reliance on hand-crafted rules. However, existing methods are typically trained and tested on the same task with a fixed size and distribution (of nodes), and hence suffer from limited generalization performance. This paper studies a challenging yet realistic setting, which considers generalization across both size and distribution in VRPs. We propose a generic meta-learning framework, which enables effective training of an initialized model with the capability of fast adaptation to new tasks during inference. We further develop a simple yet efficient approximation method to reduce the training overhead. Extensive experiments on both synthetic and benchmark instances of the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) demonstrate the effectiveness of our method. The code is available at: https://github.com/RoyalSkye/Omni-VRP.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-zhou23o, title = {Towards Omni-generalizable Neural Methods for Vehicle Routing Problems}, author = {Zhou, Jianan and Wu, Yaoxin and Song, Wen and Cao, Zhiguang and Zhang, Jie}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {42769--42789}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/zhou23o/zhou23o.pdf}, url = {https://proceedings.mlr.press/v202/zhou23o.html}, abstract = {Learning heuristics for vehicle routing problems (VRPs) has gained much attention due to the less reliance on hand-crafted rules. However, existing methods are typically trained and tested on the same task with a fixed size and distribution (of nodes), and hence suffer from limited generalization performance. This paper studies a challenging yet realistic setting, which considers generalization across both size and distribution in VRPs. We propose a generic meta-learning framework, which enables effective training of an initialized model with the capability of fast adaptation to new tasks during inference. We further develop a simple yet efficient approximation method to reduce the training overhead. Extensive experiments on both synthetic and benchmark instances of the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) demonstrate the effectiveness of our method. The code is available at: https://github.com/RoyalSkye/Omni-VRP.} }
Endnote
%0 Conference Paper %T Towards Omni-generalizable Neural Methods for Vehicle Routing Problems %A Jianan Zhou %A Yaoxin Wu %A Wen Song %A Zhiguang Cao %A Jie Zhang %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-zhou23o %I PMLR %P 42769--42789 %U https://proceedings.mlr.press/v202/zhou23o.html %V 202 %X Learning heuristics for vehicle routing problems (VRPs) has gained much attention due to the less reliance on hand-crafted rules. However, existing methods are typically trained and tested on the same task with a fixed size and distribution (of nodes), and hence suffer from limited generalization performance. This paper studies a challenging yet realistic setting, which considers generalization across both size and distribution in VRPs. We propose a generic meta-learning framework, which enables effective training of an initialized model with the capability of fast adaptation to new tasks during inference. We further develop a simple yet efficient approximation method to reduce the training overhead. Extensive experiments on both synthetic and benchmark instances of the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) demonstrate the effectiveness of our method. The code is available at: https://github.com/RoyalSkye/Omni-VRP.
APA
Zhou, J., Wu, Y., Song, W., Cao, Z. & Zhang, J.. (2023). Towards Omni-generalizable Neural Methods for Vehicle Routing Problems. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:42769-42789 Available from https://proceedings.mlr.press/v202/zhou23o.html.

Related Material