Vehicle routing with varying levels of demand information

Research output: Types of ThesisDoctoral ThesisInternal

36 Downloads (Pure)


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.
Original languageEnglish
Awarding Institution
  • Erasmus University Rotterdam
  • Wagelmans, Albert, Supervisor
  • Dekker, Rommert, Co-supervisor
  • Spliet, Remy, Co-supervisor
Award date19 Jan 2024
Place of PublicationRotterdam
Print ISBNs978-90-5892-686-9
Publication statusPublished - 19 Jan 2024


  • ERIM PhD Series Research in Management


Dive into the research topics of 'Vehicle routing with varying levels of demand information'. Together they form a unique fingerprint.

Cite this