Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

The dynamic vehicle routing problem: a metaheuristics based investigation

Wallace, Maxwell 2007. The dynamic vehicle routing problem: a metaheuristics based investigation. PhD Thesis, Cardiff University.

[thumbnail of U584999.pdf] PDF - Accepted Post-Print Version
Download (21MB)

Abstract

The desire to optimise problems is as prevalent in today's society as it has ever been. The demand for increases in speed and efficiency is relentless and has resulted in the need for mathematical models to bear greater resemblance to real-life situations. This focus on increased realism has paved the way for new dynamic variants to classic optimisation problems. This thesis begins by considering the Dynamic Vehicle Routing Problem. The basic premise of this routing problem is as follows a percentage of customers are known a priori, for which routes are constructed, further customers then arrive during the course of the working day and need to be incorporated into an evolving schedule. Literature has proposed a timeslot approach, whereby one partitions the working day into a series of smaller problems, that one is then required to solve in succession. This technique is used to produce a variety of metaheuristics based implementations, most noticeably Ant Colony Optimisation and Tabu Search. Consideration is then given to the Dynamic Vehicle Routing Problem with Time Windows. This problem is similar to the Dynamic Vehicle Routing Problem, but requires each customer to be serviced within a predefined period of the day. A metaheuristic approach adapted from the most successful algorithm implemented on the Dynamic Vehicle Routing Problem is presented. Finally consideration is given to a time-based decomposition technique for the Vehicle Routing Problems with Time Windows (Large-Scale instances). This work makes use of the dynamic solution technique developed in the preceding work, and is used in conjunction with an Ant Colony Optimisation algorithm and a descent algorithm.

Item Type: Thesis (PhD)
Status: Unpublished
Schools: Mathematics
Subjects: Q Science > QA Mathematics
ISBN: 9781303209512
Date of First Compliant Deposit: 30 March 2016
Last Modified: 12 Feb 2016 23:12
URI: https://orca.cardiff.ac.uk/id/eprint/54610

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics