Timezone: »
Recently, Transformer has become a prevailing deep architecture for solving vehicle routing problems (VRPs). However, it is less effective in learning improvement models for VRP because its positional encoding (PE) method is not suitable in representing VRP solutions. This paper presents a novel Dual-Aspect Collaborative Transformer (DACT) to learn embeddings for the node and positional features separately, instead of fusing them together as done in existing ones, so as to avoid potential noises and incompatible correlations. Moreover, the positional features are embedded through a novel cyclic positional encoding (CPE) method to allow Transformer to effectively capture the circularity and symmetry of VRP solutions (i.e., cyclic sequences). We train DACT using Proximal Policy Optimization and design a curriculum learning strategy for better sample efficiency. We apply DACT to solve the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). Results show that our DACT outperforms existing Transformer based improvement models, and exhibits much better generalization performance across different problem sizes on synthetic and benchmark instances, respectively.
Author Information
Yining Ma (National University of Singapore)
Jingwen Li (National University of Singapore)
Zhiguang Cao (Singapore Institute of Manufacturing Technology)
Wen Song (Institute of Marine Scinece and Technology, Shandong University)
Le Zhang (University of Electronic Science and Technology of China)
Zhenghua Chen (Nanyang Technological University)
Jing Tang (The Hong Kong University of Science and Technology)
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: Chromatic Correlation Clustering, Revisited »
Qing Xiu · Kai Han · Jing Tang · Shuang Cui · He Huang -
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 -
2023 Poster: Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt »
Yining Ma · Zhiguang Cao · Yeow Meng Chee -
2023 Poster: DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization »
Haoran Ye · Jiarui Wang · Zhiguang Cao · Helan Liang · Yong Li -
2023 Poster: Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement »
Jinbiao Chen · Zizhen Zhang · Zhiguang Cao · Yaoxin Wu · Yining Ma · Te Ye · Jiahai Wang -
2023 Poster: Ensemble-based Deep Reinforcement Learning for Vehicle Routing Problems under Distribution Shift »
Yuan Jiang · Zhiguang Cao · Yaoxin Wu · Wen Song · Jie Zhang -
2023 Poster: Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization »
Jinbiao Chen · Zizhen Zhang · Te Ye · Zhiguang Cao · Siyuan Chen · Jiahai Wang -
2023 Poster: MetaBox: A Benchmark Platform for Meta-Black-Box Optimization with Reinforcement Learning »
Zeyuan Ma · Hongshu Guo · Jiacheng Chen · Zhenrui Li · Guojun Peng · Yue-Jiao Gong · Yining Ma · Zhiguang Cao -
2023 Oral: MetaBox: A Benchmark Platform for Meta-Black-Box Optimization with Reinforcement Learning »
Zeyuan Ma · Hongshu Guo · Jiacheng Chen · Zhenrui Li · Guojun Peng · Yue-Jiao Gong · Yining Ma · Zhiguang Cao -
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 Spotlight: Lightning Talks 1B-2 »
Eugene Golikov · Nils M. Kriege · Qing Xiu · Kai Han · Greg Yang · Jing Tang · Shuang Cui · He Huang -
2022 Spotlight: Chromatic Correlation Clustering, Revisited »
Qing Xiu · Kai Han · Jing Tang · Shuang Cui · He Huang -
2022 Poster: Graph Learning Assisted Multi-Objective Integer Programming »
Yaoxin Wu · Wen Song · Zhiguang Cao · Jie Zhang · Abhishek Gupta · Mingyan Lin -
2021 Poster: NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem »
Liang Xin · Wen Song · Zhiguang Cao · Jie Zhang -
2021 Poster: Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee »
Xiaofeng Fan · Yining Ma · Zhongxiang Dai · Wei Jing · Cheston Tan · Bryan Kian Hsiang Low -
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