4 présentations

• 
  15h30 - 15h55

  A Reduced Cost Based Heuristic Approach for Stochastic Network Design Problems

  • Fatemeh Sarayloo, prés., Université de Montréal
  • Teodor Gabriel Crainic, Université du Québec à Montréal
  • Walter Rei, Université de Montréal

  This paper proposes a solution approach for the stochastic fixed-charge network design problem where the uncertain demands are considered as the set of scenarios. We develop a heuristic procedure which extracts and makes effective use of valuable information provided by reduced cost of out-of-basis variables to identify the collection of non-promising design variables. The proposed approach exploits the obtained information to consecutively solve the restricted problems, constructed by fixing the set of non-promising variables to zero, using a MIP solver. Extensive computational experiments demonstrate the efficiency of proposed approach in obtaining high-quality solutions and computational efforts.

• 
  15h55 - 16h20

  The vehicle routing problem with stochastic and correlated travel times

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

  In this paper we study an extension of the vehicle routing problems (VRP) in which the travel times are stochastic and correlated. Routes with high travel time variability are penalized through a mean-variance approach which requires the introduction of a quadratic component into the model. We propose two alternative formulations and develop a Branch-cut-and-price algorithm for both formulations. According to the formulation at hand, the quadratic component is dealt with either in the master problem of the column generation or in the subproblem. Preliminary computational results indicate that our algorithms reasonably efficient and that density of the covariance matrix impacts differently the performance of the two algorithms.

• 
  16h20 - 16h45

  An Exact Solution Approach for the Vehicle Routing Problem with Stochastic Demands under an Optimal Restocking Recourse Policy

  • Majid Salavati, prés., Université de Montréal
  • Michel Gendreau, Polytechnique Montréal
  • Ola Jabali, Politecnico di Milano
  • Walter Rei, Université du Québec à Montréal

  In this talk, we study the Vehicle Routing Problem with Stochastic Demands (VRPSD), where actual demands are only known through probability distributions. A planned route may fail at a specific customer due to an excessive demand. To regain routing feasibility, extra decisions must be taken in the form of return trips to the depot. We examine the VRPSD under an optimal restocking policy in which preventive returns are prescribed. We also present an exact solution approach to solve the VRPSD.

• 
  16h45 - 17h10

  A stochastic online algorithm for unloading boxes from a conveyor line

  • Reinhard Bürgy, prés., GERAD, Polytechnique Montréal
  • Pierre Baptiste, Polytechnique Montréal and GERAD
  • Alain Hertz, Polytechnique Montréal and GERAD
  • Djamal Rebaine, Université du Québec à Chicoutimi and GERAD
  • André Linhares, University of Waterloo

  We discuss the problem of unloading a sequence of boxes from a single conveyor line with a minimum number of moves. The problem under study is efficiently solvable with dynamic programming if the complete sequence of boxes is known in advance. In practice, however, the problem typically occurs in a real-time setting where the boxes are simultaneously placed on and picked from the conveyor line. Moreover, a large part of the sequence is often not visible. As a result, only a part of the sequence is known when deciding which boxes to move next.

  We develop an online algorithm that evaluates the quality of each possible move with a scenario-based stochastic method. Two versions of the algorithm are analyzed: in one version, the quality of each scenario is measured with an exact method, while a heuristic technique is applied in the second version. Numerical results show that the proposed approach consistently provides high-quality results, and compares favorably with the best known deterministic online algorithms.