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 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 a breadth of instances show that advance time related information, if used intelligently, can yield benefits. Furthermore, we showthat it is beneficial to tailor the consensus function that is used in the sample-scenario approach to the specifics of the problem setting. By doing so, our strategy performs well on instances with both short time windows and limited advance confirmation.

Additional Metadata
Keywords Pickup and delivery problem with time windows, Sample scenario strategy, Time window uncertainty
Sponsor The authors gratefully acknowledge a grant from the Lebanese American University in support of this research.
Persistent URL dx.doi.org/10.1287/trsc.2015.0658, hdl.handle.net/1765/105203
Journal Transportation Science
Note This paper has been accepted for the TSL Workshop Transportation Science Special Issue on Uncertainty in Logistics and Transportation Systems.
Citation
Srour, F.J, Agatz, N.A.H, & Oppen, J. (2016). Strategies for handling temporal uncertainty in pickup and delivery problems with time windows. Transportation Science, 52(1), 3–19. doi:10.1287/trsc.2015.0658