4
$\begingroup$

A constructive heuristic is a type of heuristic method which starts with an empty solution and repeatedly extends the current solution until a complete solution is obtained. (Wikipedia)

Which constructive heuristics exist for the time-dependent TSP? Time dependent in the sense that the travel time depends on the departure time. I already asked about the time-independent TSP (Which constructive heuristics exist for the TSP?). I think the nearest neighbor and the "fit" heuristics like first fit also work for a time-dependent TSP.

  • Is it possible to apply the cheapest insertion, christofides algorithm, and the Clarke-Wright algorithm for a time-dependent TSP? Right now, I think that the implementation is difficult for them because the graph is dependent on time and, for example, an insertion changes also the result of other paths.
  • Do other constructive heuristics exist for the time-dependent TSP?
$\endgroup$
3
  • 1
    $\begingroup$ There are 2 variants of the tdTSP: (1) where the travel time from i to j, depends on the departure time from i. (2) the travel time from i to j depends on the position of i in the TSP sequence. Case (2) should probably have been called the position-dependent TSP, but historically it's been tdTSP. Which of the 2 versions are you asking? Also, what effort did you do to find the solution to this question already? Did you look into any TDTSP papers? $\endgroup$ Jun 10, 2021 at 16:49
  • $\begingroup$ TD-TSP where the travel time depends on the departure time. I added it to the description. I already read some paper about TD-TSPs but did not find anything but the nearest neighbor as constructive heuristic. $\endgroup$
    – maxmitz
    Jun 11, 2021 at 7:54
  • $\begingroup$ Is it just out of curiosity or do you have a real application for which you need an algorithm? I'm not sure that this variant has been studied in depth in the literature. It is certainly possible to find a way to adapt these algorithms, but their computational complexity may increase and the approximation ratios might be lost compared to their TSP counterparts. There seem to be some papers about the Time-Dependent Orienteering Problem, some of them detailing efficient structures to handle time-dependency, e.g. doi.org/10.1016/j.ejor.2013.11.038 It might be a source of inspiration $\endgroup$
    – fontanf
    Jun 18, 2021 at 21:37

1 Answer 1

4
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.