Journées de l'optimisation 2017

HEC Montréal, 8-10 mai 2017

1er Atelier Canadien sur l'optimisation des soins de santé (CHOW)

HEC Montréal, 10-11 mai 2017


HEC Montréal, 8 — 11 mai 2017

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TD5 Optimisation stochastique / Stochastic Optimization

9 mai 2017 15h30 – 17h10

Salle: Nancy et Michel-Gaucher

Présidée par Reinhard Bürgy

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h30 - 15h55

    A Reduced Cost Based Heuristic Approach for Stochastic Network Design Problems

    • Fatemeh Sarayloo, Présentateur, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h55 - 16h20

    The vehicle routing problem with stochastic and correlated travel times

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

    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h20 - 16h45

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

    • Majid Salavati, Présentateur, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h45 - 17h10

    A stochastic online algorithm for unloading boxes from a conveyor line

    • Reinhard Bürgy, Présentateur, 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.