A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem

Claudia Archetti, Nicola Bianchessi*, M. Grazia Speranza

*Corresponding author for this work

    Research output: Contribution to JournalArticleAcademicpeer-review

    Abstract

    We consider the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP), a routing problem where customers may request multiple commodities. The vehicles can deliver any set of commodities and multiple visits to a customer are allowed only if the customer requests multiple commodities. If the customer is visited more than once, the different vehicles will deliver different sets of commodities. Allowing the splitting of the demand of a customer only for different commodities may be more costly than allowing also the splitting of each individual commodity, but at the same time it is easier to organize and more acceptable to customers. We model the C-SDVRP by means of a set partitioning formulation and present a branch-price-and-cut algorithm. In the pricing phase, the ng-path relaxation of a constrained elementary shortest path problem is solved with a label setting dynamic programming algorithm. Capacity cuts are added in order to strengthen the lower bound. We solve to optimality within 2 h instances with up to 40 customers and 3 commodities per customer.

    Original languageEnglish
    Pages (from-to)1-10
    Number of pages10
    JournalComputers and Operations Research
    Volume64
    DOIs
    Publication statusPublished - 8 Jun 2015

    Keywords

    • Branch-price-and-cut algorithm
    • Multiple commodities
    • Vehicle routing problems

    Fingerprint Dive into the research topics of 'A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem'. Together they form a unique fingerprint.

    Cite this