Groupe d’études et de recherche en analyse des décisions

The traveling salesman problem with time-dependent service times

Duygu Tas HEC Montréal, Canada

We consider a version of the classical Traveling Salesman Problem (TSP) where service times are time-dependent. More specifically, the duration required to serve any customer is not fixed in our setting; it is further defined as a function of the moment to begin service at that location. The objective is to minimize the total route time, which consists of the total time spent for traveling and the total time spent for service at customer locations. The proposed model can handle both discrete service times, and linear and quadratic functions of arrival times that provide corresponding service times at customers. In this study, time-dependent service times are incorporated into the model not only through objective function (e.g., problems with time-dependent travel times) but also through constraints. We describe the basic properties of the service time function, followed by computations of valid upper and lower bounds. We separately employ a number of subtour elimination constraints to measure their effect on the performance of our model. Numerical results obtained by implementing different service time functions on several test instances are presented.

Note: Duygu Tas is a Postdoctoral Fellow registered at HEC Montréal, working under the supervision of Michel Gendreau, Ola Jabali and Gilbert Laporte. She has received her Ph.D. degree at TU/e, Eindhoven University of Technology, The Netherlands. Her office is located at CIRRELT.