A branch-and-price based heuristic for the stochastic vehicle routing problem with hard time windows

In the Vehicle Routing Problem with Hard Time Windows and Stochastic travel times, a disruption occurs if, due to stochastic events, a vehicle arrives too late at a customer. In this case a recourse action is required such that the service starts within the time window, and a relevant penalty cost is incurred. Despite the problem has been inspired by a real-life application in airport ground handling optimization, it has never been addressed before in literature, to the best of our knowledge. We discuss how the expected penalty cost can be evaluated and how this computation can be integrated in a branch-and-price procedure to obtain heuristic solutions. Preliminary tests on literature instances show the effectiveness of the approach.