Solving Vehicle Routing Problems

Vehicle Routing Problems (VRPs) are one of the most common logistics problems faced by a wide range of organisations. Parcel delivery organisations are confronted with challenging transportation puzzles due to the increasing number of parcels which must be delivered on a daily basis as a result of ever-increasing levels of online shopping. Even companies whose core business is not transporting goods may also find themselves confronted with having to efficiently solve transportation problems. For example, a made-to-order kitchen manufacturer must not only produce kitchens but also ensure that those kitchens are delivered to customers in a timely and efficient manner. The first attempt to solve the VRP was made by Dantzig et al. (1954). In the years following, many academics have intensively studied the problem. Nevertheless, solving large-scale VRP instances sufficiently fast for real-world scenarios remains challenging. During the last decade, state-of-the-art solution methods have evolved towards genetic algorithms where multiple solutions evolve simultaneously. Other successful methods rely on exploring multiple neighborhoods within a local search algorithm. This PhD introduces a simple yet powerful solution method for solving VRPs: Slack Induction by String Removals (SISRs). SISRs consists of three components: a fleet minimization technique, a ruin method and a recreate method guided by Simulated Annealing (Kirkpatrick et al. 1983). This approach is shown to be remarkable effective across a wide range of VRP variants, while its implementation remains straightforward and flexible enough to accommodate novel routing constraints. Simplified and flexible solution approaches such as SISRs are essential in order to solve real-world routing problems, as such problems may become very computationally complex when special constraints are involved. The Prisoner Transportation Problem, introduced in this PhD thesis, is one such example of a setting in which routing complexity increases considerably due to the restrictions involved when it comes to combining multiple prisoners within a single vehicle. Inspired by real-world VRPs like the Prisoner Transportation Problem (PTP), SISRs successfully contributes to both academic theory as well as vehicle routing optimisation in practice.

Publication year:2021

Accessibility:Open