Canada Research Chair in Distribution Management | Canada Research Chair in Logistics and Transportation | GERAD Seminar

Title: The Traveling Salesman Problem with Time-Dependent Service Times

Speaker: TAS, Duygu (HEC Montréal, Canada)

Abstract:
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.