# What's the best way to speed up Benders Decomposition for a stochastic vehicle routing problem?

Currently I am working on an implementation of Benders Decomposition that solves a stochastic vehicle routing problem with synchronisation constraints.

Sadly, at the moment it is not performing fast enough to be a serviceable solution method.

The main problem I think is, that in the first stage of the stochastic problem, we basically generate 99% of the time tours that are rendered infeasible by the subproblem because all the information on time windows and the needed synchronisation is part of the subproblem.

So the number of feasibility cuts is extremely high.

In order to fix this, I tried to add a subset of the scenarios to the master problem, meaning it gets extended with the complete set of constraints for this subset.

It accelerated the method a little, but not enough.

Do you have further recommendations how I could deal this with problem?

• Which parts of the input are deterministic, and which parts are stochastic? Commented Nov 22, 2023 at 12:12
• The service time is currently the only stochastic parameter. For the variables, we have the classical VRP variables in the first stage like x^k_ij if vehicle k traverses edge (i,j). Second stage contains stuff like starting times of service at a node. Commented Nov 22, 2023 at 12:20
• Do you know enough about the distributions of service times to be able to omit some incompatible arcs $(i,j)$ from the master? Commented Nov 22, 2023 at 13:01
• Sadly, not really. Our time windows are quite broad, the restrictive factor in our problem is the synchronisation. That means, a lot of tours from the master are infeasible because the synchronisation doesn't happen, but there are no arcs you can forbid. Commented Nov 22, 2023 at 14:22
• This paper might be relevant: pubsonline.informs.org/doi/abs/10.1287/trsc.2019.0956 Commented Nov 27, 2023 at 14:30