We propose mathematical models, strong relaxations, and exact and metaheuristic algorithms for  the Traveling Salesman Problem with time-dependent Service Times (TSPST), which is a generalization of the well-known NP-hard Asymmetric TSP (ATSP). As in the classical ATSP, we are given a directed complete graph, and each arc is assigned a cost representing the corresponding travel time. In the TSPST, each customer also requires a service time whose duration depends on the time at which the service starts at that customer. The TSPST calls for finding a Hamiltonian tour minimizing its total duration (i.e. the sum of the travel times and of the service times).

   In Tas, Gendreau, Jabali and Laporte (“The traveling salesman problem with time-dependent service times”, European Journal of Operational Research. 248(2), pp. 372-383, 2016), “compact' Mixed Integer Programming  (MIP) formulations, using a polynomial number of constraints, are presented. With the aim of improving the Lower Bound corresponding to the Linear Programming (LP) Relaxation of the MIP model, we propose strengthened exponential-size formulations that explicitly incorporate subtour elimination constraints and additional valid inequalities. An exact branch-and-cut algorithm and a metaheuristic are also proposed for the solution of TSPST. Extensive computational experiments on symmetric and asymmetric benchmark TSPST instances are reported, showing the effectiveness of the proposed relaxations and algorithms.