HEC Montréal, Canada, 2 - 4 mai 2011

Journées de l'optimisation 2011

HEC Montréal, Canada, 2 — 4 mai 2011

Horaire Auteurs Mon horaire

WA2 Tournées d'arcs et de véhicules / Vehicle and Arc Routing

4 mai 2011 10h30 – 12h10

Salle: Béton Grilli

Présidée par Guy Desaulniers

4 présentations

  • 10h30 - 10h55

    Constructive Heuristic for a Synchronized Arc Routing Problem (SyARP)

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

    We propose a constructive heuristic for the SyARP. It consists of determining a set of routes for snow plowing operations. All streets, some of which have multiple lanes, must be plowed by using synchronized vehicles, and the objective is to minimize the time of the longest route.

  • 10h55 - 11h20

    A Branch-Price-and-Cut Algorithm for the Min-Max k-Vehicles Windy Rural Postman Problem

    • Guy Desaulniers, prés., GERAD - Polytechnique Montréal
    • François Lessard, GERAD
    • Angel Corberan, Universidad de Valencia
    • Enrique Benavent, Universidad de Valencia
    • Isaac Plana, Universidad de Valencia
    • José M. Sanchis, Universidad Politécnica de València

    We present a branch-and-price algorithm for this arc routing problem that relies on ng-paths, three families of cutting planes and a dichotomic lower bounding procedure.

  • 11h20 - 11h45

    Improved Lower Bounds for the Capacitated Arc Routing Problem

    • Enrico Bartolini, prés., HEC Montréal
    • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
    • Gilbert Laporte, HEC Montréal

    We present a cut-and-column generation bounding method for the CARP that is based on a set partitioning formulation, and uses a new dynamic programming method for generating elementary CARP routes. Extensive computational results show that the new bounds are tight, and permit to solve several open instances from the literature.

  • 11h45 - 12h10

    A General Variable Neighborhood Search for the One-Commodity Pickup-and-Delivery Travelling Salesman Problem

    • Nenad Mladenovic, prés., Mathematical Institute SANU
    • Said Hanafi, Universite de Valenciennes et du Hainaut-Cambrésis
    • Aleksandar Ilic, University of Nis, Serbia
    • Dragan Urosevic, Mathematical Institute SANU

    We present Variable Neighborhood Search (VNS) approach for the one-commodity pickup-and-delivery traveling salesman problem. We adapt a collection of neighborhood structures usually used for solving classical TSP and efficiently update the data structures for feasibility checking in these neighborhoods. We improved all best-known objective values for the benchmark instances.