Vehicle Routing with Varying Levels of Demand Information Defended on Friday, 19 January 2024

The vehicle routing problem is the problem of serving a set of customers with a fleet of vehicles such that the travel costs of those vehicles are minimized, while making sure each vehicle starts and ends at a central depot. In this thesis, we focus on exact methodology for the vehicle routing problem with three different levels of demand information: deterministic, stochastic and sensor-driven.

First, we look at set partitioning and set covering problems that are solved by a branch-price-and-cut algorithm. We introduce a new category of cuts, called “resource-robust”, which do not complicate the pricing problem if specific resources are included. We create new cuts for the capacitated vehicle routing problem, with deterministic demands, that are resource-robust when the ng-route relaxation is used, which leads to speedups for certain instances.

Second, we focus on the vehicle routing problem with stochastic demands. We develop a state-of-the-art integer L-shaped method to solve the problem to optimality. The algorithm uses all techniques from the literature, improves on some of these and uses new valid inequalities. Using this algorithm, we also investigate three commonly-made assumptions in the literature from a theoretical and computational perspective.

Third, we investigate a single-period waste collection problem with sensors. We can adjust our routing decisions based on the sensor readings. We derive theoretical properties and develop an algorithm to approximate the cost savings achieved given a certain sensor placement. Then, we investigate the effectiveness of several sensor placement rules and how they fare under sensor uncertainty.