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

Investigation into heuristic methods of solving time variant Vehicle Routing Problems

Harwood, Kieran G. 2013. Investigation into heuristic methods of solving time variant Vehicle Routing Problems. PhD Thesis, Cardiff University.
Item availability restricted.

[thumbnail of 2013harwoodkgphd.pdf]
Preview
PDF - Accepted Post-Print Version
Download (3MB) | Preview
[thumbnail of HarwoodKG3.pdf] PDF - Supplemental Material
Restricted to Repository staff only

Download (1MB)

Abstract

Traditionally, Vehicle Routing Problems (VRPs) are modelled with fixed traversal times. The amount of time it takes to drive from one end of a road to the other is unchanged throughout the day. Nearly always, the reality of the situation that is being modelled is very different, with road speeds varying heavily, especially with “rush hour" traffic. Modelling VRPs with time varying congestion means that even slight changes early in a vehicle tour can have major knock-on effects that are hard to predict. Recalculating the total traversal time of vehicles whenever their tours are changed drastically increases metaheuristic calculation times compared to non-time varying models. In this thesis we use a simple technique of calculating the localised change and inferring the global effects resulting from neighbourhood moves. Only if the localised change suggests that the global result is satisfactory do we then calculate the actual global result. Inevitably using these estimates does not give as accurate results as always calculating the changes, but we aim to show that the loss of solution quality is overshadowed by the significant savings in calculation time. We present a series of experiments comparing simple metaheuristics with and without using estimates and show consistent savings in calculation time whenever estimates are used compared to when they are not. These savings shown to increase as the size of the problem (in terms of the number of customers) increases. In addition to synthetic problems, we also present a problem based on real world vehicle traversal times and show that our estimates prove just as accurate, if not more so, at retaining solution quality as the synthetic methods. Lastly, we briefly discuss further methods of solving VRPs that could also benefit from our work here.

Item Type: Thesis (PhD)
Status: Unpublished
Schools: Computer Science & Informatics
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords: Vehicle Routing; VRP; Time-Variant; Time-Dependent; Vehicle Routing; VRP; Time-Variant; Time-Dependent; Capacity; Meta-heuristic; Simulated Annealing; Hill Climber; Time Bins; FIFO Problem; Road Timetable; Green Logistics
Funders: EPSRC
Date of First Compliant Deposit: 30 March 2016
Last Modified: 19 Mar 2016 23:22
URI: https://orca.cardiff.ac.uk/id/eprint/49087

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics