We thank the reviewer for acknowledging the competent execution of our work, the clarity of our writing, and the usefulness of our analysis in identifying the sources of improvement. We hope that our responses below address the concerns raised by the reviewer.

Summary

In brief, we have:

1. Clarified Figure 2 shows max/min savings (not confidence intervals) to emphasize the Pareto distribution pattern;
2. Confirmed fair GPU-accelerated comparison with SA using identical conditions across all baselines;
3. Added variance reporting (mean±std) across 10,000 instances per scenario, showing high variance aligns with the Pareto distribution;
4. Addressed novelty concerns by explaining non-trivial challenges: asymmetric temporal dimensions, dynamic continuous time handling, and 3D tensor complexity beyond MatNet's 2D foundation;
5. Clarified that the similar average performance is misleading because ~50% of instances don't benefit from temporal information, masking that our method significantly outperforms MatNet on the instances where time-dependency actually matters.

Detailed Reply

1. Clarification on Figure 2 visualization

Reviewer Concern: What do the two lines and the shaded region represent in Figure 2? Are these confidence intervals with one or two standard deviations?

Response: The lines represent the maximum and minimum savings across instances, not confidence intervals. This visualization emphasizes our key finding that gains from time-dependent edge weights follow a Pareto distribution—most instances show minimal improvement while a subset demonstrates substantial benefits.

2. Fair comparison with Simulated Annealing

Reviewer Concern: Is the simulated annealing implementation parallelized on a GPU for fair comparison?

Response: Yes, all baselines, including SA, are implemented with GPU acceleration for rigorous experimental fairness. All evaluations employ identical conditions: single GPU hardware, consistent datasets, uniform batch size (1024), and identical data ordering. Complete baseline implementations are available in our supplementary materials (folder rl4co/rl4co/baselines).

3. Statistical significance and error reporting

Reviewer Concern: Given your "No" answer to checklist question 7 about error bars, why not increase sample size to ensure trustworthy experimental conclusions?

Response: We appreciate this important point about statistical rigor. Our experimental design already uses 10,000 instances per scenario, providing a robust statistical foundation. While variance reporting isn't standard in neural combinatorial optimization literature [8, 16, 20, 38], we recognize its value.

Following your feedback, we report results in mean(std) format below. We will turn this table into error bars in the camera-ready version of the paper.​ The Beijing-10 results demonstrate that standard deviations of the gap on the 10000 instances often match or exceed the mean of the gaps.​ This table confirms our finding that the time saved by considering the time-varying edge weights follows a Pareto distribution.

4. Novelty Concerns

Reviewer Concern: The novelty appears limited—seems like a straightforward MatNet adaptation for temporal information.

Response: We believe this is a misunderstanding and would like to address the novelty concern.

Novel Technical Contributions: While building on MatNet's foundation, extending to time-dependent problems required solving non-trivial challenges, not direct adaptation. Here we list the technical challenges we met and our contributions to solving them.

1. Asymmetric Dimensional Integration: MatNet's dual attention naturally handles symmetric spatial dimensions (outgoing/incoming nodes), but the time dimension is fundamentally asymmetric with directionality and causality that spatial dimensions lack. Our innovation​ of the vectorized dual attention mechanism integrates temporal information while respecting time's directional nature and preserving MatNet's spatial symmetry handling.
2. Dynamic Continuous Time Handling: MatNet processes static discrete indices where the (static) adjacency matrix A[i,j] remains constant throughout decoding. However, time is a continuous and evolving variable. The current time updates during decoding require real-time edge cost interpolation from discrete time samples. Our time-aware decoder uses dynamic interpolation and sinusoidal embeddings to handle continuous temporal states.
3. Tensor Structure Complexity Handling: MatNet's elegant bipartite graph representation is designed for 2D matrices, but extending to 3D tensors A[t] breaks the natural bipartite structure since edges now have vector weights instead of scalars. We extended the bipartite representation to handle vector-weighted edges with new attention mechanisms for processing temporal vectors rather than scalar ones.

Besides technical novelties, we also want to emphasize our novelty in identifying the fundamental evaluation problem in TDTSP research.

Novel Methodology Contributions: In addition to the above algorithmic contributions, we identify and solve a fundamental evaluation problem in TDTSP research that has led to misleading conclusions in prior work, thereby providing valuable insights for future work. We identified that the single average performance value is a misleading metric (see detailed response to Q5) and therefore changed the metric to the performance on selected instances where time-dependency has a significant impact, as discussed in Section 6.2, lines 276-281.

5. Performance comparison with MatNet

Reviewer Concern: Results appear similar to MatNet on average, only improving when selecting the better method and adding local search.

Response: We appreciate the reviewer for this observation. However, this is a misleading impression because the dataset comprises two distinct subsets. One consists of instances that, considering time information, give little improvement, while the other consists of instances with significant improvements. This also indicates that the simple, single average performance is a poor metric for evaluating the performance of different methods.

Key insights: The single average performance is misleading for TDTSP. As shown in Section 4, ~50% of instances have identical optimal solutions regardless of time-dependency. This allows spatial-only methods like MatNet to achieve good averages without learning any temporal patterns.​​ This explains why prior TDTSP papers report similar performance across fundamentally different approaches. However, for the rest of the instances, MatNet performs poorly. Therefore, we argue that this is an inherited problem of the dataset. We believe that the different instances from different distribution categories should be evaluated separately, instead of using a single metric of the average performance.

In instances where temporal dependencies matter (Table 3), our method significantly outperforms MatNet. For instances with >3% potential savings, our raw model achieves 1.70% vs 9.11% gaps (Beijing-10) and 3.32% vs 6.94% (Beijing-20), demonstrating effective temporal learning. This means that, although the average performance is similar, the distribution of the gaps is fundamentally different on different instances. The gap of MatNet comes from the lack of time-dependent information. In contrast, the gap of our method comes from the inadequate spatial capability.

Follow this insight, the MoE approach is principled system design, not simple cheating. Our analysis reveals that instances naturally split into temporal-dependent vs. spatial-only categories. A hybrid approach leveraging this structure is both theoretically sound and practically valuable.

In summary, the similarity in average performance is a misleading conclusion due to the poor metric used for evaluation. Our method does capture the temporal information well, and better evaluation methodologies are needed to assess temporal reasoning capabilities in neural combinatorial optimization.

We thank the reviewer for recognizing the high technical quality of our neural architecture for encoding time-dependent adjacency tensors, the clarity of our problem formulation and model design, and the significance of our contributions to TDTSP research. We are particularly grateful for the acknowledgment of our novel evaluation methodology that identifies the Pareto distribution in real-world TDTSP instances—a critical insight that can reshape how TDTSP algorithms are assessed—as well as our original approach to directly encoding higher-dimensional time-dependent tensors and the practical relevance of our work for logistics and transportation applications. We hope that our responses below address the concerns raised by the reviewer.

Summary

In brief, we have:

1. Conducted comprehensive ablation studies on encoder layers, learning rates, and temporal embeddings;
2. Demonstrated scalability with 100-node experiments, achieving comparable ACO performance but 65× faster
3. Addressed scalability concerns with flexible local search trade-offs and preprocessing strategies for practical applications.
4. Provided multi-seed stability analysis confirming REINFORCE reliability (obj: 2.630±0.01, gap: 1.61±0.05 across 8 seeds);
5. Clarified "online refinement" terminology - will remove "online" and specify these are post-processing steps during inference;

Detailed Reply

1. Model Robustness and Hyperparameter Sensitivity

Reviewer Concern: Could the authors provide more insights into the robustness of the proposed neural model through ablation studies on key hyperparameters?

Response: Beyond MoE and local search ablation (Table 4), we conducted additional component analysis examining temporal embeddings, encoder layer numbers, and learning rate sensitivity.

Layer Num: The training time and the GPU memory increase linearly with the number of layers. The performance rises quickly when N<3, while it shows little to no improvement after N>=3.

Learning Rate: The best learning rate is between 3e-5 and 1e-3. A too large learning rate (3e-3) makes the model diverge, and a too small learning rate (3e-6) gets stuck at a bad local minimum.

Temporal embedding: The sinusoidal embedding is the most helpful one, compared with the MLP embedding and the Linear embedding. There are potentially other effective embedding methods, but that is beyond the scope of the paper.

These results, along with individual component impact assessments, will be detailed in the appendix.

2. Scalability to Large-Scale Instances

Reviewer Concern: How do the authors envision scaling this approach to much larger instances, given the reported inference times for N=50 (e.g., ~1550s for Beijing-50)?

Response: We address scalability through three complementary strategies:

Good Model Scalability: We conducted new experiments training our method on 100-node cases with 100 epochs (not converged yet), taking ~100 hours, showing comparable performance with ACO. (7.4327 (0.3962) vs 7.3997(0.4007)) while significantly outperforming the running speed (42.24s vs. 2741.25s). This shows that our neural network without the local search can learn larger-sized problems with acceptable learning time, while keeping a short inference time.

We also test the scaling of GPU memory usage and the training time required. From the table, the GPU memory grows quadratically. At the scale of 100 nodes, it requires a memory usage of 36GB and training time of an hour when setting the batch size to 128. Such training cost is acceptable in the application, validating the scalability of our method.

Flexible local search trade-off: The reported 1,550s includes extensive local search, including 2 iterations of 5 sequential operations (2-opt, 3-opt, exchange, relocate, or-opt) per iteration. There are multiple choices for reducing the running time by sacrificing the performance:

• Using 1 iteration instead of 2
• Using fewer local search operations
• Removing local search entirely for time-critical applications

Preprocessing in practice: For real-world scenarios like last-mile delivery, regional customer clustering is a common strategy that can reduce problem size without significantly compromising performance, making our approach suitable for large-scale deployment without training the full-size model.

3. Training Stability with REINFORCE

Reviewer Concern: How was training stability managed given REINFORCE's known high variance? What were the reasons for choosing REINFORCE?

Response: Although REINFORCE is known for high variance, it showed quite good stability in our experiments. The following table reports an extra experiment of training with different random seeds. The final converged states give quite stable objective: 2.630±0.01 and optimality gap: 1.61±0.05 across 8 seeds. This stability also aligns with established TDTSP literature [8,16,38], where no instability issues are reported. The observation validates our algorithmic choice of REINFORCE for TSP-related problems.

We have also implemented the PPO before, but found it not performing better than REINFORCE, with difficulty in the critic network learning. We see very few recent works about applying PPO for learning TSP and its variants, like Enhanced Reinforcement Learning for TSP: Proximal Policy Optimization with Graph Attention and Entropy Regularization in 2024 and Solving the Traveling Salesman Problem with Drones Using Proximal Policy Optimization and Deep Reinforcement Learning in 2025. While they show that PPO can work in some cases, there is still no comprehensive study comparing different learning algorithms and providing guidelines for selecting learning algorithms for TSP variants.

4. Clarification on "Online Refinement"

Reviewer Concern: Is the "online refinement" real-time adaptation or post-processing?

Response: We thank the reviewer for identifying the ambiguity. Our refinement methods (MoE and local search) are post-processing steps during inference, not real-time adaptations. We will remove the potentially misleading term "online" and explicitly describe these as inference-time post-processing steps in our revision.

We thank the reviewer for recognizing the critical evaluation insights we identified for existing TDTSP algorithms, acknowledging our methodological extensions and experimental advantages, and appreciating the clear logical structure and organization of our paper. We hope that our responses below address the concerns raised by the reviewer.

Summary

In brief, we have:

1. Acknowledged foundational work and clarified our temporal extension contribution
2. Created a comparative analysis showing our method uniquely combines full spatiotemporal processing
3. Added SOTA neural comparison with [38], demonstrating our superior performance
4. Demonstrated scalability with 100-node experiments, achieving comparable ACO performance but 65× faster
5. Improved Fig. 3 clarity with clearer stage labels and a more detailed caption.

Detailed Responses

1. Novelty Highlight and Foundational Work Acknowledgement

Reviewer Concern: The abstract should explicitly acknowledge the foundational work in [20] and highlight how the temporal dimension introduces unique innovations (e.g., tensor-based spatiotemporal integration).

Response: We thank the reviewer for this important clarification. The reviewer is absolutely correct that Kwon et al. [20] established the foundational approach for handling asymmetry in static problems through MatNet. Our contribution specifically extends this to the temporal dimension, where the adjacency tensor A[t] introduces unique spatiotemporal challenges not present in static cases.

Proposed revisions in Abstract (lines 6-9): Replace In this paper, $\cdots$ captures the complex spatiotemporal dynamics of TDTSP by

"In this paper, we propose a neural model that extends MatNet from static asymmetric TSP to time-dependent settings through an adjacency tensor that captures temporal variations, followed by a time-aware decoder. Our architecture addresses the unique challenge where asymmetry and triangle inequality violations change dynamically with time."

2. Spatiotemporal Processing Comparison

Reviewer Concern: The model's ability to "simultaneously capture spatiotemporal structures" needs explicit comparison with prior works.

Response: We created a comprehensive comparative analysis showing how our method uniquely processes complete spatiotemporal information:

Key insight: Our tensor encoding preserves complete spatiotemporal information while enabling joint attention processing, unlike prior works that either assume symmetry [8], miss arrival information [16,38], or lack temporal processing [20].

3. State-of-the-Art Neural Comparisons

Reviewer Concern: The experimental comparison omits state-of-the-art TDTSP-specific neural solvers.

Response: We added comparison with the most relevant SOTA neural TDTSP method [38]:

Technical limitations of other methods: Methods [8] and [16] require coordinate inputs, making them incompatible with our tensor-based setting, where we cannot reproduce their solution quality.

Critical evaluation insight about [38]: Zhang et al. [38] considers time-dependent distributions including both mean and variance components. However, without recognizing the Pareto distribution we identified, they falsely report their effectiveness by conflating improvements from variance handling with temporal pattern learning. Our analysis reveals that their advantage over baselines primarily stems from variance reduction rather than genuine time-dependent mean change learning. This weakness is masked when evaluating on full datasets without distinguishing between static-equivalent and truly time-dependent instances.

Key insight: As we demonstrated in our data analysis, the performance gap becomes quite small when not properly accounting for time-dependent changes, highlighting the importance of our proposed evaluation methodology that separates instances where temporal dependencies matter.

4. Scalability Validation

Reviewer Concern: Experimental validation is limited to 50 nodes, raising scalability concerns for real-world applications.

Response: We conducted extensive 100-node experiments (100 epochs, ~100 hours training, not converged yet), which show comparable performance with ACO (7.43 vs 7.40 objective) while significantly outperforming runtime (42s vs 2741s):

This demonstrates our method's practical viability for real-world applications with larger node counts.

5. Figure Clarity

Reviewer Concern: Figure 3's three-stage process description lacks clear labeling.

Response: We will enhance Figure 3 with:

• Clear stage labels for the three-stage attention process
• Detailed caption explaining each of the stage

We thank the reviewer for recognizing the practical significance of our work and acknowledging our contributions in advancing neural methods for spatiotemporal route optimization. We hope that our responses below address the concerns raised by the reviewer.

Summary

In brief, we have:

1. Provided details for local search operators and justified k=2 iteration limit empirically;
2. Clarified 3% threshold follows established literature [26] with refinements for our baseline method;
3. Demonstrated scalability with new 100-node experiments showing 65× speedup over ACO;
4. Conducted comprehensive ablation studies on encoder layers, learning rate, and temporal embeddings;
5. Added multi-seed stability analysis and error bars confirming experimental rigor;
6. Tested cross-city generalization showing acceptable performance despite expected distribution shift.

Detailed Reply

1. Local Search Design Clarification

Summary: Applied 5 operators (2-opt, 3-opt, exchange, relocate, or-opt) sequentially across all datasets. k=2 chosen empirically as optimal cost-benefit tradeoff.

We sequentially apply five operators (2-opt, 3-opt, exchange, relocate, and or-opt) across all datasets and instance sizes. The k=2 iteration limit represents an empirical tradeoff between computational cost and performance improvement. Table 4 (Page 9) shows: iteration 0→1 yields substantial improvement (1.60%→0.39%), iteration 1→2 provides moderate gains (0.39%→0.30%), while iterations 2→10 show diminishing returns (0.30%→0.20%) despite equivalent computational overhead.

2. "Sensitive" Instances Definition

The 3% optimality gap threshold builds on Melgarejo et al.'s work [26], which used a 5% threshold (90th percentile). We refined it to 3% keeping the same percentile, as our static cost matrix baseline produces smaller optimality gaps compared to their MedianTSP baseline.

3. Encoder Scalability

Summary: Architecture scales to larger graphs without approximations. New 100-node experiments show comparable performance to ACO (7.43 vs 7.40 objective) but 65× faster runtime (42s vs 2741s). Memory usage scales quadratically.

The architecture scales to larger graphs without approximation strategies. New 100-node experiments (100 epochs, ~100 hours training, not converged yet) show comparable performance with ACO (7.43 vs 7.40 objective) while significantly outperforming runtime (42s vs 2741s):

We report the results in the table here and will add the results and subgraph of GPU memory usage and runtime vs. graph size to the final version.

4. Alternative Policy Gradient Methods

Summary: PPO tested but failed due to the critic network convergence issues. No variance/instability observed with REINFORCE, consistent with prior literature.

We implemented PPO before, but it did not perform well due to difficulties in critic network convergence. REINFORCE demonstrated good stability across multiple random seeds in our experiments. The following table reports consistent performance of REINFORCE across different random seeds (objective: 2.630±0.01, gap: 1.61±0.05 across 8 seeds). This stability also aligns with established TDTSP literature [8,16,38], where no instability issues are reported.

5. Experimental Implementation Clarity

Summary: Fair comparison ensured through identical conditions (hardware, datasets, batch size, data ordering) with GPU acceleration for all methods.

We apologize for the confusion and will provide the complete implementation details in the supplementary materials. We did not offer them originally to avoid the supplementary materials from becoming too long, a common complaint during the review process. However, we ensure rigorous experimental fairness through careful baseline implementation using PyTorch tensors with GPU acceleration for all methods. All evaluations use identical conditions: single GPU hardware, consistent datasets, uniform batch size (1024), and identical data ordering. Complete implementation details will be added to the supplementary materials.

6. Reinforcement Learning Design

Our RL implementation follows standard NCO practices [8,16,20,38], employing rollout baselines with a reward signal equal to negative tour completion time. No high variance or instability issues were observed during training, as explained in (Question 4), consistent with prior NCO literature.

7. Robustness Analysis

Summary: Error bars will be added. Results show high variance, aligning with the discovered Pareto distribution issue.

Beijing-10 results with variance:

The standard deviation of the gap is similar to or even larger than the mean of the gap, aligning with the Pareto distribution issue we discovered.

We did not report the error bar because statistical significance testing isn't conventionally reported in NCO literature [8, 16, 20, 38]. We will add the error bar to the final version of the paper.

8. Ablation Study

Summary: Additional ablations conducted: encoder layers (optimal N=3), learning rate (best: 3e-5 to 1e-3), temporal embeddings (sinusoidal > MLP > linear). All results will be detailed in the appendix.

Beyond MoE and local search ablation (Table 4), we conducted additional component analysis examining temporal embeddings, encoder layer configurations, and learning rate sensitivity.

Layer Num: The training time and the GPU memory increase linearly with the number of layers. The performance rises quickly when N<3, while it shows little to no improvement after N>=3.

Learning Rate: The best learning rate is between 3e-5 and 1e-3. A too large learning rate (3e-3) makes the model diverge, and a too small learning rate (3e-6) gets stuck at a bad local minimum.

Temporal embedding: The sinusoidal embedding is the most helpful one, compared with the MLP embedding and the Linear embedding. There are potentially other effective embedding methods, but that is beyond the scope of the paper.

These results, along with individual component impact assessments, will be detailed in the appendix.

9. Generalization Analysis

Cross-city evaluation (Beijing-trained model on Lyon-10):

Performance is competitive with ACO for direct cross-city generalization, and further improved with 10 epochs of tuning on the Lyon dataset, showing superior cross-city generalization.

10. Minor Issues

• Attention Mechanism: Standard multi-head attention with distinct MLPs for Q, K, V projection.
• Notation: Equation (5) will index the adjacency matrix by time: A[t].
• All notations will be sufficiently explained in the final version.