# Cuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman Problem

arXiv: https://arxiv.org/abs/1805.01415 · HTML: https://mlsanity.com/paper/1805.01415/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2018.

## Built on by (most cited first, 11 of 11)

- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch](https://mlsanity.com/paper/2206.06965/) (2022)
- [Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation](https://mlsanity.com/paper/2310.14161/) (2023)
- [Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends](https://mlsanity.com/paper/2111.06257/) (2021)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [Neural Network Branch-and-Bound for Neural Network Verification](https://mlsanity.com/paper/2107.12855/) (2021)
- [Combinatorial Optimization with Automated Graph Neural Networks](https://mlsanity.com/paper/2406.02872/) (2024)
- [ML4CO: Is GCNN All You Need? Graph Convolutional Neural Networks Produce Strong Baselines For Combinatorial Optimization Problems, If Tuned and Trained Properly, on Appropriate Data](https://mlsanity.com/paper/2112.12251/) (2021)
- [Learning to Branch in Combinatorial Optimization with Graph Pointer Networks](https://mlsanity.com/paper/2307.01434/) (2023)
- [Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality](https://mlsanity.com/paper/2512.09355/) (2025)

## Abstract (arXiv)

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.