Step-wise deep learning models for solving routing problems

Routing problems are very important in intelligent transportation systems. Recently, a number of deep learning-based methods are proposed to automatically learn construction heuristics for solving routing problems. However, these methods do not completely follow Bellman's Principle of Optimalit...

Full description

Saved in:
Bibliographic Details
Main Authors: XIN, Liang, SONG, Wen, CAO, Zhiguang, ZHANG, Jie
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2021
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/8155
https://ink.library.smu.edu.sg/context/sis_research/article/9158/viewcontent/Step_Wise_Deep_Learning_Models_for_Solving_Routing_Problems_av.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-9158
record_format dspace
spelling sg-smu-ink.sis_research-91582023-09-26T10:22:44Z Step-wise deep learning models for solving routing problems XIN, Liang SONG, Wen CAO, Zhiguang ZHANG, Jie Routing problems are very important in intelligent transportation systems. Recently, a number of deep learning-based methods are proposed to automatically learn construction heuristics for solving routing problems. However, these methods do not completely follow Bellman's Principle of Optimality since the visited nodes during construction are still included in the following subtasks, resulting in suboptimal policies. In this article, we propose a novel step-wise scheme which explicitly removes the visited nodes in each node selection step. We apply this scheme to two representative deep models for routing problems, pointer network and transformer attention model (TAM), and significantly improve the performance of the original models. To reduce computational complexity, we further propose the approximate step-wise TAM model by modifying one layer of attention. It enables training on larger instances compared to step-wise TAM, and outperforms state-of-the-art deep models with greedy decoding strategy. 2021-07-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/8155 info:doi/10.1109/TII.2020.3031409 https://ink.library.smu.edu.sg/context/sis_research/article/9158/viewcontent/Step_Wise_Deep_Learning_Models_for_Solving_Routing_Problems_av.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Routing Deep learning Decoding Computational modeling Reinforcement learning Urban areas Informatics Deep learning Deep reinforcement learning Intelligent transportation system Routing problems Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering Transportation
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Routing
Deep learning
Decoding
Computational modeling
Reinforcement learning
Urban areas
Informatics
Deep learning
Deep reinforcement learning
Intelligent transportation system
Routing problems
Numerical Analysis and Scientific Computing
Operations Research, Systems Engineering and Industrial Engineering
Transportation
spellingShingle Routing
Deep learning
Decoding
Computational modeling
Reinforcement learning
Urban areas
Informatics
Deep learning
Deep reinforcement learning
Intelligent transportation system
Routing problems
Numerical Analysis and Scientific Computing
Operations Research, Systems Engineering and Industrial Engineering
Transportation
XIN, Liang
SONG, Wen
CAO, Zhiguang
ZHANG, Jie
Step-wise deep learning models for solving routing problems
description Routing problems are very important in intelligent transportation systems. Recently, a number of deep learning-based methods are proposed to automatically learn construction heuristics for solving routing problems. However, these methods do not completely follow Bellman's Principle of Optimality since the visited nodes during construction are still included in the following subtasks, resulting in suboptimal policies. In this article, we propose a novel step-wise scheme which explicitly removes the visited nodes in each node selection step. We apply this scheme to two representative deep models for routing problems, pointer network and transformer attention model (TAM), and significantly improve the performance of the original models. To reduce computational complexity, we further propose the approximate step-wise TAM model by modifying one layer of attention. It enables training on larger instances compared to step-wise TAM, and outperforms state-of-the-art deep models with greedy decoding strategy.
format text
author XIN, Liang
SONG, Wen
CAO, Zhiguang
ZHANG, Jie
author_facet XIN, Liang
SONG, Wen
CAO, Zhiguang
ZHANG, Jie
author_sort XIN, Liang
title Step-wise deep learning models for solving routing problems
title_short Step-wise deep learning models for solving routing problems
title_full Step-wise deep learning models for solving routing problems
title_fullStr Step-wise deep learning models for solving routing problems
title_full_unstemmed Step-wise deep learning models for solving routing problems
title_sort step-wise deep learning models for solving routing problems
publisher Institutional Knowledge at Singapore Management University
publishDate 2021
url https://ink.library.smu.edu.sg/sis_research/8155
https://ink.library.smu.edu.sg/context/sis_research/article/9158/viewcontent/Step_Wise_Deep_Learning_Models_for_Solving_Routing_Problems_av.pdf
_version_ 1779157185550352384