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

A Heuristic Branch-Cut-and-Price Algorithm for the ROADEF/EURO Challenge on Inventory Routing

Author

Listed:
  • Nabil Absi

    (Mines Saint-Étienne and LIMOS UMR CNRS 6158, CMP Georges Charpak, F-13541 Gardanne, France;)

  • Diego Cattaruzza

    (Université Lille, CNRS, Centrale Lille, Inria, UMR 9189 – CRIStAL, Centre de Recherche en Informatique Signal et Automatique de Lille, F-59000 Lille, France)

  • Dominique Feillet

    (Mines Saint-Étienne and LIMOS UMR CNRS 6158, CMP Georges Charpak, F-13541 Gardanne, France;)

  • Maxime Ogier

    (Université Lille, CNRS, Centrale Lille, Inria, UMR 9189 – CRIStAL, Centre de Recherche en Informatique Signal et Automatique de Lille, F-59000 Lille, France)

  • Frédéric Semet

    (Université Lille, CNRS, Centrale Lille, Inria, UMR 9189 – CRIStAL, Centre de Recherche en Informatique Signal et Automatique de Lille, F-59000 Lille, France)

Abstract

This paper is part of the special section devoted to the ROADEF/EURO challenge on inventory routing. We propose an extended formulation that we address with a heuristic branch-cut-and-price method. Among the difficulties that we had to face are a fractional objective function, the simultaneous generation of constraints and columns, and a complex pricing problem. We evaluate our approach on the benchmark instances proposed for the challenge.

Suggested Citation

  • Nabil Absi & Diego Cattaruzza & Dominique Feillet & Maxime Ogier & Frédéric Semet, 2020. "A Heuristic Branch-Cut-and-Price Algorithm for the ROADEF/EURO Challenge on Inventory Routing," Transportation Science, INFORMS, vol. 54(2), pages 313-329, March.
    • Handle: RePEc:inm:ortrsc:v:54:y:2020:i:2:p:313-329
    DOI: 10.1287/trsc.2019.0961
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2019.0961
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2019.0961?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. 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.
    2. Guy Desaulniers, 2010. "Branch-and-Price-and-Cut for the Split-Delivery Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 58(1), pages 179-192, February.
    3. A. Charnes & W. W. Cooper, 1962. "Programming with linear fractional functionals," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 9(3‐4), pages 181-186, September.
    4. Claudia Archetti & Guy Desaulniers & M. Grazia Speranza, 2017. "Minimizing the logistic ratio in the inventory routing problem," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 289-306, December.
    5. Hernandez, Florent & Feillet, Dominique & Giroudeau, Rodolphe & Naud, Olivier, 2016. "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 249(2), pages 551-559.
    6. S. Michel & F. Vanderbeck, 2012. "A Column-Generation Based Tactical Planning Method for Inventory Routing," Operations Research, INFORMS, vol. 60(2), pages 382-397, April.
    7. Werner Dinkelbach, 1967. "On Nonlinear Fractional Programming," Management Science, INFORMS, vol. 13(7), pages 492-498, March.
    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. Jean André & Eric Bourreau & Roberto Wolfler Calvo, 2020. "Introduction to the Special Section: ROADEF/EURO Challenge 2016—Inventory Routing Problem," Transportation Science, INFORMS, vol. 54(2), pages 299-301, March.

    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. Tunjo Perić & Josip Matejaš & Zoran Babić, 2023. "Advantages, sensitivity and application efficiency of the new iterative method to solve multi-objective linear fractional programming problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(3), pages 751-767, September.
    2. Harald Dyckhoff & Katrin Allen, 1999. "Theoretische Begründung einer Effizienzanalyse mittels Data Envelopment Analysis (DEA)," Schmalenbach Journal of Business Research, Springer, vol. 51(5), pages 411-436, May.
    3. Maziar Sahamkhadam, 2021. "Dynamic copula-based expectile portfolios," Journal of Asset Management, Palgrave Macmillan, vol. 22(3), pages 209-223, May.
    4. Laurent Alfandari & Alborz Hassanzadeh & Ivana Ljubić, 2021. "An Exact Method for Assortment Optimization under the Nested Logit Model," Working Papers hal-02463159, HAL.
    5. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    6. Vandana Goyal & Namrata Rani & Deepak Gupta, 2022. "An algorithm for quadratically constrained multi-objective quadratic fractional programming with pentagonal fuzzy numbers," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 32(1), pages 49-71.
    7. Roberto Baldacci & Andrew Lim & Emiliano Traversi & Roberto Wolfler Calvo, 2020. "Optimal Solution of Vehicle Routing Problems with Fractional Objective Function," Transportation Science, INFORMS, vol. 54(2), pages 434-452, March.
    8. Niu, Geng & Zheng, Yi & Han, Feng & Qin, Huapeng, 2019. "The nexus of water, ecosystems and agriculture in arid areas: A multiobjective optimization study on system efficiencies," Agricultural Water Management, Elsevier, vol. 223(C), pages 1-1.
    9. Claudia Archetti & Guy Desaulniers & M. Grazia Speranza, 2017. "Minimizing the logistic ratio in the inventory routing problem," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 289-306, December.
    10. Zu-Jun Ma & Fei Yang & Ying Dai & Zuo-Jun Max Shen, 2021. "The Migratory Beekeeping Routing Problem: Model and an Exact Algorithm," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 319-335, January.
    11. Huang, Nan & Li, Jiliu & Zhu, Wenbin & Qin, Hu, 2021. "The multi-trip vehicle routing problem with time windows and unloading queue at depot," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    12. 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.
    13. Vandana Goyal & Namrata Rani & Deepak Gupta, 2022. "Rouben Ranking Function and parametric approach to quadratically constrained multiobjective quadratic fractional programming with trapezoidal fuzzy number coefficients," 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. 13(2), pages 923-932, April.
    14. Alfandari, Laurent & Hassanzadeh, Alborz & Ljubic, Ivana, 2020. "An Exact Method for Assortment Optimization under the Nested Logit Model," ESSEC Working Papers WP2001, ESSEC Research Center, ESSEC Business School, revised 2020.
    15. Archetti, Claudia & Coelho, Leandro C. & Grazia Speranza, M., 2019. "An exact algorithm for the inventory routing problem with logistic ratio," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 131(C), pages 96-107.
    16. Mojtaba Borza & Azmin Sham Rambely, 2021. "A Linearization to the Sum of Linear Ratios Programming Problem," Mathematics, MDPI, vol. 9(9), pages 1-10, April.
    17. Yun He & Christian Artigues & Cyril Briand & Nicolas Jozefowiez & Sandra Ulrich Ngueveu, 2020. "A Matheuristic with Fixed-Sequence Reoptimization for a Real-Life Inventory Routing Problem," Transportation Science, INFORMS, vol. 54(2), pages 355-374, March.
    18. M. Barkhagen & S. García & J. Gondzio & J. Kalcsics & J. Kroeske & S. Sabanis & A. Staal, 2023. "Optimising portfolio diversification and dimensionality," Journal of Global Optimization, Springer, vol. 85(1), pages 185-234, January.
    19. Ritu Arora & Kavita Gupta, 2018. "Branch and bound algorithm for discrete multi- level linear fractional programming problem," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 28(2), pages 5-21.
    20. Maziar Sahamkhadam & Andreas Stephan, 2023. "Portfolio optimization based on forecasting models using vine copulas: An empirical assessment for global financial crises," Journal of Forecasting, John Wiley & Sons, Ltd., vol. 42(8), pages 2139-2166, December.

    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:54:y:2020:i:2:p:313-329. 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.