Harwood, Kieran G.
2013.
Investigation into heuristic methods of solving time variant Vehicle Routing Problems.
PhD Thesis,
Cardiff University.
Item availability restricted. |
Preview |
PDF
- Accepted Post-Print Version
Download (3MB) | Preview |
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 |