Séminaire conjoint CRT-Chaire de recherche du Canada en distributique

TITRE : Two-Phase VLSN Search Algorithms for the Single Source Transportation Problem and the Covering Assignment Problem

CONFÉRENCIER : Temel Öncan, Galatasaray University, Istanbul, et Chaire de recherche du Canada en distributique

DATE et ENDROIT : 7 décembre 2005, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Gilbert Laporte (343-6143)

RÉSUMÉ : A very large-scale neighborhood (VLSN) search algorithm is a local search algorithm specially designed to search a very-large size neighborhood (sometimes exponential in terms of input size) without performing explicit enumeration of the neighborhood. We consider the single source transportation problem and a closely related problem: the covering assignment problem. We identify neighborhoods of exponential size that can be searched in polynomial time for both of these problems. Using these neighborhoods two-phase VLSN search algorithms are developed and experimental results are reported. In Phase I of our algorithms we address the feasibility problem. Then, the optimality problem is considered in Phase II. According to our extensive computational experiments, we can say that our approach is quite efficient; it is quite successful for the solution of very large scale instances.