Thursday, 13:45 - 14:10 h, Room: H 3021


Mahdi Noorizadegan
A branch and cut approach for some heterogeneous routing problems under demand uncertainty

Coauthors: Bo Chen, Laura Galli


The Capacitated Vehicle Routing Problem (CVRP), with its many variants, is one of the most widely studied NP-hard problems in combinatorial optimisation due to its wide practical applications and tough computational challenges. An important generalisation of the classical CVRP is the so-called Heterogeneous Vehicle Routing Problem (HVRP), where a heterogeneous fleet of finite vehicles is stationed at the depot. In this study, we first consider the stochastic HVRP, and then move to a new and even more general variant known as (stochastic) Capacitated Multi-Depot Heterogeneous VRP. In the stochastic versions it is assumed that customer demands are not known for certain. There are many ways to deal with uncertainty. We present three models: two robust counterparts according to Ben-Tal & Nemirovski (1999) and Bertsimas & Sim (2004) and one chance-constrained. Our first step is to formulate the (deterministic) problems in such a way that the corresponding stochastic ones, according to the three frameworks, remain tractable. The second step is to solve the resulting models using a Branch-and-Cut approach. We present heuristic separation algorithms for some classes of valid inequalities.


Talk 2 of the invited session Thu.2.H 3021
"Combinatorial optimization under uncertainty" [...]
Cluster 2
"Combinatorial optimization" [...]


  USA Payday Loans Online. This is a permit to the world of pleasure and the lasting sex. Cialis Super Active online is a drug, the quality level of which is determined by its action speed.