Flow formulations for the Time Window Assignment Vehicle Routing Problem

In this thesis, we consider flow formulations for the Time Window Assignment Vehicle Routing Problem (TWAVRP), the problem of assigning time windows for delivery before demand volume becomes known. Using commercial solver CPLEX as a basis, we develop a branch-and-cut algorithm that is able to solve all test-instances of Spliet and Gabor (2014) to optimality and is highly competitive with the state of the art solution methods. Furthermore, we introduce a novel set of TWAVRP specific valid inequalities, the precedence inequalities, and show that applying them yields a competitive algorithm as well.