I was thinking about exact methods for solving the Time Dependent TSP (TDTSP). Clearly, it is at least as complex as TSP because it extends TSP, but why is it for exact approaches that difficult to solve instances with a greater number of nodes? Do the bounding steps, lower or upper bound, etc., not work the same?

  • $\begingroup$ It depends on how you define "complex." From a computational standpoint, both are equivalent (NP-hard). $\endgroup$
    – Kuifje
    Sep 7, 2021 at 9:12
  • $\begingroup$ Could you add references to the exact approaches you are referring to? $\endgroup$
    – fontanf
    Sep 7, 2021 at 9:25
  • $\begingroup$ Does triangle inequality hold true for TDTSP? $\endgroup$ Sep 7, 2021 at 10:32
  • $\begingroup$ It is right that they are both NP-hard, but they do not perform equally on computational experiments. E.g. ILP approaches like (sciencedirect.com/science/article/pii/…). The triangle equality holds true for most TDTSP benchmarks. $\endgroup$
    – maxmitz
    Sep 7, 2021 at 11:16
  • 1
    $\begingroup$ One of the culprits may be that the LP relaxation of TD-TSP is very weak. This may be due to the use of big-M variables in TD-TSP. $\endgroup$
    – batwing
    Sep 8, 2021 at 14:38


Your Answer

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