You could use any existing constructive heuristic to compute a TDTSP solution.
Let $T_{ij}(t)$ be the travel time on arc $(i,j)$ when departing location $i$ at time $t$. A common premises is that it is never beneficial to depart late. So for any given pair of time points $t_1$, $t_2$, with $t_1\leq t_2$ it holds that $t_1+T_{ij}(t_1)\leq t_2+T_{ij}(t_2)$.
The simplest constructive heuristic would be the nearest neighbor heuristic.This heuristic starts at the depot ($i=0$) at time $t_0=0$. At each iteration of the algorithm, you extend the tour with a new unvisited vertex $j$, and you record the arrival time $t_j$. When extending the tour, you always select a new unvisited vertex $j$ that minimizes $T_{ij}(t_i)$, where $i$ is the last visited vertex in the partial tour. The heuristic terminates when all locations are visited.
Variations of this nearest neighbor heuristic can be conceived as well, e.g. by occasionally randomly selecting the second nearest location as opposed to the nearest, or by computing a 'regret' metric for not selecting a particular vertex, or by explicitly accounting for the return segment to the depot. Any of these variants are easy to implement.
The second category of constructive heuristics require you to modify the tour. Start for instance with the trivial tour $[0,i,0]$, where vertex $i$ is a randomly selected vertex. Next you take an unvisited vertex say $j$, and insert it into the tour. The standard strategy is to insert the vertex into the location that increases the duration of the tour the least. You repeat this procedure until all vertices are in the tour. For the traditional TSP (without time), the cost of inserting a vertex is easy to derive. To insert a vertex $j$ between two vertices $i$ and $k$, the cost difference (delta) equals $t_{ij}+t_{jk}-t_{ik}$. Clearly, for the time dependent variant you would have to do a little more work, because by inserting a vertex you potentially alter the departure times of the subsequent vertices in the tour, which in turn changes the travel times. So in the worst case, you would have to recompute the travel times for the portion of the tour that succeeds the inserted vertex. Naturally this is more costly.
All other heuristics that modify the tour, e.g. 2-opt/Clarke-Wright etc, suffer from this problem. With any heuristic, the faster you could evaluate a 'move', the better it is.
Finally, you could also remove the time-dependency, treat the problem as if it were a traditional TSP, and solve with any existing constructive TSP heuristic. To remove the time-dependency, you could replace $T_{ij}(t)$ by $t_{ij}=average(T_{ij}(t))$, or $t_{ij}=max_t(T_{ij}(t))$. Once you obtained a complete tour containing all the vertices, you would evaluate its true cost using the actual time-dependent travel times.
