2016 Optimization Days

HEC Montréal, Québec, Canada, 2 — 4 May 2016

Schedule Authors My Schedule

TA10 Vehicle Routing III

May 3, 2016 10:30 AM – 12:10 PM

Location: TD Assurance Meloche Monnex

Chaired by Anna Franceschetti

4 Presentations

  • 10:30 AM - 10:55 AM

    A two-phase Pareto local search heuristic for the bi-objective pollution-routing problem

    • Luciano Costa, presenter, Polytechnique Montréal / GERAD
    • Thibaut Lust, Université Pierre et Marie Curie (Paris VI)
    • Raphael Kramer, Università degli studi di Modena e Reggio Emilia (UNIMORE - Italy)
    • Anand Subramanian, Universidade Federal da Paraíba (UFPB - Brazil)

    The bi-objective Pollution-Routing Problem deals with two conflicting objectives: CO2 emissions and labor costs. We propose a Two-Phase Pareto Local Search algorithm for generating a set of efficient solutions. Computational experiments show that the proposed procedure leads to better results when compared to those obtained by state-of-art multi-objective techniques.

  • 10:55 AM - 11:20 AM

    ALNS to solve the snow plowing problem

    • Olivier Quirion-Blais, presenter, Polytechnique Montréal
    • André Langevin, Polytechnique Montréal
    • Martin Trépanier, Polytechnique Montréal, CIRRELT
    • Olivier Péton, École des Mines de Nantes
    • Fabien Lehuédé, École des Mines de Nantes

    We present the snow plowing problem as a Min-Max k-rural postmen problem with specific constraints. Then we explain how we process data from a GIS to an analytical network. Finally we detail the ALNS metaheuristic that we developed to tackle the problem and we show some results.

  • 11:20 AM - 11:45 AM

    An exact algorithm for the departure times and speed optimization problem

    • Anna Franceschetti, presenter, HEC Montréal

    In this work we provide an efficient algorithm for solving the Departure Times and Speed Optimization Problem, that is, the problem of optimizing the departure times and travel speeds of a single vehicle visiting and serving a finite number of customer’s locations in a fixed sequence. We consider the present of traffic congestion limiting the vehicle speed during peak hours. The objective is to minimize the sum of labor and CO2e emissions costs, while satisfying hard time
    windows at the customer locations. We also provide insights on the impact of the driver wage policy and time windows on labor and emission costs.

  • 11:45 AM - 12:10 PM

    New recourse policies for the vehicle routing problem with stochastic demands

    • Majid Salavati, presenter, Université de Montréal
    • Michel Gendreau, Polytechnique Montréal
    • Ola Jabali, HEC Montréal
    • Walter Rei, Université du Québec à Montréal

    In the Vehicle Routing Problem with Stochastic Demands under the classical recourse policy, one executes the route until it fails due to an excessive demand, and then prescribes back-forth trips to recover routing feasibility. This policy entails costly trips to depot and consequently split deliveries. In this talk, we present new static recourse policies that prescribe preventive returns based on several operational criteria.