Vehicle routing problems (VRPs) are a fundamental piece of logistics planning. Exact methods for the classic capacitated VRP (CVRP) have seen significant advancements over the last ten years, pushing the boundaries of problem sizes that can be efficiently solved to optimality. Standard benchmark CVRP instances having hundreds of customers can be solved to proven optimality within seconds or a few minutes. Nevertheless, the picture is far less promising for other CVRP variants, especially variants that embed delivery decisions in the modelling. For some of these problems, instances with fewer than one hundred – or even a few dozen – customers can be challenging enough. We develop Branch-cut-and-price (BCP) algorithms, the current state-of-the-art approach for solving CVRP problems exactly, for two VRP variants with delivery decisions, namely the split delivery VRP with (SDVRPTW) or without time windows (SDVRP), and the inventory routing problem (IRP). For these problems, the best performing approaches in the literature are mainly Branch-and-cut (B&C) algorithms. Thus, we aim at designing BCP algorithms, adapting state-of-the-art BCP algorithmic components designed for the CVRP to these problems, to assess whether these algorithms can solve large instances and be competitive with tailored B&C for these problems.
[Read more]
This thesis aims to present families of fully and partially discretised formulations for vehicle routing problems with delivery decisions. These formulations bridge an existing gap in the literature for the targeted problems, namely SDVRP variants, with or without time windows, and the IRP. Existing BCP implementations in the literature for these problems rely on a concept that may require several rounds of column generation. This detrimental effect is not present in our proposed formulations. In addition, we adapt existing and novel families of non-robust inequalities for these problems by employing the limited-memory technique. Several cut separation procedures are implemented to separate robust and non-robust inequalities. Especially for SDVRP variants, we highlight that our separation algorithms are generic and capable of finding valid cuts violated for both CVRP and SDVRP variants.
[Read more]
[Read more]