Meta-heuristics for the vehicle routing problem

This dissertation involves the development and application of Meta-RaPS and its variation to the vehicle routing problem (VRP) and to the vehicle routing problem with time windows (VRPTW). It begins with the introduction and overview of these two problems and Meta-RaPS, focusing on the formulation of both problems. The latter part of the dissertation proposes one new construction method with several variants followed by an improvement method for VRPTW in Meta-RaPS. Finally the multi-objective characteristic of VRPTW is also discussed.; The dissertation is divided into seven chapters, covering problems and heuristics background, formulation and the proposed heuristics. Chapter One gives a general introduction to the VRP and to the VRPTW, and also presents an overview of the current methods and technologies for both problems. Chapter Two explores the statements and formulations for both problems. Chapter Three gives the detailed introduction to MetaRaPS along with a description of the applications and advantages. Chapter Four lists the overview related to VRP, VRPTW, Meta-RaPS and related memory-based heuristic.; Chapters Five and Six present the methodologies of the proposed algorithm for both problems. Specifically Chapter Five focuses on the algorithms for the VRP and Chapter Six emphasizes several modified algorithms for the VRPTW. The proposed algorithms are tested on a set of standard problems ( http://www.crpc.rice.edu/softlib/catalog/tsplib.html for VRP and http://elib.zib.de/pub/Packages/mp-testdata/vehicle - rout/index.html for VRPTW). Results, comparisons and discussions for both types of problems are also listed in both chapters.; Chapter Seven gives the conclusions and directs the future work. The results show the advantages of the Meta-RaPS with the effective construction method and improvement method for both types of problems.