TY - JOUR
T1 - A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem
AU - Archetti, Claudia
AU - Bianchessi, Nicola
AU - Speranza, M. Grazia
PY - 2015/6/8
Y1 - 2015/6/8
N2 - 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.
AB - 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.
KW - Branch-price-and-cut algorithm
KW - Multiple commodities
KW - Vehicle routing problems
UR - http://www.scopus.com/inward/record.url?scp=84930632732&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84930632732&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2015.04.023
DO - 10.1016/j.cor.2015.04.023
M3 - Article
AN - SCOPUS:84930632732
VL - 64
SP - 1
EP - 10
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
ER -