  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.
