Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

TD3 Tournées sur arcs / Arc Routing

8 mai 2012 15h30 – 17h10

Salle: Metro inc.

Présidée par André Langevin

4 présentations

  • 15h30 - 15h55

    The Synchronized Arc and Node Routing Problem

    • María Angélica Salazar-Aguilar, prés., HEC Montréal
    • André Langevin, Polytechnique Montréal
    • Gilbert Laporte, HEC Montréal

    The synchronized arc and node routing problem consists of finding a set of arc routes
    for several capacitated vehicles and a node route for a tank vehicle such that the duration of the longest route is minimized. Additionally, all routes must be synchronized in some specific nodes called refilling points.

  • 15h55 - 16h20

    Rural Postman Problem with Time Windows: Models and Solution Methods

    • Ingrid Marcela Monroy Licht, prés., École Polytechnique de Montréal
    • André Langevin, Polytechnique Montréal
    • Ciro Alberto Amaya, Universidad de Los Andes

    We present the rural postman problem with time windows, apparently not studied in the literature. Some mathematical models and heuristic methods were implemented to solve the problem. We tested the models for the directed and undirected case and a comparison among models is showed.

  • 16h20 - 16h45

    Demand Dependent Periodic Arc Routing Problem

    • Juan-Pablo Riquelme-Rodriguez, prés., École Polytechnique de Montréal
    • Michel Gamache, GERAD - Polytechnique Montréal
    • André Langevin, Polytechnique Montréal

    This problem combines inventory and arc routing decisions. One of the main applications is the water spreading on haul roads in open pit mines for dust suppression. A certain level of water prevents the formation of dust clouds. The objective is to find a set of routes in order to reduce the time the water level in each segment is below this required amount. The time of the day, evaporation rate and the amount of water used on the last visit influence the frequency of services and the time between them for each one of the road segments. A mathematical model is presented and solution approaches are discussed.

  • 16h45 - 17h10

    A Comparison of Three Formulations for Close Enough Arc Routing Problem

    • Ha Minh Hoang, prés., École Polytechnique de Montréal

    The Close Enough Arc Routing problem (CEARP) has an interesting real-life application on routing for meter reading. In this talk, we compare theoretically and computationally three formulations based on the efficiency of exact branch-and-cut algorithms developed from them. Computational results on the instances based on three types of graphs: directed, undirected and mixed are presented.