Hierarchical neural constructive solver for real-world TSP scenarios

Existing neural constructive solvers for routing problems have predominantly employed transformer architectures, conceptualizing the route construction as a set-to-sequence learning task. However, their efficacy has primarily been demonstrated on entirely random problem instances that inadequately c...

Full description

Saved in:
Bibliographic Details
Main Authors: GOH, Yong Liang, CAO, Zhiguang, MA, Yining, DONG, Yanfei, DUPTY, Mohammed Haroon, LEE, Wee Sun
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2024
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/9334
https://ink.library.smu.edu.sg/context/sis_research/article/10334/viewcontent/3637528.3672053.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-10334
record_format dspace
spelling sg-smu-ink.sis_research-103342024-09-26T07:27:46Z Hierarchical neural constructive solver for real-world TSP scenarios GOH, Yong Liang CAO, Zhiguang MA, Yining DONG, Yanfei DUPTY, Mohammed Haroon LEE, Wee Sun Existing neural constructive solvers for routing problems have predominantly employed transformer architectures, conceptualizing the route construction as a set-to-sequence learning task. However, their efficacy has primarily been demonstrated on entirely random problem instances that inadequately capture real-world scenarios. In this paper, we introduce realistic Traveling Salesman Problem (TSP) scenarios relevant to industrial settings and derive the following insights: (1) The optimal next node (or city) to visit often lies within proximity to the current node, suggesting the potential benefits of biasing choices based on current locations. (2) Effectively solving the TSP requires robust tracking of unvisited nodes and warrants succinct grouping strategies. Building upon these insights, we propose integrating a learnable choice layer inspired by Hypernetworks to prioritize choices based on the current location, and a learnable approximate clustering algorithm inspired by the Expectation-Maximization algorithm to facilitate grouping the unvisited cities. Together, these two contributions form a hierarchical approach towards solving the realistic TSP by considering both immediate local neighbourhoods and learning an intermediate set of node representations. Our hierarchical approach yields superior performance compared to both classical and recent transformer models, showcasing the efficacy of the key designs. 2024-08-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9334 info:doi/10.1145/3637528.3672053 https://ink.library.smu.edu.sg/context/sis_research/article/10334/viewcontent/3637528.3672053.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 neural constructive solver traveling salesman problem deep reinforcement learning Databases and Information Systems OS and Networks
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic neural constructive solver
traveling salesman problem
deep reinforcement learning
Databases and Information Systems
OS and Networks
spellingShingle neural constructive solver
traveling salesman problem
deep reinforcement learning
Databases and Information Systems
OS and Networks
GOH, Yong Liang
CAO, Zhiguang
MA, Yining
DONG, Yanfei
DUPTY, Mohammed Haroon
LEE, Wee Sun
Hierarchical neural constructive solver for real-world TSP scenarios
description Existing neural constructive solvers for routing problems have predominantly employed transformer architectures, conceptualizing the route construction as a set-to-sequence learning task. However, their efficacy has primarily been demonstrated on entirely random problem instances that inadequately capture real-world scenarios. In this paper, we introduce realistic Traveling Salesman Problem (TSP) scenarios relevant to industrial settings and derive the following insights: (1) The optimal next node (or city) to visit often lies within proximity to the current node, suggesting the potential benefits of biasing choices based on current locations. (2) Effectively solving the TSP requires robust tracking of unvisited nodes and warrants succinct grouping strategies. Building upon these insights, we propose integrating a learnable choice layer inspired by Hypernetworks to prioritize choices based on the current location, and a learnable approximate clustering algorithm inspired by the Expectation-Maximization algorithm to facilitate grouping the unvisited cities. Together, these two contributions form a hierarchical approach towards solving the realistic TSP by considering both immediate local neighbourhoods and learning an intermediate set of node representations. Our hierarchical approach yields superior performance compared to both classical and recent transformer models, showcasing the efficacy of the key designs.
format text
author GOH, Yong Liang
CAO, Zhiguang
MA, Yining
DONG, Yanfei
DUPTY, Mohammed Haroon
LEE, Wee Sun
author_facet GOH, Yong Liang
CAO, Zhiguang
MA, Yining
DONG, Yanfei
DUPTY, Mohammed Haroon
LEE, Wee Sun
author_sort GOH, Yong Liang
title Hierarchical neural constructive solver for real-world TSP scenarios
title_short Hierarchical neural constructive solver for real-world TSP scenarios
title_full Hierarchical neural constructive solver for real-world TSP scenarios
title_fullStr Hierarchical neural constructive solver for real-world TSP scenarios
title_full_unstemmed Hierarchical neural constructive solver for real-world TSP scenarios
title_sort hierarchical neural constructive solver for real-world tsp scenarios
publisher Institutional Knowledge at Singapore Management University
publishDate 2024
url https://ink.library.smu.edu.sg/sis_research/9334
https://ink.library.smu.edu.sg/context/sis_research/article/10334/viewcontent/3637528.3672053.pdf
_version_ 1814047912698576896