Simultaneous optimization of speed and buffer times with an application to liner shipping

Judith Mulder, Willem van Jaarsveld, Rommert Dekker

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)

Abstract

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 tomodel randomevents 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 10millionU.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.

Original languageEnglish
Pages (from-to)365-382
Number of pages18
JournalTransportation Science
Volume53
Issue number2
DOIs
Publication statusPublished - 1 Mar 2019

Fingerprint

shipping
Freight transportation
Sailing vessels
cost reduction
costs
Cost reduction
dollar
Sensitivity analysis
Containers
Costs
Industry
time

Keywords

  • (online) speed optimization
  • robust timetabling
  • stochastic dynamic programming

Cite this

@article{571e107f2a424844a71dd02e3bb1c236,
title = "Simultaneous optimization of speed and buffer times with an application to liner shipping",
abstract = "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 tomodel randomevents 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 10millionU.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.",
keywords = "(online) speed optimization, robust timetabling, stochastic dynamic programming",
author = "Judith Mulder and {van Jaarsveld}, Willem and Rommert Dekker",
year = "2019",
month = "3",
day = "1",
doi = "10.1287/trsc.2018.0842",
language = "English",
volume = "53",
pages = "365--382",
journal = "Transportation Science",
issn = "0041-1655",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "2",

}

Simultaneous optimization of speed and buffer times with an application to liner shipping. / Mulder, Judith; van Jaarsveld, Willem; Dekker, Rommert.

In: Transportation Science, Vol. 53, No. 2, 01.03.2019, p. 365-382.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Simultaneous optimization of speed and buffer times with an application to liner shipping

AU - Mulder, Judith

AU - van Jaarsveld, Willem

AU - Dekker, Rommert

PY - 2019/3/1

Y1 - 2019/3/1

N2 - 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 tomodel randomevents 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 10millionU.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.

AB - 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 tomodel randomevents 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 10millionU.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.

KW - (online) speed optimization

KW - robust timetabling

KW - stochastic dynamic programming

UR - http://www.scopus.com/inward/record.url?scp=85067574638&partnerID=8YFLogxK

U2 - 10.1287/trsc.2018.0842

DO - 10.1287/trsc.2018.0842

M3 - Article

AN - SCOPUS:85067574638

VL - 53

SP - 365

EP - 382

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 2

ER -