IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v48y2000i5p801-810.html

A Lower Bound for the Split Delivery Vehicle Routing Problem

Author

Listed:
  • J. M. Belenguer

    (Departament d'Estadística i Investigació Operativa, Universitat de València, Dr. Moliner, 50, Burjassot, CP.- 46100, Spain)

  • M. C. Martinez

    (Departament d'Estadística i Investigació Operativa, Universitat de València, Dr. Moliner, 50, Burjassot, CP.- 46100, Spain)

  • E. Mota

    (Departament d'Estadística i Investigació Operativa, Universitat de València, Dr. Moliner, 50, Burjassot, CP.- 46100, Spain)

Abstract

In this paper we consider the Split Delivery Vehicle Routing Problem (SDVRP), a relaxation of the known Capacitated Vehicle Routing Problem (CVRP) in which the demand of any client can be serviced by more than one vehicle. We define a feasible solution of this problem, and we show that the convex hull of the associated incidence vectors is a polyhedron ( P SDVRP ), whose dimension depends on whether a vehicle visiting a client must service, or not, at least one unit of the client demand. From a partial and linear description of P SDVRP and a new family of valid inequalities, we develop a lower bound whose quality is exhibited in the computational results provided, which include the optimal resolution of some known instances---one of them with 50 clients. This instance is, as far as we know, the biggest one solved so far.

Suggested Citation

  • J. M. Belenguer & M. C. Martinez & E. Mota, 2000. "A Lower Bound for the Split Delivery Vehicle Routing Problem," Operations Research, INFORMS, vol. 48(5), pages 801-810, October.
    • Handle: RePEc:inm:oropre:v:48:y:2000:i:5:p:801-810
    DOI: 10.1287/opre.48.5.801.12407
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.48.5.801.12407
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.48.5.801.12407?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. Moshe Dror & Pierre Trudeau, 1989. "Savings by Split Delivery Routing," Transportation Science, INFORMS, vol. 23(2), pages 141-145, May.
    2. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    3. Gerard Sierksma & Gert Tijssen, 1998. "Routing helicopters for crew exchanges on off-shore locations," Annals of Operations Research, Springer, vol. 76(0), pages 261-286, January.
    Full references (including those not matched with items on IDEAS)

    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. Mette Gamst & Richard Martin Lusby & Stefan Ropke, 2024. "Exact and Heuristic Methods for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 58(4), pages 741-760, July.
    2. 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.
    3. 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.
    4. Barbato, Michele & Gouveia, Luís, 2024. "The Hamiltonian p-median problem: Polyhedral results and branch-and-cut algorithms," European Journal of Operational Research, Elsevier, vol. 316(2), pages 473-487.
    5. 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.
    6. Fatmah Almathkour & Ibrahima Diarrassouba & Youssouf Hadhbi, 2025. "Extended formulation and Branch-and-Cut-and-Price algorithm for the two connected subgraph problem with disjunctive constraints," Annals of Operations Research, Springer, vol. 351(1), pages 965-991, August.
    7. 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.
    8. 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.
    9. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    10. 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.
    11. Shi, Zhiyuan & Hong, Shaozhi & Wang, Zeling & Li, Ang, 2026. "Exact solution approaches for the traveling salesman problem with a drone station," European Journal of Operational Research, Elsevier, vol. 328(3), pages 845-861.
    12. Bernardino, Raquel & Paias, Ana, 2018. "Solving the family traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 267(2), pages 453-466.
    13. 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.
    14. 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.
    15. 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.
    16. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    17. Nowak, Maciek & Ergun, Ozlem & White III, Chelsea C., 2009. "An empirical study on the benefit of split loads with the pickup and delivery problem," European Journal of Operational Research, Elsevier, vol. 198(3), pages 734-740, November.
    18. Rafael Blanquero & Emilio Carrizosa & Amaya Nogales-Gómez & Frank Plastria, 2014. "Single-facility huff location problems on networks," Annals of Operations Research, Springer, vol. 222(1), pages 175-195, November.
    19. Sattar Sattari & Mohammad Izadi, 2017. "An exact algorithm for the minimum dilation triangulation problem," Journal of Global Optimization, Springer, vol. 69(2), pages 343-367, October.
    20. Galli, Laura & Martello, Silvano & Toth, Paolo, 2025. "The quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 326(1), pages 1-12.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:oropre:v:48:y:2000:i:5:p:801-810. 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.