Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
thank you for your nice answer! I have a further question: In the time dependent tsp, we usually assume the cost C_{i,j,t} is a given value, right? Usually C_{i,j,t} can be expressed as a step function w.r.t t. However, if we reduce my problem to the TDTSP, then C_{i,j,t} will depend not only on $t$, but all other nodes that are visited before node $j$. Specifically, in permutation (dummy node, x_1, x_2, ... x_n, dummy node), C_{i,j,t}=d(x_j, {dummy node, x_1, ...x_i}) * p^{i+1} if t=i, and 0 therwise. In this case, I do not see an easy way of using TDTSP to solve my problem.
@ Tony Huynh. Thank you for your reply! From my understanding, the proof you provide is still a greedy proof, right? But I am specifically interested in proving the optimality of the local search algorithm. Do you have any idea of this?
