An Exploration of Heuristics Applied to Genetic Algorithms on the Capacitated Pickup and Delivery Problem with Time Windows

Abstract

Pickup and delivery is a ubiquitous part of everyday life. Being able to move goods and people between locations in the shortest amount of time and with the fewest vehicles allows packages to arrive on time, allows the just-in-time delivery paradigm that much of our industries rely on, and much more. Solving this problem is a complex task that interests both academia and industry. As time goes on the size and complexity of the problems we wish to solve also increase. Additionally, time is often a critical parameter that cannot be changed. This in turn leads to a need for better and more efficient algorithms. Due to the scale of the problems, exact solutions are often eschewed in exchange for satisfactory solutions. Many heuristics and algorithms have been designed to try and improve the solutions while not increasing the time to completion. These algorithms use local search operations to iteratively improve solutions in hopes they become better over time. This thesis aims to address the need for better algorithms. The first problem that we approach is an exploration of how different local search operations compare against each other. By identifying the operators that most improve the final solution, more intelligent algorithms can be constructed. Using genetic algorithms as the base, typical genetic algorithm operators are compared against vehicle routing operators to determine which most improves the solution. The second problem introduces a new heuristic that uses historical information to improve solutions. Previous solutions can be deconstructed into subroutes, with the most frequently occurring being extracted. Using these previously found subroutes, the new heuristic attempts to insert them into newly created solutions. This is done by removing each part of the pattern from the solution, creating route fragments. These fragments can then be recombined to create a new solution. The two principal ideas are that common routes will tend to be good routes and this process allows higher-order operations to be performed.