Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

12-2021

Abstract

We present NeuroLKH, a novel algorithm that combines deep learning with the strong traditional heuristic Lin-Kernighan-Helsgaun (LKH) for solving Traveling Salesman Problem. Specifically, we train a Sparse Graph Network (SGN) with supervised learning for edge scores and unsupervised learning for node penalties, both of which are critical for improving the performance of LKH. Based on the output of SGN, NeuroLKH creates the edge candidate set and transforms edge distances to guide the searching process of LKH. Extensive experiments firmly demonstrate that, by training one model on a wide range of problem sizes, NeuroLKH significantly outperforms LKH and generalizes well to much larger sizes. Also, we show that NeuroLKH can be applied to other routing problems such as Capacitated Vehicle Routing Problem (CVRP), Pickup and Delivery Problem (PDP), and CVRP with Time Windows (CVRPTW).

Keywords

Deep learning, Graph theory, Vehicle routing

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

Proceedings of the 35th Conference on Neural Information Processing Systems, Virtual Conference, 2021 Dec 6-14

Volume

9

First Page

7472

Last Page

7483

ISBN

9781713845393

Identifier

10.48550/arXiv.2110.07983

Publisher

Neural information processing systems foundation

City or Country

California

Copyright Owner and License

Authors

Additional URL

http://doi.org/10.48550/arXiv.2110.07983

Download

Share

COinS