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

Optimal Solution of Vehicle Routing Problems with Fractional Objective Function

Author

Listed:
  • Roberto Baldacci

    (Department of Electrical, Electronic, and Information Engineering “Guglielmo Marconi,” 47521 Cesena, Italy)

  • Andrew Lim

    (Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore 117576, Singapore)

  • Emiliano Traversi

    (Laboratoire d’Informatique de Paris Nord, Université de Paris 13; and Sorbonne Paris Cité, CNRS (UMR 7538), France)

  • Roberto Wolfler Calvo

    (Laboratoire d’Informatique de Paris Nord, Université de Paris 13; and Sorbonne Paris Cité, CNRS (UMR 7538), France; Dipartimento di Matematica e Informatica, Università degli Studi di Cagliari, 09124 Cagliari, Italy)

Abstract

In this paper, we consider the vehicle routing problem (VRP) with fractional objective function. We investigate how the principal techniques used either in the context of fractional programming or in the context of vehicle routing problems interact. We present new dual and primal bounding procedures that have been incorporated in an exact method. The method proposed allows extending specific variants of the VRP to their counterpart with a fractional objective function. Extensive numerical experiments prove the validity of our approach.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:54:y:2020:i:2:p:434-452
    DOI: 10.1287/trsc.2019.0929
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2019.0929
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2019.0929?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. Thierry Benoist & Frédéric Gardi & Antoine Jeanjean & Bertrand Estellon, 2011. "Randomized Local Search for Real-Life Inventory Routing," Transportation Science, INFORMS, vol. 45(3), pages 381-398, August.
    2. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    3. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    4. Bazsa, E. M. & Frenk, J. B. G. & den Iseger, P. W., 2001. "Modeling of inventory control with regenerative processes," International Journal of Production Economics, Elsevier, vol. 71(1-3), pages 263-276, May.
    5. Moshe Dror & Michael Ball, 1987. "Inventory/routing: Reduction from an annual to a short‐period problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(6), pages 891-905, December.
    6. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi & Roberto Roberti, 2010. "An exact solution framework for a broad class of vehicle routing problems," Computational Management Science, Springer, vol. 7(3), pages 229-268, July.
    7. Ricardo Ródenas & M. López & Doroteo Verastegui, 1999. "Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 7(1), pages 33-70, June.
    8. 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.
    9. 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.
    10. 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.
    11. 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. Li, Yifu & Qi, Xiangtong, 2022. "A geometric branch-and-bound algorithm for the service bundle design problem," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1044-1056.

    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. Baldacci, Roberto & Hill, Alessandro & Hoshino, Edna A. & Lim, Andrew, 2017. "Pricing strategies for capacitated ring-star problems based on dynamic programming algorithms," European Journal of Operational Research, Elsevier, vol. 262(3), pages 879-893.
    2. Yu Zhang & Zhenzhen Zhang & Andrew Lim & Melvyn Sim, 2021. "Robust Data-Driven Vehicle Routing with Time Windows," Operations Research, INFORMS, vol. 69(2), pages 469-485, March.
    3. 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.
    4. Zhenzhen Zhang & Zhixing Luo & Roberto Baldacci & Andrew Lim, 2021. "A Benders Decomposition Approach for the Multivehicle Production Routing Problem with Order-up-to-Level Policy," Transportation Science, INFORMS, vol. 55(1), pages 160-178, 1-2.
    5. Baldacci, Roberto & Hoshino, Edna A. & Hill, Alessandro, 2023. "New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems," European Journal of Operational Research, Elsevier, vol. 307(2), pages 538-553.
    6. William Cook & Sanjeeb Dash & Ricardo Fukasawa & Marcos Goycoolea, 2009. "Numerically Safe Gomory Mixed-Integer Cuts," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 641-649, November.
    7. Thiago Serra & Ryan J. O’Neil, 2020. "MIPLIBing: Seamless Benchmarking of Mathematical Optimization Problems and Metadata Extensions," SN Operations Research Forum, Springer, vol. 1(3), pages 1-6, September.
    8. 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.
    9. Saïd Echchakoui, 2020. "Why and how to merge Scopus and Web of Science during bibliometric analysis: the case of sales force literature from 1912 to 2019," Journal of Marketing Analytics, Palgrave Macmillan, vol. 8(3), pages 165-184, September.
    10. Balma, Ali & Salem, Safa Ben & Mrad, Mehdi & Ladhari, Talel, 2018. "Strong multi-commodity flow formulations for the asymmetric traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 72-79.
    11. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    12. 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.
    13. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2012. "New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 356-371, August.
    14. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    15. 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.
    16. Malaguti, Enrico & Martello, Silvano & Santini, Alberto, 2018. "The traveling salesman problem with pickups, deliveries, and draft limits," Omega, Elsevier, vol. 74(C), pages 50-58.
    17. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.
    18. Ernst Althaus & Felix Rauterberg & Sarah Ziegler, 2020. "Computing Euclidean Steiner trees over segments," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 309-325, October.
    19. Saïd Echchakoui, 0. "Why and how to merge Scopus and Web of Science during bibliometric analysis: the case of sales force literature from 1912 to 2019," Journal of Marketing Analytics, Palgrave Macmillan, vol. 0, pages 1-20.
    20. William Cook & Daniel G. Espinoza & Marcos Goycoolea, 2007. "Computing with Domino-Parity Inequalities for the Traveling Salesman Problem (TSP)," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 356-365, August.

    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:434-452. 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.