The Traveling Salesman Problem with time-dependent Service Times (TSP-TS) is a variant of the well-known Asymmetric TSP (ATSP). In addition to the classical constraints of ATSP, in TSP-TS each customer requires a service time, whose duration depends on the time at which the service starts at that customer. The TSP-TS calls for finding a Hamiltonian tour (i.e. a tour visiting each customer exactly once) such that the total duration of the tour (i.e. the sum of the travel times and of the service times) is minimized.
Tas, Gendreau, Jabali and Laporte, in “The traveling salesman problem with time-dependent service times”, European Journal of Operational Research (2016), proposed Mixed Integer Programming (MIP) formulations with a polynomial number of constraints. In this talk, we propose and solve exponential-size formulations that explicitly incorporate subtour elimination constraints. Additional valid inequalities, strengthening those presented in Tas et al. (2016), and an exact branch-and-cut algorithm are also proposed. Extensive computational experiments on benchmark TSP-TS instances with small, medium and large service times are reported.
| Subject : | : | Abstracts |
| Topics | : | Exact Methods |
| Topics | : | TSP Variants |
| PDF version | : |  PDF version |
