Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport

TITRE : Online Traveling Salesman Problems with Flexible Services

CONFÉRENCIER : Patrick Jaillet, Massachusetts Institute of Technology, Cambridge, Massachusetts

DATE et ENDROIT : 5 novembre, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l'Université de Montréal

RESPONSABLE : Gilbert Laporte (514-343-6143)

RÉSUMÉ : The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem. We are concerned here with online versions of a generalization of the TSP on metric spaces where the server doesn't have to accept all requests. Associated with each request (to visit a point in the metric space) is a penalty (incurred if the request is rejected). Requests are revealed over time to a server, initially at a given origin, who must decide which requests to serve in order to minimize the time to serve all accepted requests plus the sum of the penalties associated with the rejected requests. In the first online version of this problem, called the basic version, we assume that the server's decision to accept or reject a request can be made any time after its release date. In the second online version of this problem, called the real-time version, we assume that the server's decision to accept or reject a request must be made exactly at its release date. In this talk, we provide an optimal online algorithm for the basic version of the problem in a general metric space, improving all known results to date. We then consider the real-time version of the problem. We first provide an optimal polynomial time online algorithm on the non-negative real line. We also consider the case of a general metric space and show that there can't be any finite competitive online algorithm. We finally describe an asymptotically optimal online algorithm for this general case.