IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v218y2012i3p764-774.html
   My bibliography  Save this article

Maritime crude oil transportation – A split pickup and split delivery problem

Author

Listed:
  • Hennig, F.
  • Nygreen, B.
  • Christiansen, M.
  • Fagerholt, K.
  • Furman, K.C.
  • Song, J.
  • Kocis, G.R.
  • Warrick, P.H.

Abstract

The maritime oil tanker routing and scheduling problem is known to the literature since before 1950. In the presented problem, oil tankers transport crude oil from supply points to demand locations around the globe. The objective is to find ship routes, load sizes, as well as port arrival and departure times, in a way that minimizes transportation costs. We introduce a path flow model where paths are ship routes. Continuous variables distribute the cargo between the different routes. Multiple products are transported by a heterogeneous fleet of tankers. Pickup and delivery requirements are not paired to cargos beforehand and arbitrary split of amounts is allowed. Small realistic test instances can be solved with route pre-generation for this model. The results indicate possible simplifications and stimulate further research.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:218:y:2012:i:3:p:764-774
    DOI: 10.1016/j.ejor.2011.09.046
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711008964
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2011.09.046?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Rejoinder on: Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 45-47, July.
    2. 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.
    3. M. Bellmore & G. Bennington & S. Lubore, 1971. "A Multivehicle Tanker Scheduling Problem," Transportation Science, INFORMS, vol. 5(1), pages 36-47, February.
    4. Leif H. Appelgren, 1969. "A Column Generation Algorithm for a Ship Scheduling Problem," Transportation Science, INFORMS, vol. 3(1), pages 53-68, February.
    5. Gerardo Berbeglia & Jean-François Cordeau & Irina Gribkovskaia & Gilbert Laporte, 2007. "Static pickup and delivery problems: a classification scheme and survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 1-31, July.
    6. Lawrence E. Briskin, 1966. "Selecting Delivery Dates in the Tanker Scheduling Problem," Management Science, INFORMS, vol. 12(6), pages 224-235, February.
    7. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    8. Archetti, Claudia & Savelsbergh, Martin W.P. & Grazia Speranza, M., 2008. "To split or not to split: That is the question," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 44(1), pages 114-123, January.
    9. Leif H. Appelgren, 1971. "Integer Programming Methods for a Vessel Scheduling Problem," Transportation Science, INFORMS, vol. 5(1), pages 64-78, February.
    10. Maciek Nowak & Özlem Ergun & Chelsea C. White, 2008. "Pickup and Delivery with Split Loads," Transportation Science, INFORMS, vol. 42(1), pages 32-43, February.
    11. Persson, Jan A. & Gothe-Lundgren, Maud, 2005. "Shipment planning at oil refineries using column generation and valid inequalities," European Journal of Operational Research, Elsevier, vol. 163(3), pages 631-652, June.
    12. Merrill M. Flood, 1954. "Application of Transportation Theory to Scheduling a Military Tanker Fleet," Operations Research, INFORMS, vol. 2(2), pages 150-162, May.
    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.
    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. Chen, Qingfeng & Li, Kunpeng & Liu, Zhixue, 2014. "Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 218-235.
    2. Dimitri J. Papageorgiou & Ahmet B. Keha & George L. Nemhauser & Joel Sokol, 2014. "Two-Stage Decomposition Algorithms for Single Product Maritime Inventory Routing," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 825-847, November.
    3. Wang, Shuang & Jia, Haiying & Lu, Jing & Yang, Dong, 2023. "Crude oil transportation route choices: A connectivity reliability-based approach," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    4. Wang, Shuang & Wallace, Stein W. & Lu, Jing & Gu, Yewen, 2020. "Handling financial risks in crude oil imports: Taking into account crude oil prices as well as country and transportation risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    5. Frank Hennig & Bjørn Nygreen & Marco E. Lübbecke, 2012. "Nested column generation applied to the crude oil tanker routing and scheduling problem with split pickup and split delivery," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 298-310, April.
    6. Ditta, A. & Figueroa, O. & Galindo, G. & Yie-Pinedo, R., 2019. "A review on research in transportation of hazardous materials," Socio-Economic Planning Sciences, Elsevier, vol. 68(C).
    7. Hennig, F. & Nygreen, B. & Furman, K.C. & Song, J., 2015. "Alternative approaches to the crude oil tanker routing and scheduling problem with split pickup and split delivery," European Journal of Operational Research, Elsevier, vol. 243(1), pages 41-51.
    8. Rigot-Müller, Patrick & Cheaitou, Ali & Etienne, Laurent & Faury, Olivier & Fedi, Laurent, 2022. "The role of polarseaworthiness in shipping planning for infrastructure projects in the Arctic: The case of Yamal LNG plant," Transportation Research Part A: Policy and Practice, Elsevier, vol. 155(C), pages 330-353.
    9. 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.
    10. Xu, Dongyang & Li, Kunpeng & Zou, Xuxia & Liu, Ling, 2017. "An unpaired pickup and delivery vehicle routing problem with multi-visit," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 218-247.

    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. 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.
    2. 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.
    3. 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.
    4. Hennig, F. & Nygreen, B. & Furman, K.C. & Song, J., 2015. "Alternative approaches to the crude oil tanker routing and scheduling problem with split pickup and split delivery," European Journal of Operational Research, Elsevier, vol. 243(1), pages 41-51.
    5. 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.
    6. Sophie N. Parragh & Jorge Pinho de Sousa & Bernardo Almada-Lobo, 2015. "The Dial-a-Ride Problem with Split Requests and Profits," Transportation Science, INFORMS, vol. 49(2), pages 311-334, May.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Gábor Nagy & Niaz A. Wassan & M. Grazia Speranza & Claudia Archetti, 2015. "The Vehicle Routing Problem with Divisible Deliveries and Pickups," Transportation Science, INFORMS, vol. 49(2), pages 271-294, May.
    12. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    13. Said El Noshokaty, 2017. "Shipping Optimisation Systems (SOS): tramp optimisation perspective," Journal of Shipping and Trade, Springer, vol. 2(1), pages 1-36, December.
    14. 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.
    15. Mutlu, Fatih & Msakni, Mohamed K. & Yildiz, Hakan & Sönmez, Erkut & Pokharel, Shaligram, 2016. "A comprehensive annual delivery program for upstream liquefied natural gas supply chain," European Journal of Operational Research, Elsevier, vol. 250(1), pages 120-130.
    16. Agra, Agostinho & Christiansen, Marielle & Delgado, Alexandrino & Simonetti, Luidi, 2014. "Hybrid heuristics for a short sea inventory routing problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 924-935.
    17. Salazar-González, Juan-José & Santos-Hernández, Beatriz, 2015. "The split-demand one-commodity pickup-and-delivery travelling salesman problem," Transportation Research Part B: Methodological, Elsevier, vol. 75(C), pages 58-73.
    18. Regnier-Coudert, Olivier & McCall, John & Ayodele, Mayowa & Anderson, Steven, 2016. "Truck and trailer scheduling in a real world, dynamic and heterogeneous context," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 389-408.
    19. Leandro C. Coelho & Jean-François Cordeau & Gilbert Laporte, 2014. "Thirty Years of Inventory Routing," Transportation Science, INFORMS, vol. 48(1), pages 1-19, February.
    20. Brønmo, Geir & Nygreen, Bjørn & Lysgaard, Jens, 2006. "Column generation approaches to ship scheduling with flexible cargo sizes," CORAL Working Papers L-2006-07, University of Aarhus, Aarhus School of Business, Department of Business Studies.

    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:eee:ejores:v:218:y:2012:i:3:p:764-774. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.