Timezone: »
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).
Author Information
Liang Xin (Nanyang Technological University)
Wen Song (Institute of Marine Scinece and Technology, Shandong University)
Zhiguang Cao (Singapore Institute of Manufacturing Technology)
Jie Zhang (Nanyang Technological University)
More from the Same Authors
-
2021 Spotlight: Learning Large Neighborhood Search Policy for Integer Programming »
Yaoxin Wu · Wen Song · Zhiguang Cao · Jie Zhang -
2022 Poster: Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation »
Jieyi Bi · Yining Ma · Jiahai Wang · Zhiguang Cao · Jinbiao Chen · Yuan Sun · Yeow Meng Chee -
2022 Spotlight: Lightning Talks 5B-3 »
Yanze Wu · Jie Xiao · Nianzu Yang · Jieyi Bi · Jian Yao · Yiting Chen · Qizhou Wang · Yangru Huang · Yongqiang Chen · Peixi Peng · Yuxin Hong · Xintao Wang · Feng Liu · Yining Ma · Qibing Ren · Xueyang Fu · Yonggang Zhang · Kaipeng Zeng · Jiahai Wang · GEN LI · Yonggang Zhang · Qitian Wu · Yifan Zhao · Chiyu Wang · Junchi Yan · Feng Wu · Yatao Bian · Xiaosong Jia · Ying Shan · Zhiguang Cao · Zheng-Jun Zha · Guangyao Chen · Tianjun Xiao · Han Yang · Jing Zhang · Jinbiao Chen · MA Kaili · Yonghong Tian · Junchi Yan · Chen Gong · Tong He · Binghui Xie · Yuan Sun · Francesco Locatello · Tongliang Liu · Yeow Meng Chee · David P Wipf · Tongliang Liu · Bo Han · Bo Han · Yanwei Fu · James Cheng · Zheng Zhang -
2022 Spotlight: Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation »
Jieyi Bi · Yining Ma · Jiahai Wang · Zhiguang Cao · Jinbiao Chen · Yuan Sun · Yeow Meng Chee -
2022 Poster: Graph Learning Assisted Multi-Objective Integer Programming »
Yaoxin Wu · Wen Song · Zhiguang Cao · Jie Zhang · Abhishek Gupta · Mingyan Lin -
2021 Poster: Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer »
Yining Ma · Jingwen Li · Zhiguang Cao · Wen Song · Le Zhang · Zhenghua Chen · Jing Tang -
2021 Poster: Learning Large Neighborhood Search Policy for Integer Programming »
Yaoxin Wu · Wen Song · Zhiguang Cao · Jie Zhang -
2020 Poster: Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning »
Cong Zhang · Wen Song · Zhiguang Cao · Jie Zhang · Puay Siew Tan · Xu Chi -
2018 Poster: Inference Aided Reinforcement Learning for Incentive Mechanism Design in Crowdsourcing »
Zehong Hu · Yitao Liang · Jie Zhang · Zhao Li · Yang Liu