Simultaneous Optimization of Speed and Buffer Times with an Application to Liner Shipping

摘要

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 integrates timetable development and execution. 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 optimal speed adjustments. However, SDPs alone cannot incorporate the buffer allocation during timetable development, as buffer allocation requires choosing the same action in different states of the SDP. Motivated by the practical need for timetables that operate well during timetable execution, our model seeks the buffer allocation that yields the SDP that 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 we develop theory to compute subgradients. Our fast and exact 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. The algorithm finds the optimal timetable in roughly 70 seconds for realistic problem instances. The optimal timetable yields cost reductions of about four to 10 million U.S. dollars per route per year in comparison with the current timetable. Finally, we show the robustness of our solution approach for different parameter settings using a sensitivity analysis.