4 Presentations

• 
  03:30 PM - 03:55 PM

  A Branch-Cut-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands

  • Charles Gauvin, presenter, Polytechnique Montréal

  This talk presents a state-of-the-art branch-cut-and-price (BCP) algorithm for the vehicle routing problem with stochastic demands (VRPSD). We adapt the model of Christiansen and Lysgaard (Christiansen, H. C. and Lysgaard, J. (2007). A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research Letters, 37, 773–781.) and formulate the VRPSD as a set partitioning model with additional constraints. Feasible routes are generated using a dynamic programming algorithm executed over a state-space graph. Our method combines 2-cycle elimination with ng-routes. In addition, our pricing problem is significantly accelerated by the introduction of a new aggregate dominance rule. To speed up the generation of negative reduced costs columns, we use a tabu search heuristic and a bidirectional labelling algorithm. We also add capacity constraints and subset-row inequalities dynamically in order to strengthen the linear relaxation of the master problem. To derive integer solutions, we dynamically choose between 2 types of branching methods. As extensive tests illustrate, our algorithm is very competitive with the one of Christiansen and Lysgaard. We manage to solve 20 additional instances and we considerably improve the computing times for instances already closed. Only 2 instances out of the 40 considered remain unsolved.

• 
  03:55 PM - 04:20 PM

  A Branch-and-Price Approach for a Stochastic Vehicle Routing Problem with Correlated Demands.

  • Iman Dayarian, presenter, Université de Montréal
  • Teodor Gabriel Crainic, Université du Québec à Montréal
  • Michel Gendreau, Polytechnique Montréal
  • Walter Rei, Université du Québec à Montréal

  Many applications of the Vehicle Routing Problem (VRP) with correlated stochastic demands (supplies) exist in real-life logistic systems. In this paper, we model one type of these problems which is encountered in the context of milk collection from the milk producers' farms in the Province of Quebec. In the derived model, the uncertainty in terms of producers' daily production levels is represented through a set of finite scenarios. We propose a branch-and-price solution approach to optimally solve this problem. Computational results showed that this approach is able to solve instances with up to 25 producers and 10 scenarios.

• 
  04:20 PM - 04:45 PM

  The Vehicle Routing Problem with Hard Time Windows and Stochastic Service Times

  • Fausto Errico, presenter, Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Michel Gendreau, Polytechnique Montréal
  • Walter Rei, Université du Québec à Montréal
  • Louis-Martin Rousseau, Polytechnique Montréal

  We consider a variant of the Vehicle Routing Problem where stochastic service times and hard time windows are associated with customers. We provide a new set-partitioning formulation which includes a probabilistic constraint and solve the problem by Branch & Price & Cut. We deploy new heuristic and exact dominance rules to limit the number of states visited in the Dynamic Programming algorithm. This is done by developing a recursive method to exactly compute the arrival time probability distribution at customers . Results show that on modified Solomon’s R100 and RC100 benchmark instances, our algorithm optimally solves all but two of the 50-customer instances

• 
  04:45 PM - 05:10 PM

  Vehicle Routing with Soft Time Windows and Stochastic Travel Times: A Column Generation and Branch-and-Price Solution Approach

  • Michel Gendreau, presenter, Polytechnique Montréal
  • Duygu Tas, TU/e Eindhoven University of Technology
  • Nico P. Dellaert, TU/e Eindhoven University of Technology
  • Tom Van Woensel, Eindhoven University of Technology
  • A.G. (Ton) de Kok, Eindhoven University of Technology

  We study a vehicle routing problem with stochastic travel times. For each customer, a soft time window allows early and late servicing. The objective is to minimize the sum of transportation costs (total distance traveled, number of vehicles used and total expected overtime of drivers) and service costs (penalties for time-window violations). We apply a column generation procedure. The master problem is a classical set partitioning problem. The pricing subproblem corresponds to an elementary shortest path problem with resource constraints. Integer solutions are obtained by branch-and-price.