Schedule | Author Index

Session WB2 - Tournées de véhicules 6 / Vehicle Routing 6

Wednesday, May 9, 2012

Location: KPMG

Chaired by André Langevin

Presentations

11:00 -
11:25
Problematic Encountered in a Real Case Study on Winter Maintenance
  Olivier Quirion-Blais, presenter, École Polytechnique de Montréal, olivierqb@gmail.com
Martin Trépanier, École Polytechnique de Montréal, mtrepanier@polymtl.ca
André Langevin, Polytechnique Montréal, andre.langevin@polymtl.ca
 

Vehicle routing for winter maintenance causes many problems due to the specificity of the requirements and the diversity related to the location and the weather condition. We discuss some of the issues encountered within a case study of a small city in the province of Quebec. The issues discussed are related to the inadequacy of the available algorithms, as well as the technical difficulties of performing theoretical tour on the field.

11:25 -
11:50
Hybrid Metaheuristics for Routing and Scheduling problems
  Jamal Ouenniche, University of Edinburgh, jamal.ouenniche@ed.ac.uk
Prasanna Kumar Ramaswamy, presenter, University of Edinburgh, p.ramaswamy@sms.ed.ac.uk
 

In the Management Science/Operational Research (MS/OR) area, routing and scheduling problems have been at the origin of the design of many optimal and heuristic solution frameworks such as branch-and-bound algorithms, branch-and-cut algorithms, and metaheuristics. In this study we develop a new hybrid metaheuristic framework and test both its effectiveness and its efficiency in solving complex combinatorial optimization problems such as routing and scheduling problems. Hybridising metaheuristics has proven to be a promising area of research because of its ability to exploit the strengths of various methods embedded within the hybrid design. The design of hybrid metaheuristics is not new to MS/OR researchers; however, most designs tend to combine different search strategies of “pure” metaheuristics such as simulated annealing and tabu search. In this research, we explore different ways of designing hybrid metaheuristics. The main question we intend to answer could be summarized as follows: Is it possible to use the intelligence of exact algorithms to guide the search? We adapt our novel ideas to the case of the well known travelling salesman problem and use our algorithm to solve the TSPLIB test instances. Computational results confirm the attractiveness of this type of hybrid design in addressing Routing and Scheduling problems.

Back