Calendrier

Séminaire : The Traveling Salesman Problem with Time-Dependent Service Times

Séminaire : The Traveling Salesman Problem with Time-Dependent Service Times

Séminaire Chaire de recherche du Canada en distributique | GERAD

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

Conférencier : TAS, Duygu (HEC Montréal, Canada)

Résumé :
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.

Entrée gratuite

Bienvenus à tous

Date

Mercredi 11 juin 2014
Débute à 10h30

Prix

gratuit

Contact

514-340-6053 6991

Lieu

Université de Montréal - Pavillon André-Aisenstadt
2920, chemin de la Tour
Montréal
QC
Canada
H3T 1N8
514 343-6111
4488

Catégories