IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v294y2020i1d10.1007_s10479-018-3042-5.html
   My bibliography  Save this article

Solving the petroleum replenishment and routing problem with variable demands and time windows

Author

Listed:
  • Yan Cheng Hsu

    (University at Buffalo, The State University of New York)

  • Jose L. Walteros

    (University at Buffalo, The State University of New York)

  • Rajan Batta

    (University at Buffalo, The State University of New York)

Abstract

In this paper we develop a methodological framework for designing the daily distribution and replenishment operations of petroleum products over a weekly planning horizon by taking into account the perspectives of both the transporter and its customers. The proposed approach considers the possibility of having late deliveries due to the variability of the customers’ demands and expected time windows. We first develop an inventory model for the customers to identify the optimal order quantities and time windows. Then, we solve a sequence of mixed-integer optimization models for designing distribution routes based on the order quantities and time windows selected by the inventory models. We design the optimization models so that late deliveries are balanced among the customers in order to mitigate the overall customer dissatisfaction. We test the proposed approach by solving a set of instances adapted from the literature. The empirical results show that the proposed approach can be used for designing the distribution plan for delivering petroleum products in conditions where the operational capabilities of the transporter are limited for generating optimal on-time plans.

Suggested Citation

  • Yan Cheng Hsu & Jose L. Walteros & Rajan Batta, 2020. "Solving the petroleum replenishment and routing problem with variable demands and time windows," Annals of Operations Research, Springer, vol. 294(1), pages 9-46, November.
    • Handle: RePEc:spr:annopr:v:294:y:2020:i:1:d:10.1007_s10479-018-3042-5
    DOI: 10.1007/s10479-018-3042-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-018-3042-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-018-3042-5?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. van der Bruggen, Lambert & Gruson, Ruud & Salomon, Marc, 1995. "Reconsidering the distribution structure of gasoline products for a large oil company," European Journal of Operational Research, Elsevier, vol. 81(3), pages 460-473, March.
    2. Leonardo Lozano & Daniel Duque & Andrés L. Medaglia, 2016. "An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints," Transportation Science, INFORMS, vol. 50(1), pages 348-357, February.
    3. Ann Melissa Campbell & Martin W. P. Savelsbergh, 2004. "A Decomposition Approach for the Inventory-Routing Problem," Transportation Science, INFORMS, vol. 38(4), pages 488-502, November.
    4. Henke, Tino & Speranza, M. Grazia & Wäscher, Gerhard, 2015. "The multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 246(3), pages 730-743.
    5. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    6. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    7. Dimitris J. Bertsimas, 1992. "A Vehicle Routing Problem with Stochastic Demand," Operations Research, INFORMS, vol. 40(3), pages 574-585, June.
    8. Dan O. Bausch & Gerald G. Brown & David Ronen, 1995. "Consolidating and Dispatching Truck Shipments of Mobil Heavy Petroleum Products," Interfaces, INFORMS, vol. 25(2), pages 1-17, April.
    9. 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.
    10. Brian Kallehauge & Jesper Larsen & Oli B.G. Madsen & Marius M. Solomon, 2005. "Vehicle Routing Problem with Time Windows," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 67-98, Springer.
    11. Hemmelmayr, Vera C. & Doerner, Karl F. & Hartl, Richard F., 2009. "A variable neighborhood search heuristic for periodic routing problems," European Journal of Operational Research, Elsevier, vol. 195(3), pages 791-802, June.
    12. David Ronen, 1995. "Dispatching Petroleum Products," Operations Research, INFORMS, vol. 43(3), pages 379-387, June.
    13. Cornillier, Fabien & Boctor, Fayez & Renaud, Jacques, 2012. "Heuristics for the multi-depot petrol station replenishment problem with time windows," European Journal of Operational Research, Elsevier, vol. 220(2), pages 361-369.
    14. Remy Spliet & Adriana F. Gabor, 2015. "The Time Window Assignment Vehicle Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 721-731, November.
    15. Amy Cohn & Sarah Root & Alex Wang & Douglas Mohr, 2007. "Integration of the Load-Matching and Routing Problem with Equipment Balancing for Small Package Carriers," Transportation Science, INFORMS, vol. 41(2), pages 238-252, May.
    16. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2016. "An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 95-123.
    17. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    18. Spliet, Remy & Desaulniers, Guy, 2015. "The discrete time window assignment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 244(2), pages 379-391.
    19. Gerald G. Brown & Carol J. Ellis & Glenn W. Graves & David Ronen, 1987. "Real-Time, Wide Area Dispatch of Mobil Tank Trucks," Interfaces, INFORMS, vol. 17(1), pages 107-120, February.
    20. Cornillier, Fabien & Boctor, Fayez F. & Laporte, Gilbert & Renaud, Jacques, 2008. "A heuristic for the multi-period petrol station replenishment problem," European Journal of Operational Research, Elsevier, vol. 191(2), pages 295-305, December.
    21. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    22. 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.
    23. A N Letchford & J Lysgaard & R W Eglese, 2007. "A branch-and-cut algorithm for the capacitated open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1642-1651, December.
    24. Muyldermans, L. & Pang, G., 2010. "On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm," European Journal of Operational Research, Elsevier, vol. 206(1), pages 93-103, October.
    25. Gerald G. Brown & Glenn W. Graves, 1981. "Real-Time Dispatch of Petroleum Tank Trucks," Management Science, INFORMS, vol. 27(1), pages 19-32, January.
    26. Lahyani, Rahma & Coelho, Leandro C. & Khemakhem, Mahdi & Laporte, Gilbert & Semet, Frédéric, 2015. "A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia," Omega, Elsevier, vol. 51(C), pages 1-10.
    27. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    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. Vincent F. Yu & Putu A. Y. Indrakarna & Anak Agung Ngurah Perwira Redi & Shih-Wei Lin, 2021. "Simulated Annealing with Mutation Strategy for the Share-a-Ride Problem with Flexible Compartments," Mathematics, MDPI, vol. 9(18), pages 1-18, 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. 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.
    2. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    3. Samira Mirzaei & Sanne Wøhlk, 2019. "A Branch-and-Price algorithm for two multi-compartment vehicle routing problems," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(1), pages 1-33, March.
    4. Samira Mirzaei & Sanne Wøhlk, 2017. "Erratum to: A Branch-and-Price algorithm for two multi-compartment vehicle routing problems," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 185-218, June.
    5. Bani, Abderrahman & El Hallaoui, Issmail & Corréa, Ayoub Insa & Tahir, Adil, 2023. "Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints," European Journal of Operational Research, Elsevier, vol. 311(1), pages 154-172.
    6. Furkan Uzar, M. & Çatay, Bülent, 2012. "Distribution planning of bulk lubricants at BP Turkey," Omega, Elsevier, vol. 40(6), pages 870-881.
    7. Katrin Heßler & Stefan Irnich, 2023. "Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 50-65, January.
    8. Henriette Koch & Tino Henke & Gerhard Wäscher, 2016. "A Genetic Algorithm for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," FEMM Working Papers 160004, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    9. Sun, Lijun & Zhang, Yuankai & Hu, Xiangpei, 2021. "Economical-traveling-distance-based fleet composition with fuel costs: An application in petrol distribution," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).
    10. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2019. "A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes," Annals of Operations Research, Springer, vol. 275(2), pages 321-338, April.
    11. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    12. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    13. Campelo, Pedro & Neves-Moreira, Fábio & Amorim, Pedro & Almada-Lobo, Bernardo, 2019. "Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector," European Journal of Operational Research, Elsevier, vol. 273(1), pages 131-145.
    14. Bruck, Bruno P. & Cordeau, Jean-François & Iori, Manuel, 2018. "A practical time slot management and routing problem for attended home services," Omega, Elsevier, vol. 81(C), pages 208-219.
    15. 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.
    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. Cornillier, Fabien & Boctor, Fayez & Renaud, Jacques, 2012. "Heuristics for the multi-depot petrol station replenishment problem with time windows," European Journal of Operational Research, Elsevier, vol. 220(2), pages 361-369.
    18. Han, Shuihua & Zhao, Ling & Chen, Kui & Luo, Zong-wei & Mishra, Deepa, 2017. "Appointment scheduling and routing optimization of attended home delivery system with random customer behavior," European Journal of Operational Research, Elsevier, vol. 262(3), pages 966-980.
    19. Aderemi Oluyinka Adewumi & Olawale Joshua Adeleke, 2018. "A survey of recent advances in vehicle routing problems," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(1), pages 155-172, February.
    20. Ostermeier, Manuel & Hübner, Alexander, 2018. "Vehicle selection for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 269(2), pages 682-694.

    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:spr:annopr:v:294:y:2020:i:1:d:10.1007_s10479-018-3042-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.