Vehicle Routing with Uncertain Demand



In distribution networks a supplier transports goods from a distribution center to customers by means of vehicles with limited capacity. Drivers will drive routes on which they visit multiple customers to make deliveries. Typically, deliveries are made regularly and a fixed schedule is maintained. A fixed schedule is beneficial for many operational purposes, as it for instance allows for easy planning of the packing of the vehicles at the distribution center, or it allows the customer to roster the delivery handling personnel. A fixed schedule is often reused to make weekly deliveries for a period of a year or longer.

However, at the moment of designing a schedule, the demand of the customers is usually unknown. Moreover, in most cases, demand of a customer will be different for each delivery. Therefore, it will be necessary to construct or adapt vehicle routes for each day of delivery, without deviating too much from the fixed schedule.

In this thesis several different views on a fixed schedule are explored. It addresses the need from practice to incorporate the uncertainty of demand in transportation models to increase the efficiency of transport. Innovative vehicle routing models are presented taking uncertain or varying demand into account. New algorithms using state-of-the-art methods are presented based on these models, to construct fixed schedules and vehicle routes. The algorithms make use of recent scientific advances in mathematical programming, specifically in the domain of vehicle routing.