Neural Combinatorial Optimization for Time-Dependent Traveling Salesman Problem
Authors: Ruixiao Yang
Chuchu Fan
Venue: NeurIPS 2025 poster ()
Keywords: Time-Dependent Routing
Neural Combinatorial Optimization
Traveling Salesman Problem
Deep Reinforcement Learning
Primary area: optimization
TL;DR: We propose a state-of-the-art neural-based method for solving Time-Dependent Traveling Salesman Problem and identify the limitation of existing evaluation method..

Abstract: The Time-Dependent Traveling Salesman Problem (TDTSP) extends the classical TSP by allowing dynamic edge weights that vary with departure time, reflecting real-world scenarios such as transportation networks, where travel times fluctuate due to congestion patterns. TDTSP violates symmetry, triangle inequality, and cyclic invariance properties of classical TSP, creating unique computational challenges.
In this paper, we propose a neural model that extends MatNet from static asymmetric TSP to time-dependent settings by using an adjacency tensor to capture temporal variations, followed by a time-aware decoder. Our architecture addresses the unique challenge of asymmetry and triangle inequality violations that change dynamically over time.
Beyond architectural innovations, our research reveals a critical evaluation insight: many practical TDTSP instances maintain the same optimal solution regardless of time-dependent edge weights. This exposes a fundamental limitation in current evaluation practices for TDTSP that rely solely on average travel time metrics across all instances. Such metrics fail to effectively distinguish between methods that genuinely capture temporal dynamics and those that merely perform well on static routing problems. 
Instead, we present extensive experiments on real-world datasets, evaluating our approach on both entire datasets and specifically filtered instances where temporal dependencies alter the optimal solution. Results show that our method achieves state-of-the-art average optimality gap on full instances and significant travel-time reduction on instances where time-aware routing saves time. These results demonstrate state-of-the-art ability to identify and exploit temporal dependencies, setting new standards for evaluating time-dependent routing problems.

Neural Combinatorial Optimization for Time-Dependent Traveling Salesman Problem
Ruixiao Yang Massachusetts Institute of Technology ruixiao@mit. edu
Chuchu Fan Massachusetts Institute of Technology chuchu@mit.edi
Abstract
The Time-Dependent Traveling Salesman Problem (TDTSP) extends the classical TSP by allowing dynamic edge weights that vary with departure time, reflecting real-world scenarios such as transportation networks, where travel times fluctu- ate due to congestion patterns. TDTSP violates symmetry, triangle inequality, and cyclic invariance properties of classical TSP, creating unique computational challenges. In this paper, we propose a neural model that extends MatNet from static asymmetric TSP to time-dependent settings by using an adjacency tensor to capture temporal variations, followed by time-aware decoder. Our architecture addresses the unique challenge of asymmetry and triangle inequality violations that change dynamically over time. Beyond architectural innovations, our research reveals critical evaluation insight: many practical TDTSP instances maintain the same optimal solution regardless of time-dependent edge weights. This exposes a fundamental limitation in current evaluation practices for TDTSP that rely solely on average travel time metrics across all instances. Such metrics fail effectively distinguish between methods that genuinely capture temporal dynamics and those that merely perform well on statie routing problems. Instead, we present extensive experiments on real-world datasets, evaluating our approach on both entire datasets and specifically filtered instances where temporal dependencies alter the optimal solution. Results show that our method achieves fate--of-the-art average optimal- ity gap on full instances and significant travel-time reduction on instances where time-aware routing saves time. These results demonstrate state-of-the-ar ability identify and exploit temporal dependencies, setting new standards for evaluating time-dependens routing problems.
Introduction
The Traveling Salesman Problem (TSP) is widely studied optimization problem with applications in logistics and transportation. However, the classic TSP assumes static edge weights, failing to capture real-world dynamics in which travel times vary with departure time due to traffic patterns. This limitation is particularly relevant urban environments where optimal routes during off-peak hours may become inefficient during rush hour. As cities continue to grow and delivery demands increase, the ability to optimize routes with time-dependent considerations becomes increasingly valuable for logistics operations, environmental impact reduction, and customer service.
The Time-Dependent Traveling Salesman Problem (TDTSP) (23 extends the classical TSP by incorporating time-varying edge weights. In TDTSP, the cost of traversing edge depends not only on the distance but also on the departure time from the origin node. This time dependency reflects real-world scenarios where traffic patterns, weather conditions, create dynamic travel costs throughout the day. Compared with the metric TSP, TDTSP violates the symmetry, triangle inequality, and cyclic invariance properties, making it more challenging.
operational schedules
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

While traditional exact and heuristic methods exist, finding near-optimal solutions efficiently remains difficult. Recent Neural Combinatorial Optimization approaches using deep reinforcement learning (DRL) have shown promise. However, current DRI. approaches exhibit limitations in learning spatiotemporal dynamics and in their evaluation methodology. Existing models either separate the dime-dependent adjacent tensor by node [8 [6] or by time [8) failing to capture both spatial and temporal structures simultaneously. Meanwhile, existing works evaluate methods across all instances in datasets, using only the average tour duration the evaluation metric. Through our analysis of real-world datasets from cities, we identify a shared instance distribution, where most instances randomly generated from a practical dataset maintain the optimal solution regardless of time-dependent edge weights. Under such a distribution, a well-designed ATSP solver could also achieve low average durations, rendering the metric insufficient to demonstrate the model's s effectiveness in learning time dependencies. To overcome these limitations, we introduce a novel neural model that learns spatial and temporal structures simultaneously, and post-processing step improve solution quality based on the data distribution.
In summary, the contribution of the paper can be highlighted as:
1. Empirical analysis of practical TDTSP data, identifying the limitations of the evaluation method in existing DRL work and proposing
evaluation method.
2. An end-to-end neural network model that directly encodes the dime-dependent adjacency tensors, effectively capturing the complicated spatiotemporal dynamics in TDTSP.
3. An effective inference process to enhance the solution quality based on the data distribution.
4. We conduct comprehensive experiments on real-world datasets using the proposed evaluation method, demonstrating our method's s state-of-the-art performance and strong support for learning spatiotemporal dependencies.
2 Related Work
2.1 Time Dependent Traveling Salesman Problem
The Time-Dependern Traveling Salesman Problem (TDTSP) is used refer two different problems:
the scheduling problem where job time depends on the order in the sequence [30, 15] and the
routing problem where the traveling time depends on the distance and departure time 23 24 21).
In this paper, we focus on the latter one. This problem is sometimes studied within the broader framework of Dynamic TSP (DTSP) and Dynamic VRP (DVRP) 12
Solution methods fall into three categories, each with distinct advantages and limitations:
Exact methods include Branch-and-Cur [00. Branch-and- Bound [2], and Constraint Programming 266.. While these guarantee optimal solutions, they scale poorly to practical instances, with computa- tional complexity growing exponentially with problem size.
Heuristic approaches such as Ant Colony Optimization L2
25
27 Monte-Carlo 4 Neighborhood
Search [36 33), Tabu Search 14). and Simulated Annealing [3 offer better scalability and can handle larger instances. However, they can still not provide a satisfactory solution within a short computational time.
Neural methods 38 16
use the Attention Model 18 structure and the REINFORCE (35)
training algorithm, providing remarkably short inference time and a small optimality gap. Taking the time-dependent adjacency matrix input, Guo al. [66] and Zhang et al. (38 encode each row separately as a node feature, focusing on temporal structure while overlooking asymmetric spatial relations. On the contrary, Chen et al. [8] processes the adjacency matrix only at specifie time point during decoding, thereby failing to incorporate temporal structure. Our method directly encodes the time-dependent adjacency matrix, capturing the spatiotemporal dynamics simultaneously.
2.2 Neural Combinatorial Optimization for Routing
The pioneering work of Vinyals et al. 34 introduced Pointer Networks, a sequence-to-sequencc learning method with attention to output permutations for TSP, which effective but requires expensive labeled training data. The follow-up work [3] addresses the issue by combining pointer

---

A
B
A
B
I+t
2
1+t
1-t
D
C
D
C
(a) TSP instance and solution
(b) TDTSP instance and solution
Figure 1: Example showing the changing weights results in changing optimal solution. We mark the starting node and the solution in yellow. the TSP instance, the shortest tour is ACDBA, with a traveling time of 6. The TDTSP instance, sharing the same adjacent matrix with the TSP instance starting time = O, has the optimal solution ABCDA, which differs from the TSP instance with a traveling time of 8. Note that the tour ACDBA now has the traveling time (1 (1+0) +20 (1+3) 9.
networks with reinforcement learning (RL) to train without labels. Kool et al. [8] further advanced this direction with the Attention Model (AM), which uses multi-heat attention encoder and single- head attention decoder to construct TSP tours auto-regressively Following the same structure, Bresson and Laurent 7 replaces the attention encoder with transformer encoder for better performance.
The early works focus on metric TSP
22 which can be easily encoded by node coordinates in 1R= Recent advances have begun ex explore the more general routing problem non-Euclidean spaces using edge features. Kwon al. [20] proposes the MatNet to encode the adjacency matrix for Asymmetric TSP (ATSP) with separation of nodes' departure and arrival roles, which also used by Gaile et al. [13]. Zhang et al. (37] proposes variant the graph attention network to take edge features input. Our work follows MatNet for encoding tensor inputs.
28
19
3
Preliminary
In this section, we will first give a formal problem statement of TDTSP with theorem of its hardness. Then we will briefly introduce the existing method that encodes matrix input for Asymmetric TSP.
3.1 Problem Statement
The Time-Depen DeppedDenndnt Traveling Salesman Problem (TDTSP) is generalization the classical TSP where the travel time between locations varies as function of time. Formally, we define it as follows:
Given complete directed graph G (V, E) where V {0i, u2,..., vn) is the set of nodes (cities or locations) and E is the set of edges connecting these nodes. Unlike the classical TSP, where each edge (w;, v;)) has constant cost Cıj. in TDTSP, the cost of traversing an edge depends on the departure time from the origin node.
Let esg (L) denote the time needed for traveling from node to node v, when departing node at time t. We do not assume symmetry, which means (t) * (t.(t) in general. We assume c.y (t) is a continuous function for t [0, T'. The arrival time node 2/ when departing from v, time is t + Ci (t). We assume the salesman is not waiting at any nodes, which valid when the property of the First-In-First-Ouu (FIFO) [17] holds. Then the departure time is the same the arrival time.
The objective of TD-TSP find a permutation æ = (II,... Xn,) of nodes in V where m en typically designated as the depot, such that the total traveling time is minimized:
min
CreTEET (tmx) + Cram (ta.):
where t, 2 is the initial departure time and ti is the arrival time at my which is defined
IT bxc- + Cra- (Ire-1)-
We show an example in Fig. Next, we present the hardness of approximating TDTSP. Theorem 1 (Hardness of TDTSP). TDTSP cannot upproximated by any apprrxxiiiiiiio algorithu unless P=NP, where a(n) is function that can be computed in polynomial time.
3

---

Beijing
London
Lyon
Nairobi
Savings (%)
Sen Savina (%)
10
Savings (%)
Sevings
10
0.5
1.0
0.5
1.0
0.5
1.0
0.5
1.0
Percentile
Percentile
Percentile
Percentile
Figure 2: Distribution of travel time savings achieved by time-aware routing compared to static routing on randomly sampled instances from real-world datasets. The x-axis shows percentiles of instances, and the y-axis shows the corresponding travel time saved (in percentage). Note the long-tail distribution, indicating that significant time savings occur in small but important subset of instances.
The proof can be found in Appendix A due to space limitations.
TDTSP can be described by the time-dependent adjacent matrix A(t) [c)g())s.iev. Since the continuous function c(t) is usually not analytical in practice, we approximate it by interpolating samples of {ca (0), Ciy (1). Ci 1)}. In this paper, the imput of TDTSP is a tensor A[t] {.((t) tt= =, 1.. _ 1} with linear interpolation to approximate A(t).
3.2 Encoding Adjacent Matrix Input
To solve the asymmetric TSP (ATSP) with neural methods, Kwon et al. [20 proposes a dual graph attention layer. The static adjacency matrix of set of node V {ui,,.. Un) is treated as the weights of a bipartite graph (V+, V=), where V {uT.... x } the set of nodes with outgoing edges and V- {uT 1. 1 is the set of nodes with incoming edges. The edge weight is defined as dvv 07 nature of ATSP, where generally A.j # Aji-
d(v,, v2y) = Ag. This bipartite construction elegantly addresses the asymmetric
The nodes in V+ and V- encoded into separate set of vectors: (httt) } and (h.)). The embedding (h+) is initialized zero vectors and (h5,) } as one-hot vectors. To encode the asymmetric distance information, (htt) and (hr:) are iteratively updated using both current node embeddings and the edge weights A.
Inside each update iteration, {htt} and } are processed through dual graph attention layer, which consists of two attention-base update functions F+ and F with identical structure. Function F+ updates the embeddings {ht, based on the embeddings of nodes V-, while F updates { based on the embeddings all nodes in V+:
(btt)' F ( (1, Ag) : oj VV - (Mr, (1ht, Aji) : of vV+))
Through this iterative process, each node accumulates information about its distance relationships with other nodes, enabling the model to leam effective representations for the ATSP.
4 Data Analysis
We analyze time-dependent travel time data from 12 cities across three benchmarks 26 38 5 Fig. shows 4 examples (remaining in Appendix C). The travel time saved by considering time demedde edge weights follows Pareto distribution consistently across all cities. Approximately half of the instances show no change in optimal tours despite varying edge weights, while roughly 20% of instances contribute more than 80% of total savings, resulting in low average improvement.
This distribution pattern creates two significant challenges. First, evaluating algorithms by average performance across all instances, as done in previous works [38 [6 8, fails to distinguish between general routing capability and the specific ability to exploit time-dependent patterns. Second, the limited number of meaningful time-dependent instances complicates the learning process. For supervised learning, obtaining labels is prohibitively expensive due to the NP-hard nature of TDTSP For DRL, quantifying the potential improvement without ground truth becomes difficult.

---

Row Emb
Filter
MLP
A[T] [
A[t]
MLP
Concatenate
Product
Mask
Add
Context
Attention
Action
Col Emb
XN
Sinusoidal
Encoder
Decoder
Figure 3: Architecture of our time-dependent method. The encoder processes the adjacency tensor A[t] and its transpose A [t] (where rows and columns represent departure and arrival nodes, respec- tively) through N iterative dual graph attention layers produce node embeddings. The decoder then constructs the tour auto-regressively, maintaining state of (partial tour, current time) and using masked attention with temporal embeddings to select each subsequent node.
Despite these challenges, the problem remains economically significant. In logistics markets worth trillions, even I % improvement yields substantial cost savings.
5
Methodology
To extend current methods TDTSP and develop effective solver in practical scenarios, must address two key challenges:
The complex spatio-temporal features in TDTSP, where the adjacency matrix is expanded to A|t] include one more dimension of time making neural methods challenging to train.
The Pareto distribution of TDTSP solutions, where problem instances whose optimal solu- tions differ from their static counterparts are rare but critically important in practice.
Our methodology addresses these challenges through two components: (1) a neural architecture directly encoding the time-dependent adjacency tensor to capture spatio-temporal structures and decode complete trajectory solutions; and (2) post-processing refinement method enhancing solution quality while preserving computational efficiency. The following sections detail each component and demonstrate how each component addresses the identified TDTSP challenges.
5.1 Model Structure
Our model, shown in Fig. uses encoder-decoder architecture based AM [1]] It takes the time-dependent adjacency tensor A[t] as input, encoding it into two sets of node embeddings {ht) } and {hr,}, representing nodes with outgoing and incoming edges, respectively. Using these embeddings, the decoder then auto-regressively constructs the full trajectory step by step.
5.1.1 Encoder
The goal of the encoder is to transform the adjacency tensor A[t] into sets of node embeddings (h+, and (hr,). ). As introduced Section 3.2 encoding a static adjacency matrix A for spatial information has been well-established. The challenge lies in extending the approach to the time- dependent adjacency tensor A[4] to capture both spatial and temporal information simultaneously.
For the higher dimensional Alt). similar to the operation of static A, we treat the input time-dependent adjacency tensor A(t] as bipartite vector-weighter graph G = (V+, VV())) where V+ and V- correspond to the nodes of outgoing edges and incoming edges. Each edge (uit .17) has vector weight A; it] with costs at discrete time steps. The node embedding ht and h, are similarly initialized zero and one-hot vectors and updated according the mechanism in Eq. (
To facilitate the exchange of temporal information while keeping computational cost manageable, the update function F+ is designed as three-stage process. First, compute attention scores between
5

---

outgoing and incoming nodes:
W Score ( (h,
where W is an n x n matrix representing the importance of each outgoing incoming node pair. Intuitively, this matrix represents how much attention each source node should pay to each destination node, independent of the specific time of travel.
Second, we then integrate the temporal information by concatenating these attention weights W+ with the time-dependent adjacency tensor A[t] along the time dimension. This combined representation is then processed through multi-layer perceptron (MLP) that learns to compress the temporal patterns into the attention weights:
(W+y= MLP((AAE), W+])
This step allows the model to selectively focus on the most relevant temporal patterns for each node pair (uy+, , while reducing the computation from naively processing the full temporal dimension. Finally, we update the embedding by weighted aggregation
(het) (ootmaxx(W:")""
J
(6)
The softmax operation ensures that the attention weights are normalized, allowing the model to focus on the most relevant connections while maintaining consistent scale for the embeddings.
The update function F- shares the same update mechanism for nodes with incoming edges. We stack N of these dual graph attention layers, allowing the embeddings to progressively refine their
representation of spatio-temporal patterns. The final embeddings { }(M) and { }(M) capture the rich spatio-temporal structure of the problem instance and are passed the decoder.
5.1.2 Decoder
Our decoder constructs the complete tour in an auto-regressive manner, meaning it sequentially predicts the next node TT++1 each time step based previously selected partial tour and until the entire trajectory is constructed. This approach is particularly well-suited to TDTSP, as it naturally accommodates the problem's 's time-dependent nature by updating temporal information at each step.
At each step of decoding, the decoder takes two state variables: the partial tour T (containing ( visited nodes) and the current time that tracks when would arrive node The probability distribution of the next node is computed via a masked attention mechanism, where the query vector q MLP((h; h
1) is extracted from current node and the start (which also the destination)
node. The key, value, and logit key k, v, k MLP(((T) }) are extracted from the node set V-
To take into account the time information, encode the current time with Sinusoidal embedding into t, and compute the probability of the next node as
pe (o( = Softmax + () + t) [ vdk
vk
One key insight about the sinusoidal embedding's role in the attention mechanism involves its addition node embeddings. This operation introduces temporal information while leveraging the fixed norm property of sinusoidal embeddings. Specifically:
(q + (k+t))
qk
+
bq+kjt
TE
(8)
node -ode
node time
constant!
5.2 Training
Unlike static ATSP models, our time-dependent approach cannot use the POMO 19 training frame- work directly. The challenge arises from the addition of edge weights, which result in asymmetric travel times for cycle with different starting nodes. As a result, we choose to train our model with the classic REINFORCE, algorithm 35), employing a rollout baseline with reward signal equal to the negative tour completion time.

---

Table Summary of test datasets.
City
Size
Start Time
End Time
Interval
Sample
Dilatation (%)
Instance Size
Beijing
100
0:00
0:00 (+1)
2 h
Uniform
0
10. 20, 50
Lyon
255
6:00
12:30
6 min
Uniform
20
10, 20
Nairobi
2000
15:00
21:00
10 min
Congestion
10, 20
London
2000
15:00
21:00
min
Congestion
10, 20
5.3 Inference
During inference, we employ two types of post-processing refinement methods sequentially to improve solution quality without introducing significant computational overhead.
Mixture of Experts (MoE). Due to the Pareto distribution property of TDTSP solutions, large fraction of instances share the same optimal solutions with their corresponding ATSP counterparts, where a dedicated ATSP solver may excel. Leveraging this insight, we implement a Mixture of Experts (MoE) approach that evaluates solutions from both our neural model and state-of-the-ar ATSP solver, selecting the one with lower lime-dependent cost.
Local Search. We treat the output trajectory of our method as a high-quality warm start of near- optimal solution and apply local search procedure to refine it further, including two-opt, three-opt, or-opt, exchange, and relocate, which are commonly used in solving TSP (6]. We limit the local search to k = 2 iterations to ensure computational efficiency.
This hybrid approach combines our neural model's fast inference and ability learn spatio-temporal patterns with the strengths of existing methods, while addressing potential suboptimalities in the neural solution arising from the REINFORCE algorithm.
Experiments
In this section, we validate the effectiveness and scalability of our method real-world datasets. Our proposed approach was programmed with PyTorch. All the experiments were conducted on workstation with 128 Ryzen Threadripper PRO 7985WX 64-Cores CPU and 4 NVIDIA A800 GPUs.
6.1 Experiments Setup
We compare our algorithm to typical algorithms that accept tensor input for TDTSP, which can be further categorized into three types:
Baselines.
1. Exact method. We implement dynamic programming (DP) to solve TDTSP as the representative of the exact method. The computational cost low on 10-node instances, expensive 20-node instances, and unacceptable on 50-node instances.
2. ATSP. As shown in Sec. 4 the average travel time saving is relatively low due to the data distribution. We select the DP for ATSP and MatNet as baselines to test the ability of learning time-dependent patterns.
3. Heuristic Algorithms. We implement three heuristic algorithms, including the greedy algorithm (GR), the Simulated Annealing algorithm (SA), and the Ant Colony Optimization algorithm (ACO). The greedy algorithm always selects the next unvisited node with the shortest time needed. The SA follows the pseudo code provided by Zhang et al. 38 with the same parameters. Details of GR and ACO provided in Appendix B.
To ensure rigorous experimental fairness. we implement baselines using PyTorch tensors with GPU acceleration for all methods. All evaluations use identical conditions: single GPU hardware, consistent datasets, uniform batch size of 1024, and identical data ordering.
Dataset. We generate data from real-world datasets across four cities: Beijing 38 Lyon 26 Nairobi, and London (5). These datasets contain time-dependent travel times between nodes, with

---

Table 2: Computational results on TDTSP.
(a) Scalability experiments.
Method
Obj
Gap(%) L Time(s)
Obj 4 Gap(%) Time(s) +
Obj Gap(%) J Time(s)
Boijing-10 10
Beijing-00
Beijing-50
DP, TDTSP
2.59
0.00
15.00
4.27
0.00
DP, ATSP
2.70
4.43
5.08
4.46
4.52
MatNet, ATSP
2.71
4.66
1.06
4.48
5.18
2.33
8.38
8.61
GR
3.34
19.72
0.16
5.90
38.58
0.98
11.66
14.16
SA
2.60
0.06
226.03
4.30
0.85
3491.62
8.17
38112.78
ACO
2.95
14.23
77.86
4.93
15.51
314.47
9.40
1128.55
Ours (Raw)
2.63
1.60
1.20
1.39
3.14
2.66
8.24
9.37
Ours (Imp)
2.59
0.21
14.06
4.30
0.89
108.25
8.09
1549.88
(b) TDTSP results on cities.
Method
Obj L Gap(5) +
Time(s) 4
Obj 4
Gap(%) + Time(s) 4
Obj
Gap(%)
Time(s)
Lyon-10
Nairobi-10
London-10
DP, TDTSP
18.76 79
0.00
27.48
18.18
0.00
30.31
24.54
0.00
27.38
ATSP
18.92
0.66
10.63
18.43
1.32
10.57
24.60
0.25
10.50
MatNet, ATSP
18.94
0.78
0.84
18.45
1.41
0.91
24.65
0.47
0.98
28.09
50.31
0.45
25.46
40.29
0.62
33.38
36.22
0.70
SA
18.80
0.07
353.1 17
18.19
0.02
345.15
24.55
0.01
376.58
ACO
19.64
4.78
141.84
18.63
2.49
171.71
24.91
1.50
139.77
Ours (Raw)
18.95
0.87
0.78
18. 18.23
0.28
0.77
24.64
0.43
0.99
Ours (Imp)
18.81
0.11
29.63
18.19
0.04
23.06
24.55
0.04
40.00
(c) TDTSP results on 20 cities.
Method
Ohj + Gap(%) +
Time(s) +
Ohj
Gap(%) 4 Time(s) +
Obj + Gap(%) Time(s)
Lyon-20
Nairobi-20
London-20
DP. TDTSP
27.64
0.00
24.78
0.00
32.29
0.00
DP, ATSP
27.76
0.48
25. 19
1.67
32.49
0.61
MatNet, ATSP
27.97
1.19
2.35
25.29
2.06
1.95
32.65
1.11
2.06
GR
40.85
87.52
4.50
41.07
65.84
4.11
61.26
89.63
4.90
SA
27.83
0.72
4362.10 10
24.87
0.35
4870.34
32.35
0.19
5008.44
ACO
29.33
6.60
500.63
26.09
5.41
566.32
33.38
3.38
570.10
Ours (Raw)
28.13
1.83
2.63
25.31
2.85
2.17
32.38
0.30
2.79
Ours (Imp)
27.74
0.40
221.59
24.88
0.40
290.73
32.31
0.08
297.61
varying sampling intervals and time horizons. For Nairobi and London, we create smaller datasets by selecting the 50 most congested nodes based on the average edge-weight variance over time. From each city's 's data, we generate problem instances with n E {10, 20) nodes via downsampling (50-node instances were generated only for Beijing due to time-horizon constraints in the other cities). For each problem size and city combination, we generated 10,000 test instances. Dataset characteristics, including sampling frequencies and time periods, are summarized in Table
Hyper Parameters. We train our model with a batch size 1024 for instances of size 10 and 20, and 256 for instances of size 50. We use Adam optimizer with a learning rate 1 x 10-1, We train 200, 300, and 500 epochs, respectively, with each epoch 1,280,000 data. We train MatNet with the same batch size and epochs, and learning rate of x 10 All training distributed 4 GPUs.

---

Table Average gaps tested on two sets of selected instances. Gaps report in %.
0
3%
>
3%
0
> 3%
> 3%
Model
Beijing- 10
Lyon-18 10
Nairobi 10
London- 10
DP
0.00
9.16
0.00
4.68
0.00
4.76
0.00
3.20
MatNet
0.70
9.11
0.24
4.04
0.25
4.41
0.33
1.52
Ours (Raw)
1.42
1.70
0.72
1.25
0.24
0.22
0,40
1.00
Ours (Imp)
0.05
0.32
0.03
0.29
0.01
0.06
0.02
0.00
Model
Beijing-20
Lyon-20
Nairobi-20
London-20
DP
0.00
6.94
0.00
3.92
0.00
4.61
0.00
3.31
MatNet
6.94
1.03
2.14
0.86
4.22
0.89
2.21
Ours (Raw)
2.75
3.32
1.75
2.03
3.14
3.66
0.33
0.10
Ours (Imp)
0.34
1.34
0.35
0.69
0.19
0.88
0.05
0.10
6.2
Comparison Results
In the comparison experiments, we test both the direct output of our neural model (Raw) and the improved solution with MoE and local search (Imp). We evaluate the methods based average tour duration, average gap to the optimal solution, and running time.
Full Instances. We first evaluate our method on all instances and show the results in Table 2 Our method achieves competitive performance with the best heuristic, SA, on small cases with 10. As the problem size n increases, our method outperforms all baseline methods, demonstrating the effectiveness of our pipeline for TDTSP. On the Beijing dataset, our method successfully scales to 50-node instances, as shown in Table 2a demonstrating its scalability. The strong performance across four datasets also supports the general applicability of our method. We also compare two variants of our method. The sole neural model produces slightly worse solution runs much faster, revealing the great potential of solving TDTSP with a learning-basee method alone.
Selected Instances. To better understand our model's performance, we evaluate on two distinet subsets of the data. The first contains instances where time- dependennd routing offers duration reduction, while the second includes instances where it provides reduction greater than 3%. This threshold is based the 90th percentile of improvement in our dataset, adapting the methodology of Melgarejo et al. [26] to our stronger static baseline. As shown in Table 3] our neural model is generally worse than MatNet in the first type of instances, but consistently outperforms both ATSP solvers. The results suggest that our method excels at capturing temporal structure but slightly falls short of MatNet in capturing spatial structure, which motivates the use of MoE during inference.
6.3 Ablation Study
We conduct an ablation study to evaluate the impact of key design choices and hyperparameters, including the inference improvement methods, the number of encoder layers, the learning rate, and the temporal embedding technique.
Inference. We assess our solution improvement methods on 10-node instances from the Beijing dataset. As shown in Table 4 both MoE and local search enhance solution quality. The MoE effectively addresses the limitations of our neural model in learning spatial structure. The local search delivers significant improvements in the first iteration, with diminishing returns thereafter. The first iteration alone yields a substantial improvement, reducing the optimality gap from 1.60% 0.39%. A second iteration yields more moderate gain of 0.30%, while subsequent iterations, to the tenth, offer minimal further improvement, reaching 0.20% similar computational cost per iteration. Given the computational cost per iteration, we recommend using the based MoE with single local search iteration for large-scale problems.
Number of layers. As detailed in Table 5a both training time and GPU memory consumption scale linearly with the number of encoder layers, N. Model performance improves substantially as N increases to 3, but shows little to further improvement for N > 3.

---

Table Comparison of different improving methods on Beijing- 10.
Iterations
2
10
Expert
Obj
Gap(%)
Obj
Gap(%)
Obj
Gap(%)
Obj
Gap(%)
None
2.6298
1.6017
2.5990
0.3851
2.5970
0.3034
2.5945
0.2081
DP, ATSP
2.6120
0.8648
2.5956
0.2472
2.5946
0.2073
2.5930
0.1467
MatNet, ATSP
2.6129
0.9056
2.5960
0.2640
2.5946
0.2091
2.5930
0.1470
Table 5: Ablation Study for structural and training parameters.
(a) Number of encoder layers N.
N
2
4
GPU Memory (GiB)
2380
3018
3764
4478
5212
Training Time (s epoch)
33,06
52.56
72.24
91.63
111.59
Obj
2.93
2.66
2.63
2.63
2.63
Gap 96) 4
13.43
2.63
1.80
1.63
1.60
(b) Learning rate.
3c-3
lc-3
3c-4
1c-4
36-5
1c-5
3c-6
Obj Gap %))
4.2230
2.6409
2.6305
2.6293
2.6468
2.6852
2.8778
65.7460
2.0525
1.6316
1.5793
2.2775
3.8439
11.4468
(c) Time embedding.
Embedding
Sinusoidal
MLP
Linear
Obj
2.6298
2.6409
2.6447
Gap(%)
1.6018
2.0443
2.1953
Learning rate. The results in Table 5h
indicate that the optimal learning rate lies between 3e - and 1e-3. An excessively large rate (3e-3) 3) causes the training diverge, whereas rate that is too small (3e-6) results in the model converging to poor local minimum.
Temporal embedding. We compared three different temporal embedding methods, shown in Table The sinusoidal embedding proved to the most effective, outperforming both MI-P-based and linear embeddings. While other embedding strategies may exist, a broader investigation is beyond the scope of this paper.
7 Conclusion and Discussion
In this paper, we investigated the Time Dependent Traveling Salesperson Problem (TDTSP), which ex- tends classic TSP by incorporating dynamic edge weights to reflect real-world environmental changes. Our primary contribution is novel neural-based approach that directly encodes time-dependent tensors to effectively capture spatial-temporal dynamics. We identified limitations evaluating with average tour duration on full learning-and and proposed new evaluation method. Experimental results validate our method's state-of-the-art performance and effectiveness in capturing complex spatial-temporal structures.
inneuftiiisf for showing effective temporal structure
Our approach shows limitations on problem instances where TDTSP solutions coincide with static ATSP counterparts, where specialized ATSP methods slightly outperform our approach. This stems from a key challenge: training with REINFORCE compromises spatial structure learning because TDTSP violates the cyclic invariance property present in ATSP. While we demonstrated mitigation through an MoE approach during inference, developing training algorithms that better preserve spatial structure learning without relying on eyclic invariance remains important direction for future work.
10

---

Acknowledgments
This work was partly supported by the National Science Foundation (NSF) CAREER Award #CCF- 2238030 and the MITEI Future Energy Systems Center. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the authors and don't necessarily reflect the views of the sponsors.
References
[1] Hernán Abeledo, Ricardo Fukasawa, Artur Pessoa, and Eduardo Uchoa. The time dependent traveling salesman problem: polyhedra and algorithm. Mathematical Programming Computa- lion, 5(1):27-55, 2013.
[2] Anna Arigliano, Tobia Calogiuri, Gianpaolo Ghiani, and Emanuela Guerriero. A branch-and- bound algorithm for the time-dependee dependennd travelling salesman problem. Networks, 72(3):382-392, 2018.
[3] Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint wrXiv::611.099000 2016.
[4] Johannes Bentner, Günter Bauer, Gustav M Obermair, Ingo Morgenstern, and Johannes Schnei- der. Optimization of the time-dependent traveling salesman problem with monte carlo methods. Physical Review 64(3)003670,, 2001.
[5] Jannis Blauth, Stephan Held, Dirk Müller, Niklas Schlomberg, Vera Traub, Thorben Tröbst, and Jens Vygen. Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks. Discrete Optimization, 53: 53:100848, 2024.
[6] Olli Bräysy and Michel Gendreau. Vehicle routing problem with time windows, part i: Route construction and local search algorithms. Transportation science, 39(1):104-118, 2005.
[7] Xavier Bresson and Thomas Laurent. The transformer network for the traveling salesman problem. arXiv preprint arXhv:2103.03013 2021.
[8] Dawei Chen. Christina Imdahl, David Lai, and Tom Van Woensel. The dynamic traveling salesman problem with deneddepnddnnt and stochastic travel times: A deep reinforcement learning approach. Transportation Research Part C: Emerging Technologies, 172: 2025.
[9] Taesu Cheong and Chelsea C White. Dynamic traveling salesman problem: Value of real-time time traffic information. IEEE Transactions on Intelligent Transportation Systems, 13(2):619-633 2011.
[10] Jean-François Cordeau, Gianpaolo Ghiani, and Emanuela Guerriero. Analysis and branch-and- cut algorithm for the time-dependent travelling salesman problem. Transportation science, 48 (1):46-58, 2014.
[11] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26-29, 2018, Proceedings 15, pages 170-181. Springer, 2018
[12] Casper Joost Eyckelhof and Marko Snock. Ant systems for a dynamic tsp: Ants caught in traffic jam. In International workshop on ant algorithms, pages 88 99. Springer, 2002.
[13] Eliza Gaile, Andis Draguns, Emils Ozolinš, and Kärlis Freivalds. Unsupervised training for neural tsp solver. In International Conference Learning and Intelligent Optimization, pages 334-346. Springer, 2022.
[14] Maha Gmira, Michel Gendreau, Andrea Lodi, and Jean-Yves Potvin. Tabu search for the time-dependent vehicle routing problem with time windows on road network. European Journal of Operational Research, (88(1))129-144)) 2021.

---

[15] Luis Gouveia and Stefan VoB. A classification of formulations for the (time- demeeddeenndent traveling salesman problem. European Journal of Operational Research, 83(1):69 82. 1995.
[16] Feng Guo, Qu Wei, Miao Wang, Zhaoxia Guo, and Stein W Wallace. Deep attention models with dimension-reductinn and gate mechanisms for solving practical time-dependent vehicle routing problems. Transportation research part E: logistics and transportation review, 173: 103095, 2023.
[17] Soumia Ichoua, Michel Gendreau, and Jean- Yves Potvin. Vehicle dispatching with time- dependent travel times. European journal of operational research, 144(2):379-3966 2003.
[18] Wouter Kool, Herke Van Hoof. and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv: 1803.8803..77 2018.
[19] Yeong- Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 00:21188--20 118-2188111111 198, 2020.
[20] Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park. Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Informa- tion Processing Systems, 34:5138-55 11133-144,, 2021.
[21] Feiyue Li, Bruce Golden, and Edward Wasil. Solving the time dependent traveling salesman problem. In The Next Wave in Computing, Optimization, and Decision Technologies, pages 163-182. Springer, 2005.
[22] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36:8845 118845588644, 2023.
[23] Chryssi Malandraki and Mark S Daskin. Time dependent vehicle routing problems: Formula- tions, properties and heuristic algorithms. Transportation science, (663)):855200 1992.
[24] Chryssi Malandraki and Robert B Dial. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operational Research, 90(1) -5555555,, 1996.
[25] Michalis Mavrovouniotis and Shengxiang Yang. Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors. Applied Soft Comput- ing, 13(10)44023 4037, 2013.
[26] Penélope Aguiar Melgarejo, Philippe Laborie, and Christine Solnon. A time-dependent no- overlap constraint: Application to urban delivery problems. Integration of Al and OR Tech- niques in Constraint Programming: 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, Pruceedings 12, pages 1-17. Springer, 2015.
[27] Leonor Melo, Francisco Pereira, and Ernesto Costa. Multi-caste ant colony algorithm for the dynamic traveling salesperson problem. In Adaptive and Natural Computing Algorithmss: 1 1th International Conference, ICANNGA 2013, Lausanne, Switzerland, April 4-6, 2013. Proceedings 11, pages 179-188. Springer, 2013.
[28] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[29] Binbin Pan, Zhenzhen Zhang, and Andrew Lim. Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research, 291(1):218-231) 2021.
[30] Jean-Claude Picard and Maurice Queyranne. The time-dependent traveling salesman problem and its application to the tardiness problem one-machine scheduling. Operations research, 26( 1601).8--110 1978.
12

---

[31] Johannes Schneider. The -eeeddependent traveling salesman problem. Physica A: Statistical Mechanics and its Applications, 3 514(1-4):151-55, 2002.
[32] Anabela Simoes and Ernesto Costa. Che-based algorithms for the dynamic traveling salesman problem. In European Conference the Applications of Evolutionary Compulation, pages 354 364-363.55 Springer, 2011.
[33] Peng Sun, Lucas P Veelenturf, Mike Hewitt, and Tom Van Woensel. Adaptive large neighbor- hood search for the time-dependent profitable pickup and delivery problem with time windows. Transportation Research Part E: Logistics and Transportation Review, 138: 101942, 2020.
[34] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[35] Ronald J Williams. Simple statistical following algorithms for connectionist reinforce- ment learning. Machine learning, 1.229-256, 1992.
[36] Yiyong Xiao and Abdullah Konak. The heterogeneous green vehicle routing and scheduling problem with vareingying traffic congestion. Transportation Research Part E: Logistics and Transportation Review, 88:146-1666 2016.
[37] Yongxin Zhang, Jiahai Wang, and Zizhen Zhang. Edge-based formulation with graph attention network for practical vehicle routing problem with time windows. In 2022 International Joint Conference Neural Networks (IJCNV), pages 01-08. IEEE, 2022.
[38] Zizhen Zhang, Hong Liu, MengChu Zhou, and Jiahai Wang. Solving dynamic traveling salesman problems with deep reinforcement learning. JEEE Transactions on Neural Networks and Learning Systems, 34(4):2119 2132,,, 2021.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction summarize the scope and contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, is discussed the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
The theorem is in section with the proof and assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have reported all the hyperparameters used, We also provide code in the supplementary material.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
We upload the data and code the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
cisssnnniccyyyli for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppi.ccppulli//uuuiu wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: is in the experiment part. It can also be found in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bars are reported in appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: can be found at the beginning of section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: htttps://euur: http://enrrrisscc.ooo
Answer:
[Yes]
Justification:
We have read the code of ethics and carefully checked our paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: It can be found in the introduction and the conclusion.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
17

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not pose such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All used assets are publicly available and cited
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whw.ree.wthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
18

---

Answer: [Yes]
Justification:
We provide a readme file for how to run the code
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
we do not have crowdsourcing nor human subjects in the research
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not involve crowdsourcing research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
19

---

Justification:
We only use LLM to polish our writing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httees////aarrppc.cc///oorrrrrrp for what should or should not be described.
20

---

Berlin
Cincinnati
Kyiv
Madrid
Savings (%)
Sauinee (%)
Savings (%)
10
Sevings
5
0
0.5
1.0
0.5
1.0
0.5
1.0
0.5
1.0
Percentile
Percentile
Percentile
Percentile
New York
San Francisco
Sao Paulo
Seattle
Savings (%)
10
Savings (%)
Savings (%)
Savings (%)
10
0.5
1.0
0.5
1.0
0.5
1.0
0.5
1.0
Percentile
Percentile
Percentile
Percentile
Figure 4: Distribution of travel time savings achieved by time-aware routing compared to static routing on randomly sampled instances from real-world datasets. The x-axis shows percentiles of instances, and the y-axis shows the corresponding travel time saved (in percentage). Note the long-tail distribution, indicating that significant time savings occur small but important subset of instances.
A Proof of Theorem 1
Theorem 1 (Hardness of TDTSP). TDTSP cannot be approximated by any approxxiimtiiaaio algorithm unless P=NP, where a(n) is a function that can be computed in polynomial time.
E), let Ciş (1) for S n and (i,j) E graph. Otherwise, (t) a(n) The FIFO property holds. If Hamiltonian cycle exists, the salesman can travel along cycle with a traveling time n. Otherwise, the salesman needs least a(n) n traveling time. So a(n) a(z))aapprxiimatin exists if and only if P equals NP.
Proof. For any Hamiltonian problem G
B Baseline Algorithms
This section describes the details of the baseline algorithms
B.1 Greedy Algorithm
The pscudo code of the greedy algorithm is presented in Algorithm The greedy algorithm chooses the earliest reachable node among unvisited nodes each step based on the current node. The bottleneck of the algorithm is the computation speed of the function by interpolation.
Algorithm 1 Greedy Algorithm
Input: node set V, start node πi start time t, time dependent cost function c Output: A permutation π of the node set V as a TDTSP tour.
1: for = 2,3,
do
2: H; = arg min Cr. CT. (x(())(()
3: t, = f + CT- (mmL))
4: end for
B.2 Ant Colony Optimization
The pseudo code the Ant Colony Optimization is presented Algorithm) 2 For the visited node, we do not compute its score and assign value -00.
21

---

Algorithm 2 Ant Colony Optimization
Input: node set V, start node æ1, start time 11, time dependent cost function
Parameters:
number of ants Nant = 20, number iterations Niters 100, pheromone importance 1, heuristic importance 3 = evaporation rate p = 0.1, exploitation rate go 0.9
Output: A permutation æ of the node set V as a TDTSP tour.
1: for u, U V do pheromone ( [ (- 3: end for
2:
4: for
1,2, ..... ,...,,,,e Niters do for 1,2, N ant do
5:
6:
for 2,3, ......11 7i do
7:
for v E V [ h do
8:
heuristic(w) ( 1 1// scorefe) < (TeromonneTxx-ll10 (heuristic(ul))
9:
10:
q Uniform[0,
11:
if S go then
m < arg max, score(u]
13:
else
T softmax(score)
15:
end if
tx-1 + CT2-1171 (tk-1)
17: end for
end for
19: deposit + 1/(fn + CrA (tn) t
pheromone 1 pheromone/m: -T; [[m deposit
21: end for
22:
pheromone +- p pheromone
23:
end for
Table 6: Performance comparison against baselines 100-node problem instances.
Method
Random
Greedy
ACO
Ours
Obj mean (std) Time (s)
26.98 (1.60)
8.30 (0.51)
7.40 (0.40)
7.43 (0.40)
4.75
172.24
2741.25
42.24
C Data Analysis
We show the data analysis of the remaining eight cities in Fig. The cities show similar distributions Beijing, London, Lyon, and Nairobi.
D Encoder Scalability
To further evaluate the scalability of our method, we conducted an additional experiment on 100- node instances. The following results were obtained after approximately 100 hours of training for 100 epochs. As shown in Table O our method's s solution quality (objective score of 7.43) remains comparable to the strong ACO baseline (7.40), even though our model had not yet fully converged. Critically, our method's 's runtime of 42 seconds is approximately 65 times faster than ACO's 2741 seconds, demonstrating that its significant computational advantage scales to larger problem sizes.
We also report the training resource used by our method, shown in Table The GPU memory usage grows quadratically with the number of nodes, which is proportional to the size of the graph's adjacency matrix. The bottleneck to scale up the training time. As the problem scales, the training time needed to converge quickly scales up and becomes difficult to track.
22

---

Table 7: Scalability analysis of computational resource
Nodes
10
20
50
100
GPU Memory (GiB/batchsize)
5212/1024
14326/1024
18748/256
35884/128
Train Time (s/epoch)
111.60
201.08
687.10
3463.77
Table 8: Performance using different random seeds.
Metric
Seed
0
132
1178
1234
203681
385172
759043
847592
Obj mean
2.6314 14
2.6299
2.6289
2.6298
2.6313
2,6300
2.6290
2,6301
Obj (std)
(0.5786)
(0.5768)
(0.5765)
(0.5770)
(0.5771)
(0.5768)
(0.5768)
(0.5776)
Gap ()) mean
1.6532
1.6065
1.5678
1.6018
1.6587
1.6097
1.5659
1.6048
Gap( () (std)
(2.4259)
(2.4204)
(2.3958)
(2.4561)
(2.4427)
(2.4195)
(2.3820)
(2.3326)
Table Cross-city generalization analysis using Beijing- 10 and Lyon-10
Method
ACO
Beijing trained only
Beijing trained, Lyon tuned 10 epochs
Lyon trained only
Obj
19.64
19.72
19.09
18.95
Gap (%)
4.78
3.69
1.61
0.87
Table 10: Computational results with statistical significance on Beijing- 10
Method
DP, TDTSP
DP, ATSP
MatNet
GR
SA
ACO
Ours(Raw)
Ours(Imp)
Obj mean
2.59
2.70
2.71
3.34
2.60
2.95
2,63
2.59
Obj (std) Gap(%) (%)
(0.57)
(0.63)
(0.63)
(0.74)
(0.57)
(0.68)
(0.58)
(0.57)
4.43
4.66
19.72
0.06
14.23
1,60
0.22
Gap (6) (std)
(5.83)
(5.97)
(14.73)
(0.40)
(10.25)
(2.46)
(0.72)
E Training Stability
To show the stability of training, we evaluate our trained neural policy under different random seeds. Shown in Table & the policies trained from different random initializations perform similarly.
F Cross-City Generalization
test the cross-city generalization ability using the Beijing-10 and Lyon-10 datasets. As shown in Table the 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.
G Experiment Statistical Significance
In this section, present the experiment results, including both the mean and the standard deviation. The Beijing-10 10 results demonstrate that standard deviations of the gap on the 10000 instances often match or exceed the of the gaps. This table confirms finding that the time saved by considering the time-varying edge weights follows a Pareto distribution.
23

---

Table 11: Ablation Study for structural and training parameters.
(a) Number of encoder layers N.
N
2
3
4
GPU Memory (GiB)
2380
3018
3764
4478
5212
Training Time (s/ epoch)
33.06
52.56
72.24
91,63
111.59
Obj
2.93 (0.64)
2.66 (0.58)
2.63 (0.58)
2.63(0.58)
2.63 (0.58)
Gap(5) (%) 4
13.43 (9.02)
2.63 (3.33) 1.80 (2.59)
1.63 (2.44)
1.60 (2.45)
(b) Learning rate.
Ir
3e-3
le-3
3e-4
le-4
3e-5
1e-5
3e-6
Obj mean
4.2230
2.6409
2.6305
2,6293
2.6468
2.6852
2.8778
Obj (std)
(0.7554)
(0,5773)
(0,5766)
(0,5775)
(0.5800)
(0.5814)
(0.6259)
Gap(%) (6) mean
65.7460
2,0525
1.6316
1.5793
2.2775
3.8439
11.4468
Gap(%) (std)
(22.6098)
(2.8460)
(2.4443)
(2.4065)
(3.0714)
(4.2814)
(8.2724)
(c) Time embedding.
Emhedding
Sinusoidal
ML.P
Linear
Obj (std)
(.6298(0.5770) 2.6409 (0.5783) 2.6447 (0.5790)
Gap(%) mean (std) 1.6018 (2.4561) 2.0443 (2.8317) 2.1953 (2.9547)
24


Reviews:
[{"review_id": "1mVp2fqzGc", "reviewer": "Reviewer_5THB", "summary": "This paper addresses the TDTSP, a generalization of the classic TSP where edge costs vary with departure time. The authors propose a novel neural model that directly encodes a time-dependent adjacency tensor using a dual-graph attention mechanism, and introduce a new evaluation protocol to enhance the solution quality based on the data distribution.", "questions": "1. Clarification on Local Search Design: Could the authors specify which local search operators (e.g., 2-opt, relocation) were applied across different datasets or instance sizes? Additionally, how was the iteration limit k=2 determined? Providing this information would enhance the reproducibility and clarity of the proposed post-processing step.\n2. Definition and Justification of “Sensitive” Instances: Table 3 introduces a 3% optimality gap threshold to define \"sensitive\" instances. Is this threshold empirically derived, or dataset-specific? An ablation study or justification for this choice would help clarify its robustness and generalizability.\n3. Scalability of the Proposed Encoder: Can the proposed encoder architecture scale to larger graphs? If so, is any subgraph sampling or other approximation strategy employed? It would be helpful to report GPU memory usage and runtime as a function of graph size n to assess scalability.\n4. Consideration of Alternative Policy Gradient Methods: Given the known limitations of REINFORCE in terms of spatial learning and sample efficiency, have the authors considered more stable or efficient policy gradient variants?", "limitations": "YES", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n1. This work addresses a practically significant and societally relevant problem, time-dependent route optimization in urban logistics, by advancing neural methods to better capture real-world spatiotemporal dynamics.\n2. This paper proposes to capture spatio-temporal dependencies more effectively than prior approaches that separate node and time representations, and integrates MoE with classical ATSP solvers and local search, leading to better empirical performance.\n3. The paper is written with a well-structured motivation and methodology, making it easy to understand.\nWeaknesses:\n1.\tThe setting and implementation of the experiment in this paper are not clear enough. For example, the setting and comparison details of the baseline should be given in the supplementary materials instead of the pseudo code of the algorithm. The reader concern about how to make a fair comparison with different types of baselines, rather than the principles of different algorithms.\n2.\tReinforcement learning design is under-specified. While REINFORCE is employed, the paper omits details on the reward signal, whether techniques like baselines or advantages are used to reduce variance, and how sparsity or instability is addressed.\n3.\tLack of robustness analysis. The paper does not report error bars or statistical significance testing, which weakens the reliability of the reported improvements, especially when differences are small.\n4.\tMissing ablation study. The individual contributions of key components (such as temporal embeddings, dual-graph attention, MoE, and local search) are not given, making it hard to assess their necessity or impact.\n5.\tMissing generalization analysis. The paper lacks analysis on the model’s generalization ability. It is unclear whether cross-city generalization or evaluation on perturbed/synthetic data was performed to test robustness.\n6.\tMinor issues:\nThe paper should clarify how keys and values for attention are computed (line 181); at minimum, this should be included in the supplementary material.\nIn Equation (5), the adjacency matrix should be indexed by time, i.e., A[t].\nSeveral notations are insufficiently explained, which affects readability and clarity.", "was_revised": true, "final_justification": "Authors have address part of my concerns.", "rebuttal": "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.\n\n# Summary\n\nIn brief, we have:\n\n1. Provided details for local search operators and justified k=2 iteration limit empirically;\n2. Clarified 3% threshold follows established literature [26] with refinements for our baseline method;\n3. Demonstrated scalability with new 100-node experiments showing 65× speedup over ACO;\n4. Conducted comprehensive ablation studies on encoder layers, learning rate, and temporal embeddings;\n5. Added multi-seed stability analysis and error bars confirming experimental rigor;\n6. Tested cross-city generalization showing acceptable performance despite expected distribution shift.\n\n# Detailed Reply\n\n### 1. Local Search Design Clarification\n\n**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.\n\nWe 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.\n\n### 2. \"Sensitive\" Instances Definition\n\nThe 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.\n\n### 3. Encoder Scalability\n\n**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.\n\nThe 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):\n\n| Method          | Random      | Greedy     | ACO        | Ours       |\n| --------------- | ----------- | ---------- | ---------- | ---------- |\n| Obj mean (std)  | 26.98(1.60) | 8.30(0.51) | 7.40(0.40) | 7.43(0.40) |\n| Time | 4.75        | 172.24     | 2741.25    | 42.24      |\n\nWe 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.\n\n| Nodes                      | 10        | 20         | 50        | 100       |\n| -------------------------- | --------- | ---------- | --------- | --------- |\n| GPU Memory (GiB/batchsize) | 5212/1024 | 14326/1024 | 18748/256 | 35884/128 |\n| Train Time (s/epoch)       | 111.60    | 201.08     | 687.10    | 3463.77   |\n\n### 4. Alternative Policy Gradient Methods\n\n**Summary:** PPO tested but failed due to the critic network convergence issues. No variance/instability observed with REINFORCE, consistent with prior literature.\n\nWe 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.\n\n| Seed           | 0               | 132             | 1178            | 1234            | 203681          | 385172          | 759043          | 847592          |\n| -------------- | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- |\n| Obj mean (std) | 2.6314 (0.5786) | 2.6299 (0.5768) | 2.6289 (0.5765) | 2.6298 (0.5770) | 2.6313 (0.5771) | 2.6300 (0.5768) | 2.6290 (0.5768) | 2.6301 (0.5776) |\n| Gap mean (std) | 1.6532 (2.4259) | 1.6065 (2.4204) | 1.5678 (2.3958) | 1.6018 (2.4561) | 1.6587 (2.4427) | 1.6097 (2.4195) | 1.5659 (2.3820) | 1.6048 (2.3326) |\n\n### 5. Experimental Implementation Clarity\n\n**Summary:** Fair comparison ensured through identical conditions (hardware, datasets, batch size, data ordering) with GPU acceleration for all methods.\n\nWe 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.\n\n### 6. Reinforcement Learning Design\n\nOur 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.\n\n### 7. Robustness Analysis\n\n**Summary:** Error bars will be added. Results show high variance, aligning with the discovered Pareto distribution issue.\n\nBeijing-10 results with variance:\n\n| Method    | Obj        | Gap          |\n| --------- | ---------- | ------------ |\n| DP, TDTSP | 2.59(0.57) | \\            |\n| DP, ATSP  | 2.70(0.63) | 4.43(5.83)   |\n| SA        | 2.60(0.57) | 0.06(0.40)   |\n| ACO       | 2.95(0.68) | 14.23(10.25) |\n| Ours(Raw) | 2.63(0.58) | 1.60(2.46)   |\n| Ours(Imp) | 2.59(0.57) | 0.22(0.72)   |\n\nThe 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.\n\nWe 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. \n\n### 8. Ablation Study\n\n**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.\n\nBeyond MoE and local search ablation (Table 4), we conducted additional component analysis **examining temporal embeddings, encoder layer configurations, and learning rate sensitivity**. \n\n| Layer N    | 1            | 2           | 3           | 4           | 5           |\n| ---------- | ------------ | ----------- | ----------- | ----------- | ----------- |\n| Train time | 33.06        | 52.66       | 72.23       | 91.63       | 111.59      |\n| GPU Mem    | 2380         | 3018        | 3764        | 4478        | 5212        |\n| Obj        | 2.93 (0.64)  | 2.66 (0.58) | 2.63 (0.58) | 2.63 (0.58) | 2.63 (0.58) |\n| Gap        | 13.43 (9.02) | 2.63 (3.33) | 1.80 (2.59) | 1.63 (2.44) | 1.60 (2.46) |\n\n**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.  \n\n| lr   | 3e-3              | 1e-3            | 3e-4            | 1e-4            | 3e-5            | 1e-5            | 3e-6             |\n| ---- | ----------------- | --------------- | --------------- | --------------- | --------------- | --------------- | ---------------- |\n| Obj  | 4.2230 (0.7554)   | 2.6409 (0.5773) | 2.6305 (0.5766) | 2.6293 (0.5775) | 2.6468 (0.5800) | 2.6852 (0.5814) | 2.8778 (0.6259)  |\n| Gap  | 65.7460 (22.6098) | 2.0525 (2.8460) | 1.6316 (2.4443) | 1.5793 (2.4065) | 2.2775 (3.0714) | 3.8439 (4.2814) | 11.4468 (8.2724) |\n\n**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.\n\n| Temporal Encoder | Sinusoidal      | MLP              | Linear          |\n| ---------------- | --------------- | ---------------- | --------------- |\n| Obj              | 2.6298(0.5770)  | 2.6409 (0.5783)  | 2.6447 (0.5790) |\n| Gap              | 1.6018 (2.4561) | 2.0443 (2.8317)% | 2.1953 (2.9547) |\n\n**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. \n\nThese results, along with individual component impact assessments, will be detailed in the appendix.\n\n### 9. Generalization Analysis\n\nCross-city evaluation (Beijing-trained model on Lyon-10):\n\n| Method                                | Obj   | Gap  |\n| ------------------------------------- | ----- | ---- |\n| ACO                                   | 19.64 | 4.78 |\n| Beijing Trained only                  | 19.72 | 3.69 |\n| Beijing Trained, Lyon-tuned 10 epochs | 19.09 | 1.61 |\n| Lyon Trained only                     | 18.95 | 0.87 |\n\nPerformance 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. \n\n### 10. Minor Issues\n\n- **Attention Mechanism:** Standard multi-head attention with distinct MLPs for Q, K, V projection.\n- **Notation:** Equation (5) will index the adjacency matrix by time: A[t].\n- All notations will be sufficiently explained in the final version."}, {"review_id": "QuMstcG9o6", "reviewer": "Reviewer_Zrkp", "summary": "This paper proposes a neural model that encodes the time-dependent adjacency tensor to address asymmetry and triangle inequality violations. Beyond architectural innovations, the research highlights a critical evaluation insight: many practical TDTSP instances retain the same optimal solution despite time-dependent edge weights, exposing a fundamental flaw in current evaluation practices that rely solely on average travel time metrics.", "questions": "See strengths and weaknesses.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\nThe paper identifies critical limitations in the evaluation of existing algorithms and extends prior methodologies, with experimental results demonstrating notable advantages. Additionally, the logical structure of the paper is well-organized, facilitating clear comprehension of the research framework and conclusions.\n\nWeaknesses:\n\n1.\tThe paper proposes a time-dependent adjacency tensor encoding and time-aware decoder for TDTSP, but the abstract’s claim to address asymmetry and triangle inequality requires clarification. While the authors frame this as a novel contribution, Kwon et al. [20] already resolved these issues for static ATSP using matrix encoding. The extension to TDTSP is valuable, but the abstract must explicitly acknowledge the foundational work in [20] and highlight how the temporal dimension introduces unique innovations (e.g., tensor-based spatiotemporal integration). Without this distinction, the novelty of addressing asymmetry is diminished.\n\n2.\tThe model’s ability to \"simultaneously capture spatiotemporal structures\" needs explicit comparison with prior works (e.g., [8,16,38]). Current neural approaches for TDTSP either separate temporal and spatial processing (e.g., [16] by node, [8] by time) or focus on static ATSP ([20]). To validate the claimed advantage, the authors should: 1) Provide a comparative diagram in the Introduction/Methodology showing how their tensor encoding differs from matrix-based methods in [20] and temporal segmentation in [8,16]. 2) Quantify the mechanism through which the tensor structure models time-space interactions (e.g., via attention layers that process temporal and spatial features jointly). \n\n3.\tThis paper describes the three-stage process in line 181, but Fig. 3 is not clearly labeled. It is recommended to modify Fig. 3.\n\n4.\tThe experimental comparison is limited to classical algorithms (DP, GR, SA, ACO) and static ATSP methods (MatNet), omitting state-of-the-art TDTSP-specific neural solvers. It is recommended to add benchmarks against SOTA TDTSP methods.\n\n5.\tThe experimental validation is currently limited to test sets of up to 50 nodes, which raises concerns about the algorithm's scalability to problem sizes exceeding 50. It is recommended to include additional experimental evaluations on larger-scale instances to verify the method's performance and efficiency in real-world applications with higher node counts.", "was_revised": true, "final_justification": "The author's response has addressed most of my concerns, and I have accordingly updated my evaluation to \"borderline accept\". The authors are advised to incorporate the suggested revisions in detail when preparing the final version of the manuscript.", "rebuttal": "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.\n\n## Summary\n\nIn brief, we have:\n\n1. Acknowledged foundational work and clarified our temporal extension contribution\n2. Created a comparative analysis showing our method uniquely combines full spatiotemporal processing\n3. Added SOTA neural comparison with [38], demonstrating our superior performance\n4. Demonstrated scalability with 100-node experiments, achieving comparable ACO performance but 65× faster\n5. Improved Fig. 3 clarity with clearer stage labels and a more detailed caption.\n\n## Detailed Responses\n\n### 1. Novelty Highlight and Foundational Work Acknowledgement\n\n**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).*\n\n**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.\n\n**Proposed revisions in Abstract (lines 6-9)**: Replace *In this paper, $\\cdots$ captures the complex spatiotemporal dynamics of TDTSP* by \n\n\"*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.*\"\n\n### 2. Spatiotemporal Processing Comparison\n\n**Reviewer Concern**: *The model's ability to \"simultaneously capture spatiotemporal structures\" needs explicit comparison with prior works.*\n\n**Response**: We created a comprehensive comparative analysis showing how our method uniquely processes complete spatiotemporal information:\n\n| Method      | Input                        | Spatial Structure                    | Temporal Structure | Joint Processing                       |\n| ----------- | ---------------------------- | ------------------------------------ | ------------------ | -------------------------------------- |\n| [8]         | Coordinates + Time index     | Assumes symmetry/triangle inequality | Full horizon       | ✓ Attention processes time+coordinates |\n| [16]        | Coordinates + Chunked matrix | Departure only, missing arrival info | Per-node patterns  | ✗                                      |\n| [20] MatNet | Adjacency Matrix             | Complete spatial info                | None               | ✗                                      |\n| [38]        | Chunked matrix features      | Departure only, missing arrival info | Per-node patterns  | ✗                                      |\n| **Ours**    | **Time-dependent tensor**    | **Complete spatial info**            | **Full horizon**   | **✓ Joint tensor processing**          |\n\n**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].\n\n### 3. State-of-the-Art Neural Comparisons\n\n**Reviewer Concern**: *The experimental comparison omits state-of-the-art TDTSP-specific neural solvers.*\n\n**Response**: We added comparison with the most relevant SOTA neural TDTSP method [38]:\n\n| Method   | Objective       | Performance         |\n| -------- | --------------- | ------------------- |\n| [38]     | 3.08 (0.15)     | Baseline            |\n| **Ours** | **2.63 (0.58)** | **20% improvement** |\n\n**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.\n\n**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.\n\n**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.\n\n### 4. Scalability Validation\n\n**Reviewer Concern**: *Experimental validation is limited to 50 nodes, raising scalability concerns for real-world applications.*\n\n**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):\n\n| Method   | Objective       | Runtime (seconds) | Speedup |\n| -------- | --------------- | ----------------- | ------- |\n| Random   | 26.98 (1.60)    | 4.75              | -       |\n| Greedy   | 8.30 (0.51)     | 172.24            | -       |\n| ACO      | 7.40 (0.40)     | 2,741.25          | 1×      |\n| **Ours** | **7.43 (0.40)** | **42.24**         | **65×** |\n\nThis demonstrates our method's practical viability for real-world applications with larger node counts.\n\n### 5. Figure Clarity\n\n**Reviewer Concern**: *Figure 3's three-stage process description lacks clear labeling.*\n\n**Response**: We will enhance Figure 3 with:\n\n- **Clear stage labels** for the three-stage attention process\n- **Detailed caption** explaining each of the stage"}, {"review_id": "Yv3FWTaYXp", "reviewer": "Reviewer_mtMa", "summary": "This paper addresses the Time-Dependent Traveling Salesman Problem (TDTSP), a more realistic version of the Traveling Salesman Problem where travel times on edges are not static but change based on the departure time. The authors highlight that TDTSP violates fundamental properties of classical TSP like symmetry and triangle inequality, making it computationally challenging. Existing neural combinatorial optimization methods often fail to capture both spatial and temporal dynamics simultaneously, or their evaluation methodologies are insufficient for TDTSP.\n\nThe key insight of the paper is an empirical analysis revealing that in many practical TDTSP instances, the optimal solution (the sequence of visited nodes) remains the same regardless of time-dependent edge weights. This exposes a limitation in prior evaluation methods that rely solely on average tour duration, as such metrics cannot effectively differentiate between methods truly exploiting temporal dynamics and those merely performing well on static routing.\n\nTo overcome these challenges, the paper proposes:\n\nA novel end-to-end neural network model designed to directly encode the time-dependent adjacency tensor, thereby capturing complex spatio-temporal dynamics simultaneously. The model uses an encoder-decoder architecture with dual graph attention layers in the encoder and a time-aware decoder that incorporates sinusoidal embeddings for temporal information.\n\nAn effective inference process that enhances solution quality based on the data distribution, specifically employing a Mixture of Experts (MoE) approach (combining their neural model with a state-of-the-art Asymmetric TSP (ATSP) solver) and a local search refinement.\n\nA new evaluation methodology that accounts for instances where temporal dependencies truly alter the optimal solution, rather than just relying on average performance across all instances.\n\nThe paper presents extensive experiments on real-world datasets from cities like Beijing, Lyon, Nairobi, and London, demonstrating state-of-the-art performance in terms of average optimality gap and significant travel time reduction on instances where time-aware routing provides actual benefits. This establishes new standards for evaluating routing problems with temporal dependencies.", "questions": "Question: Could the authors provide more insights into the robustness of the proposed neural model? For example, how sensitive are the results to variations in the number of dual graph attention layers (N) or different initialization strategies?\nSuggestion: Conduct ablation studies or sensitivity analyses on key hyperparameters (e.g., varying the number of attention layers, exploring different learning rates for REINFORCE, or alternative temporal encoding methods beyond sinusoidal embeddings).\n\nQuestion: For real-world logistics, TDTSP instances can involve hundreds or thousands of nodes. The current experiments primarily focus on N=10, 20, and 50 nodes. 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)?\n\nQuestion: The paper mentions using the REINFORCE algorithm for training due to the asymmetric traveling times. REINFORCE is known for high variance. Can the authors elaborate on how they managed training stability (e.g., specific baselines, large batch sizes)? Were other policy gradient methods (e.g., Actor-Critic, PPO) considered, and if so, what were the reasons for choosing REINFORCE?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nQuality: The paper demonstrates a high level of technical quality. The proposed neural architecture for encoding time-dependent adjacency tensors is well-designed to capture spatio-temporal dynamics. The integration of sinusoidal embeddings and the inference process with Mixture of Experts (MoE) and local search show a sophisticated understanding of both neural network design and combinatorial optimization heuristics. The experimental setup is robust, comparing against various baselines (exact methods, ATSP solvers, heuristics) on real-world datasets from multiple cities, which strengthens the validity of their claims. The results indicate state-of-the-art performance, especially in instances where time-awareness is critical.\n\nClarity: The paper is generally well-structured and easy to follow. The problem statement for TDTSP is clearly defined. The proposed model's architecture (encoder-decoder, dual graph attention, time-aware decoder) is explained with good accompanying diagrams (Figure 3). The rationale behind each component, such as the three-stage process for the encoder's update function, is clearly articulated. The empirical analysis of TDTSP data distribution (Pareto distribution) and its implications for evaluation are presented concisely and are supported by Figure 2.\n\nSignificance: The paper makes several significant contributions.\nNovel Evaluation Methodology: The identification of the \"Pareto distribution\" in real-world TDTSP instances and the proposal of a new evaluation method that focuses on instances where temporal dependencies truly matter is a critical and highly significant contribution. This insight can re-shape how TDTSP algorithms are assessed in future research.\n\nEffective Model for TDTSP: The proposed neural model effectively tackles the complex spatio-temporal nature of TDTSP, which has been a challenge for existing neural methods. Its state-of-the-art performance on real-world datasets demonstrates its practical value.\n\nPractical Relevance: TDTSP has immense practical applications in logistics and transportation, where even small improvements can lead to substantial cost savings. By providing a more effective and accurately evaluated solution, the paper has a high potential for real-world impact.\n\nOriginality: The originality of the paper lies primarily in two areas:\nEmpirical Data Analysis and New Evaluation: The discovery of the Pareto distribution of savings in real-world TDTSP instances and the subsequent proposal for a refined evaluation methodology is a truly original insight. This challenges existing benchmarks and provides a more meaningful way to assess performance.\n\nDirect Encoding of Time-Dependent Tensor: While the base encoder-decoder framework and dual graph attention layers build upon prior work (e.g., MatNet, Attention Model) , the specific approach to directly encode the higher-dimensional time-dependent adjacency tensor and integrate temporal information throughout the attention mechanism is novel. The use of MoE in inference to leverage the ATSP solution for \"static\" instances is also a smart and original engineering contribution.\n\n\nWeaknesses:\n\nClarity on \"Online Refinement\": While the paper mentions \"online refinement methods\", the term \"online\" might be misleading if it refers strictly to inference-time enhancements. It should be clarified if the MoE and local search components involve any real-time adaptation or merely post-processing of the neural model's output. The current description implies they are sequential post-processing steps.\n\nLimited Deep Dive into Model Sensitivity: The paper does not thoroughly explore the sensitivity of the model to different hyperparameters (e.g., number of dual graph attention layers (N), learning rate) or variations in the sinusoidal embedding. Such analysis would provide more insights into the model's robustness.\n\nScalability for Larger Instances (my major concern): While the paper shows good scalability up to 50 nodes for Beijing, and 20 nodes for other cities, TDTSP in real-world logistics can involve hundreds or thousands of nodes. The computational time for \"Ours (Imp)\" on Beijing-50 (1549.88s) is quite high, suggesting that further work on scalability for very large instances (at least 100) is needed, or a discussion of trade-offs.\n\nTraining Complexity/Algorithm: The paper states that it cannot use the POMO training framework and instead relies on the REINFORCE algorithm. While REINFORCE is a classic choice, it is known for high variance. A brief discussion on how training stability or convergence was managed, or whether alternative lower-variance policy gradient methods were considered, would be beneficial.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n# Summary\n\nIn brief, we have:\n\n1. Conducted comprehensive ablation studies on encoder layers, learning rates, and temporal embeddings;\n2. Demonstrated scalability with 100-node experiments, achieving comparable ACO performance but 65× faster\n3. Addressed scalability concerns with flexible local search trade-offs and preprocessing strategies for practical applications.\n4. Provided multi-seed stability analysis confirming REINFORCE reliability (obj: 2.630±0.01, gap: 1.61±0.05 across 8 seeds);\n5. Clarified \"online refinement\" terminology - will remove \"online\" and specify these are post-processing steps during inference;\n\n# Detailed Reply\n\n### 1. Model Robustness and Hyperparameter Sensitivity\n\n**Reviewer Concern:** *Could the authors provide more insights into the robustness of the proposed neural model through ablation studies on key hyperparameters?*\n\n**Response:** Beyond MoE and local search ablation (Table 4), we conducted additional component analysis examining **temporal embeddings**, **encoder layer numbers**, and **learning rate** sensitivity.\n\n| Layer N    | 1            | 2           | 3           | 4           | 5           |\n| :--------- | :----------- | :---------- | :---------- | :---------- | :---------- |\n| Train time | 33.06        | 52.66       | 72.23       | 91.63       | 111.59      |\n| GPU Mem    | 2380         | 3018        | 3764        | 4478        | 5212        |\n| Obj        | 2.93 (0.64)  | 2.66 (0.58) | 2.63 (0.58) | 2.63 (0.58) | 2.63 (0.58) |\n| Gap        | 13.43 (9.02) | 2.63 (3.33) | 1.80 (2.59) | 1.63 (2.44) | 1.60 (2.46) |\n\n**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.\n\n| lr   | 3e-3              | 1e-3            | 3e-4            | 1e-4            | 3e-5            | 1e-5            | 3e-6             |\n| :--- | :---------------- | :-------------- | :-------------- | :-------------- | :-------------- | :-------------- | :--------------- |\n| Obj  | 4.2230 (0.7554)   | 2.6409 (0.5773) | 2.6305 (0.5766) | 2.6293 (0.5775) | 2.6468 (0.5800) | 2.6852 (0.5814) | 2.8778 (0.6259)  |\n| Gap  | 65.7460 (22.6098) | 2.0525 (2.8460) | 1.6316 (2.4443) | 1.5793 (2.4065) | 2.2775 (3.0714) | 3.8439 (4.2814) | 11.4468 (8.2724) |\n\n**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.\n\n| Temporal Encoder | Sinusoidal      | MLP              | Linear          |\n| :--------------- | :-------------- | :--------------- | :-------------- |\n| Obj              | 2.6298(0.5770)  | 2.6409 (0.5783)  | 2.6447 (0.5790) |\n| Gap              | 1.6018 (2.4561) | 2.0443 (2.8317)% | 2.1953 (2.9547) |\n\n**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.\n\nThese results, along with individual component impact assessments, will be detailed in the appendix.\n\n### 2. Scalability to Large-Scale Instances\n\n**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)?*\n\n**Response:** We address scalability through three complementary strategies:\n\n**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**.\n\n| Method         | Random      | Greedy     | ACO        | Ours       |\n| :------------- | :---------- | :--------- | :--------- | :--------- |\n| Obj mean (std) | 26.98(1.60) | 8.30(0.51) | 7.40(0.40) | 7.43(0.40) |\n| Time           | 4.75        | 172.24     | 2741.25    | 42.24      |\n\nWe 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.\n\n| Nodes                      | 10        | 20         | 50        | 100       |\n| :------------------------- | :-------- | :--------- | :-------- | :-------- |\n| GPU Memory (GiB/batchsize) | 5212/1024 | 14326/1024 | 18748/256 | 35884/128 |\n| Train Time (s/epoch)       | 111.60    | 201.08     | 687.10    | 3463.77   |\n\n**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:\n\n- Using 1 iteration instead of 2\n- Using fewer local search operations\n- Removing local search entirely for time-critical applications\n\n**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.\n\n### 3. Training Stability with REINFORCE\n\n**Reviewer Concern:** *How was training stability managed given REINFORCE's known high variance? What were the reasons for choosing REINFORCE?*\n\n**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.\n\n| Seed | 0               | 132             | 1178            | 1234            | 203681          | 385172          | 759043          | 847592          |\n| ---- | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- |\n| Obj  | 2.6314 (0.5786) | 2.6299 (0.5768) | 2.6289 (0.5765) | 2.6298 (0.5770) | 2.6313 (0.5771) | 2.6300 (0.5768) | 2.6290 (0.5768) | 2.6301 (0.5776) |\n| Gap  | 1.6532 (2.4259) | 1.6065 (2.4204) | 1.5678 (2.3958) | 1.6018 (2.4561) | 1.6587 (2.4427) | 1.6097 (2.4195) | 1.5659 (2.3820) | 1.6048 (2.3326) |\n\nWe 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. \n\n### 4. Clarification on \"Online Refinement\"\n\n**Reviewer Concern:** *Is the \"online refinement\" real-time adaptation or post-processing?*\n\n**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."}, {"review_id": "6U3XTclo99", "reviewer": "Reviewer_n5Wo", "summary": "The paper develops a neural combinatorial optimization method for time dependent travelling salesman problem. This extends previous works on neural combinatorial optimization methods for TSP, adding a time dependent component. The architecture extends MatNet to incorporate temporal information. The paper also shows that only a small fraction of instances from real-world distribution show substantial improvement when taking temporal information into account and propose selecting between the best solution found using only static information with that found using temporal information and performs further local search.", "questions": "1. For figure 2, what are the two lines shown and the region between the lines? Is that the confidence interval and if it is, is it one or two standard deviation?\n2. For comparison with simulated annealing, is the SA implementation also parallelized with GPU for fair comparison?\n3. For question 7 of the checklist, \"Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?\", you answered \"Answer: [No]. Justification: Error bars do not support our conclusion.\" Is it not possible to increase the test sample size so that we can trust your experimental conclusions?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The work is competently done.\n- The paper is clearly written.\n- The analysis showing where the improvements are coming from is useful. In cases where temporal information gives more than 3% gain, the method does show useful improvements.\n\nWeaknesses:\n- Novelty is not that high. The method appears to be a straightforward adaptation of MatNet to incorporate temporal information.\n- On average, results are similar to MatNet. Results are only better by selecting the better of the two methods and doing additional local search.", "was_revised": true, "final_justification": "In the rebuttal, the authors provided sample size and variance information, which would be enough to compute error bars for their results. They also committed to adding error bars to their results in the paper, which I think would be useful. The authors also clarified that the results provided is enough to infer that their method provide good improvement over the baseline on the subset of problems where temporal information is important. After rebuttal clarification, I think that the work have made useful progress. In addition, I think that time dependent TSP is a useful direction for neural combinatorial optimization, hence I have increased my rating.", "rebuttal": "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.\n\n# Summary\n\nIn brief, we have:\n\n1. Clarified Figure 2 shows max/min savings (not confidence intervals) to emphasize the Pareto distribution pattern;\n2. Confirmed fair GPU-accelerated comparison with SA using identical conditions across all baselines;\n3. Added variance reporting (mean±std) across 10,000 instances per scenario, showing high variance aligns with the Pareto distribution;\n4. Addressed novelty concerns by explaining non-trivial challenges: asymmetric temporal dimensions, dynamic continuous time handling, and 3D tensor complexity beyond MatNet's 2D foundation;\n5. 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. \n\n# Detailed Reply\n\n### 1. Clarification on Figure 2 visualization\n\n**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?*\n\n**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.\n\n### 2. Fair comparison with Simulated Annealing\n\n**Reviewer Concern:** *Is the simulated annealing implementation parallelized on a GPU for fair comparison?*\n\n**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*).\n\n### 3. Statistical significance and error reporting\n\n**Reviewer Concern:** *Given your \"No\" answer to checklist question 7 about error bars, why not increase sample size to ensure trustworthy experimental conclusions?*\n\n**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.\n\nFollowing 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.\n\n| Method       | Obj         | Gap           |\n| ------------ | ----------- | ------------- |\n| DP, TDTSP    | 2.59 (0.57) | \\             |\n| DP, ATSP     | 2.70 (0.63) | 4.43 (5.83)   |\n| MatNet, ATSP | 2.71 (0.63) | 4.66 (5.97)   |\n| GR           | 3.34 (0.74) | 19.72 (14.73) |\n| SA           | 2.60 (0.57) | 0.06 (0.40)   |\n| ACO          | 2.95 (0.68) | 14.23 (10.25) |\n| Ours(Raw)    | 2.63 (0.58) | 1.60 (2.46)   |\n| Ours(Imp)    | 2.59 (0.57) | 0.22 (0.72)   |\n\n### 4. Novelty Concerns\n\n**Reviewer Concern:** *The novelty appears limited—seems like a straightforward MatNet adaptation for temporal information.*\n\n**Response:** We believe this is a misunderstanding and would like to address the novelty concern. \n\n**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. \n\n1. **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.\n2. **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.\n3. **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.\n\nBesides technical novelties, we also want to emphasize our novelty in identifying the fundamental evaluation problem in TDTSP research.\n\n**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. \n\n### 5. Performance comparison with MatNet\n\n**Reviewer Concern:** *Results appear similar to MatNet on average, only improving when selecting the better method and adding local search.*\n\n**Response:** \nWe 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.\n\n**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.\n\n**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.\n\nFollow 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.\n\nIn 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."}]

Author rebuttal:

Meta-review: This paper addresses the Time-Dependent Traveling Salesman Problem (TDTSP).
All four reviewers unanimously agree that the paper makes significant contributions and recommend acceptance (scores: 4, 4, 4, 4). After careful check, the AC concurs with the reviewers and also recommends acceptance.

---------
The AC notes, however, that the authors may have overlooked an important family of methods for TSP: two-stage and end-to-end trainable approaches (e.g., [a], [b]). Including a brief discussion or analysis of these methods could further enhance the comprehensiveness of the work and inspire future research on two-stage approaches to time-dependent TSP.
[a] A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge-Based Systems, 2020.
[b] iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2024.
Decision: Accept (poster)