4 Presentations

• 
  03:30 PM - 03:55 PM

  Improving Benders decomposition method for the traveling salesman problem with generalized latency

  • Mohsen Dastpak, presenter, Ecole de technologie superieur
  • Fausto Errico, École de technologie supérieure

  The Traveling Salesman Problem with Generalized Latency finds application in the context of intelligent transportation systems and telecommunications, among others. We develop a solution method based on an improved Benders Decomposition (BD) scheme. Preliminary results show the effectiveness of the proposed method with respect to the classical BD.

• 
  03:55 PM - 04:20 PM

  Approximate solution methods for the vehicle routing problem with stochastic and correlated travel times

  • Borzou Rostami, presenter, Polytechnique Montreal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Fausto Errico, École de technologie supérieure
  • Andrea Lodi, Polytechnique Montreal

  In this talk, we propose approximation solution methods for the capacitated vehicle routing problem (CVRP) with uncertain and statistically correlated travel times (CVRP-SCT). The CVRP-SCT is a convex binary quadratic program with exponentially many variables and seeks vehicle routes that their observed travel times are not excessively dispersed with respect to their expected value. We provide new insights into the problem using the eigenvalue decomposition and approximate the problem based on the principal component analysis (PCA). We discuss the quality of the approximate solutions by analyzing the worst case optimality gap. Moreover, we also construct a linear approximation that exploits the convexity of the problem. To solve the approximate models to optimality, we develop exact branch-price-and-cut algorithms based on a labeling algorithm for generating feasible vehicle routes. Our experimental results on a rich collection of instances show the efficiently of the proposed approximate algorithms in finding good quality feasible solutions. In particular, the PCA-based algorithm provides solutions that are optimal for all instances with known optimal values.

• 
  04:20 PM - 04:45 PM

  Vehicle routing with arrival time diversification

  • Maaike Hoogeboom, presenter, Vrije Universiteit Amsterdam

  One way to generate unpredictable routes is to vary the arrival time of each customer over successive visits. Inspired by a real-life case in cash distribution, we present an efficient solution approach to generate sufficiently unpredictable routes by varying the arrival time at a customer, while minimizing transportation costs.

• 
  04:45 PM - 05:10 PM

  A computational study on methods to increase the offer of time windows in time window assignment problems

  • Jean-François Côté, presenter, Université Laval
  • Jacques Renaud, Université Laval, CIRRELT
  • Ranya El Byaz, Université Laval

  This work addresses the challenge of establishing delivery schedules for consumers who buy goods online or who buy furniture and appliances in a store. Home delivery companies try to increase the satisfaction of their customers by offering them a delivery schedule that includes several choices of time windows while limiting transportation costs. This work presents several methods for building delivery schedules. Extensive computational experiments compare the methods in terms of transportation costs, number of served customers and number of offered time windows. Our results show that some methods used in the literature might be very costly and that there exists methods that increase the number of choices while limiting the transportation costs.