IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v42y2008i3p336-351.html
   My bibliography  Save this article

A Branch-and-Price-and-Cut Method for Ship Scheduling with Limited Risk

Author

Listed:
  • Hee-Su Hwang

    (US Airways, Tempe, Arizona 85281)

  • Siriwat Visoldilokpun

    (Department of Industrial and Manufacturing Systems Engineering, University of Texas at Arlington, Arlington, Texas 76019)

  • Jay M. Rosenberger

    (Department of Industrial and Manufacturing Systems Engineering, University of Texas at Arlington, Arlington, Texas 76019)

Abstract

Maritime logistics operations are full of uncertainty such as severe weather, mechanical problems, strikes, and fluctuating freight rates. Traditional ship-scheduling models ignore uncertainty, even in highly volatile markets. Although ship operators can increase revenue by delivering many spot cargoes, they have to embrace the risk of the fluctuation of spot rates. We present a set-packing model that limits risk using a quadratic variance constraint. We use a traditional Kelley's cutting plane algorithm and a delayed column-and-cut generation (branch-and-price-and-cut) algorithm on medium-sized ship-scheduling problems with restricted variance. We develop a second set of cuts that are more restrictive under certain conditions. Computational results show that the variance of profit can be significantly reduced with a reasonable increase in cost.

Suggested Citation

  • Hee-Su Hwang & Siriwat Visoldilokpun & Jay M. Rosenberger, 2008. "A Branch-and-Price-and-Cut Method for Ship Scheduling with Limited Risk," Transportation Science, INFORMS, vol. 42(3), pages 336-351, August.
    • Handle: RePEc:inm:ortrsc:v:42:y:2008:i:3:p:336-351
    DOI: 10.1287/trsc.1070.0218
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1070.0218
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1070.0218?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Azaron, Amir & Kianfar, Farhad, 2003. "Dynamic shortest path in stochastic dynamic networks: Ship routing problem," European Journal of Operational Research, Elsevier, vol. 144(1), pages 138-156, January.
    2. Ronen, David, 1993. "Ship scheduling: The last decade," European Journal of Operational Research, Elsevier, vol. 71(3), pages 325-333, December.
    3. Gerald G. Brown & Glenn W. Graves & David Ronen, 1987. "Scheduling Ocean Transportation of Crude Oil," Management Science, INFORMS, vol. 33(3), pages 335-346, March.
    4. T. Andersson * & P. Värbrand, 2004. "The flight perturbation problem," Transportation Planning and Technology, Taylor & Francis Journals, vol. 27(2), pages 91-117, March.
    5. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    6. Ronen, David, 1983. "Cargo ships routing and scheduling: Survey of models and problems," European Journal of Operational Research, Elsevier, vol. 12(2), pages 119-126, February.
    7. Leif H. Appelgren, 1969. "A Column Generation Algorithm for a Ship Scheduling Problem," Transportation Science, INFORMS, vol. 3(1), pages 53-68, February.
    8. Leif H. Appelgren, 1971. "Integer Programming Methods for a Vessel Scheduling Problem," Transportation Science, INFORMS, vol. 5(1), pages 64-78, February.
    9. D. Chinhyung Cho & Manfred W. Padberg & M. R. Rao, 1983. "On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 590-612, November.
    10. Jay M. Rosenberger & Ellis L. Johnson & George L. Nemhauser, 2003. "Rerouting Aircraft for Airline Recovery," Transportation Science, INFORMS, vol. 37(4), pages 408-421, November.
    11. D. Chinhyung Cho & Ellis L. Johnson & Manfred Padberg & M. R. Rao, 1983. "On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 579-589, November.
    12. Anuj Mehrotra & Ellis L. Johnson & George L. Nemhauser, 1998. "An Optimization Based Heuristic for Political Districting," Management Science, INFORMS, vol. 44(8), pages 1100-1114, August.
    13. Rossi, Fabrizio & Smriglio, Stefano, 2001. "A set packing model for the ground holding problem in congested networks," European Journal of Operational Research, Elsevier, vol. 131(2), pages 400-416, June.
    14. Lo, Hong K. & McCord, Mark R., 1998. "Adaptive ship routing through stochastic ocean currents: general formulations and empirical results," Transportation Research Part A: Policy and Practice, Elsevier, vol. 32(7), pages 547-561, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ksciuk, Jana & Kuhlemann, Stefan & Tierney, Kevin & Koberstein, Achim, 2023. "Uncertainty in maritime ship routing and scheduling: A Literature review," European Journal of Operational Research, Elsevier, vol. 308(2), pages 499-524.
    2. Zhixing Luo & Hu Qin & T. C. E. Cheng & Qinghua Wu & Andrew Lim, 2021. "A Branch-and-Price-and-Cut Algorithm for the Cable-Routing Problem in Solar Power Plants," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 452-476, May.
    3. Harilaos N. Psaraftis, 2019. "Ship routing and scheduling: the cart before the horse conjecture," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 21(1), pages 111-124, March.
    4. Christiansen, Marielle & Fagerholt, Kjetil & Nygreen, Bjørn & Ronen, David, 2013. "Ship routing and scheduling in the new millennium," European Journal of Operational Research, Elsevier, vol. 228(3), pages 467-483.
    5. Pang, King-Wah & Xu, Zhou & Li, Chung-Lun, 2011. "Ship routing problem with berthing time clash avoidance constraints," International Journal of Production Economics, Elsevier, vol. 131(2), pages 752-762, June.
    6. Zhixing Luo & Hu Qin & Wenbin Zhu & Andrew Lim, 2017. "Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost," Transportation Science, INFORMS, vol. 51(2), pages 668-687, May.
    7. Wu, Lingxiao & Wang, Shuaian & Laporte, Gilbert, 2021. "The Robust Bulk Ship Routing Problem with Batched Cargo Selection," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 124-159.
    8. Asteris, Michael & Collins, Alan & Jones, Dylan F., 2012. "Container port infrastructure in north-west Europe: Policy-level modeling," Journal of Policy Modeling, Elsevier, vol. 34(2), pages 312-324.
    9. Zhijia Tan & Yadong Wang & Qiang Meng & Zhixue Liu, 2018. "Joint Ship Schedule Design and Sailing Speed Optimization for a Single Inland Shipping Service with Uncertain Dam Transit Time," Service Science, INFORMS, vol. 52(6), pages 1570-1588, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ricardo Gatica & Pablo Miranda, 2011. "Special Issue on Latin-American Research: A Time Based Discretization Approach for Ship Routing and Scheduling with Variable Speed," Networks and Spatial Economics, Springer, vol. 11(3), pages 465-485, September.
    2. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    3. Meng, Qiang & Wang, Shuaian & Lee, Chung-Yee, 2015. "A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem," Transportation Research Part B: Methodological, Elsevier, vol. 72(C), pages 1-19.
    4. Shih, Li-Hsing, 1997. "Planning of fuel coal imports using a mixed integer programming method," International Journal of Production Economics, Elsevier, vol. 51(3), pages 243-249, September.
    5. Hennig, F. & Nygreen, B. & Christiansen, M. & Fagerholt, K. & Furman, K.C. & Song, J. & Kocis, G.R. & Warrick, P.H., 2012. "Maritime crude oil transportation – A split pickup and split delivery problem," European Journal of Operational Research, Elsevier, vol. 218(3), pages 764-774.
    6. Bilgen, Bilge & Ozkarahan, Irem, 2007. "A mixed-integer linear programming model for bulk grain blending and shipping," International Journal of Production Economics, Elsevier, vol. 107(2), pages 555-571, June.
    7. Harilaos N. Psaraftis, 2019. "Ship routing and scheduling: the cart before the horse conjecture," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 21(1), pages 111-124, March.
    8. Rizvanolli, Anisa & Haupt, Alexander & Müller, Peter Marvin & Dornemann, Jorin, 2019. "Fleet based schedule optimisation for product tanker considering shipʼs stability," Chapters from the Proceedings of the Hamburg International Conference of Logistics (HICL), in: Jahn, Carlos & Kersten, Wolfgang & Ringle, Christian M. (ed.), Digital Transformation in Maritime and City Logistics: Smart Solutions for Logistics. Proceedings of the Hamburg International Conference of Logistics, volume 28, pages 395-426, Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management.
    9. Sun, Qinghe & Meng, Qiang & Chou, Mabel C., 2021. "Optimizing voyage charterparty (VCP) arrangement: Laytime negotiation and operations coordination," European Journal of Operational Research, Elsevier, vol. 291(1), pages 263-270.
    10. Kjetil Fagerholt *, 2004. "Designing optimal routes in a liner shipping problem," Maritime Policy & Management, Taylor & Francis Journals, vol. 31(4), pages 259-268, October.
    11. Lin, Dung-Ying & Tsai, Yu-Yun, 2014. "The ship routing and freight assignment problem for daily frequency operation of maritime liner shipping," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 67(C), pages 52-70.
    12. Said El Noshokaty, 2017. "Shipping Optimisation Systems (SOS): tramp optimisation perspective," Journal of Shipping and Trade, Springer, vol. 2(1), pages 1-36, December.
    13. Lin, Dung-Ying & Chang, Yu-Ting, 2018. "Ship routing and freight assignment problem for liner shipping: Application to the Northern Sea Route planning problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 110(C), pages 47-70.
    14. Ge, Fangsheng & Beullens, Patrick & Hudson, Dominic, 2021. "Optimal economic ship speeds, the chain effect, and future profit potential," Transportation Research Part B: Methodological, Elsevier, vol. 147(C), pages 168-196.
    15. Jahn, Carlos & Kersten, Wolfgang & Ringle, Christian M. (ed.), 2019. "Digital Transformation in Maritime and City Logistics: Smart Solutions for Logistics," Proceedings of the Hamburg International Conference of Logistics (HICL), Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management, volume 28, number 28.
    16. Ghosh, Sugoutam & Lee, Loo Hay & Ng, Szu Hui, 2015. "Bunkering decisions for a shipping liner in an uncertain environment with service contract," European Journal of Operational Research, Elsevier, vol. 244(3), pages 792-802.
    17. Gustavo Diz & Luiz Felipe Scavarda & Roger Rocha & Silvio Hamacher, 2014. "Decision Support System for PETROBRAS Ship Scheduling," Interfaces, INFORMS, vol. 44(6), pages 555-566, December.
    18. Fagerholt, Kjetil & Christiansen, Marielle & Magnus Hvattum, Lars & Johnsen, Trond A.V. & Vabø, Thor J., 2010. "A decision support methodology for strategic planning in maritime transportation," Omega, Elsevier, vol. 38(6), pages 465-474, December.
    19. Wang, Shuaian & Meng, Qiang, 2012. "Liner ship route schedule design with sea contingency time and port time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 615-633.
    20. Elin Halvorsen-Weare & Kjetil Fagerholt, 2013. "Routing and scheduling in a liquefied natural gas shipping problem with inventory and berth constraints," Annals of Operations Research, Springer, vol. 203(1), pages 167-186, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:42:y:2008:i:3:p:336-351. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.