In this thesis we consider two combinatorial optimisation problems; the Capacitated Vehicle Routing Problem (CVRP) and the Capacitated Arc Routing Problem (CARP). In the CVRP, the objective is to find a set of routes for a homogenous fleet of vehicles, which must service a set of customers from a central depot. In contrast, the CARP requires a set of routes for a fleet of vehicles to service a set of customers at the street level of an intercity network. After a comprehensive discussion of the existing exact and heuristic algorithmic techniques presented in the literature for these problems, computational experiments to provide a benchmark comparison of a subset of algorithmic implementations for these methods are presented for both the CVRP and CARP, run against a series of dataset instances from the literature. All dataset instances are re-catalogued using a standard format to overcome the difficulties of the different naming schemes and duplication of instances that exist between different sources. We then present a framework, which we shall call Genetic Algorithm with Perturbation Scheme (GAPS), to solve a number of combinatorial optimisation problems. The idea is to use a genetic algorithm as a container framework in conjunction with a perturbation or weight coding scheme. These schemes make alterations to the underlying input data within a problem instance, after which the changed data is fed into a standard problem specific heuristic and the solution obtained decoded to give a true solution cost using the original unaltered instance data. We first present GAPS in a generic context, using the Travelling Salesman Problem (TSP) as an example and then provide details of the specific application of GAPS to both the CVRP and CARP. Computational experiments on a large set of problem instances from the literature are presented and comparisons with the results achieved by the current state of the art algorithmic approaches for both problems are given, highlighting the robustness and effectiveness of the GAPS framework.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:584425 |
| Date | January 2008 |
| Creators | Morgan, Matthew J. W. |
| Publisher | Cardiff University |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://orca.cf.ac.uk/55459/ |
Page generated in 0.001 seconds