Exact algorithms for the traveling salesman problem with time-dependent service times
Valentina Cacchiani  1, *@  , Carlos Contreras Bolton  1@  , Paolo Toth  1@  
1 : DEI, University of Bologna
* : Corresponding author

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.

Online user: 1 RSS Feed