A Branch-and-Cut Algorithm for the Time Window Assignment Vehicle Routing Problem

In distribution networks, decisions are often made on both the tactical and the operational level. On the tactical level, it is decided in which time windows deliveries will be made to the clients. On the operational level it is determined which vehicles will be used, which goods they will be transporting, and which routes they will use. If the demand on the operational level is uncertain, the Time Window Assignment Vehicle Routing Problem (TWAVRP) can be solved to determine the optimal time window assignments. The TWAVRP has been introduced by Spliet and Gabor (2014), who use a branch-price-and-cut approach to solve it. In this paper, we take a branch-and-cut approach and show that this approach is highly competitive: the same set of test-instances considered by Spliet and Gabor (2014) can now be solved over 40 times faster. To achieve this result we make use of both the well-studied rounded capacity cuts, as do we introduce a novel class of valid inequalities and separation heuristics.

• Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars