Problem Abstract:

The Pickup and Delivery Problem with Time Windows (PDPTW) is a vehicle routing problem with added constraints in the form of time windows. These time windows are distinctive to each shipment and determine what the earliest and latest times a truck can service that shipment.

Problem Explanation:

The pickup and delivery problem, using time windows, or simply the PDPTW, uses the Zeus system to route vehicles to meet predetermined time constraints. The time constraints are the windows of time that must be met by a vehicle making a pickup or delivery in that vehicle’s particular route. The time constraints are hard, meaning that there is no leeway. A vehicle cannot make a pickup or delivery one or more units of time earlier or later than what is already set by the standard input of data. If a vehicle arrives before the early time for a shipment, it has to wait to service that shipment.

The standard input of data includes the polar coordinates of the single depot where all of the vehicles are based. The input file also includes the information for each particular customer. A customer can either be a pickup or a delivery. The standard data file gives the information as to whether the shipment is a pickup or delivery and how many units of capacity that shipment will add (pickup) or subtract (delivery) from the total capacity held by the vehicle. The data file gives the earliest time a shipment can be picked up or delivered and also the latest time. The latest time minus the earliest time is the amount of time for that particular shipment’s time window. Some windows are more constraining than others. Finally, the data file gives the information as to where the shipment must be delivered if it is a pickup.

The vehicles were limited to a coupling constraint, meaning shipments and deliveries are coupled together and must be serviced by the same vehicle. After determining the route a vehicle will take, there must be an even number of shipments on the vehicle. That is, if a vehicle picks up a shipment, then that shipment must be delivered by that vehicle.

A vehicle cannot travel over a certain distance/time. That is, although there is no limit as to how many vehicles can be used in the routing system, a vehicle is limited as to how far/long it can travel before returning to the depot for the end of the trip.

The goal of the problem is to have the system produce extremely efficient results. Not only should the system minimize distance traveled, it should in turn, reduce the number of vehicles used. The system should also optimize the routes taken by the vehicles and their respective waiting times at shipments and deliveries.

Results

253