We consider the time-dependent traveling salesman problem (TDTSP), a
generalization of the asymmetric traveling salesman problem (ATSP) to
incorporate time-dependent cost functions. In our model, the costs of an arc
can change arbitrarily over time (and do not only dependent on the position in
the tour). The TDTSP turns out to be structurally more difficult than the TSP.
We prove it is NP-hard and APX-hard even if a generalized version of the
triangle inequality is satisfied. In particular, we show that even the
computation of one-trees becomes intractable in the case of time-dependent
costs. We derive two IP formulations of the TDTSP based on time-expansion and
propose different pricing algorithms to handle the significantly in- creased
problem size. We introduce multiple families of cutting planes for the TDTSP as
well as different LP-based primal heuristics, a propaga- tion method and a
branching rule. We conduct computational experiments to evaluate the
effectiveness of our approaches on randomly generated in- stances. We are able
to decrease the optimality gap remaining after one hour of computations to
about six percent, compared to a gap of more than forty percent obtained by an
off-the-shelf IP solver. Finally, we carry out a first attempt to learn strong
branching decisions for the TDTSP. At the current state, this method does not
improve the running times.

本研究探讨了时间依赖旅行商问题（TDTSP），证明了其为 NP-hard 和 APX-hard，并针对该问题提出了两个 IP 公式以及不同的定价算法、割平面和基于 LP 的凸先发方法、传播方法和分支规则。同时，开展了计算实验以评估这些方法的有效性，并首次尝试学习 TDTSP 的强分支决策，但该方法目前并未改善运行时间。