[Back]

G. Raidl, T. Baumhauer, B. Hu:
"Speeding up logic-based benders' decomposition by a metaheuristic for a bi-level capacitated vehicle routing problem.";
Talk: International Workshop on Hybrid Metaheuristics 2014 - HM 2014, Hamburg; 2014-06-11 - 2014-06-13; in: "Hybrid Metaheuristics, 9th Int. Workshop, HM 2014", M. Blesa, C. Blum, S. Voß (ed.); (2014), ISBN: 978-3-319-07643-0; 183 - 197.

Benders´ Decomposition (BD) is a prominent technique for tackling large mixed integer programming problems having a certain structure by iteratively solving a series of smaller master and subproblem instances. We apply a generalization of this technique called Logic-Based BD, which does not restrict the subproblems to have continuous variables only, to a bi-level vehicle routing problem originating in the timely distribution of printed newspapers to subscribers. When solving all master and subproblem instances exactly by CPLEX, it turns out that the scalability of the approach is quite limited. The situation can be dramatically improved when using a meaningful metaheuristic - in our case a variable neighborhood search - for approximately solving either only the subproblems or both, the master as well as the subproblem instances. More generally, it is shown that Logic-Based BD can be a highly promising framework also for hybrid metaheuristics.

http://dx.doi.org/10.1007/978-3-319-07644-7_14