IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v36y1989i1p27-42.html
   My bibliography  Save this article

An interactive optimization system for bulk‐cargo ship scheduling

Author

Listed:
  • Marshall L. Fisher
  • Moshe B. Rosenwein

Abstract

This article considers the efficient scheduling of a fleet of ships engaged in pickup and delivery of bulk cargoes. Our optimization system begins by generating a menu of candidate schedules for each ship. This menu can contain all feasible solutions, which guarantees we will find an optimal solution or can be heuristically limited to contain only those schedules likely to be in an optimal solution. The problem of choosing from this menu an optimal schedule for the fleet is formulated as a set‐packing problem and solved with a dual algorithm. Computational experience is presented based on real data obtained from the Military Sealift Command of the U. S. Navy. Run times for this data were reasonable and solutions were generated with the potential of saving up to about $30 million per year over the manual system currently in place. We also describe a color‐graphics interface developed to facilitate interaction with the optimization system.

Suggested Citation

  • Marshall L. Fisher & Moshe B. Rosenwein, 1989. "An interactive optimization system for bulk‐cargo ship scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 36(1), pages 27-42, February.
    • Handle: RePEc:wly:navres:v:36:y:1989:i:1:p:27-42
    DOI: 10.1002/1520-6750(198902)36:13.0.CO;2-0
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(198902)36:13.0.CO;2-0
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(198902)36:13.0.CO;2-0?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. Kenneth L. Stott & Burnie W. Douglas, 1981. "A Model-Based Decision Support System for Planning and Scheduling Ocean-Borne Transportation," Interfaces, INFORMS, vol. 11(4), pages 1-10, August.
    2. Leif H. Appelgren, 1969. "A Column Generation Algorithm for a Ship Scheduling Problem," Transportation Science, INFORMS, vol. 3(1), pages 53-68, February.
    3. Lawrence E. Briskin, 1966. "Selecting Delivery Dates in the Tanker Scheduling Problem," Management Science, INFORMS, vol. 12(6), pages 224-235, February.
    4. Leif H. Appelgren, 1971. "Integer Programming Methods for a Vessel Scheduling Problem," Transportation Science, INFORMS, vol. 5(1), pages 64-78, February.
    5. J. Laderman & L. Gleiberman & J. F. Egan, 1966. "Vessel allocation by linear programming," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 13(3), pages 315-320, September.
    6. M. Bellmore & G. Bennington & S. Lubore, 1968. "A maximum utility solution to a vehicle constrained tanker scheduling problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 15(3), pages 403-411, September.
    7. Merrill M. Flood, 1954. "Application of Transportation Theory to Scheduling a Military Tanker Fleet," Operations Research, INFORMS, vol. 2(2), pages 150-162, May.
    8. FISHER, Marshall L. & WOLSEY, Laurence A., 1982. "On the greedy heuristic for continuous covering and packing problems," LIDAM Reprints CORE 505, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. C. A. Olson & E. E. Sorenson & W. J. Sullivan, 1969. "Medium-Range Scheduling for a Freighter Fleet," Operations Research, INFORMS, vol. 17(4), pages 565-582, August.
    10. M. D. McKay & H. O. Hartley, 1974. "Computerized scheduling of seagoing tankers," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 21(2), pages 255-264, June.
    11. Walter J. Bell & Louis M. Dalberto & Marshall L. Fisher & Arnold J. Greenfield & R. Jaikumar & Pradeep Kedia & Robert G. Mack & Paul J. Prutzman, 1983. "Improving the Distribution of Industrial Gases with an On-Line Computerized Routing and Scheduling Optimizer," Interfaces, INFORMS, vol. 13(6), pages 4-23, December.
    12. G. B. Dantzig & D. R. Fulkerson, 1954. "Minimizing the number of tankers to meet a fixed schedule," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(3), pages 217-222, 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. Larry W. Jacobs & Michael J. Brusco, 1995. "Note: A local‐search heuristic for large set‐covering problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(7), pages 1129-1140, October.
    2. Marielle Christiansen, 1999. "Decomposition of a Combined Inventory and Time Constrained Ship Routing Problem," Transportation Science, INFORMS, vol. 33(1), pages 3-16, February.
    3. Jinming Liu & Guoting Zhang & Lining Xing & Weihua Qi & Yingwu Chen, 2022. "An Exact Algorithm for Multi-Task Large-Scale Inter-Satellite Routing Problem with Time Windows and Capacity Constraints," Mathematics, MDPI, vol. 10(21), pages 1-24, October.
    4. Marielle Christiansen & Kjetil Fagerholt, 2002. "Robust ship scheduling with multiple time windows," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(6), pages 611-625, September.

    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. Nikiforos A. Papadakis & Anastassios N. Perakis, 1989. "A nonlinear approach to the multiorigin, multidestination fleet deployment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 36(4), pages 515-528, August.
    2. 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.
    3. 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.
    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. Zolfagharinia, Hossein & Haughton, Michael A., 2017. "Operational flexibility in the truckload trucking industry," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 437-460.
    6. 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.
    7. 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.
    8. Said El Noshokaty, 2017. "Shipping Optimisation Systems (SOS): tramp optimisation perspective," Journal of Shipping and Trade, Springer, vol. 2(1), pages 1-36, December.
    9. 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.
    10. Kristin Uggen & Marte Fodstad & Vibeke Nørstebø, 2013. "Using and extending fix-and-relax to solve maritime inventory routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(2), pages 355-377, July.
    11. 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.
    12. 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.
    13. Marielle Christiansen, 1999. "Decomposition of a Combined Inventory and Time Constrained Ship Routing Problem," Transportation Science, INFORMS, vol. 33(1), pages 3-16, February.
    14. 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.
    15. Torbjörn Larsson & Michael Patriksson, 2006. "Global Optimality Conditions for Discrete and Nonconvex Optimization---With Applications to Lagrangian Heuristics and Column Generation," Operations Research, INFORMS, vol. 54(3), pages 436-453, June.
    16. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    17. Roar Grønhaug & Marielle Christiansen & Guy Desaulniers & Jacques Desrosiers, 2010. "A Branch-and-Price Method for a Liquefied Natural Gas Inventory Routing Problem," Transportation Science, INFORMS, vol. 44(3), pages 400-415, August.
    18. 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.
    19. Bredström, David & Rönnqvist, Mikael, 2006. "Supply Chain Optimization in Pulp Distribution using a Rolling Horizon Solution Approach," Discussion Papers 2006/17, Norwegian School of Economics, Department of Business and Management Science.
    20. Wu, Lingxiao & Pan, Kai & Wang, Shuaian & Yang, Dong, 2018. "Bulk ship scheduling in industrial shipping with stochastic backhaul canvassing demand," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 117-136.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:36:y:1989:i:1:p:27-42. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.