Séance TA11 - Heuristiques II / Heuristics II
Jour mardi, le 05 mai 2009 Salle Demers Beaulne Président Bernard Gendron
Présentations
|
10h30- 10h55 |
Applying Genetic Algorithm and Simulated Annealing to Plan UMTS Networks |
|
Shangyun Liu, Carleton University, Department of Systems and Computer Engineering, 1125 Colonel By Drive, Ottawa, Ontario, Canada, K1S 5B6 Marc St-Hilaire, Carleton University, Department of System and Computer Engineering, 1125 Colonel By Dr, Ottawa, Ontario, Canada, K1S 5B6 The global planning problem of Universal Mobile Telecommunication System (UMTS) networks is NP-hard. As a result, approximate algorithms are used to find good solutions within a reasonable amount of computation time. In this presentation, we will outline how the genetic algorithm and the simulated annealing can be applied to solve this problem. Algorithmic details and simulations results are presented. |
|
10h55- 11h20 |
A Multistart Variable Neighborhood Search for Multiplierless Filter Design |
|
Marc Joliveau, Université de Montréal, CIRRELT, C.P. 6128, Succ. Centre-ville, Montreal, Quebec, Canada , H3T 1J4 Michel Gendreau, Université de Montréal, Informatique et recherche opérationnelle, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7 Francois Gagnon, École de Technologies Supérieures, LACIME, C.P. 6128, Succ. Centre-ville, Montréal, Quebec, Canada , H3C 1K3 Digital filters are essential building blocks of communication systems, used for mixer image rejection, pulse shaping, modulation and demodulation. Nowadays filters are designed according to known architectures easy to understand but which don't demonstrate any properties assuring their quality, particularly about filters size. This presentation introduces a metaheuristic to accurately design filters without referring to any fixed structure. |
|
11h20- 11h45 |
A Variable Neighbourhood Search for the Multi-Echelon Location-Distribution Problem |
|
Bernard Gendron, Université de Montréal, Informatique et de recherche opérationnelle/CIRRELT, Montréal, Québec, Canada Paul-Virak Khuong, Université de Montréal, Informatique et de recherche opérationnelle/CIRRELT Frédéric Semet, École centrale de Lille, LAGIS, France We consider a two-echelon location-distribution problem. In order to solve realistic medium-sized instances in reasonable time (less than 2h), we developed a variable-neighbourhood-search--based method. We describe the method and present numerical results on a practical instance in which the heuristic significantly outperforms exact formulations. |
|
11h45- 12h10 |
Large Neighborhood Search for the Airline Recovery Problem |
|
Jean-François Cordeau, GERAD, HEC Montréal, Chaire de recherche du Canada en logistique et en transport/CIRRELT, 3000 Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7 Serge Bisaillon, Université de Montréal, CIRRELT, Canada Gilbert Laporte, GERAD, HEC Montréal, Chaire de recherche du Canada en distributique/GERAD/CIRRELT, 3000 Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7 Federico Pasin, HEC Montréal, Production and Operations Management, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7 The operations of a commercial passenger airline are often disrupted by unforeseen events such as mechanical failures or bad weather. When such events occur, airlines must react quickly to recover from the disruptions and minimize their impact. The talk will introduce a large neighborhood search heuristic for an airline recovery problem combining aircraft routing and passenger assignment. This work was initiated in the context of the 2009 ROADEF Challenge in which our team won the first prize. |