4
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Which parts of the input are deterministic, and which parts are stochastic? $\endgroup$
    – RobPratt
    Commented Nov 22, 2023 at 12:12
  • $\begingroup$ 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. $\endgroup$ Commented Nov 22, 2023 at 12:20
  • $\begingroup$ Do you know enough about the distributions of service times to be able to omit some incompatible arcs $(i,j)$ from the master? $\endgroup$
    – RobPratt
    Commented Nov 22, 2023 at 13:01
  • $\begingroup$ 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. $\endgroup$ Commented Nov 22, 2023 at 14:22
  • $\begingroup$ This paper might be relevant: pubsonline.informs.org/doi/abs/10.1287/trsc.2019.0956 $\endgroup$
    – RobPratt
    Commented Nov 27, 2023 at 14:30

1 Answer 1

0
+50
$\begingroup$

Without knowing much about the problem, there are several approaches (listed in increasing difficulty of implementation):

1). Warm-start the model at a known feasible solution.

2). You could try modeling the problem with complete recourse and extremely large penalties for violating the constraints.

3). You can study your problem to determine additional first-stage cuts that will eliminate candidate first-stage solutions that turn out to be infeasible.

Are your first stage decision variables binary? If so, there are different forms for the cuts that will work better. What about second-stage? How many scenarios are you using? More information would help.

$\endgroup$
2
  • $\begingroup$ Hello, thank you for those recommendations. My first-stage variables are all binary. They essentially embody the usual VRP decision variables. My second-stage variables are all continuous. They are: start time of service at a node, overtime of a vehicle, idle time of a vehicle. Currently I am using between 6-10 scenarios but the goal should be at least 100. $\endgroup$ Commented Nov 30, 2023 at 8:18
  • 1
    $\begingroup$ Ok, in that case changing the optimality cuts to be specific for first-stage binary variables would not help since the problem is in feasibility. Without an initial known feasible solution, your problem is likely to be very difficult computationally. Modeling the problem with complete recourse by penalizing infeasibility might help somewhat, but other than that your problem just might be a hard one to solve. Could always try getting a faster computer! $\endgroup$ Commented Dec 8, 2023 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.