A column generation approach for the split delivery vehicle routing problem

C. Archetti, N. Bianchessi, M. G. Speranza

    Research output: Contribution to JournalArticleAcademicpeer-review

    Abstract

    In this article we present a branch-and-price-and-cut method for the solution of the split delivery vehicle routing problem (SDVRP). The SDVRP is the problem to serve customers with a fleet of capacitated vehicles at minimum traveling cost. With respect to the classical vehicle routing problem, where each customer is visited exactly once, in the SDVRP a customer may be visited any number of times. The exact method we propose is based on a decomposition of the problem where the possible routes, with the delivery quantities, are generated in the subproblem. The generated routes are also used to find a heuristic solution to the problem. We consider both the case where the fleet of vehicles is unlimited and the case where the fleet is limited to the minimum possible number of vehicles. We solve to optimality instances with larger size with respect to previous approaches, find new best solutions to several benchmark instances and reduce the optimality gap on most of the benchmark instances.

    Original languageEnglish
    Pages (from-to)241-254
    Number of pages14
    JournalNetworks
    Volume58
    Issue number4
    DOIs
    Publication statusPublished - 1 Jul 2011

    Fingerprint

    Vehicle routing
    Decomposition
    Costs

    Keywords

    • branch-and-price-and-cut method
    • column generation
    • split delivery vehicle routing problem
    • unlimited and limited fleet

    Cite this

    Archetti, C. ; Bianchessi, N. ; Speranza, M. G. / A column generation approach for the split delivery vehicle routing problem. In: Networks. 2011 ; Vol. 58, No. 4. pp. 241-254.
    @article{96d9e612a87143c092c16c9f540ba2cb,
    title = "A column generation approach for the split delivery vehicle routing problem",
    abstract = "In this article we present a branch-and-price-and-cut method for the solution of the split delivery vehicle routing problem (SDVRP). The SDVRP is the problem to serve customers with a fleet of capacitated vehicles at minimum traveling cost. With respect to the classical vehicle routing problem, where each customer is visited exactly once, in the SDVRP a customer may be visited any number of times. The exact method we propose is based on a decomposition of the problem where the possible routes, with the delivery quantities, are generated in the subproblem. The generated routes are also used to find a heuristic solution to the problem. We consider both the case where the fleet of vehicles is unlimited and the case where the fleet is limited to the minimum possible number of vehicles. We solve to optimality instances with larger size with respect to previous approaches, find new best solutions to several benchmark instances and reduce the optimality gap on most of the benchmark instances.",
    keywords = "branch-and-price-and-cut method, column generation, split delivery vehicle routing problem, unlimited and limited fleet",
    author = "C. Archetti and N. Bianchessi and Speranza, {M. G.}",
    year = "2011",
    month = "7",
    day = "1",
    doi = "10.1002/net.20467",
    language = "English",
    volume = "58",
    pages = "241--254",
    journal = "Networks",
    issn = "0028-3045",
    publisher = "Wiley-Liss Inc.",
    number = "4",

    }

    Archetti, C, Bianchessi, N & Speranza, MG 2011, 'A column generation approach for the split delivery vehicle routing problem' Networks, vol. 58, no. 4, pp. 241-254. https://doi.org/10.1002/net.20467

    A column generation approach for the split delivery vehicle routing problem. / Archetti, C.; Bianchessi, N.; Speranza, M. G.

    In: Networks, Vol. 58, No. 4, 01.07.2011, p. 241-254.

    Research output: Contribution to JournalArticleAcademicpeer-review

    TY - JOUR

    T1 - A column generation approach for the split delivery vehicle routing problem

    AU - Archetti, C.

    AU - Bianchessi, N.

    AU - Speranza, M. G.

    PY - 2011/7/1

    Y1 - 2011/7/1

    N2 - In this article we present a branch-and-price-and-cut method for the solution of the split delivery vehicle routing problem (SDVRP). The SDVRP is the problem to serve customers with a fleet of capacitated vehicles at minimum traveling cost. With respect to the classical vehicle routing problem, where each customer is visited exactly once, in the SDVRP a customer may be visited any number of times. The exact method we propose is based on a decomposition of the problem where the possible routes, with the delivery quantities, are generated in the subproblem. The generated routes are also used to find a heuristic solution to the problem. We consider both the case where the fleet of vehicles is unlimited and the case where the fleet is limited to the minimum possible number of vehicles. We solve to optimality instances with larger size with respect to previous approaches, find new best solutions to several benchmark instances and reduce the optimality gap on most of the benchmark instances.

    AB - In this article we present a branch-and-price-and-cut method for the solution of the split delivery vehicle routing problem (SDVRP). The SDVRP is the problem to serve customers with a fleet of capacitated vehicles at minimum traveling cost. With respect to the classical vehicle routing problem, where each customer is visited exactly once, in the SDVRP a customer may be visited any number of times. The exact method we propose is based on a decomposition of the problem where the possible routes, with the delivery quantities, are generated in the subproblem. The generated routes are also used to find a heuristic solution to the problem. We consider both the case where the fleet of vehicles is unlimited and the case where the fleet is limited to the minimum possible number of vehicles. We solve to optimality instances with larger size with respect to previous approaches, find new best solutions to several benchmark instances and reduce the optimality gap on most of the benchmark instances.

    KW - branch-and-price-and-cut method

    KW - column generation

    KW - split delivery vehicle routing problem

    KW - unlimited and limited fleet

    UR - http://www.scopus.com/inward/record.url?scp=80755188983&partnerID=8YFLogxK

    UR - http://www.scopus.com/inward/citedby.url?scp=80755188983&partnerID=8YFLogxK

    U2 - 10.1002/net.20467

    DO - 10.1002/net.20467

    M3 - Article

    VL - 58

    SP - 241

    EP - 254

    JO - Networks

    JF - Networks

    SN - 0028-3045

    IS - 4

    ER -