EUVIMEDEUVIMED entdecken
Crossref

Rethinking Supervised Learning-Based Neural Combinatorial Optimization for Routing Problem

Shunyu Yao, Xi Lin, Jiashu Wang, Qingfu Zhang, Zhenkun Wang

ACM Transactions on Evolutionary Learning and Optimization · 31.12.2025 · 5 (4) · 1-24

DOI: 10.1145/3694690 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Evolutionary Learning and Optimization, online erschienen am 06.12.2025. Verfasst von Shunyu Yao und 4 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 55 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Natural Science Foundation of Guangdong Province, National Natural Science Foundation of Shenzhen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Neural combinatorial optimization (NCO) is a promising learning-based approach to solving complex combinatorial optimization problems such as the traveling salesman problem (TSP), the vehicle routing problem (VRP), and the orienteering problem (OP). However, how to efficiently train a powerful NCO solver for routing problems remains a crucial challenge. The widely used reinforcement learning method suffers from sparse rewards and low data efficiency, while the supervised learning approach requires a large number of high-quality solutions (i.e., labels) that could be costly to obtain. In this work, we find that simple data augmentation operations can drastically reduce the number of required high-quality solutions for supervised learning. Moreover, simple boosting strategies that leverage the property of multiple optima can significantly improve training efficiency. With only a small set of \(50{,}000\) labeled instances, supervised learning can achieve a competitive in-distribution performance with the widely used reinforcement learning counterpart. Furthermore, we also investigate the generalization ability for larger out-of-distribution problems. We believe the findings from this work may lead to a rethinking of the value of data-efficient supervised learning for NCO solver training.

Förderung

  • National Natural Science Foundation of China
  • Natural Science Foundation of Guangdong Province
  • National Natural Science Foundation of Shenzhen

Zitieren

APA

Yao, S., Lin, X., Wang, J., Zhang, Q., & Wang, Z. (2025). Rethinking Supervised Learning-Based Neural Combinatorial Optimization for Routing Problem. ACM Transactions on Evolutionary Learning and Optimization, 5(4), 1-24. https://doi.org/10.1145/3694690

Vancouver

Yao S, Lin X, Wang J, Zhang Q, Wang Z. Rethinking Supervised Learning-Based Neural Combinatorial Optimization for Routing Problem. ACM Transactions on Evolutionary Learning and Optimization. 2025;5(4):1-24. doi:10.1145/3694690

BibTeX
@article{Yao2025,
  author = {Yao, Shunyu and Lin, Xi and Wang, Jiashu and Zhang, Qingfu and Wang, Zhenkun},
  title = {Rethinking Supervised Learning-Based Neural Combinatorial Optimization for Routing Problem},
  journal = {ACM Transactions on Evolutionary Learning and Optimization},
  year = {2025},
  volume = {5},
  number = {4},
  pages = {1--24},
  doi = {10.1145/3694690}
}
Kostenlos starten →