This thesis identifies some problems, the genetic algorithm (GA) is facing in the area of vehicle routing and proposes various methods to address those problems. Those problems arise from the unavailability of suitable chromosomal representation and evaluation schemes of GA for the Vehicle Routing Problem (VRP). The representation and evaluation schemes already in use have problems of high computational cost, illegal chromosomes (chromosomes not representing a legal tour) and wrong fitness assignment (fitness not truly representing chromosome genetic makeup). These problems are addressed by several proposed new schemes, namely the Self Imposed Constraints Evaluation scheme, the Contour and Reverse Contour Evaluation schemes and the Order Skipping Evaluation scheme, which are specifically tailored for various objectives, problems and situations. Apart from this, a methodology, which has previously being used in other meta-heuristics, is incorporated into GA i.e., the independent application of GA on various sub-localities of the problem. We call this GA, a Localized Genetic Algorithm (LGA). LGA is an iterative procedure between optimization and controlled de-optimization. The procedure of controlled de-optimization is also novel. It brings the solution into a new search space while controlling its cost effectively. LGA is introduced with various search techniques, i.e. intensive, extensive and selective, the use of which depends on the problem size and the availability of computational resources. Furthermore, search reduction techniques (Fitness Approximation Methods) are also introduced into the LGA, which has enabled the LGA to be applied to large scale problems. Due to the implementation of those proposals, LGA is the first GA-driven approach to be applied to very large scale CVRP problems of up to 1200 customers, i.e. datasets presented by Feiyue in 2005 and large scale VRPTW problems of up to 1000 customers, datasets presented by Gehring and Homberger in 1999. Lastly, a standard unit for computational comparison, i.e., Bellman's Evaluation Units BEUs, is also introduced to facilitate computational comparisons for future researchers. LGA has shown promising results on CVRP and VRPTW problems. It is flexible and also has the potential to be extended to not only other vehicle routing problems, but also to other ordering problems.
| Identifer | oai:union.ndltd.org:ADTP/258701 |
| Date | January 2009 |
| Creators | Ursani, Ziauddin, Engineering & Information Technology, Australian Defence Force Academy, UNSW |
| Publisher | Awarded by:University of New South Wales - Australian Defence Force Academy. Engineering & Information Technology |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | http://unsworks.unsw.edu.au/copyright |
Page generated in 0.002 seconds