ViTSP: A Vision Language Models Guided Framework for Solving Large-Scale Traveling Salesman Problems
Authors: Zhuoli Yin
Yi Ding
Reem Khir
Hua Cai
Venue: ICLR 2026 Poster (2026)
Keywords: Machine Learning
Large Language Model
Traveling Salesman Problem
Combinatorial Optimization
Primary area: optimization
TL;DR: ViTSP introduces a novel hybrid approach that leverages Vision Language Models to visually decompose routing problems for exact OR solvers, achieving high-quality results without any task-specific training.

Abstract: Solving the Traveling Salesman Problem (TSP) is NP-hard yet fundamental for a wide range of real-world applications. Classical exact methods face challenges in scaling, and heuristic methods often require domain-specific parameter calibration. While learning-based approaches have shown promise, they suffer from poor generalization and limited scalability due to fixed training data. This work proposes ViTSP, a novel framework that leverages pre-trained vision language models (VLMs) to visually guide the solution process for large-scale TSPs. The VLMs function to identify promising small-scale subproblems from a visualized TSP instance, which are then efficiently optimized using an off-the-shelf solver to improve the global solution. ViTSP bypasses the dedicated model training at the user end while maintaining effectiveness across diverse instances. Experiments on real-world TSP instances ranging from 1k to 88k nodes demonstrate that ViTSP consistently achieves solutions with average optimality gaps of 0.24\%, outperforming existing learning-based methods. Under the same runtime budget, it surpasses the best-performing heuristic solver, LKH-3, by reducing its gaps by 3.57\% to 100\%, particularly on very-large-scale instances with more than 10k nodes. Our framework offers a new perspective in hybridizing pre-trained generative models and operations research solvers in solving combinatorial optimization problems. The framework holds potential for integration into more complex real-world logistics systems.  The code is available at https://github.itap.purdue.edu/uSMART/ViTSP_ICLR2026.

Published as a conference paper at ICLR 2026
VITSP: A VISION LANGUAGE MODELS GUIDED FRAMEWORK FOR SOLVING LARGE-SCALE TRAVEL-
ING SALESMAN PROBLEMS
Zhuoli Yin', Yi Ding", Reem Khir', Hua Cait.3
1 Edwardson School of Industrial Engineering, Purdue University, USA
Elmore Family School of Electrical and Computer Engincering, Purdue University, USA Schooo of Sustainability Engineering and Environmental Engineering, Purdue University, USA Shuoliying yiding, rkhir, huacai @purduu..
ABSTRACT
Solving the Traveling Salesman Problem (TSP) is NP-hard yet fundamental for wide range of real-world applications. Classical exact methods face challenges in scaling, and heuristic methods often require domain-specific parameter cali- bration. While learning-basee approaches have shown promise, they suffer from poor generalization and limited scalability due to fixed training data. This work proposes VITSP, novel framework that leverages pre-tree pre-trained vision language models (VLMs) to visually guide the solution process for large-scale TSPs. The VLMs function to identify promising small-scale subproblems from a visualized TSP instance, which are then efficiently optimized using off-the-shelf solver to improve the global solution. VITSP bypasses the dedicated model training at the user end while maintaining effectiveness across diverse instances. Ex- periments on real-world TSP instances ranging from 1k to 88k nodes demon- strate that VITSP consistently achieves solutions with average optimality gaps of 0.24%, outperforming existing learning-based methods. Under the same run- time budget, it surpasses the best-performing heuristic solver, LKH-3, by reduc- ing its gaps by 3.57% to 100%. particularly on very-large-scae instances with more than 10k nodes. Our framework offers a new perspective in hybridizing pre-trained generative models and operations research solvers in solving com- binatorial optimization problems. The framework holds potential for integra- tion into more complex real-word wallworld logistics systems. The code is available at /ttps://gitee itap. purdue. edu www./uusu///vVTTT ICLR2026.
INTRODUCTION
The Traveling Salesman Problem (TSP) is fundamental combinatorial optimization (CO) problem with broad real-world applications, including transportation, logistics, and chip design (Applegate, 2006; Yin al., 2023). Efficiently solving TSPs not only yields economical and societal benefits across those domains but also informs the development of solution strategies for other CO problems. The operations research (OR) community has developed numerous exact and heuristic algorithms address this NP-hard problem (Davendra, 2010). However, exact methods often struggle to produce high-quality solutions as the problem size increases. Heuristic algorithms offer faster approximate solutions, yet their effectiveness depends on domain knowledge and careful calibration of instance-specific parameters (Adenso-Díaz & Laguna, 2006).
Advances of machine learning (ML) have led to various learning- based approaches for solving TSPs (referred to as neural solvers), including end-to-end models for solution construction (Vaswani et al., 2017; Jin et al., 2023; Sun & Yang, 2023; Li et al., 2024) and learned neural strategies for local improvement (Zong et al., 2022; Cheng et al., 2023; Ye et al., 2023; 2024b; Zheng et al., 2024). These methods shorten the computation time and maintain good solutions for in-distribution, small-scale instances (nodes < 1,000) (Wu et al., 2024). However, they suffer from poor generalization and limited scalability as the real-world problem deviates from the training data.

---

Published as a conference paper at ICLR 2026
The surge of pre-trained large language models (LLMs) and vision language models (VLMs) has raised interest in their potential for tackling optimization problems. Existing efforts mainly focused on end-to-end construction of text-based solutions (Yang et al., 2023; Elhenawy et al., 2024) or on heuristic designs (Ye et al., 2024a; Liu et al., 2024) that rely solely on textual information of TSP instances. While these studies open new perspectives using generative models to rethink optimization, their approaches fall short of demonstrating reliable performance on large-scale practical TSPs (Khan& & Hamad, 2024)
In this study, we reconsider how pre-trained generative models can effectively complement established OR techniques for solving large-scale TSP instances with varying distributions and scales, enabling broader optimization applications. We leverage pre-trained VLMs to provide adaptive decomposition heuristics that complement the existing optimization routine, as effective decomposition must account not only for spatial locality but also for combinatorial neighborhoods that help escape local optima. VLMs are well-suited for this task, as they can interpret instance-specifie spatial structures by treating TSP instances as 2D images, enabling more informed selection of subproblems. Unlike ML approaches that require comainn-ppcciffe training for graph embeddings, VLMs offer generic reasoning capabilities without costly data collection retraining. The resulting subproblems, being smaller than their original TSP, can be reliably solved by exact solvers, avoiding performance degradation often experienced in learned neural solvers (Joshi et al., 2022; Wu al., 2024).
We propose ViTSP, a Vision-guided framework for solving large-scale TSP. In ViTSP, VLMs guide the optimization process by identifying meaningful subproblems from visualized TSP instances, while an off-the-shelf solver continuously refines those subproblems. VITSP orchestrates the two modules asynchronously to accommodate the heterogeneous computational overheads of input/output (I/O) intensive VLMs and CPU-intensive solvers. On unseen TSPLIB (Reinelt, 1991) instances ranging from 1k to 88k, VITSP finds the global optimum in 11 out of 33 instances and outperforms baseline bearning-based methods, whose performance degrades significantly compared to their reported in- distribution results. Compared to the best- rest-performin heuristic solver, LKH-3,, VITSP converges to superior solutions under the same time budget and reduces optimality gaps by 12% to 100%. Our key contributions in this study are summarized below:
1. We propose vision-guided solution framework VITSP that hybridizes VLMs and off-the- shelf solvers to reach strong performance. VITSP able to adapt to TSP instances with varying distributions and scales.
2. Our approach leverages pre- ore-trained VLMs to visually derive decomposition heuristics while bypassing the costly and time-consuming training and data curation for edge deployment.
3. We conduct experiments on
instances to validate the effectiveness of VITSP. The ablation studies further underpinned ViTSP's ability to perform principled guidance. To the best of our knowledge, our work presents one of the most comprehensive evaluations of real-world TSPLIB instances with N > 1000, whereas few prior works reported sufficient results at this scale.
2 RELATED WORKS
Existing approaches of solving large-scale TSP can categorized into three primary schemes: (1) OR approaches, (2) learning-basse approaches, and (3) L.L./VL approaches. We briefly review these works in this section, and we supplement the detailed discussion in the Appendix B.
2.1 OR APPROACIIES
Exact algorithms typically require explicit mathematical formulations and search for exact solutions via branch and bound procedures (Laporte, 1992; Wolsey, 2020). Off-the-shelf exact solvers, such as Concorde, Gurobi, and OR-Tools, have the potential to reach global optimality. Among them, Concorde remains the -tate-of-the-art (SOTA), using specialized rules to speed up the search process. However, the computation time of exact solvers becomes intractable as the problem size increases.
Heuristic algorithms, such as farthest insertion (Rosenkrantz et al., 1974), genetic algorithm (Holland, 1992), and Lin- LinKernighhn- Kernighan-Helggann- (LKH-3) (Helsgaun, 2017), iteratively refine solutions based on hand-crafted rules. LKH-3 is regarded as the SOTA in solving TSPs. However, LKH-3 relies on tunable parameters, such as the number of total runs and candidate edges. Without domain knowledge and instance-specific calibration, achieving strong performance is often non-trivial. According to
2

---

Published as a conference paper at ICLR 2026
Adenso-Diaz & Laguna (2006), only about 10% of the effort in developing and testing heuristics or metaheuristics goes into designing it, with the remaining 90% spent in parameter tuning.
2.2 LEARNING-BASHE APPROACHES
I Learning-based approaches for solving CO problems have gained wide attention since the surge of deep learning. These works commonly employ graph neural networks to embed TSP instances. The networks are trained using either supervised learning. which requires high-quality solutions from exact or heuristic methods as labels, or reinforcement learning, which relies on extensive trial-and-error (Fu al., 2021). Existing works mainly deploy trained networks under two paradigms.
End-to-end construction. This paradigm seeks to learn a policy to directly construct solution, using either autoregressive or non- aon-autoregressive (heatmap-baseed scheme trains attention-ban based neural networks (Vaswani et al., 2017; Kwon et al., 2020; Jin et al., 2023). The network sequentially constructs solutions by outputting one node at time, with previous outputs incorporated into the network to guide the generation of subsequent nodes (Deudon et al., 2018; Kool et al., 2019). In contrast, the non-autoreereesive approaches, such as Qiu et al. (2022); Sun & Yang (2023); Li et al. (2023; 2024), estimate the likelihood of connecting each edge between nodes and construct the solution in one shot.
schemes. The autoregressive
Local improvement. This paradigm iteratively updates solutions using learned policies in two ways. First, repeatedly selects partial problems or decomposes the whole problem into separate subproblems, and reconstructs them using separate neural solver an OR solver (Li al., 2021; Fu et 2021; Zong et al., 2022; Cheng et al., 2023; Pan et al., 2023; Ye et al., 2024h; Zheng et al., 2024). Second, learns to predict stepwise searching to assist existing OR algorithms (Xin et al., 2021; Hudson et al., 2022; Zheng et al., 2022; Wu et al., 2022; Ye et al., 2023; Ma et al., 2023).
Despite promising in-distribution performance presented, specialized learning- -based approaches often fall short in handling out-of-distribution (OOD) instances since their neural networks were trained on fixed datasets (Li Zhang, 2025). Therefore, they often fail to compete with the reliability of established OR solvers. Such limitations hinder their applicability at practical scale. In fact, few studies have evaluated OOD performance on open-source TSPLIB instances with more than 5,000 nodes (Reinelt, 1991), limiting our understanding of their robustness in real-world scenarios.
2.3 LLMS/VV.MS-BASER APPROACHES
The surge of pre-trained LLMs/VLMs has drawn wide attention for optimization problems, including TSP. Yang et al. (2023) treats node coordinates as text input and prompts LLMs to output solutions, but the resulting solutions exhibit large optimality gaps even on small instances (i.e., N= 50). Another approach in Elhenawy et al. (2024) uses TSP images and relies the VLMs read node indices to construct tours. This design has limited scalability, as densely distributed nodes make difficult for the VL.Ms correctly recognize node indices. Liu al. (2024) prompts LLMSs for automatic heuristics design and translates them into code. However, their text-only framework overlooks instnnc--ppecffic spatial structure. Consequently, their standalone strategy exhibits large variance in optimality gaps when applied to varying TSPs, limiting their reliability for practical use.
3 METHODS
We reposition VLMs from unreliable end-to-end solvers practical complements that can be integrated with established OR tools in building scalable optimization routines. In contrast to graph- based neural solvers, which demand extensive training and still struggle to generalize, we leverage the generic multi-modal reasoning of VL.Ms to process TSP as an image, enabling them to interpret spatial structures and provide adaptive decompositions without task-specific training.
Building on this motivation, we propose the VITSP framework (Figure 1), which integrates VLM guidance into the optimization pipeline through three key modules: solution initialization, visual selection, and subproblem optimization. Starting from initial solution for given TSP instance (Sec 3.2 ), VLMs identify box coordinates that delineate promising subproblems for further refinement based on the visualized TSP solution (Sec 3.3. The exact solver then iteratively optimizes returned subproblems to improve global solutions (Sec 3.4). Iteratively solving subproblems allows certain subproblems to be optimized combinatorially under varying neighborhoods escape local optima.
3

---

Published as a conference paper at ICLR 2026
Original route
Visual selection of subproblems (See 5.3)
Marged super node
Removed route
Fixed
Optimized
Selected region
Vision language madel
Subproblem job
Instruation Trajantory
AA
Visual prompt
T
Text prompt
Asynchronous orchestration
VV VO-intensiive
VLMs
CP Unndereeeeeeee
Salvers
Global solution
Trajectory pool
Supprahiom quaua
Solution Inttialization (Sec 322
Subproblem optimization (Sec 3.4)
Figure The vision- vision-guided framework (VTTSP) large-scale TSP, where pre-trained VLMS and off- the-shelf solvers are asynchronously coordinated to identify and optimize subproblems, respectively.
Since visual selection and subproblem optimization have distinct computational overheads, VITSP co- ordinates their outputs asynchronously via a shared global solution, trajectory history, and subproblem queue to minimize the idle time in the subproblem optimization (Sec 3.5).
The key advantages that ensure the effectiveness and scalability our approach are threefold:
1. We leverage the pre-trained models to provide decomposition like heuristic rather than an error-prone end-to-end solution construction. As strong generalists for user-specified tasks, these models eliminate the need for ad hoc (re- Jtraining during real-world deployment.
2. Visually guiding the selection of box regions enables scalable subproblem decomposition
based on the geometric structure
the TSP instance grows in size.
3. We reformulate the identified subproblems as standard TSPs. This allows us to harness the robust exact solvers, guaranteeing high-quality improvement to the global solution.
3.1 PRELIMINARY: TRAVELING SALESMAN PROBLEM (TSP)
We briefly introduce the TSP in this section and provide detailed notations and descriptions in the Appendix A. A TSP characterized by a list of nodes and the corresponding coordinate sets or the distance matrix. The goal of TSP is to find an optimal tour //" that departs from initial node, visits each node exactly once, and returns to the starting node, which minimizes the total distance traveled L(II*). Notably, when the distance between known as symmetric TSP (STSP). In contrast, asymmetric TSP (ATSP) allows for different distances between certain node pairs in opposite directions.
nodes is identical both directions, the problem is
3.2 SOLUTION INITIALIZATION
The VITSP warm-started using heuristic solvers. Critically, to effectively handle OOD instances, VITSP avoids extensive parameter tuning and instead always uses the default settings of the solver. This eliminates the dependency on prior domain knowledge that would otherwise hinder ViTSP's adaptability to varying instances.
3.3 VISUAL SELECTION OF SURPROBLEMS BY VLMS
In the visual selection module (.), prompt VLMs select box regions and then formulate them as subproblems. We provide an overview of multimodal prompts and expected outputs in this section, and defer the detailed example prompts in Appendix C. The pseudocode for the visual selection process is detailed in Algorithm in Appendix D.
Visual prompts. Given TSP instance, plot its nodes and their current connections image based on their 2D coordinates and the global solution II. This image is input to VLMs as a visual prompt. An example of such visual input is illustrated in Figure 4 of Appendix C.
4

---

Published as a conference paper at ICLR 2026
Textual prompts. We specify three types of information textual inputs to an VLM: (1) meta- instructions I, detailing the subproblem selection task description and the expected output format; (2) selection trajectories + = { Ø2.... served memory to address the stateless nature of API-based VLM calls. Each trajectory entry @; includes a selected subproblem, the number of nodes within this subproblem, the solution gain through optimization, and the solver's runtime. The selection trajectories from earlier steps reveal instance-specific structures as the solving progresses, which informs VLMs to make better subsequent selections (Yang et al., 2023; Laskin al., 2023; Monea et al., 2024; Moeini et al., 2025); (3) Pending subproblems Q = fwi, u2...., indicating identified yet unsolved subproblems that remain in the queue. This avoids duplicated subproblems selected by VLMs.
Image-level output. The VLM prompted to generate a quadruple C = (Jmin: Tmax, Umin: Ymax) as a textual response. This quadruple represents the coordinates of a box region at the image level. As generative models, VLMs can be flexibly tailored to generate Q coordinate sets C1, C2. ........ Co per response (where Q 2). We will leverage these multiple-subproblem outputs during module orchestration as described in Section 3.5.
Forming subproblem. Given the current global solution II, connections to the covered nodes within a given box region are removed, leading to a list free nodes W = (w1, W2, W|W }. The remain-
[K] Te k))}. m denotes the k-th segment containing |c&| connected nodes; and कर and x denote the starting and ending nodes in the k-th segment, respectively. As result, the visual selection module produces a subproblem w = K).
ing connected nodes outside of the box form segments
{ =T )......... (5
where
Zoom-in reselection. VITSP employs zoom-in reselection to ensure scalability on very large-scale TSPs. Because such instances often exhibit highly dense node distributions, making connections in the initial visualization less discernible. To address this, a second round of selection is performed on the initially identified subregion bounded by C. If the number of nodes [W| covered by the subregion exceeds predefined threshold a, the VL. zooms into to examine the finer-grained pattern and identify a new quadruple C".
3.4 SUBPROBLEM OPTIMIZATION
Rather than training a dedicated neural solver to optimize selected subproblems separately, as in prior works that adopt the local improvement paradigm (Cheng et al., 2023; Pan et al., 2023; Zheng et al., 2024), we transform the formulated subproblem w (W, K)) into standard symmetric TSP (STSP). As existing exact solvers are primarily designed for STSP, this reformulation allows us to leverage solvers obtain globally feasible solution with guaranteed quality.
3.4.1 REFORMULATING SUBPROBLEMS
During subproblem optimization, free nodes are reconnected either to other free nodes or existing segments. Similarly, connections within each segment are preserved from the solution II, while the links between the segment's ' endpoints and the rest of the segments free nodes aggregating each segment (Tf...., m into a super node Sk. we construct a new list of nodes of size [K| + [W, denoted as (si,... $IK, W.,....Wii }. This updated node list leads to a partially asymmetric TSP (ATSP), characterized by an asymmetric block distance matrix:
refined. By
.........
DIKIIII Di D
D KI
DATSP =
((WIHI)))((W
where D D[i contains symmetric distances dwn,. between free nodes. The submatrices D Dw [ D D]]x|[W] and D [|x[R] are the root of asymmetry. D Pw x|K] contains distances d dw,,. from free nodes to the starting nodes of fixed segments, whereas D []]])[ represents distances d=t from the ending nodes of fixed segments to free nodes; D|K] indicates the distances day from the ending nodes of fixed segments the starting nodes of other segments.
We further transform this partially ATSP into a standard STSP to make compatible with the solver. Following the approaches in Jonker & Volgenant (1983); Cirasella et al. (2001), the trans- formation introduces a dummy node sy for each node s in the ATSP, expanding the node set to (81,... 8) $1.-.., K(x]) W1, []]..,,a]]]]]] w| )- The resulting STSP is characterized by a symmetric block
5

---

Published as a conference paper at ICLR 2026
distance matrix:
D DIWIXIKI Diwixim
D DIKIMIK D PiKxiii
DTTSP=
Dw x| DIKIXIKI
DIKIXII
(] (()(()2)))
where the diagonal of D || Kj is set to be a small enough value compared to the original D D which encourages the super nodes k and their corresponding dummy nodes k: + [W] to be adjacently connected during the optimization.
3.4.2 SOLVING AND RECOVERING THE SOLUTION FOR THE ORIGINAL TSP
The solver optimizes an STSP using its D DSTSP and produces an optimal solution STSSP. The output solution ST is then recovered into the corresponding ATSP solution AT by directly removing all dummy nodes in the solution 9T Furthermore, each super node 8% E lIrrSP is unfolded into its original segment ( T This recovery process results in an updated solution for the original TSP conditioned on the identified subproblem w: II* = Fssteer ( (DSTSP, Tixx w).
where max is the runtime limit set for the exact solvers. The time limit m forces the solver to stop improving lower bounds and return the best incumbent solutions. This prevents the solver from getting stuck certain subproblems for an excessively long time. We use the hill-clim hill-climbing rule in accepting this new solution if it reaches a lower objective value than the current solution.
3.5 ASYNCHRONOUS ORCHESTRATION
The visual selection module Faetecorr() (-) is I/O intensive, dominated by waiting for responses from the VLM server, whereas the exact solver module (-) () is CPU-intensive. Due to their distinct compu- tational profiles, sequential execution easily leaves solvers idle while waiting for VLM selection, and vice versa. To address this, VITSP executes the optimization and selection modules asynchronously on multi-core CPU systems, assigning them to separate cores and coordinating through three shared components: global solution I1, trajectory pool 4, and subproblem queue !2 These components provide the necessary contextual information required for module execution.
To further improve efficiency, VITSP deploys multiple VLMs and solvers. On the selection side, we employ both fast- thinking and reasoning VLMs, leveraging pre-trained models with complementary strengths (Shen et al., 2023; Snell et al., 2024; Kumar et al., 2025). Each single VLM is elicited to generate Q coordinate sets {C1, C2,,..., Cq} per prompt, where Q 2 2.
On the optimization side, multiple identical solvers retrieve and optimize subproblems from the shared queue in parallel, ensuring that newly generated subproblems are not left unprocessed. To mitigate conflicts in updating global solutions, VISPP assigns P "slave solvers" to optimize and screen the retrieved subproblems, while a single "master solver" is permitted to update II. "Slave solvers" discard subproblems without improvements, while those yielding net gains forwarded to the "master solver" for refining IT. The process continues iteratively until no improvement is observed in K consecutive steps. Detailed pseudo-code is provided in Algorithm 2 in Appendix E.
4
EXPERIMENTS AND RESULTS ANALYSIS
4.1 EXPERIMENTAI. SETUPS SETUPS
Evaluation datasets. To comprehensively assess the performance of VITSP, this work used TSP instances from TSPLIB (Reinelt, 1991) and a synthetic TSP-10K dataset with uniformly distributed nodes as primary evaluation datasets. The synthetic dataset contains 16 instances, following (Fang al., 2024). TSPLIB offers wide range of real-worid instances for TSP, covering diverse dis- tributions and scales. Moreover, Reinelt (2007) provides proven optimality for TSPL.B instances, enabling the measurement of optimality gaps even at very large scales. We chose TSP instances with N > 000 from the dataset to represent (very-)large-scall problems, where exact solvers begin to struggle. This results in 33 TSPLIB instances. These instances follow a naming format of keywords [ass]nnubee [number of nodes], such pla8590G Instances with the same keywords from the same application domain. Notably, since our framework does not require additional training or fine-tuning during implementation, we do not curate any training dataset.
None of the TSPLIB instances has been exposed to the baseline learning- based algorithms during their training phase. This ensures fair evaluation of generalizability and scalability across all baselines.

---

Published as a conference paper at ICLR 2026
To the best of our knowledge, work provides one of the most comprehensive evaluations this real-world benchmark dataset, offering a thorough assessment of the proposed VITSP.
Evaluation metrics. We used two metrics to measure the performance of algorithmss (1) Optimality gaps (%); and (2) Runtime (in seconds). We used the reported proven optimal objective values I. (total distance traveled) for TSPLIB instances in Reinelt (2007) reference and the gap is calculated as: _ x 100%, where LMtdel is the objective value produced by a baseline model. The recorded wall-clock runtime of VITSP explicitly includes (1) the LKH initialization, (2) all VLM API waiting and latency, and (3) the Concorde solving time for subproblems. Thus, our reported time reflects the actual end-to- wall time required by VITSP in real-world settings.
VTTSP setups. In the initialization module, we used LKH-3 with its default parameter settings to warm start the VITSP. In the visual selection module, we employed GPT-4.1 (fast thinking VLM) and 04-mini (reasoning VLM) as the selectors in this study. We set the number of subproblems generated per prompt Q 2. In the subproblem optimization module, Concorde, the SOTA exact solver, was utilized as the subproblem solver. VITSP terminates when no improvement is observed in K consecutive steps, and the duration from initialization to termination is recorded as runtime. We ran VITSP for five runs and obtained the average gaps and runtimes. For more detailed parameter configurations, please refer to Section F.5 in Appendix F.
Baselines. We compared our VITSP against both classical OR approaches and learning-based approaches. Specifically, applied the following ten baselines: (1) Concorde; (2) LKH-3 (Default); (3) LKH-3 (more RUNS) (4) FI; (5) AM; (6) DIFUSCO; (7) INViT; (8) SIT; (9) DeepACO; (10) SO; (11) UDC; (12) EoH. Their description and implementation are provided in the Appendix F.
The selected learning-based approaches include both end-to-end solution construction methods and local improvement techniques that match the decomposition heuristics used in this study. They either provided source code and pre-trained checkpoints or reported results on TSPLIB instances (e.g., SO). The selected EoH produced applicable results on large-scale instances, whereas other LLM--based approaches, such as Yang et al. (2023); Elhenawy et al. (2024), failed to generate valid solutions even on small-scale cases and were therefore not included as baselines in this study.
We align the runtime across baselines to ensure fair comparison. In addition to using the default parameter values of LKH-3, we introduce LKH-3 (more RUNS), where the RUNS value increased to match LKH-3's runtime with that of VTTSP on each instance. Similarly. Concorde, DeepACO, UDC, and EoH are run with the same or slightly longer time limit as VTTPP For FI, runtime is deterministic with respect to instance size. End-to-end methods (AM, DIFUSCO, and INVIT) also have deterministic runtimes, as they perform only a single feedforward inference. When running synthetic TSP-10K, set the timelimit 600 compare baselines' performances.
Hardware. We used an AMD EPYC 7443 24-Core CPU and an Nvidia L40 GPU with 48GB memory to implement our work and bascline algorithms. In VITSP, the VLMs were accessed demand online. Their usage did not rely on local GPU resources but was confined by the I/O rate.
4.2 MAIN RESULTS
We summarize the full performance comparison results in Table I (22 large TSPLIB instances) and Table 2 (11 very-large instances), reporting runtime (in seconds) and optimality gaps with the lowest gaps highlighted. The results of VITSP are averaged over five runs. The selected box regions yielding gap reductions by VLMs are illustrated in Appendix H.
Overall, VITSP achieves an average optimality gap of 0.24%, outperforming classical OR methods, including LKH-3 (more RUNS) 0.31% and Concorde at 0.34%. In contrast to maaming-based methods that fail to generalize to these unseen TSPLIB instances, VITSP demonstrates consistently superior performance. More specifically, VITSP attains the best performance on 20 (highlighted) out of 33 instances even when classical OR methods are allocated equal longer runtimes. At instance-level, in relative to the optimality gaps of LKH-3, ViTSP further reduced gaps by 3.57% to 100.00%. While LKH-3 remains highly efficient for large instances with 1, 000 N < 4, 000, the SOTA heuristic, the advantage of VITSP becomes more pronounced as instance size further increases.
Since VITSP is warm-started from LKH-3 (Default), we further compare the reduction of optimality gaps over time between VITSP and LKH-3 (more RUNS) on selected instances of different scales in Figure 2. When given small amount of additional runtime beyond LKH-3's default settings,
7

---

Published as a conference paper at ICLR 2026
it reduces optimality gaps more rapidly than ViTSP in the early phase. However, its improvement quickly plateaus, whereas VITSP continues to improve and eventually surpasses or matches LKH-3. As the problem size increases beyond 4, 000 in Table 2, VVTSP significantly speeds up the reduction of optimality gaps and consistently reaches lower gaps compared to LKH-3. We present the complete results for optimality gap reduction over time across all TSPLIB instances between VITSP and L.H-3 in Appendix G.
Table 1: Performance comparison on 22 large TSPLIB instances (1000 S n < 4000).
dsj1000
pr1002
u1060
vmm1044
pcb1173
d1291
v11.94
vI1323
mrw1379
B1400
uI432
Concorde
Gap
Timels)
0.00%
46.2
0.00%
8.3
0.00%
106.7
0.00%
57.5
0.00%5
50.2
0.65%
252.5
0.00%
25.8
0.03%
122.3
0.00%
45,7
0.24%
115.4
0.03%
111.8
LKH-3
Timels)
1.9
2.0
2.5
2.7
4.5
(Defaulo
Gap
0.17%
0.47%
0,53%
0.12%
1.00%
0.61%
0.55%
0.21%
0.61%
0.19%
0,541
LKH-3
Timels)
20.5
95,1
100.4
22.9
93.0
248.8
45,9
99.2
162.4
75.0
95.6
(RUNS)
0.0015
0.00%
0.0118
00.00%
0.0015
0.001
0.05%
0.18%
0.0311
Time(s)
0.4
0.5
0.7
Gap
11.25%
10.30%
12.45%
9.51%
15.27%
21,50%
22.99%
20.7816
11.29%
4.17%
12.71%
AM (G)
Time(s)
Gup
41.43%
0.8
0.7
40.57%
56.78%
0.8
44.05%
41.71%
18.82%
1.0
38.22%
42.85%
1.1
37.74%
63.15%
1.1
37.27%
1.1
DIFUSCO
Timels)
23.6
23.1
23.9
25.8
29.3
31,9
33,1
34.7
36,1
33,1
37,4
2-opp)
Gup
7.83%
9.04%
7.5216
9,2611
9.201
9.22%
8.23%
9.70%
4.48%
8.8011
INVIT
Gup
Timels)
7.6
8.68%
6.5
10.55%
6.7
9.74%
6.61%
6.5
8.1
6.85%
8.92%
8.7
8.3
8,978
8.33%
8.4
6.57%
10.0
8.7
13.86%
10.1
5.09%
Timels)
70.1
66.0
51.2
38,9
124,3
169.2
27.4
95.7
104.8
54,1
83,5
Gap
1.21%
1,33%
4.33%
1.35%
1.55%
2.28%%
DeepACO
Timeis)
Gog
21.51%
165.1
20,966
37.97%
167.0
34.59%
20.40%
24.85%
199.7
35,00%
29.60%
200.8
209.8
18.92%
215.7
45.59%
213.4
14.75%
S0
Gap
Timels)
NEA
NA
35.0
2.21%
2.20%
35,0
2,87%
36.0
N/A
6.76%
42.0
12.0
4.21%
44.0
1.63%
45.0
1.96%
N/A
ULX
Time(s)
Gap
15.36%
91.5
18.75%
32.81%
29.28%
20.70%
25.30%
242.8
28.29%
18.01%
123.2
18.94%
33.57%
89.2
17.33%
Boll
Time(s)
Gop
448.088
48.1
93.2
56.86%
62.7
596.534
$3.8
6.47%
104.29%
137.7
245.3
18.315
89.73%
41.9
50.14%
123.5
94.52%
146.2
69.8
36.38%
87,4
35.99%
VITSP
Timels)
69.6
65.0
57.1
38.5
124.3
168.6
27.2
95.6
104.6
53.9
83.2
Gap
0,02%
0.01%
0.0015
0.00%
0.1618
0.15%
0.14%
03031
0.00%
0.18%
0.0314
B1577
d1655
vm1778
u1817
#11889
d2103
u2152
u2319
pr2392
pcb3038
B3399
Concorde
Gap
Timels)
262.7
1,525
0.00%
24.4
0.05%
189.4
0.34%
199.8
0.09%
112.3
100.0
147%
0.25%
314.7
0.115
443.9
0.00%
13.1
390.6
0.11%
0.44%
600.0
LKI1-3
Time(s)
4.0
5.3
6.1
11.4
15.3
25.1
(Default)
Gap
0.25%
0.80%
0.55%
1.11%
0.57%
0.54%
0.95%
0.32%
1.08%
1.20%5
1.73%
LKH-3
Time(s)
16.3
150.0
180.0
202.3
118.8
104.5
331.5
316.4
282.1
407.6
$27.4
(RUNS)
Gap
0,00%
0.00%
0.12%
00.15
0.061
0.00%
0.09%
0.08%
0.03%%
0.12%
0,67%
Time(s)
1.0
1.2
1.7
2.1
Gap
17.61%
15.41%
11.00%
18.10%
17.63%
23,575
20.65%
6.54%
13.71%
14,92%
17.57%
(M)
Time(s)
Gup
51.92%
1.3
61.15%
49.56%
1.5
56.51%
49,57%
55.48%
1.9
66. 66.28%
2.2
29, 92.9%%
62.35%
3.1
62.33%
84.55%
DIFUSCO
Timeis)
44.3
46.2
$3.8
55.9
61.4
77,8
79.1
94.8
111.22
214.1
327.3
2-0pe)
Gap
7.66%%
10.33%
8.93%
13.47%
12,655
13.949%
5.72%
10.74%
10.95%
6,98%
INVT
Gop
Time(s)
7.68%
10.7
12.7
11.54%
8.26%
11.8
8.32%
13.4
10.03%
13,1
15.9
7.74%
7.11%
17.1
0.93%
18.8
8.12%
20.7
30.0
7.85%
36.4
15.15%
SIT
Gup
Timeis)
$9.0
5.04%
111.6
1.17%
163.1
180.3
89.2
$4.5
238.5
0.22%
245.1
187.8
336.6
7.55%
252.7
DeepACO
Timeis)
236.8
241.7
250.8
276.3
296.3
321.1
418.0
Gop
42.74%
25.46%
34.78%
25.78
42.15%
19.32%
24.52%
11.12%
30.43%
24.71%
SO
Time's)
51.0
N/A
53
N/A
39.0
71.0
66.0
N/A
N/A
93.0
121.0
Gap
4,425%
3.615
4.63%%
8.32%
4.91%
2.67%
5.49%
UDC
Timels)
146.8
178.3
265.1
364.5
Gop
24.94%
19.55%
33.24%
24.43%
36.28%
15.79%
27.32%
21.52%
28.258
26.98%
BoH
Timels)
Gap
181.7588
26.82%
3.47%
179.6
18.07%
515.05%
108.3
279.006
57.30%
50.31%
265.7
11.71%
365.5
33.82%
39.464
VITSP
Time's)
58.9
111.2
162.8
180.0
89.0
84,0
238.3
244.9
187.6
336.3
252.4
Gup
0.00%
0.00%
0.05%
0.24%
0.03%
0.39%
0.08%
0.08%
0.091
0.09%
0,5718
Ogdinnllty Gas PN)
u u1060
Optma by Gap (Ng
u2319
n5934
ny by Gap (8)
usal 36699
a55000
Orpimallty Cep
Detmalty exp
1.0
R2
LKH
8,0
25
50
103
200
300
8.0
750
(scoonds
Runlime (seconda)
Rundime (secorda))
Runtimc (seconds)
Runlmm (seconds)
Figure 2: Optimality gaps over time on selected instances between VITSP and LKH-3 (more RUNS).
8

---

Published as a conference paper at ICLR 2026
Table 2: Performance comparison on 11 very-large TSPLIB instances (4000 n 85900).
#19915
pla7397
r111849
usa13509
d15112
pla33810
pla85900
Concurde
Time(s)
305.0
$50.0
266.0
671.3
1000.0
1742.0
2500.0
2941.0
Gup
0.30%
0.67%
0.89%
0.48%
0.85%
0.48%
0.49%
0.44%
0.57%
LKIE-3
Timels)
39.8
63.3
61.00
92.0
3118
382,9
417.5
521.3
728.2
2079.7
22346,0
(Defaulo
Gap
0.96%
1.96%
1,36%
0.83%
1.75R
1.25%
1.88%
1.22%
1.29%
1.43%
1.31%
LKH--
Time(s)
202.9
1014,4
2974.5
3176.2
8237.9
33066.5
(RUNS)
Gup
0.45%
0.73%
0.47%
0.29%
1.06%
0.81%
0.82%
0.84%
0.44%
1.00%
1.13%
Time(s)
8.85
14,96
15:42
22.26
60.50
82.51
$9.38
104.11
155.37
462.16
3264,
FI
Cup
11.30%
22.15%
20.91%
13.24%
19, 19.795
12,52%
11.64%
11.67%
11.77%
16,84%
14 46%
(M) (G)
Time(s)
Gap
5.18
7.97
8.23
11006
107.178
23,51
29.63
31,62
35.46
448.44%
50.37
153.60
959.18
(8 2-0pt)
DIFUSCO
Time(s)
Gap
11.03%
596.0
1321.0
11.531
11.01%
1317.3
9.32%
1946.9
5097.6
52.49%
26.47%
6598.8
53,809
7098.5
61.81%
82268
80.45%
13163.2
00M
COM
INVIT
Time(s)
55.3
51,4
$1.5
73.6
154.0
220.0
232.4
234.3
373.9
1010.4
5910.8
Cap
6.58%
9,438
10.84%
7.66%
10.19%
9.21
8.38%
6.3%
SIT
Time(s)
277,4
386.5
485.7
575.6
785.2
995.5
1725.9
2173.2
2320.1
5759.3
29864.0
Gup
1.42%
3,46%
5.09%
.666
5.01%
12.34%
4.39%
3.50%
3.73%
4.40%
6.60%
DeepACO
Time(s)
594.7
766.9
763.7
1061.7
25134
3424,8
38188
4560.3
7665.8
53819.5
COM
Gap
37.31%
73.034%
77.79%
76.26%
94,37%
130.05%
102.88%
$4.05%
100.42%
160.7998
Timets)
139,00
196,00
N/A
NIA
Gap
2.43%
7.99%
6.14%
UDC
Timets)
304.1
ODM
00M
00M
OOM
O0M
00M
00M
00M
0OM
OOM
Cup
12.80%
FaH
Timels)
Gap
305.1
3.10%
15.15%
539.2
26.08%
168.2
23.72%
739,2
814,8666
725.6
60.94%
961.0
70.6458
1764.5
2501.7
11.41%
Failed
Failed
Failed
VIIP
Timets) Gup
277.3
386.5
485.5
578.5
785.1
995.2
1725.3
2172.0
2319.0
5758,1
29863.6
1.13%
0.28%
0.4715
0,31%
Learning-basee methods struggle to generalize their learned policies to OOD instances, leading to inferior performance compared to VITSP. Large gaps remain across the baselines, which impair their utilization at practical scale. For example, AM and DeepACO underperform the simple heuristic algorithm FI, demonstrating their brittleness when no model reconfiguration or time-consuming retraining performed. Furthermore, due to their high GPU memory requirements, all learning- algorithms except AM and INVIT fail to scale to p 859000 and encounter out-of-memory (0OM) errors. Notably, UDC suffers from OOM when the instance size exceeds 5,000, failing to produce feasible decomposition heuristics for very large-scale TSPs. For LLM-based approaches, EoH shows limited effectiveness in designing heuristics for varying TSP instances, exhibiting high variance in optimality gaps across all TSPLIB instances in both Table and Table 2. These observations highlight the advantage of VITSP, which leverages generative models to visually guide high-quality decomposition heuristics while reducing reliance on local GPU resources and (re-)training.
The results on very-large-scale synthetic TSP (Table 3) further confirm the effectiveness of our proposed VITSP, matching with the superior performance of VITSP in TSPLIB instances with n> 10,000 Notably, VITSP outperforms standalone LKH-3 and other learning-bass methods. Even though SIT has been trained on TSP-10K, it is still less effective than VITSP at such scale even longer runtime budgets were given.
Table 3: Performance comparison on uniform instances with 72 10, 000.
Near- optimaityy
(mone RUNs)
LKH-3
FI
AMGG)
(5 (5+22-up 2-upt
DIFUSCO
INVIT
SIT (PRC,1000)
DespACO
SO
UDC
VIISP
Cbjj
71.78
72.54
80.59
141.68
73.89
76.09
73.08
79.76
NIA
ODM
72.38
Gap
1.06%
12.27%
97.38%
2.94%
6.01%
1815
11.12%
0.70%
Time
553
17.5
30.9
605.1
613.7
Our experiments suggest that certain TSP structures can make optimization more or less difficult. Although pr pr 92 is twice the size of prcc1111 13,, Concorde uses only 26% of the time required for prel1 1 73 to reach optimality for pr2392. Also, both VITSP and LKH-3 struggle find high-quality solutions on fl14 4 00, and VITSP shows difficulty in reducing gaps on d21 0.100 03 and r15915.
To further elucidate the efficiency and practical cost of VITSP, provide a detailed analysis of iteration-level behavior, valid subproblem rates, and VLM API expenses in Appendix I.
4.3 ABLATION STUDIES
The effectiveness of VLMs. To verify that VLMs can conduct principled selection as visual selectors, rather than fruitless permutation,
devise two heuristic selection policies adopted from Li et al. (2021) and Cheng et al. (2023): (1) Random sequence selector: uniformly and randomly selecting segment of given length from the tour. The segment length is set to match the average number
9

---

Published as a conference paper at ICLR 2026
of nodes selected per step by ViTSP. (2) Random box selector: uniformly and randomly selecting rectangular subproblems of random sizes. It chooses Q = 2 subproblems at each step, the same as in VITSP. We replace the default VLM selector modules with these alternatives in ViTSP and execute the same experiments on a given instance, where all scenarios start with solutions initialized using LKH-3. Due the page limit, we report the optimality gaps over time using different selector policies on selected instances in Figure 3. The full results are illustrated in Appendix J.
Oytinalyy 19
u1060
Defeaa Ge PNN
U2319
1%% deg Ainupo
Lset 1350
ple65900
& 0
1.0
VITSP Random Sequance Belaclor Random Sulector
82
0.5
2.0
200
453
Runtime (ssconds)
Runtin (seconda)
Rundmm (scoonds)
Runlime
Rurtimm (secondss)
Figure 3: Ablation studies of different selection policies on selected instances. VLMs are capable of performing meaningful, non-random subproblem selection as prompted in the framework VITSP. As shown in Figure 3, VTTSP consistently reduces optimality gaps over time and outpaces both random sequence and random box methods. This highlights the effectiveness of visually leveraging instance-speciffe structures to guide subproblem selection and generalize to (very-) large-scale unseen TSP instances.
While the two random selection strategies demonstrate some ability to reduce gaps, they consistently converge to local optima. Interestingly, for pla85900, the random sequence selection outperforms VITSP in the early stages by reducing the gap more rapidly. This suggests the potential value of alternative operations beyond the box-region selection used in this study.
The effect of solution initialization. We examine the impact of solution initialization on the overall performance of VITSP. Based on the same runtime budget, we run VITSP using LKH-3 with default parameters and FI, respectively, to imitialize the solution. We report the average optimality gaps based on five runs in Table 4. The results show that the ViTSP initialized by LKH consistently outperforms the one initialized by FI, since LKH is known for providing higher quality solutions. These results confirm that while initialization affects performance, the VLM-guided decomposition consistently improves over its corresponding initialization baseline.
Table 4: Optimality gap comparison of VITSP under LKH and FI initializations
ds,1000
pe1002
n1060
vma084
pcb1173
d1291
a13304
d1325
arw1379
81400
u1432
Time LKH
69.6
65.0
57.1
38.5
124.3
168.6
27.2
95.6
105.6
53,9
83.2
0.02%
0.11%
0.16%
0.15%
0.14%
0.0%
0.00%
0.18%
0.03%
F1
0.50%
0.03%
0.64%
0.67%
0.21%
2.42%
8.01%
0.39%
0.01%
1,30%
L.43%
B1577
d1655
vm1748
w1817
d1889
62103
22152
22319
pr239
pcb3038
B3795
Time 64)
58.9
111.2
1628
180.0
89.0
84.0
238.3
244.9
187.
336.3
252.4
I.H
0.00%
0.00%
0.5%%
0.445
0.03%
0.39%
0.85
0.06%
0.09%
0.09%
0.575
FI
17.61%
6.56%
0.04%
3.16%
0.50%
23.55%
0.98%
0.07%
0.41%
0.34%8
3. 3.02%
fn14461
d35115
115934
pla7397
d11849
usa13508
bed14051
d15112
d18512
pla33810
pla82900
Time (s)
277.3
286.5
485.5
575.5
785.1
995.2
1725.3
2172.0
2319.0
5758.1
29863.6
LKII
0.16%
1.3%%
0.1%%
0.28%
1.03%
0.47%
0.31%
0.22%
0.36%
0.52%
0.83%
2.49%
8.42%
6.40%
5.72%
8.89%
0.52%
0.34%
2.81%
5 CONCLUSIONS
In this study, we proposed vision-guided framework to effectively solve TSPs with varying scales and distributions. VITSP hybridizes the strength of pre-trained VLMs and existing OR techniques by selecting instance-specific subproblems visually and then delegating them off-the-shelf solver. Our proposed VITSP bypasses ad hoc training while exhibiting effectiveness and scalability, achieving lower average optimality gaps than LKH-3 and baseline learning- based approaches. Because TSP serves as the base case for a wide family of routing problems, the promising results from VITSP suggest opportunities to expand our framework other routing problems. While this study validates the effectiveness of visual guidance, interpreting how the decomposition is determined lies beyond our current scope and remains an important future direction. Additionally, lightweight fine-tuning of offline VLMs, and further exploration of in-context reinforcement learning, represent promising future directions to further enhance performance of VLMs for TSP and broad routing problems. Further limitations are discussed in the Appendix K. More broadly, this work highlights the potential of using generative AI to support CO at practical scales, particularly in settings where abundant training data is unavailable.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
I lacknowledge that and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics. To the best of our knowledge, this work does not involve potential violations of the ICLR Code Ethics.
REPRODUCIBILITY STATEMENT
We have made efforts ensure the reproducibility of this work. The source code is available https: h/g/tttuu tiit..u... itap. purdue- edd/uuMAaRR /w//////M//// /ViTTTT//VTPPP TttT/VVVSSS_IIR222255555 ICLR2026. Details of the exper- imental setup are provided in Section 4.1 of the main text and in Sections C and F.5 of the Appendix to further support reproducibility. Additionally, the TSPLIB dataset used in this study is publicly available, which ensures the reproducibility of the results.
THE USE OF LARGE LANGUAGE MODELS (LLMs)
The authors confirm that LLMs were used only for grammar checking and text polishing. They were not involved in research ideation. Their role writing was limited, such that they are not considered contributors.
REFERENCES
Belarmino Adenso-Dia and Manuel Laguna. Fine-Tuning of Algorithms Using Fractional Ex-
perimental Designs and Local Search. Operations Research, 54(1):99-114 February 2006.
ISSN 0030-364X, 1526-5463. doi: 00.1287//rre.15500024... URL https:://///e //pp/////oo/no/////////////ooo iine
1050.0243.
informs wwwp///g///o///oooo /toddoii11110 wtt.1118/ooppr 10w............................. 0243..223.....
David L. Applegate. The traveling salesman problem: a computational study, vol-
ume 17. Princeton university press, 2006. URL
google com/
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Qingfu Zhang, Joungho Kim, Jie Zhang, Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song, Changhyun Kwon, Kevin Tierney, Lin Xie, and Jinkyoo Park. RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark, June 2024. URL http:// /tap:://rree vwvvv org/ abs/ 2230/33.11.1 171117000011 00. arXiv:2306. 17100 [cs].
Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learning to solve large-scale tsp instances. In International Conference on Artificial Intelligence and Statis- tics, pp. 1219-1231. PMLR, 2023. URL https: httt:::/pproceedinng mlr. press/v206/ cheng23 3a html.
Jill Cirasella, David S. Johnson, Lyle A. McGeoch, and Weixiong Zhang. The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. Adam L. Buchsbaum and Jack Snoeyink (eds.), Algorithm Engineering and Experimentation, pp. 32-59, Berlin, Heidelberg, 2001. Springer. ISBN 378-3-540-44808-2. doi: 10.1007/3- 1110073-5500-4445 4400- X_3
Donald Davendra (ed.). Traveling Salesman Problem, Theory and Applications. InTTec,, December 2010. ISBN 978-953-307-4223
doi: 10.5772/547.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning Heuristics for the TSP by Policy Gradient. In Willem-Jan Van Hoeve (ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research, volume 10848, pp. 170-181. Springer International Publishing, Cham, 2018. ISBN 978-3-319-930303 978-3-319- 93031-2, doi: 10. 1011100077--311111 3-1-333991999-2-2--- 93031-2_12, URL https: /link. spr.sgeriee.... com/ 10. 1007 3- 93031
Series Title: Lecture Notes in Computer Science.
11

---

Published as a conference paper at ICLR 2026
Mohammed Elhenawy, Ahmad Abutahoun, Taqwa I. Alhadidi, Ahmed Jaber, Huthaifa I. Ashqar, Shadi Jaradat, Ahmed Abdelhay, Sebastien Glaser, and Andry Rakotonirainy. Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs); Solving TSP and mTTP Combinatorial Challenges, June 2024. URL /tt.ihttt////rrtt..rr/////////// arXiv:2407.00099
Han Fang. Zhihao Song, Paul Weng, and Yutong Ban. INVIT: generalizable routing problem solver with invariant nested view transformer. In Proceedings of the 41st International Conference on Muchine Learning, volume 235 of ICML 24, pp. 12973-12992, Vienna, Austria, July 2024.
JMLR.org.
Zhang-Huu Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize Small Pre-trained Model to Arbitrarily Large TSP Instances. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8):
7474-7482, May 2021. ISSN 2374-3468, 2159-5399 doi: 10. 10.1609/anai.v35i88 16916. URL
https://ojs.eet www.aaaii..igiie.....rr.a
AAAI http:////A////aircc/////////////
Keld Helsgaun. Short description of the parameters to LKH-2.0, March 2016. URL
http::/weblti http//wwwbeeeeeeeeeoccoeee ruc hekk/kkel//esaaeeee /ttp:///////./////////////// /DDOC/LKH-2.
LKH-
0 PAPAAAAARRSSS.. pdf.
Keld Helsgaun. An extension of the Kinn-Kegghhaa-eelggaa TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-980, 2017. URL
http::/akkee ruc. dk wtt.////e//eeeeeee//eeaaaaaaa LKH REPORE pdf..
John H. Holland. Genetic algorithms. Scientific american, 267(():66-73,, 1992. URL https:
Xtt.araiiccciicoooooooooaaaaaaar DAUUSS DAUUSs
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph Neural Network Guided Local Search for the Traveling Salesperson Problem, April 2022. URL http: pettt:://ariii /arxiv. org/ 2210..111.0 05291, arXiv:2110.05291 [cs].
Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforced multi-pointe transformer for the traveling salesman problem. In Proceedings the the
AAAI Conference on Artificial Intelligence, volume 37, pp. 8132-8140, 2023. /ttp::/:: //js www...a............. org. ittp//idexx..///// http:///taaaaaiie//e////////////
Roy Jonker and Ton Volgenant. Transforming asymmetric into symmetrie traveling salesman problems. Operations Research Letters, 264):161 November 1983. ISSN 0167-6377. doi:
10.101660667-63778839990088 URL https: wwww http://wwwwwwwwweeeeeeeeeeeee..e www.eeeedeeedddecccoooooo. wwtpc/i/////////cccccccccccccccc articcle/p110011777788838
Chaitanya K. Joshi, Quentin Cappart, Louis- Rousseau, and Thomas Laurent. Learning the Travelling Salesperson Problem Requires Rethinking Generalization, May 2022. URL http: 07054. arXiv:2006.07054.
Muhammad Asif Khan and Layth Hamad. On the Capability of LLMs in Combinatorial Optimization, November 2024. URL /tt.tttttt/////...ccc.t....oooo http:///sseee///////r/riiie commi hr
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems!. February 2019. URL http:hhttt/aaeeee
httg:/bb/110000 08475. arXiv:1803.088. 100.00883 [cs, stat].
Komal Kumar, Tajamul Ashraf, Omkar Thawakar, Rao Muhammad Anwer, Hisham Cholakkal, Mubarak Shah, Ming- Hsuan Yang. Phillip H. S. Torr, Salman Khan, and Fahad Shahbaz Khan. LLM Post- Training: A Deep Dive into Reasoning Large Language Models, February 2025. URL http://arxist org/ abs 2202 21321. arXiv:2502.21321 [es].
12

---

Published as a conference paper at ICLR 2026
Yeong-Das Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO:
Policy Optimization with Multiple Optima for Reinforcement Learning. In Ad- vances in Neural Information Processing Systems, volume 33, pp. 21188- 21198. Curran As- sociates, Inc., 2020. URL htt.:tts:// http::ssss/////pepepeoeceoeeeeee www.eiiiisnnnnnnnneeeeeeeeeeeeee neurips cc/ pttpp/ppppr//////// 2000r///00////////// / --bsttrctt.........ao......aa..e html.
Gilbert Laporte. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Rexeurch, 59(2)233-224,, June 1992. ISSN 03772217. doi: 10.
1016603777-221779299011333 URL https: www.iiiiniigh.... www.bb..eleeveiee. com/ retrieve/
Michael Laskin, Luyu Wang, Junhyuk Oh, Emilio Parisotto, Stephen Spencer, Richie Steigerwald, DJ Strouse, Steven Hansen, Angelos Filos. Ethan Brooks, Maxime Gazeau, Himanshu Sahni, Satinder Singh, and Volodymyr Mnih. IN-CONTEXT REINFORCEMENT LEARNING WITH AL.GORITHM DISTILLATION. 2023.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In Advances in Neural Information Processing Systems, volume 34, pp. 1198122111. Curran As- sociates, Inc., 2021, URL httpss://proceeediiiiiien// Falff217lleee aa (55
neurips cc/ http:/appr/22111/m/e2 html.
Xiayang Li and Shihua Zhang. Learning TSP-Solvers Tend to Be Overly Greedy, February 2025. URL htttp::/arxxv..og//aat..
C0767, arXiv:250200076 [cs].
Yang Li, Jinpei Guo, Runzhong Wang. and Junchi Yan. T2:: From distribution learn- ing in training to gradient search in testing for combinatorial optimization. Ad- vances Neural Information Processing Systems, 36:50020-50040, 2023.
URL
nwwrips cct.cc/ccppppeeeeeee http://aappppeeeeeeeeeeeeeeeeeee https: hww.eeeepsiinn......s..........e http::://proceediing
http://aaeeeeeeeee2/2.2 / html.
Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast T2T: Optimization Con- sistency Speeds Up Diffusion-Basel Training-to- te-tttingg Solving for Combinatorial Optimization. 2024.
Fei Liu, Tong Xialiang, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model. In Proceddings of the 41st International Conference on Machine Learning, July 2024. URL httpt:://///. https::/proceed.aeee wttppnnwww.............eeee
mlr wwwpppreesseee 1iu2 4bs .hmll.
Fu Luo, Xi Lin, Yaoxin Wu, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Boosting neural combinatorial optimization for large-scale vehicle routing problems. In The Thirteenth International Conference on Learning Representations, 2025. URL https:
//openreview..omm////oe wwwenreview.ne//ooreee forum?id Tor TDTJJNjumY.
Yining Ma, Zhiguang Cao. and Yeow Meng Chee. Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt. In Advances in Neural Information Processing Systems, volume 36, pp. 49555 49578, December 2023. URL https:: htttps://proceedinngg -atpraacceeeo---aaatttt-------o
html.
Amir Moeini, Jiuqi Wang. Jacob Beck, Ethan Blaser, Shimon Whiteson, Rohan Chandra, and Shangtong Zhang. A Survey of In-Context Reinforcement Learning, February 2025. URI http:///rxivv
orwoor///oo. argg/bb/ abs/2502. .79778. arXiv:2502.07978 [es].
Giovanni Monea, Antoine Bosselut, Kianté Brantley, and Yoav Artzi LLMs Are In-Context Reinforcement Learners, October 2024. URL htttt:://xxxivoor//bbbaee arXiv:2410.05362.
05362.
Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, and Jiang Bian. H- TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem. Proceedings of the AAAI Conference Artificial Intelligence, 37(8):935-995) 99553, June 2023. ISSN 2374-3468, 2159. 5399. doi: 10. 10.1609/ v37ii//aii............. 26122. URL https: /ojs. j.s.... aaai. org index..exx.///// /AAI/AAI/ article/ ew 2
13

---

Published as a conference paper at ICLR 2026
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A Differentiable Meta Solver for Combina- torial Optimization Problems, October 2022. URL http:://axxxv..rrgg///// arXiv:2210.04123.
2210. 04123.
Gerhard Reinelt. TSPLIB-A Traveling Salesman Problem Library. ORSA Journal on Compuling,
3(4):376-384, November 1991. ISSN 0899-1499, 2326-3245, doi: 10.1 00.1287/jjo......3777 URL
htttps://puboolinee informs....... ozg/ http://////// 1tt.0..887/// 1287/1jocc 3.4.376
Gerhard Reinelt. Optimal solutions for symmetric tsps, May 2007. URL http: http://comopt... http:/tcooppttcccoooooooo .ff.
uni-heidell berg. de/ http//ottwareeee htt.t//wwwew/SPPP////////
html.
Daniel J. Rosenkrantz, Richard Edwin Stearns, and Philip M. Lewis. Approximate algorithms for the traveling salesperson problem. In 15th Annual Symposium Switching and Aulomata Theory
(swat 1974), pp. 33-42, IEEE, 1974. URL https: httpe/eeeeeepporeeee Leee wwg.ooog///o......oooo... abspractt/ document / /11.////595569// casa http://aaaaaaaaaaaaaaeeoeeoeeeee AAw. 6og.aaaa11-- eeox
Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. Hug- gingGPT: Solving AI Tasks with ChatGPT and its Friends in HuggingFace, April 2023. URL
http:// org/ abs
17580. arXiv:2303.1758 [es].
Charlie Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM Test-Time Compute Optimally be More Effective than Scaling Model Parameters, August 2024. URL http:
//arxiv. wrg./oorggoooo.... abs 2408. 03314. arXiv:2408.03311 [cs].
Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based Diffusion Solvers for Combina- torial Optimization, December 2023. URL http: www.eiiv..rrg/.eooooo /abs aww.ab//22222 08224.
arXiv:2302.08224.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, f. ukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: https://procediing www.ddiiiiinnnnnnnnioeeeee httplpps..pppppppeepeeee cccpppprr/211//aahh
Laurence A. Wolsey, Integer programming. John Wiley & Sons, 2020.
URL
http.///obbotttheeeeerreaaedeeee Xt- (e--92c3eccko61ffsssstttss
https: //tooss////oos///
oi
Chen Wu, Yin Song. Verdi March, and Eden Duthie. Learning from Drivers to Tackle the Amazon Last Mile Routing Research Challenge, May 2022. URL httLitt///xxxx..rrgg abs 2205. 04001. arXiv:2205.0400 [cs].
Xuan Wu, Di Wang, Lijie Wen, Yubin Xiao, Chunguo Wu, Yuesong Wu, Chaoyu Yu, Douglas L. Maskell, and You Zhou. Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: Comprehensive Survey with Perspectives, October 2024. URL http:
/llaxiv.orgg//et..i.. wtt.////46/bb......... 00415. arXiv:2406.00415 [cs].
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining Deep Learning Heuristic for Solving the Traveling Salesman Problem. In Advances in Neural Information Processing Systems, volume 34, pp. 7472-7483. Curran Asso- ciates, Inc., 2021. URL https: / otw.ppoooooooooe........ooo.ooo. ccppaper files/ /tse/pppr//////// htmi.
Model with Lin- -eeninghnn-Hllseee
2021/hasen htt.///dd3333aaaaaeaa http://222288888833777777111acc3
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, and Xinyun Chen. Large Language Models Optimizers, September 2023. URL http:://axii...e//////////// org/abs/ 2309. 03409. arXiv:2309.0344 [cs].
Haoran Ye, Jiarui Wang. Zhiguang Cao, Helan Liang, and Yong Li. DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization, November 2023. URL http: /ttp/vxxvvvvo///// www.ii.ogg..a......a.oaaaaaaaaae 2309. 14032. MXiv:2309.14033
14

---

Published as a conference paper at ICLR 2026
Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. ReEvo: Large Language Models as Syyper-Heuristii with Reflective Evolution. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (eds.), Ad- vances in Neural Information Processing Systems, volume 37, pp. 43571-43608 Curran Associates, Inc., 2024a. URL https: / htttps://proceeedinggg ngs www.i ps ec cc/ sarpaperr_flespppeeeee Pttprrssr1ss---arr--e-eee--e- CopereCon pdf.
Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time, org abs 22312 08224. arXiv:2312.08224 [cs].
July 2024b. URL
Zhuoli Yin, Zhaoyu Kou, and Hua Cai. A Deep Reinforcement Learning Model for Large-Scale Dynamic Bike Share Rebalancing with Spatial- Temporal Context. In The 12th International Work- shop Urban Computing, 2023. URL http: (urban-computt ing.. com/ ur23 file/UBf 0rrbcomp2023_pppe____.2
_.pmf..
Jiongzi Zheng, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. Reinforced Lin-Kernighan Helsgaun Algorithms for the Traveling Salesman Problems, July 2022. URL http://arxiy
arg//bss/an 03876. arXiv:2207 201.::2007008776 [es].
Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. UDC: A Unified Neural Siiie-andd-ooquee Framework for Large-Scale Scale Combinatorial Optimization Problems, 2024. URL http::///// /ttt:://aaiivv org/ 2407. 00312. MtXiv:2407.0033 [cs].
Zefang Zong, Hansen Wang, Jingwei Wang, Meng Zheng, and Yong Li. RBG: Hierarchically Solving Large-Scale Routing Problems in Logistic Systems via Reinforcement Learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, pp. 4648-4658, New York, NY, USA, August 2022. Association for Computing Machinery. ISBN 078-1-4503-9385-0 doi: 10.1145/3534678.5533888 1145/3534678.355
URL https: / /dl. acm. org/doi/10.
15

---

Published as a conference paper at ICLR 2026
A TRAVELING SALESMAN PROBLEM (TSP)
A TSP is characterized by list of nodes i E .... N). and the corresponding coordinate sets {(2,, yr) i 1, ........NV ] or the 2D Euclidean distance matrix DN. The 2D Euclidean distance between node pair calculated as j(i,j) to the nearest integer in this study.
(a, - xz (yg y:)² and we round the distance
The goal of TSP is to find an optimal tour that departs from an initial node, visits each node exactly once, and returns to the starting node. Without loss of generality, the solution // in this study is represented as a cyclic sequence of nodes // = [m1, m2, ny] + [T]]. where Tr represents the n-th node in this sequence, and denotes both the starting and ending node of the tour to form complete cycle. The objective is to minimize the total distance traveled L(II) E d(TT, m+-1)+ d(TTN, T1).
When the distance between two nodes is identical in both directions, i.e., d(i, d(i. i), the problem is known as symmetric TSP (STSP). In contrast, asymmetric TSP (ATSP) allows for different distances between certain node pairs in opposite directions, i.e., d(i.j) * d(j.t).
B ADDITIONAL RELATED WORKS
B.1 OR APPROACHES
Many commercial solvers, such as Gurobi, OR-Tools, and CPLEX, are designed for generic optimiza- tion purposes. They search for exact optimal solutions using techniques like branch and cut, but these solvers struggle with large-scale optimization problems. Besides these commercial solvers, Concorde is believed to be the SOTA exact solver designed for TSP to obtain optimal solutions. Essentially, it also employs the LKH algorithm- the SOTA heuristic solver- and branch-ana and--uu techniques to find exact solutions. Concorde has been shown to solve TSPs with more than 80k nodes, but still the expense of years of computation.
B.2 LEARNING-BASED APPROACHES
End-to-end construction. The autoregressive approach is characterized by an attention -based network architecture, such as the Transformer (Vaswani et al., 2017), or its variants, such Pointer- former (Jin et al., 2023). AM in Kool et al. (2019) uses the REINFORCE algorithm to sequentially predict the node with the highest probability, while POMO in Kwon et al. (2020) produces multiple solutions in decoding steps to improve the model performance. In contrast, the non-autoregressive approaches estimate the likelihood of connecting each edge between nodes to produce heatmap. For example, DIMES in Qiu et al. (2022) proposed learning continuous space to parameterize the solution distribution using an anisotropic graph neural network. DIFUSCO (Sun Yang, 2023), T2T (Li et al., 2023), and Fast T2T (Li et al., 2024) developed graph-based based diffusion model to generate the solution, which denoises random noise and the problem instance to gradually produce a feasible solution. However, DIFUSCO employs the 2-opt method further refine the output, which brings a significant performance gain. Its standalone performance to generalize to new instances is questionable. Fang et al. (2024) introduced Invariant Nested View Transformer (INViT) identify partial nodes with similar distributions as the trained ones to hierarchically handle partial problems. However, since these solvers always generate approximate solutions with an inevitable optimality gap, the overall solution quality can deteriorate significantly in out-of- -i-riiitinttionn instances.
Local improvement. Li et al. (2021) trains a backbone to select a promising subproblem and then delegates it to an off-the-sheef solver for further improvement. Zong et al. (2022) developed Rewriting-by- byegg-erat-eeeeiningggg (RBG) to iteratively refine the solution partitioning and infer new local solutions by trained generator. Similarly. Select-and-Opee and-Optimize (SO) in Cheng et al. (2023) trained a policy to select promising sequences within the complete tour and used a trained solver to improve the selected sequence iteratively. Intuitively, the subproblem solution quality fully depends on the solver. RBG and SO trained small-scale solvers following the methods in end-to-end construction. Fu et al. (2021) developed graph convolutional residual neural network with attention mechanisms (AuGCRNN) to optimize split subgraphs, and fuses optimized partial solutions as the complete solution. Similarly, H-TSP (Pan et al., 2023), GLOP (Ye et al., 2024b), and UDC (Zheng al., 2024)
16

---

Published as a conference paper at ICLR 2026
decompose TSP into open TSPs (instead of standard symmetric TSP) and optimize them using dedicated trained solvers.
C PROMPTS TO VLMS FOR SUBPROBLEM VISUAL SELECTION
The meta- text prompt instructing VLMs to select promising TSP subproblems is devised as follows. Italicized text in bold denotes placeholders for problem-speciffe imputs, and Q represents the number of sub-regions to be selected per query. A indicates the margin used to allow selection near the edge of the instance. It is set to 10% of the spatial boundary of the given TSP instance. We do not set parameters or rules for exploring, to investigate VLMs' capability to learn from the context determine the best selection by itself. Due the inherent differing execution pace between modules in asynchronous orchestration, VLMs can generate selections on the same global solutions before solvers finish current subproblem jobs. To mitigate duplicate selections from VLMs during asynchronous processes, the real-time subproblem queue Ω is included as part of the input prompts VI.Ms.
You are tasked with improving an existing solution to a Traveling Salesman Problem (TSP) by selecting sub-region where the routes can be significantly optimized. Carefully consider the locations of the nodes (in red) and connected routes (in black) in the initial solution on map. The boundary of the map is x min= {x_min- AJ. x max= {x. jax + AJ, y y_min= (y_min- A/. m_m_ymmaa_____ fy max A/.
Please return (Q) sub-rectangle(s) that you believe would most reduce total travel distance from further optimization by downstream TSP solver. Analyze the problem to do meaningful selections. Remember, if you don't 't see significant improvement, try selecting larger areas that cover more nodes based on your analysis of the prior selection trajectory.
Keep your output very brief as in the following template. Don't tell me you cannot view analyze the map. I don't 't want an excuse: (coordinates) =_min=1,000, x_ maxx=x2000 y_min=1,000 y_max=220000 (/coordinates)
Avoid selecting the same regions as follows, which pending optimization: (pending regions}
Below are some previous selection trajectories. Please avoid selecting the same subrectangle: (prior selection trajectory)
where each entry in (pending regions) is retrieved from up-to-date subproblem queue Q. Each entry the prior selection trajectory is based on the trajectory pool and formatted follows:
(coordinates). number of nodes within the subrectangle= (number of nodes), travel distance reduction= (delta objective improvement), computational time for this subproblem= (solver runtime in second)
The visual prompt is an instance-specife image, visualizing the position of nodes and the current tour based on TT An example visual prompt shown in Figure 4. our implmentation, all TSP instances are rendered using consistent figure size (figsiz=(20.20)). The image is gridded based on
Mrees Shiin
to adaptively provide coordinate reference for VLM.
100
17

---

Published as a conference paper at ICLR 2026
nrw1379
8801
8207
Coorriiate
7613
6425
5831
5237
2626
3220
3814
4408
5002
5596
Coordinate
Figure 4: An example of the visual prompt to VLMs. In this example, nrw1379 is used. The tour is initialized by LKH-3.
D PSEUDO-CODES FOR VISUAL SELECTION MODULE
Algorithm Visual Selection Module
1:
Input: Current global solution IIo, Selection trajectory Φ Meta-instruction J, Pending subprob- lem queue Ω2 Number of subproblems per prompt Q, Maximum number of covered nodes a, VLM visual selection Fselector
2: (CI, C²) Fselector (II", 4, 1,1,,55 S, Q)
3:
for to Q do
4:
Compute the number of covered nodes M
5: while M > do
6:
Cg < Fselector (TT' $ 1,
Zoom-in based on current solution within C2
7:
Update M
8:
end while
9: Wy (W K2) FORMSUBPROBLEMSS(] CC)
10: end for
11: if
- Wg S a or 3i such that W; W3 * then
Too small or overlapping
subproblems
12:
w + wi U... U@@
b Merge subproblems
Enqueue into
14: else
for g to do
16:
Enqueue wig into ?
17: end for
18: end if
19:
Return
b. Updated subproblem queue
18

---

Published as a conference paper at ICLR 2026
E PSEUDO-CODES FOR ASYNCHRONOUS ORCHESTRATION
Algorithm 2 Asynchronous Orchestration of VITSP
1: Input: Distance matrix DN meta-instin instructitnnn I, subproblems per prompt Q. node cap a, initializer Finitializee. VLM family (VLM1, VLM2, solver Fsolvers max no-improvement steps K. number parallel slave solvers P.
2: IT" Pinitializer (Dx)
Sec. 3.2 3: 4 + 0, 12' + 0 > Selection trajectory, subproblem queue, screened subproblem queue Sec. 3.3
4: [Parallel: Visual Selection Loop]
5: I' (ssteccoo(-)) < ROULETTE( (VLM, VLM2,...)
6: Q < VISUAALSLLECTION["" Φ, I, Q. Q, a, Fselector)
b Alg. Sec. 3.5
7: [Parallel: P Slave Solvers Loop]
8: Dequeue w from Q
9: DSTSP <- RFFORMULLATESSUSSIORREEEEEE
10: II 4- Fsotver (solver
11: if L(II*) L(1I) then Enqueue into !!'
Retain promising subproblem Sec. 3.5
12: [Parallel: One Master Solver Loop]
13: while Counter K do
14: i' * 0 then Dequeue w from !
else Dequeue from Ω DSTSP +
16:
II solver (DSTsp)
18: if L(II)) > L(II) then II" + II
>> Only master updates global solution
else Counter Counter
20:
end while
21:
Terminate all parallel processes
D Stop VITSP
22: Return IIo
P Final solution
19

---

Published as a conference paper at ICLR 2026
F IMPLEMENTATION DETAILS OF VITSP AND BASELINE ALGORITHMS
F.1 CLASSICAL OR APPROACHES
Concorde We used PyConcorde, a Python wrapper for the Concorde solver, to solve the TSP instances. Concorde provides t timelimie imit parameter that can be used to constrain its execution time. The runtime limit for Concorde is set to match the time ViTSP takes to converge on each specific instance.
LKH-3 The implementation version used in this study is LKH-330013. For LKH-3 (Default), we used the default parameters specified in Helsgaun (2016), including RUNS=10, MAX TRIALS-number (i.e., 5-opt). For LKH-3 (more RUNS), we incrementally increase the
of nodes, and MOVE_TTVEEEE value of RUNS by 50 until the actual runtime matches that of ViTSP. In the event that the gap is 0%, we report the runtime to reach this optimality.
LKH-3's performance is controlled by parameters like RUNS, TRIALS, etc. By default, RUNS is set to 10, which is used for LKH-3 (default) in our study. TRIALS is always set to be equivalent to the problem size, e.g., TRIALS= 1000 for dsj1000. We extend RUNS ad hoc ensure LKH-3 runtime matches with VITSP, and we report the per-instance settings of RUNS in Table 5.
Table 5: Per-instance setting of RUNS across 33 TSPLIB instances.
dsj 1s00000
p=1002
w1060
vm1084
pcbl1133
d1291
r1330
dI323
un79379
01400
ul452
160
210
R1577
d1655
vmi748
u1817
(18890
42103
02152
pr2302
peb3038
R3795
560
310
310
fn14661
119155
15934
pl97397
d11849
d15112
d18512
pla33110
plass900
110
130
130
130
44
50
70
50
Farthest insertion (FI) No parameters required for this algorithm.
F.2 END-TO-END CONSTRUCTION APPROACHES
Attention Model (AM) The algorithm was implemented based on RL4CO package (Berto et al., 2024). We utilized the open-source tsp100 checkpoint as the backbone for the AM (Kool al., 2019). Attempts to train new model for larger instances, like tsp/000, failed due to an out-of-memory issue. We adopted the greedy decoding strategy since our experiments show demonstrated superior performance compared to the sampling strategy. We denoted this algorithm as AM(G).
DIFUSCO (Sun Yang, 2023) We used the published pre-trained checkpoint Isp 1p00000-categorical as the backbone for DIFUSCO in this study. All other parameters followed the defaults provided in the open-source code. Specifically, a sampling-base based strategy was implemented with 10 diffusion steps and 16 samples. Additionally, 2-opt operations with 5,000 steps were applied. The diffusion type was categorical. We refer to this algorithm as DIFUSCO(S+2-apt)
Invariant Nested View Transformer (INVIT) (Fang et al., 2024) We used the open-sourced check- point for TSP as the backbone in assessing INVIT's performance in this study and followed the default settings.
Self-Improved Training (SIT) (Luo et al., 2025) We used the open-sourced checkpoint tsp-1k as the backbone. Random Destroy and Repair (PRC) iterations were performed to improve the solutions until the runtime hits the limit aligned with VITSP for each instance.
F.3 LOCAL IMPROVEMENT APPROACHES
DeepACO (Ye et al., 2023) We used an open-sourced checkpoint ts0 Following the specifications in the paper, we use the configuration Pants 100, Nnodes 500, hsparse 100, faco 100.
Select-and-Optimmize (SO) (Cheng et al., 2023) No public codes and checkpoints are available. We extracted the results reported in the original paper.
Framework (UDC) (Zheng et al., 2024) We used their pre- trained checkpoints for partitioning (dividing) and sub-TSP solver (conquering) to evaluate UDC's
Unified Neural Divide-and- Cond-uunuuerrr
20

---

Published as a conference paper at ICLR 2026
performance in TSP. We followed the default parameters reported in the paper. We set the runtime to align with ViTSP's s runtime on each instance.
F.4 LLM-BASED APPROACH
EoH (Liu et al., 2024) We used the open-source LLM4AD platform to run EoH with default parameters. For LLM, we used GPT-4.1, the same as in VITSP. Additionally, iterations are terminated once the runtime limit, matched to that of ViTSP, is reached.
F.5
VITSP
We used LKH-3 (Default) as the solution initializer, For VLMs, we set the number of subproblems set the upper bound of the number selected nodes to a 1000 for instances N < 10, 000 and a = 2000 for instances N 10, 000 and we imposed the time limit Concorde for solving each subproblem to Tmax = 10 seconds. The number of slave solvers set to be P 8 in the asynchronous orchestration. For the VIM, maximum of 100 tokens is set ensure brief and speedy output. VITSP is set to terminate if there are five consecutive solving steps without any improvement in the global objective value.
generated per prompt Q = 2. To reconcile the solving time spent a single subproblem,
21

---

Published as a conference paper at ICLR 2026
G COMPLETE PLOTS OF OPTIMALITY GAP REDUCTION OVER TIME BETWEEN VITSP AND LKH-3 (MORE RUNS)
Opttmality Gap (85
dsj1000
Optimalay M Gap (16
pr1002
Opiimality Gap (K)
u1060
Optimality Byy Gap (%)
1084
Optiallly Gap (8)
pcb1173
1.0
0.4
0.100
0.4
0.2
0.5
20
40
0.0
25
50
75
25
50
25
50
50
100
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Opimallty Gap (8)
d1291
Oplimality Gap (%)
r1304
Opiimalty Gap (%)
r11323
Oplimality Gap (%)
nrw1379
Opimality Gap (%)
f11400
0.50
0.4
3.50
0.25
0.2
0.1
0.25
0.1
0.00
100
200
0.0
40
100
50
100
25
50
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Oplimality Gap (9))
u1432
Optimalty Gap (%)
f11577
Oplimality Gap (%)
d1655
Optimality Gap (%)
1748
Opiimality Gap (%)
u1817
1.0
0.4
0.4
0.5
0.1
0.5
25
75
0.0
75
50
100
0.0
50
100 150
50 100150
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Optimality Gap (%)
r11889
Optimaityy Gap (%)
d2103
Optimality Gap (%)
u2152
Optimality Gap (%)
u2319
Oplimality Gap (%)
pr2392
1.0
0.4
0.4
0.2
0.5
0.5
0.2
0.0
0.0
50
100
25
50 75
100 200 300
100
200 300
100
200
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Optimaltty Gap (9)
pcb3038
Oplimaltyy Cap (%)
f137 95
Oplimality Gap (%)
1.0
fn14461
Oplimality Gap (%)
r15915
Oplimality Gap (%)
r1593
1.0
0.5
0.5
100 200 300
100 200 300
100
200 300
250
500
200
400
Runlime (seconds)
Runlime (seconds)
Runlime (seconds)
Runtime (secondis)
Runtime (seconds)
Optimality Gap (9%)
pla7397
Optimaltyy Gap (9)
r111849
Oplimality Gap (%)
usa1 15099
Oplimality Gap (%)
brd 4051
Oplimality Gap (%)
d15112
1.0
1.0
1.0
0.5
0.5
0.5
250
500
400
600
500
750
500 1000 1500
1000
2000
Runlime (seconds)
Runlime (seconds)
Runtime (seconds)
Runlime (seconds)
Runtime (seconds)
Optimaliyy Gap (%)
d18512
Optimality Gap (%)
pla33810
Optimality Gap (%)
pla85900
1.0
1.0
LLM-TSP
0.5
0.5
0.5
1000
2000
4000
6000
25000 30000
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Figure 5: Optimality gap reduction over time between VITSP and LKH-3 (more RUNS).
22

---

Published as a conference paper at ICLR 2026
H IDENTIFIED SUBPROBLEMS BY VLMS THAT CONTRIBUTE TO OPTIMALITY GAP REDUCTION
In Figure 6, we plot the identified subproblems by VLM. For clarity, the selected box regions without contributing to optimality gap reductions are omitted.
Besides correcting crisscrossed edges, which is the most visually apparent suboptimality, VITSP can also achieve improvements through:
(I) Refining dense regions mate solution (initialized by LKH-3) to locally optimal one, as each subproblem is re-optimized using an exact solver (Concorde).
where small gains accumulate by transitioning from locally approxi-
(2) Combinatorially selecting neighborhoods whose joint optimization can escape the local optimum and lead to global improvements, recall that use Q 2 allow subproblem selections simultaneously at each step.
As shown in Figure the subregions identified by the VLM often correspond to these two patterns. Dense areas may contain sub-paths that are locally optimal but globally improvable when viewed in context. Additionally, we detailed in Section 3.3, we designed zoom-in reselection so VL.Ms always have chances to inspect detailed edge connections in a dense area.
23

---

Published as a conference paper at ICLR 2026
exji
000
PrA002
110000
pcb1173
1000
41291
11304
01323
nnw1379
110000
01432
113577
01055
vm1748
V1817
11889
62103
U2352
U2319
Dr2392
pcb 30.30
113795
Iri4461
15915
15994
Bla7397
m11849
Usa1 3509
Brd14051
d15112
d18512
pla89900
Figure 6: Visualization of selected box regions by VLMs on TSP instances. Darker shaded areas represent more frequently selected subproblems
I ANALYSIS OF ViTSP ITERATIONS
Valid subproblem rate. We here report the average valid subproblem rate per instance by VLMs over five runs of VISSP. The valid rate is the ratio of subproblems that lead to gap reductions after optimization to the total number of subproblems proposed by the VLMs during the iterations. As shown in Table 6, the average valid rate ranges between 10% 50%. These valid rates achieved without any task-specific training, as the VLMs used in this study are entirely Overall, results demonstrate that VLMS generate practically meaningful decomposition
24

---

Published as a conference paper at ICLR 2026
heuristics. Parameters such box size, number of boxes per call, and subregion shape offer additional room for optimization.
The visual and textual prompts in VITSP play complementary and essential roles in eliciting effective subproblems selection from VLMs. Prior works have shown that relying solely on textual inputs, such approaches use only coordinate lists, such in Yang al. (2023) and Liu et al. (2024), struggle to produce high-quality solutions. Conversely, multimodal approaches like Elhenawy et al. (2024) attempt to read specific node indices from TSP images through VLMs are unable scale effectively as visual clutter and index ambiguity grow rapidly with problem size. Together, these observations highlight the necessity of carefully designed multimodal prompting achieve valid and effective performance throughout the VITSP iterations.
Table 6: Valid rate of subproblems selected by VLMs across 33 TSPLIB instances.
ds11000
pr1002
u1060 48.14%
vm1084
pcb1173
d1291
01301
fI1323 30.15%
arw 1379
E1:400
u1432
41.72%
53.81
35.935
35.00%
10.42%
41.67%
39,40%
33,00%
34.92%
B1577
d1655
vm1748
01817
11389
42103
u2152
02319
pr2392
peb30ss8
815995
25.44%
22.64%
37.47%
6a94661
d5934
pla7397
3509
Ind1405)
d15112
d18512
43.99%
23.069
37,629
29.05%
17.02%
25.47%
39.2356
35,895
38 909
40.37%
Cost of VLM API calls per instance. VITSP, the primary cost comes from online VLM API calls. The cost of an API call depends on the input and output tokens. For GPT-4.1 1, the pricing is $2 for every one million input tokens and S8 for every one million output tokens, while the pricing is $1.10 for every million input tokens and $4.40 for million output tokens for 04-mini. Here report in Table 7 the per-instance average API cost based on five runs. The remaining components of the system, including LKH initialization and Concorde subproblem solving, open-source CPU-based tools and therefore incur negligible cost relative to VLM inference. The cost of API calls for individual instances varies due the number of valid iterations needed to reach the convergence. From dis 1000 to pla85900, the average cost ranges between $0. 12 and $39.40.
Table 7: Average API cost per instance.
dsj 1000
pc1002
w1060
vmL184 50.15
peb1173
d1291 $0.83
r11304 $0.13
d1323
msw1379 $0.55
R11000
u1432
50.12
50.26
50.15
50.51
50.35
$0.21
$0.22
01577
d1655
7748
u1817
r1889
02103
u2152
u2319
pr2392
peb3038
133795
50.35
$1.21
$1.70
fo1446]
119115
#1934
pla7397
d11849
uss13509 $1.57
bxd14051
d15112
418512
pla33810
pla85900
$1.20
$11.47
25

---

Published as a conference paper at ICLR 2026
J COMPLETE PLOTS FOR ABLATION STUDIES OF DIFFERENT SELECTION POLICIES
In Figure 7, we illustrate the optimality gap reduction curves among VTTSP and two random selectors across 33 TSPLIB instances to demonstrate the effectiveness of VLM in selecting meaningful subproblems.
26

---

Published as a conference paper at ICLR 2026
Optmmaity Gep (%)
dsj1000
Opömality Gap (%)
pr1002
Optmmalty altty Gap (%)
u1060
Optmallty Gap (%)
1084
pcb1173
1.0
0.4
0.4
0.10
Opiimality Gap
0.1
0.2
0.2
0.05
0.0
0.0
0.0
0.00
0.0
75
100
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Oplimaitty Gap (%)
d 11291
Optmallyy Cap (%)
r1304
Optmalty Gap (%)
r1323
Opömallyy Gap (%)
nrw1379
Optimaiity Gap (%)
f11400
0.2
0.50
0.4
0.50
0.25
0.2
0.1
0.00
0.0
0.0
0.00
50
100
Runlime (seconds)
Runlime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Optinally Gep (%)
u1432
Optimality Oap (%)
f11577
Optimality Gap (%)
d1655
Oplimality Gap (%)
vm 1748
Optimality Gap (%)
u1817
0.4
0.2
0.4
0.2
0.1
0.2
0.5
0.0
25
75
0.0
25
75
0.0
100
0.0
50
100 150
0.0
50 100
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Optinalty Gap (%)
r11889
Optimality Gap (%)
d2103
Optimaiit Gap (%)
u2152
Oglimalit Sap (%)
u2319
Oplimality Gap (%)
pr2392
1.0
0.4
0.2
0.2
0.2
0.5
0.5
50
100
0.0
25
50 75
0.0
100 200 300
0.0
100
300
0.0
100
200
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Optimalty Gap (%)
pcb3038
Optimality Gap (%)
93
Optimality Gap (%)
fn|4461
Optimality Gap (%)
r15915
Optimality Gap (%)
r15934
7
0.5
0.5
0.0
100 200
0
100
0.0
100
300
400
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Runtime (seconds)
Optinally dap (%)
pla7397
Optimally Gap (%)
r/1
Optimality Gap (%)
usar 3509
Oplimaliy Gap (%)
1051
Optimality Gap (%)
d15112
1.0
1.0
1.0
0.5
0.5
0.5
0.0
250 500
0
400
600
0.0
500
750
800 1000 1500 Runtime (seconds)
0.0
1000 2000
Runtime (seconds)
Runtime (soconds)
Runtime (seconds)
Runlime (seconds)
Optinalty Gap (%)
d d18512
Oplimality Gap (%)
pla33810
Optimality Gap (%)
pla85900
1.0
1.0
1.0
VITSP
Random Sequence Selector
0.5
0.5
0.5
Random Box Selector
0.0
0.0
0.0
1000
2000
4000
6000
25000 30000
Runtime (seconds)
(seconds)
Runlime (seconds)
Figure 7: Optimality gap reduction time among three selection policies.
27

---

Published as a conference paper at ICLR 2026
K
LIMITATIONS AND BROADER IMPACTS
We discuss three limitations and additional directions of future work in this section. First, the box- based subproblem decomposition guided by VLMs this study represents one type of metaheuristic operation for combinatorial optimization. As ablation studies show, selecting a sequence of nodes may also be a helpful metaheuristic operation. Thus, exploring additional operations designed by VLMs could further unlock the potential of hybridizing machine learning and operations research methods. Second, although parallel computing is employed, this study does not explicitly optimize the coordination between the selector and solver modules. In particular, there is an unexplored trade-off between solving a single large subproblem with longer runtime versus solving multiple smaller subproblems within the same time. We leave this investigation for future work. Third, exploring batch-pt patch-parallel execution to enable the optimization of multiple instances simultancously could further improve overall throughput in practice.
Broadly, the TSP is more than an academic challenge- is a foundational problem with broad applications across industries, such transportation, logistics, chip design, and DNA sequeneing. This work creates new opportunities for the machine learning community to develop high-quality solutions for large-scale TSP and related problems using general-purpose large models. As VL.Ms become increasingly accessible and capable of advanced reasoning, they offer scalable solutions deployable on both cloud and edge devices, paving the way for practical and impactful applications.
L THE USE OF LARGE LANGUAGE MODELS (LLMS)
The authors confirm that LLMs were used only for grammar checking and text polishing. They were not involved in research ideation. Their role in writing was limited, such that they are not considered contributors.
28


Reviews:
[{"review_id": "zTUawZpAKW", "reviewer": "Reviewer_AY9B", "summary": "This paper proposes a vision-language-based framework that utilizes VLMs to identify subareas capable of reconstructing trajectories. The use of vision-language models is novel, and the evaluation on large-scale real-world datasets demonstrates the model’s strong generalization ability. However, some experimental limitations hinder a comprehensive assessment of the model’s performance.", "questions": "See details in Weaknesses.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "The incorporation of vision-language models is innovative, and experiments conducted on large-scale TSPLIB instances demonstrate the model’s strong generalization capability.", "weaknesses": "1.The main concern lies in the solution initialization process. The model uses LKH for initialization, which introduces bias in evaluating its standalone effectiveness. To more fairly demonstrate the model’s capability, the authors should consider using random or greedy initialization instead. Comparing a method initialized by LKH against other heuristics or neural solvers is inherently unfair. Moreover, since the proposed framework is initialized by LKH yet fails to consistently outperform LKH under comparable runtime conditions, its claimed effectiveness remains questionable.\n\n2.Although the paper emphasizes scalability, it only evaluates 33 instances, which is insufficient to support the claim of large-scale generalization. The authors are encouraged to include TSPLIB instances with more than 500 nodes to better align with the paper’s stated focus on large-scale problems and to provide stronger empirical evidence.\n\n3.Additional baselines should be incorporated for a more comprehensive comparison. Specifically, large-scale solvers such as RBG[1] and SIT[2] are relevant benchmarks. Furthermore, NeuroLKH[3], a neural variant based on LKH, should be included as it provides a closer reference point for hybrid approaches similar in spirit to the proposed method.\n\n4.The abstract mentions that the proposed method reduces the optimality gap by 12% to 100%, but this claim is only briefly mentioned in the main text without sufficient explanation. Can the author further explain it?\n\n[1] Hierarchically solving large-scale routing problems in logistic systems via reinforcement learning.\n[2] Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems.\n[3] Neurolkh: Combining deep learning model with lin-kernighan-helsgaun heuristic for solving the traveling salesman problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BUFaigbiJn", "reviewer": "Reviewer_RptF", "summary": "This paper proposes ViTSP, a hybrid optimization framework that leverages pre-trained Vision-Language Models (VLMs) to identify promising spatial subregions in large-scale Traveling Salesman Problem (TSP) instances. These subproblems are then optimized by Concorde, forming an asynchronous pipeline with LKH-3 used for initialization. The approach avoids model training, claims strong scalability, and achieves competitive optimality gaps on 33 TSPLIB instances up to 85k nodes, outperforming LKH-3 under equal runtime budgets in many cases and achieving up to 0.19% average optimality gap.", "questions": "Please provide the full prompt text, the average number of boxes returned per call, and statistics on invalid VLM outputs \n\nFor result stability, report mean ± std (or confidence intervals) over 5–10 independent runs per instance to ensure results are not accidental.\n\nClarify runtime measurement: does the VLM API waiting/latency count toward total runtime? \n\nRegarding baselines: how are LKH-3 (multiple runs) parameters set? How are time limits aligned for Concorde, DeepACO, etc.? Please provide a per-instance configuration table (in appendix or supplementary).\n\n\nIf considering offline/self-hosted VLMs (or fine-tuned models), what is the scalability and cost trade-off? Have the authors tried lightweight fine-tuning or RL signal-guided selection enhancement?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The framework is well-designed and modular (visual selection, subproblem reconstruction, exact solver, asynchronous orchestration).\n\nExtensive experiments and detailed comparisons on large-scale real benchmarks (TSPLIB, N ≥ 1000) demonstrate practical effectiveness.\n\nNo need for training/fine-tuning; low deployment barrier (uses existing VLM APIs + classical solvers), aligning well with real-world engineering needs.", "weaknesses": "Insufficient quantitative analysis on VLM output stability, repeatability, and prompt sensitivity.\n\nFairness of runtime alignment and whether real online VLM latency is fully included needs clearer justification.\n\nLacks theoretical analysis (convergence/performance guarantees) and interpretability evidence (why VLM can select “beneficial” regions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TtMn6Iuihk", "reviewer": "Reviewer_ZmWq", "summary": "This paper proposes a vision-guided solution framework ViTSP for Traveling Salesman Problem, leveraging pre-trained VLMs to act as selector of improvement region and exact solvers to settle down the subproblem. The authors also conduct experiments on some real-world instances in TSPLIB to show the performance on large-scale scenario.", "questions": "Please see weaknesses. The idea is very interesting and  I will adjust the paper’s score accordingly in my rebuttal to reflect the strengths identified.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1 This paper introduce VLM to directly determine the box region to be revised instead of time-consuming training, which is an interesting attempt compared to traditional learning-based paradigm.\n\n2 The proposed method outperforms the baselines on most of large-scale non-uniform real-world instances (N>1000).\n\n3 Figure 1 presents clear and nice visualization to understand the pipline.", "weaknesses": "1 The experiment is not sufficient for merely certain large-scale instances in TSPLIB. I suggest that the authors need to demonstrate its effectiveness on other random uniform and non-uniform datasets, datasets in INViT.\n\n2 ViTSP is essentially an improved approach. So how does its iterative improvement efficiency compare to other neural improvement methods?\n\n3 Dealing with TSP in a visual way is not a new \nthing. In the past, there were a series of methods that used two-dimensional scatter plots as input. I suggest the author review relevant visual methods and elaborate on the advantages of VLM compared to them.\n\n4 The way to leverage VLM in this paper is invoking API, which is a simple way to use a large model. But is it possible to design a reasonable way to fine tune the model based on TSP tasks, making the combination of VLM and tasks more collaborative?\n\n5 The problem discussed in this paper is merely TSP, which is narrow. Can the VLM-based method adapt to solving other routing tasks?\n\n6 What is the initialization method used in this paper? From the title of Figure 4 in Appendix, it appears to be LKH3. Is the parameter values (especially the number of runs) of LKH-3 in initialization default? What's more, the quality of iteration and final solution highly depend on initialization. How about the performance of VLM-based improvement integrated with other solution initialization methods, e.g. random initialization or insertion initialization? I suggest the author provide more details about de initialization and comparative experiments with other initialization methods.\n\n7 Does the solution time include the initial solution generation time? I suggest the author provide more details about the solution time, including initial solution generation, VLM inference, and exact solving of subproblems.\n\n8 Does the input 2D image in ViTSP need scale, quality, and formatting requirements? When the instance scale is huge, scatter plots and circumnavigation maps appear crowded and convergent visually, which leads to a serious lack of fine-grained information. Applying the same scaling to instances of different sizes does not seem to lead to good visual perception of VLM. How was this paper handled?\n\n9 The leverage of VLM avoids the cost of intensive training. However, I would like to know if it would cause an increase in inference time compared to end-to-end methods.\n\n10 It seems that ViTSP is iteratively improved instance by instance. Can it be executed in parallel in batches?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RUnPp6uVYI", "reviewer": "Reviewer_v67N", "summary": "The paper tackles the classical TSP with a hybrid approach combining an exact solver (Concorde) with a Vision Language Model. The workflow proceeds iteratively between the solver and the VLM, with the VLM identifying sub problems based on a visualization of the problem + current solution, and the solver improving the current solution. Results show improvements on the TSPLIB benchmark.", "questions": "1. What is the advantage of ViTSP over Concorde? You claimed that exact solvers like Concorde are become intractable for very large problem sizes -- can you show / have you already shown any problem where Concorde is intractable and ViTSP can do the job?\n\n2. Is it possible to further ablate the VLM component? For instance, how important is the visual prompt vs. the textual prompt?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think that the paper's idea is original and novel. I am not aware of such an approach combining VLMs and exact solvers for this problem before. I think that the fact that a simple visualization of the current TSP solution being fed to a VLM gives us some meaningful results is pretty interesting and creative, if true!\n\nI think the results presented here seem very promising and significant, as the scale of TSPLIB problems solved by this method is claimed to be unprescedented. \n\nHowever, I would like to note to the AC that I am not very confident about my review and understanding of the current landscape of this field. I will be reading other reviews carefully during the rebuttal period to identify potential gaps in my assessment.", "weaknesses": "I think that presentation of the results can be improved. The paper requires a lot of flipping between the main and appendix. The authors may try to make the main section more self contained when revising the paper.\n\nI also think that, practically, the real cost of a VLM-based approach will likely far exceed Concorde/other solvers at the moment. The authors noted simply \"In ViTSP, the VLMs were accessed on demand online. Their usage did not rely on local GPU resources but was confined by the I/O rate.\" -- but perhaps a more nuanced discussion/justification/cost estimation would be helpful. There is a cost to each API call to an OpenAI-hosted model. Beyond that, there is a cost to running these models themselves.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RktpRGBm6Y", "reviewer": "Reviewer_ThrP", "summary": "The authors propose a divide-and-conquer approach for large-scale TSP: a VLM selects regions to optimize on a visualization of the current tour, and those regions are then handed to a traditional solver.", "questions": "Please see weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Introducing LMs into combinatorial optimization is an interesting idea, and the writing is clear.", "weaknesses": "1. Limited novelty\nIn neural TSP solvers, divide-and-conquer is already a common paradigm. The use of a VLM here is not particularly fancy; it mainly selects axis-aligned rectangles and relies on sparse optimization rewards, amounting to a straightforward integration of a VLM into a standard divide-and-conquer framework.\n\n2. Experimental results and setup lack persuasiveness\nThe method is built on traditional solvers but does not compare against improved neural solvers such as NeuroLKH. The current results only show that the combination of divide-and-conquer framework and efficient solvers (LKH, Concorde) outperforms constructive neural solvers, weak local reform (neuro)solvers, and traditional solvers; they do not demonstrate the added value of introducing a complex VLM.\nThe benchmarks are mainly several TSPLIB instances, without tests on the commonly used ([0,1]×[0,1]) randomly generated Euclidean datasets. According to the NeuroLKH report, LKH and NeuroLKH can achieve sub–one-per-thousand gaps on such datasets. It would be useful to see how the proposed method performs under the same setting.\nThe authors are encouraged to discuss whether the method can be applied to more complex, more constrained tasks and to provide attempts. Although focusing on large-scale TSP already represents substantial effort, more comprehensive discussion and trials would be valuable.\n\nOverall, my initial suggestion is borderline reject.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)