4 Presentations

• 
  10:45 AM - 11:10 AM

  Crowd-shipping with stochastic crowd drivers

  • Fabian Torres, presenter, Polytechnique Montreal
  • Michel Gendreau, Polytechnique Montréal
  • Walter Rei, Université du Québec à Montréal

  Crowd-shipping can provide the capacity needed to meet the growing demand of home deliveries in a cost-effective way. We consider a setting where delivery requests are fulfilled from a single depot by a fleet of Professional Vehicles (PV) and a pool of Stochastic Crowd Drivers (CD).

  Keywords: Crowd-shipping, Crowdsourcing, Stochastic programming, Vehicle Routing Problem, City logistics, Crowd-Drivers.
• 
  11:10 AM - 11:35 AM

  Compact routes for postal-VRPTW

  • Alexis Bretin, presenter, Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Louis-Martin Rousseau, Polytechnique Montréal

  We will present a Branch-and-Price-Based Large Neighborhood Search algorithm to solve the Vehicle Routing Problem with Time Windows that arises in postal services (parcel deliveries). Classic constraints and specific ones, such as minimum feeding curves of the sorting machines, have to be handled, as well as preferences for compact routes. Constraint Programming is used for pre-processing purpose.
• 
  11:35 AM - 12:00 PM

  Relaxations for pickup and delivery problems

  • Luciano Costa, presenter, Polytechnique Montréal / GERAD
  • Claudio Contardo, ESG UQÀM / GERAD
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  We propose a series of relaxation mechanisms aiming at reducing the computational burden arising from the handling of pairing and precedence constraints in pickup and delivery problems when solved by column generation. The relaxations are both at the master and subproblem levels. We provide computational evidence of the efficiency of the proposed mechanism.

  Keywords: Column generation; relaxation; pickup and delivery problem.
• 
  12:00 PM - 12:25 PM

  The time-dependent shortest path and vehicle routing problem

  • Rabie Jaballah, presenter, Université Laval
  • Marjolein Veenstra, University of Groningen
  • Leandro C. Coelho, Université Laval
  • Jacques Renaud, Université Laval, CIRRELT

  Many of today’s logistics systems are based on variants of the well-known vehicle routing problem (VRP). In VRP one needs to answer a simple question: in which sequence should we visit a set of clients in order to minimize mainly the total distance. Advances in com- munications and real-time data acquisition technologies have made it possible to collect a huge amount of data on vehicles such as their driving speed and CO2 emission. This has led to what is known as the time-dependent VRP, in which the time (or cost) to move from one customer to another change depending on the starting time. In this work we integrate the time-dependent shortest path within the time-dependent VRP to create a more general and realistic problem called the time-dependent shortest path and vehicle routing problem (TDSPVRP). TDSPVRP effectively determines the path to take when visiting customers by considering both the real underlying street map and the real travel time to each them. We provide a mathematical formulation for the problem and also develop valid inequalities to strengthen this formulation which significantly improve the lower bounds. Given the size and difficulty of the problem, a heuristic based on the local search and simulated annealing is proposed. Finally, we provide a sensitivity analysis that highlights the importance of in- corporating traffic in routing models and how ignoring traffic data can impose substantial delays.

  Keywords: Time Dependent Shortest Path, Time Dependent Vehicle Routing Problem, Traffic and congestion, City logistics, Heuristic, Simulated annealing