This paper describes an exact algorithm for a variant of the vehicle routing problem in which customer demands to be collected are stochastic. Demands are revealed upon the vehicle arrival at customer locations. As a result, a vehicle may reach a customer and does not have sufficient capacity to collect the realized demand. Such a situation is referred to as a failure. In this paper the following recourse action is then applied when failure occurs: the vehicle returns to the depot to unload and resumes its planned route at the point of failure. The capacitated vehicle routing problem with stochastic demands (VRPSD) consists of minimizing the sum of the planned routes cost and of the expected recourse cost. The VRPSD is formulated as a two-stage stochastic programming model and solved by means of an integer L-shaped algorithm. This paper introduces three lower bounding functionals based on the generation of general partial routes, as well as an exact separation procedure to identify violated cuts. Extensive computational results confirm the effectiveness of the proposed algorithm, as measured by a substantial reduction in the number of feasible solutions that have to be explicitly eliminated. This translates into a higher proportion of instances solved to optimality, reduced optimality gaps, and lower computing times. © 2014 Elsevier B.V. All rights reserved.


    Access

    Download


    Export, share and cite



    Title :

    Partial-route inequalities for the multi-vehicle routing problem with stochastic demands



    Publication date :

    2014-01-01



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629



    The consistent vehicle routing problem with stochastic customers and demands

    Alvarez, Aldair / Cordeau, Jean-François / Jans, Raf | Elsevier | 2024


    The Multi-period Fleet Size and Mix Vehicle Routing Problem with Stochastic Demands

    Pasha, Urooj / Hoff, Arild / Hvattum, Lars Magnus | Springer Verlag | 2017


    Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

    Bianchi, L. / Birattari, M. / Chiarandini, M. et al. | British Library Online Contents | 2006


    The Multi-period Fleet Size and Mix Vehicle Routing Problem with Stochastic Demands

    Pasha, Urooj / Hoff, Arild / Hvattum, Lars Magnus | British Library Conference Proceedings | 2018