Strategies for Handling Temporal Uncertainty in Pickup and Delivery Problems with Time Windows

In many real-life routing problems there is more uncertainty with respect to the required timing of the service than with respect to the service locations. We focus on a pickup and delivery problem with time windows in which the pickup and drop-off locations of the service requests are fully known in advance, but the time at which these jobs will require service is known probabilistically and only fully revealed during operations. We develop a sample-scenario routing strategy to accommodate a variety of potential time realizations while designing and updating the routes. Our experiments on realistic instances show that our sample-scenario strategy performs well.