Simultaneous optimization of speed and buffer times for robust transportation systems

Transport companies often have a published timetable. To maintain timetable reliability despite delays, companies include buffer times during timetable development, and adjust the traveling speed during timetable execution. We develop an approach that can integrate decisions at different time scales (tactical and operational). We model execution of the timetable as a stochastic dynamic program (SDP). An SDP is a natural framework to model random events causing (additional) delay, propagation of delays, and real-time speed adjustments. However, SDPs alone cannot incorporate the buffer allocation, as buffer allocation requires to choose the same action in different states of the SDP. Our objective is finding the buffer allocation that yields the SDP which has minimal long run average costs. We derive several analytical insights into the model. We prove that costs are joint convex in the buffer times, and develop theory in order to compute subgradients. Our optimal algorithm for buffer time allocation is based on these results. Our case study considers container vessels sailing a round tour consisting of 14 ports based on Maersk data. Our algorithm finds the optimal timetable in less than 80 seconds. The optimal timetable yields cost reductions of about six to ten million USD per route per year in comparison to the current timetable.