Optimization Days 2017
HEC Montréal, May 8-10, 2017
1st Canadian Healthcare Optimization Workshop (CHOW)
HEC Montréal, May 10-11, 2017
JOPT2017
HEC Montréal, 8 — 11 May 2017
TD5 Optimisation stochastique / Stochastic Optimization
May 9, 2017 03:30 PM – 05:10 PM
Location: Nancy et Michel-Gaucher
Chaired by Reinhard Bürgy
4 Presentations
-
03:30 PM - 03:55 PM
A Reduced Cost Based Heuristic Approach for Stochastic Network Design Problems
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.
-
03:55 PM - 04:20 PM
The vehicle routing problem with stochastic and correlated travel times
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.
-
04:20 PM - 04:45 PM
An Exact Solution Approach for the Vehicle Routing Problem with Stochastic Demands under an Optimal Restocking Recourse Policy
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.
-
04:45 PM - 05:10 PM
A stochastic online algorithm for unloading boxes from a conveyor line
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.