The Multiple Vehicle Pickup and Delivery Problem with Time Windows
The pickup and delivery problem with time windows (PDPTW) is an important practical problem that is likely to assume even greater prominence in the future. Current concerns over global warming, resource depletion and the social impact of traffic ccongestion and pollution, are driving companies and government entities to increase the efficiency of their logistics operations. In addition, the rapid growth in parcel transportation as a result of e-commerce, is likely to have an increasing impact. More cooperation between manufacturers, shippers and carriers in supply chains could greatly reduce the environmental impact of transport. In addition, an important variant of the PDPTW, known as dial-a-ride, can provide an effective means of transport for delivering people from door to door. This model is frequently adopted for the disabled, but could provide a greener alternative than the car and taxi to the wider community.
The pickup and delivery problem deals with a number of customer requests that must be satisfied by a homogeneous fleet of vehicles. Each vehicle has a known capacity, and all vehicle routes must start and end with a central depot. A request must be picked up from a pickup location before being delivered to a corresponding delivery location, and every 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 start of the specified service time. All requests must be served in a way that minimizes the number of vehicles used and the total travel cost of all vehicles, without violating precedence, capacity and time windows constraints.
The PDPTW is known to be NP-hard, and the presence of many constraints makes the problem particularly complicated. This could be one reason that the problem has actually attracted less attention compared to other classical vehicle routing and scheduling problems. When solving this kind of problem, exact algorithms are often too slow for large problem sizes. Accordingly, heuristic and meta-heuristic approaches seem to be good alternatives.
The main goals of our research are, first of all to devise a good representation for the PDPTW. Our concern here is how a solution to such complicated problem can be efficiently represented, such that all problem constraints are reflected and adhered with, without complicating the solution methodology. Our second goal is to develop effective operators that can be applied to make intelligent neighbourhood moves capable of directing a heuristic or ameta-heuristic search towards high quality solutions. A major challenge is to avoid inefficiencies that can too easily result if large numbers of infeasible solutions (that violate one or more of the hard constraints) are generated.
References and publications can be found here