The Single Vehicle Pickup and Delivery Problem with Time Windows
The single vehicle pickup and delivery problem with time windows (PDPTW) is an important practical problem, having applications such as mail delivery, newspaper distribution, school bus routing and the transportation of employees. Indeed, we think that the PDPTW will assume even greater prominence in the future, if we are to design more efficient transport systems and reduce the environmental impact of the ever increasing volumes of goods transported on our roads.
The PDPTW deals with a number of customer requests that must be satisfied by one vehicle with a known capacity. The route of the vehicle usually starts and ends with a central depot. A request must be collected from a pickup location before being dropped off at a corresponding delivery location, and every pickup and delivery request is associated with a specific time window during which it must be served. If the vehicle arrives earlier than the beginning of the designated time window interval, it must wait until the service time begins. All requests must be served in a way that minimizes the total travel cost of the vehicle, without violating precedence, capacity and time windows constraints.
The PDPTW is known to NP-Hard, with the presence of time windows making the problem particularly complicated. Since exact algorithms are too slow for large problem sizes, heuristic and meta-heuristic approaches seem to be good alternatives. Amongst meta-heuristics, genetic algorithms (GAs) are well known for their robustness, parallelism, and their ability to perform reasonably well on a wide variety of problems, including ordering and grouping problems, as well as highly constrained problems. Thus, exploring GAs to solve the PDPTW would seem to be a justified option. Besides their ability to widely explore the search space, GAs are easy to implement and do not depend so much on the quality of the initial solution as some other heuristic and meta-heuristic techniques.
To the best of our knowledge, only a few researchers have experimented with genetic algorithms (GAs) to tackle the single vehicle pickup and delivery problem with time windows, possibly due to the large number of constraints involved and the difficulty in handling them. In particular, there is the difficulty in designing an appropriate genetic representation and intelligent genetic operators that are able to transfer the ordering characteristic of the parents to the offspring, while preserving the feasibility of the solution. In this research, we will experiment with a genetic encoding and operators specially designed to deal with the problem in hand. We will present a duplicate gene encoding that guarantees the satisfaction of the the precedence constraint, between the pickup and the delivery requests, throughout the search. We aim to show that GAs, if guided by some problem-specific information, will be able to handle this hard problem and possibly other similarly highly constrained problems.
Nevertheless, we are also exploring alternative heuristics and meta-heuristic options as part of our research, such as simulated annealing and hill climbing.
Test Data for the Problem:
To test our algorithm, we have created a data set having a number of requests ranging from 100 to 200. These data sets can be obtained here.
Our References: A list of some important references for the pickup and delivery problem can be found here