Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
2-2021
Abstract
We present a novel deep reinforcement learning method to learn construction heuristics for vehicle routing problems. In specific, we propose a Multi-Decoder Attention Model (MDAM) to train multiple diverse policies, which effectively increases the chance of finding good solutions compared with existing methods that train only one policy. A customized beam search strategy is designed to fully exploit the diversity of MDAM. In addition, we propose an Embedding Glimpse layer in MDAM based on the recursive nature of construction, which can improve the quality of each policy by providing more informative embeddings. Extensive experiments on six different routing problems show that our method significantly outperforms the state-of-the-art deep learning based models.
Keywords
Routing
Discipline
Databases and Information Systems
Research Areas
Data Science and Engineering
Publication
Proceedings of the 35th AAAI Conference on Artificial Intelligence, Virtual event, 2021 February 2–9
First Page
12042
Last Page
12049
ISBN
9781713835974
Identifier
10.1609/aaai.v35i13.17430
Publisher
Association for the Advancement of Artificial Intelligence
City or Country
California
Citation
XIN, Liang; SONG, Wen; CAO, Zhiguang; and ZHANG, Jie.
Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. (2021). Proceedings of the 35th AAAI Conference on Artificial Intelligence, Virtual event, 2021 February 2–9. 12042-12049.
Available at: https://ink.library.smu.edu.sg/sis_research/8135
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://doi.org/10.1609/aaai.v35i13.17430