The vehicle routing problem with simultaneous pick-up and deliveries and a GRASP-GA based solution heuristic

In this dissertation, the vehicle routing problem and one of its variants, the vehicle routing problem with simultaneous pick up and deliveries (VRPSPD) are studied. The traditional vehicle routing problem (VRP) consists of constructing minimum cost routes for the vehicles to follow so that the set of customers are visited only once. A lot of effort has been devoted to research on developing fast and effective solution methods for many different versions of this problem by different majors of engineering profession. Thus, a structuring effort is needed to organize and document the vast literature so far has accumulated in this field. Over its lifespan the VRP literature has become quite disjointed and disparate. Keeping track of its development has become difficult because its subject matter transcends several academic disciplines and professions that range from algorithm design to traffic management. Consequently, this dissertation begins with defining VRP\u27s domain in its entirety, accomplishes an allencompassing taxonomy for the VRP literature, and delineates all of VRP\u27s facets in a parsimonious and discriminating manner. Sample articles chosen for their disparity are classified to illustrate the descriptive power and parsimony of the taxonomy. Next, a more detailed version of the original problem, the VRPSPD is examined and a more abstract taxonomy is proposed. Additionally, two other existing classification methodologies are used to distinguish all published VRPSPD papers on their respective research strategies and solution methods. By using well-organized methods this study provides a solid multidimensional identification of all VRPSPD studies? attributes thus synthesizing knowledge in the filed. Finally, a hybrid metaheuristic solution algorithm for the VRPSPD problem is presented. To solve this NP-hard vehicle routing problem a GRASP initiated hybrid genetic algorithm is developed. The algorithm is tested on two sets of benchmark problems from the literature with respect to computational efficiency and solution quality. The effect of starting with a better initial population for the genetic algorithm is further investigated by comparing the current results with previously generated ones. The experimental results indicate that the proposed algorithm produces relatively good quality solutions and a better initial population yields a reduction in processing cycles