Improving column complementarity in a restricted master heuristic with a GRASP-guided completion: Application to the vehicle routing problem with stochastic demands

Many combinatorial optimization problems, such as vehicle and crew scheduling, can be modeled using path-flow formulations, where each variable represents a feasible route. A major challenge in these formulations lies in efficiently generating high-quality integer solutions from a model with exponentially many variables. We propose a hybrid restricted master heuristic that combines column generation with a greedy randomized adaptive search procedure (GRASP) to improve solution quality in these settings. The method first uses dynamic programming-based pricing to generate routes guided by dual variables from the linear relaxation. It then applies GRASP to complete partial solutions and introduce new routes that complement those with positive reduced costs, thereby improving column complementarity before solving the resulting model as a mixed-integer program. This integration leverages both the global guidance of column generation and the diversification strength of GRASP. We illustrate the approach on the vehicle routing problem with stochastic demands, where customer demands are modeled as random variables revealed upon arrival. Experimental results on 40 benchmark instances with up to 60 customers show that the method reliably produces high-quality solutions, achieving optimality gaps below 5% in all cases and averaging under 2% within 5 minutes of computation, with a higher proportion of best solutions returned than any other variant considered.Keywords: vehicle routing, stochastic demands, restricted master heuristic,GRASPEmail addressesgael-simon.reynal@polymtl.ca (Ga¨el REYNAL), quentin.cappart@polymtl.ca (Quentin CAPPART), guy.desaulniers@polymtl.ca(Guy DESAULNIERS), louis-martin.rousseau@polymtl.ca (Louis-Martin ROUSSEAU)Preprint submitted to Computers and Operations Research July 17, 2025mark instances with up to 60 customers show that the method reliably produces high-quality solutions, achieving optimality gaps below 5% in all cases and averaging under 2% within 5 minutes of computation, with a higher proportion of best solutions returned than any other variant considered.