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.