Background

The Vehicle Routing Problem

Overview

The Vehicle Routing Problem (VRP) is a combinatorial optimisation problem that seeks to answer the question: "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a set of locations?". It is a classical problem in operations research and logistics, with applications ranging from parcel delivery and public transport scheduling to waste collection and field service management.

The VRP was formally introduced in 1959 by George Dantzig and John Ramser in their seminal paper “The Truck Dispatching Problem.” Their work modelled a fleet of oil-delivery trucks operating from a central depot and servicing multiple stations, with the objective of minimising total distance travelled.

This early formulation built upon the Travelling Salesman Problem (TSP), a challenge in which a single entity must visit a set of locations exactly once and return to its starting point, by extending it to multiple vehicles and introducing depot-based operations. Since then, the VRP has become one of the most studied problems in combinatorial optimisation, inspiring decades of research and practical applications.

At its core, the VRP captures the essence of last-mile delivery, where goods are transported from a central distribution point, or depot, to the customer’s location. However, real-world delivery scenarios are rarely this straightforward. Over time, numerous VRP variants have been developed to address practical constraints, including the Capacitated VRP (CVRP), which accounts for vehicle load limits, and the VRP with Time Windows (VRPTW), which ensures deliveries occur within specified time frames.

For this project, the focus was on combining the CVRP and VRPTW (together referred to as the CVRPTW), as they provide a realistic and suitably challenging foundation for modelling and solving the problem in a way that reflects real-world logistics.

Solving the VRP

The Vehicle Routing Problem (VRP) is an NP-hard combinatorial optimisation problem. This computational characteristic means that finding the absolute optimal solution becomes prohibitively complex as the number of stops increases, with the number of possible routes growing factorially. Consequently, exact solution methods are only practical for very small problem instances.

For real-world applications, which often involve hundreds or thousands of locations, heuristic and meta-heuristic algorithms are commonly used to generate near-optimal solutions within acceptable timeframes. Prominent examples of such algorithms include Ant Colony Optimisation, Simulated Annealing, and the Genetic Algorithm (GA).

Ultimately, the GA was selected due to its robustness and effectiveness in tackling multi-objective optimisation problems, a characteristic of advanced VRP formulations.