Overview of the research:

We tackle three variants of the pickup and delivery problem:

• The single vehicle pickup and delivery problem with time windows,
• The multiple vehicle pickup and delivery problem with time windows, and
• The single commodity pickup and delivery problem

These problems are difficult to solve because of the hard constraints, and feasible solutions can be challenging to find. We devise simple representations and operators that deal with constraints as naturally as possible. In particular, we present a duplicate code which encodes paired pickup and delivery locations with identical IDs. This approach easily handles the precedence constraint (for which the pickup of goods must always precede the delivery of those goods). We beat previously best published results for the single vehicle pickup and delivery problem using simple three-stage metaheuristic algorithms. Our algorithms also proved to be very fast and robust, needing little re-tuning when run on new unseen instances.
We also beat previously best published results for the single commodity pickup and delivery problem, although our approach needs some more work to improve the run time.
Our main contribution to the multiple vehicle pickup and delivery problem with time windows has been our work on construction heuristics. We also developed a new genetic algorithm to solve the problem.
More details about the problems can be found in the following links:

• The Single Vehicle Pickup and Delivery Problem with Time Windows
• The Multiple Vehicle Pickup and Delivery Problem with Time Windows
• The Single Commodity Pickup and Delivery Problem

Supervisor: Dr. Christine Mumford