Hierarchical Neural Constructive Solver for Real-world TSP Scenarios

• URL: http://arxiv.org/abs/2408.03585v1
• Date: Wed, 7 Aug 2024 06:44:47 GMT
• Title: Hierarchical Neural Constructive Solver for Real-world TSP Scenarios
• Authors: Yong Liang Goh, Zhiguang Cao, Yining Ma, Yanfei Dong, Mohammed Haroon Dupty, Wee Sun Lee,
• Abstract summary: We introduce realistic Traveling Salesman Problem (TSP) scenarios relevant to industrial settings. Our hierarchical approach yields superior performance compared to both classical and recent transformer models.
• Score: 27.986011761759567
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Scalable spectral representations for network multiagent control [53.631272539560435]
  A popular model for multi-agent control, Network Markov Decision Processes (MDPs) pose a significant challenge to efficient learning. We first derive scalable spectral local representations for network MDPs, which induces a network linear subspace for the local $Q$-function of each agent. We design a scalable algorithmic framework for continuous state-action network MDPs, and provide end-to-end guarantees for the convergence of our algorithm.
  arXiv  Detail & Related papers  (2024-10-22T17:45:45Z)
• Towards Adaptive Neighborhood for Advancing Temporal Interaction Graph Modeling [19.831424038609462]
  Temporal Graph Networks (TGNs) have demonstrated their remarkable performance in modeling temporal interaction graphs. In this paper, we aim to enhance existing TGNs by introducing an adaptive neighborhood encoding mechanism. We present SEAN, a flexible plug-and-play model that can be seamlessly integrated with existing TGNs.
  arXiv  Detail & Related papers  (2024-06-14T07:57:17Z)
• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  We propose an adaptive Graph Attention Sampling with the Edges Fusion framework to solve vehicle routing problems. Our proposed model outperforms the existing methods by 2.08%-6.23% and shows stronger generalization ability.
  arXiv  Detail & Related papers  (2024-05-21T03:33:07Z)
• Adaptive Hierarchical SpatioTemporal Network for Traffic Forecasting [70.66710698485745]
  We propose an Adaptive Hierarchical SpatioTemporal Network (AHSTN) to promote traffic forecasting. AHSTN exploits the spatial hierarchy and modeling multi-scale spatial correlations. Experiments on two real-world datasets show that AHSTN achieves better performance over several strong baselines.
  arXiv  Detail & Related papers  (2023-06-15T14:50:27Z)
• On the Effective Usage of Priors in RSS-based Localization [56.68864078417909]
  We propose a Received Signal Strength (RSS) fingerprint and convolutional neural network-based algorithm, LocUNet. In this paper, we study the localization problem in dense urban settings. We first recognize LocUNet's ability to learn the underlying prior distribution of the Rx position or Rx and transmitter (Tx) association preferences from the training data, and attribute its high performance to these.
  arXiv  Detail & Related papers  (2022-11-28T00:31:02Z)
• Continuous-Time and Multi-Level Graph Representation Learning for Origin-Destination Demand Prediction [52.0977259978343]
  This paper proposes a Continuous-time and Multi-level dynamic graph representation learning method for Origin-Destination demand prediction (CMOD) The state vectors keep historical transaction information and are continuously updated according to the most recently happened transactions. Experiments are conducted on two real-world datasets from Beijing Subway and New York Taxi, and the results demonstrate the superiority of our model against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-06-30T03:37:50Z)
• Sign-Agnostic CONet: Learning Implicit Surface Reconstructions by Sign-Agnostic Optimization of Convolutional Occupancy Networks [39.65056638604885]
  We learn implicit surface reconstruction by sign-agnostic optimization of convolutional occupancy networks. We show this goal can be effectively achieved by a simple yet effective design.
  arXiv  Detail & Related papers  (2021-05-08T03:35:32Z)
• Dynamic Hierarchical Mimicking Towards Consistent Optimization Objectives [73.15276998621582]
  We propose a generic feature learning mechanism to advance CNN training with enhanced generalization ability. Partially inspired by DSN, we fork delicately designed side branches from the intermediate layers of a given neural network. Experiments on both category and instance recognition tasks demonstrate the substantial improvements of our proposed method.
  arXiv  Detail & Related papers  (2020-03-24T09:56:13Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.