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

Mixed Integer Formulations for a Short Sea Fuel Oil Distribution Problem

Author

Listed:
  • Agostinho Agra

    (Department of Mathematics, University of Aveiro, 3810-193 Aveiro, Portugal)

  • Marielle Christiansen

    (Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, NO-7491 Trondheim, Norway)

  • Alexandrino Delgado

    (Cape Verde University, CP 163 Mindelo, Cape Verde)

Abstract

We consider a short sea fuel oil distribution problem occurring in the archipelago at Cape Verde. Here, an oil company is responsible for the routing and scheduling of ships between the islands such that the demand for various fuel oil products is satisfied during the planning horizon. Inventory management considerations are taken into account at the demand side but not at the supply side. The ports have restricted opening hours each day, so multiple time windows are considered. In contrast to the ships in many other studies within ship routing and scheduling, ships here spend considerable time in the ports compared to at sea. Hence, the time in port is modeled in detail by incorporating both a variable (un)loading time and a setup time for loading different products in the same ports. A mathematical model of the problem is presented and it includes a combined continuous and discrete time horizon because of the multiple time windows and a daily varying consumption rate of the various products in the different ports. We discuss several strategies to improve the proposed model, such as tightening bounds, using extended formulations, and including valid inequalities. The computational study shows that the real problem can be solved to optimality within reasonable time by the use of improved formulations based on a combination of such strategies.

Suggested Citation

  • Agostinho Agra & Marielle Christiansen & Alexandrino Delgado, 2013. "Mixed Integer Formulations for a Short Sea Fuel Oil Distribution Problem," Transportation Science, INFORMS, vol. 47(1), pages 108-124, February.
    • Handle: RePEc:inm:ortrsc:v:47:y:2013:i:1:p:108-124
    DOI: 10.1287/trsc.1120.0416
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1120.0416
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1120.0416?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. Hugues Marchand & Laurence A. Wolsey, 2001. "Aggregation and Mixed Integer Rounding to Solve MIPs," Operations Research, INFORMS, vol. 49(3), pages 363-371, June.
    2. Marielle Christiansen & Bjorn Nygreen, 1998. "A method for solving ship routing problemswith inventory constraints," Annals of Operations Research, Springer, vol. 81(0), pages 357-378, June.
    3. Fagerholt, Kjetil, 2001. "Ship scheduling with soft time windows: An optimisation based approach," European Journal of Operational Research, Elsevier, vol. 131(3), pages 559-571, June.
    4. Koorush Ziarati & François Soumis & Jacques Desrosiers & Marius M. Solomon, 1999. "A Branch-First, Cut-Second Approach for Locomotive Assignment," Management Science, INFORMS, vol. 45(8), pages 1156-1168, August.
    5. Marielle Christiansen & Bjørn Nygreen, 2005. "Robust Inventory Ship Routing by Column Generation," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 197-224, Springer.
    6. Marielle Christiansen, 1999. "Decomposition of a Combined Inventory and Time Constrained Ship Routing Problem," Transportation Science, INFORMS, vol. 33(1), pages 3-16, February.
    7. Al-Khayyal, Faiz & Hwang, Seung-June, 2007. "Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, Part I: Applications and model," European Journal of Operational Research, Elsevier, vol. 176(1), pages 106-130, January.
    8. Marielle Christiansen & Bjørn Nygreen, 1998. "Modelling path flows for a combined ship routingand inventory management problem," Annals of Operations Research, Springer, vol. 82(0), pages 391-413, August.
    9. 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.
    10. D Ronen, 2002. "Marine inventory routing: shipments planning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(1), pages 108-114, January.
    11. M. W. Padberg & T. J. Van Roy & L. A. Wolsey, 1985. "Valid Linear Inequalities for Fixed Charge Problems," Operations Research, INFORMS, vol. 33(4), pages 842-861, August.
    12. MARCHAND, Hugues & WOLSEY, Laurence A., 2001. "Aggregation and mixed integer rounding to solve mips," LIDAM Reprints CORE 1513, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. 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.
    14. 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.
    15. Padberg, M.W. & Van Roy, T.J. & Wolsey, L.A., 1985. "Valid linear inequalities for fixed charge problems," LIDAM Reprints CORE 656, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. 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.
    2. Ioannis Fragkos & Bert De Reyck, 2016. "Improving the Maritime Transshipment Operations of the Noble Group," Interfaces, INFORMS, vol. 46(3), pages 203-217, April.
    3. Papageorgiou, Dimitri J. & Nemhauser, George L. & Sokol, Joel & Cheon, Myun-Seok & Keha, Ahmet B., 2014. "MIRPLib – A library of maritime inventory routing problem instances: Survey, core model, and benchmark results," European Journal of Operational Research, Elsevier, vol. 235(2), pages 350-366.
    4. Miranda, Pablo A. & Blazquez, Carola A. & Vergara, Rodrigo & Weitzler, Sebastian, 2015. "A novel methodology for designing a household waste collection system for insular zones," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 77(C), pages 227-247.
    5. Archetti, Claudia & Christiansen, Marielle & Grazia Speranza, M., 2018. "Inventory routing with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 268(1), pages 314-324.
    6. 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.
    7. Li, Feng & Yang, Dong & Wang, Shuaian & Weng, Jinxian, 2019. "Ship routing and scheduling problem for steel plants cluster alongside the Yangtze River," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 198-210.
    8. Archetti, Claudia & Speranza, M. Grazia & Boccia, Maurizio & Sforza, Antonio & Sterle, Claudio, 2020. "A branch-and-cut algorithm for the inventory routing problem with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 282(3), pages 886-895.
    9. 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.
    10. Zelda B. Zabinsky & Pattamon Dulyakupt & Shabnam Zangeneh-Khamooshi & Cao Xiao & Pengbo Zhang & Seksan Kiatsupaibul & Joseph A. Heim, 2020. "Optimal collection of medical specimens and delivery to central laboratory," Annals of Operations Research, Springer, vol. 287(1), pages 537-564, April.
    11. Hemmati, Ahmad & Hvattum, Lars Magnus & Christiansen, Marielle & Laporte, Gilbert, 2016. "An iterative two-phase hybrid matheuristic for a multi-product short sea inventory-routing problem," European Journal of Operational Research, Elsevier, vol. 252(3), pages 775-788.
    12. Agra, Agostinho & Christiansen, Marielle & Wolsey, Laurence, 2022. "Improved models for a single vehicle continuous-time inventory routing problem with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 297(1), pages 164-179.
    13. Christiansen, Marielle & Fagerholt, Kjetil & Rachaniotis, Nikolaos P. & Stålhane, Magnus, 2017. "Operational planning of routes and schedules for a fleet of fuel supply vessels," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 163-175.
    14. De, Arijit & Choudhary, Alok & Turkay, Metin & Tiwari, Manoj K., 2021. "Bunkering policies for a fuel bunker management problem for liner shipping networks," European Journal of Operational Research, Elsevier, vol. 289(3), pages 927-939.
    15. Kirschstein, Thomas, 2018. "Rail transportation planning in the chemical industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 112(C), pages 142-160.
    16. Katrin Heßler & Stefan Irnich, 2021. "Partial Dominance in Branch-Price-and-Cut for the Basic Multi-Compartment Vehicle-Routing Problem," Working Papers 2115, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    17. Agostinho Agra & Marielle Christiansen & Lars Magnus Hvattum & Filipe Rodrigues, 2018. "Robust Optimization for a Maritime Inventory Routing Problem," Transportation Science, INFORMS, vol. 52(3), pages 509-525, June.
    18. Ostermeier, Manuel & Henke, Tino & Hübner, Alexander & Wäscher, Gerhard, 2021. "Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 799-817.
    19. Jørgen Bjaarstad Nikolaisen & Sofie Smith Vågen & Peter Schütz, 2023. "Solving a maritime inventory routing problem under uncertainty using optimization and simulation," Computational Management Science, Springer, vol. 20(1), pages 1-27, 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. 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.
    2. 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.
    3. Faramroze G. Engineer & Kevin C. Furman & George L. Nemhauser & Martin W. P. Savelsbergh & Jin-Hwa Song, 2012. "A Branch-Price-and-Cut Algorithm for Single-Product Maritime Inventory Routing," Operations Research, INFORMS, vol. 60(1), pages 106-122, February.
    4. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    5. Jørgen Glomvik Rakke & Henrik Andersson & Marielle Christiansen & Guy Desaulniers, 2015. "A New Formulation Based on Customer Delivery Patterns for a Maritime Inventory Routing Problem," Transportation Science, INFORMS, vol. 49(2), pages 384-401, May.
    6. 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.
    7. 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.
    8. Papageorgiou, Dimitri J. & Nemhauser, George L. & Sokol, Joel & Cheon, Myun-Seok & Keha, Ahmet B., 2014. "MIRPLib – A library of maritime inventory routing problem instances: Survey, core model, and benchmark results," European Journal of Operational Research, Elsevier, vol. 235(2), pages 350-366.
    9. Hemmati, Ahmad & Hvattum, Lars Magnus & Christiansen, Marielle & Laporte, Gilbert, 2016. "An iterative two-phase hybrid matheuristic for a multi-product short sea inventory-routing problem," European Journal of Operational Research, Elsevier, vol. 252(3), pages 775-788.
    10. Stålhane, Magnus & Andersson, Henrik & Christiansen, Marielle & Fagerholt, Kjetil, 2014. "Vendor managed inventory in tramp shipping," Omega, Elsevier, vol. 47(C), pages 60-72.
    11. Wei-Kun Chen & Liang Chen & Mu-Ming Yang & Yu-Hong Dai, 2018. "Generalized coefficient strengthening cuts for mixed integer programming," Journal of Global Optimization, Springer, vol. 70(1), pages 289-306, January.
    12. G Brønmo & M Christiansen & B Nygreen, 2007. "Ship routing and scheduling with flexible cargo sizes," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1167-1177, September.
    13. 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.
    14. 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.
    15. Christiansen, Marielle & Fagerholt, Kjetil & Flatberg, Truls & Haugen, Øyvind & Kloster, Oddvar & Lund, Erik H., 2011. "Maritime inventory routing with multiple products: A case study from the cement industry," European Journal of Operational Research, Elsevier, vol. 208(1), pages 86-94, January.
    16. Brønmo, Geir & Nygreen, Bjørn & Lysgaard, Jens, 2010. "Column generation approaches to ship scheduling with flexible cargo sizes," European Journal of Operational Research, Elsevier, vol. 200(1), pages 139-150, January.
    17. Quentin Louveaux & Laurence Wolsey, 2007. "Lifting, superadditivity, mixed integer rounding and single node flow sets revisited," Annals of Operations Research, Springer, vol. 153(1), pages 47-77, September.
    18. Alper Atamtürk & Martin Savelsbergh, 2005. "Integer-Programming Software Systems," Annals of Operations Research, Springer, vol. 140(1), pages 67-124, November.
    19. 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.
    20. Mervat Chouman & Teodor Gabriel Crainic & Bernard Gendron, 2017. "Commodity Representations and Cut-Set-Based Inequalities for Multicommodity Capacitated Fixed-Charge Network Design," Transportation Science, INFORMS, vol. 51(2), pages 650-667, May.

    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:47:y:2013:i:1:p:108-124. 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.