A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem |
| |
| Affiliation: | 1. Department of Management Science, Lancaster University, Lancaster LA1 4YW, UK;2. Department of Mathematics, Universidad de La Laguna, 38271 Tenerife, Spain;1. École Polytechnique de Montréal, C.P. 6079, succursale Centre-ville, Montréal H3C 3A7, Canada;2. GERAD, 3000 chemin de la Côte-Sainte-Catherine, Montréal H3T 2A7, Canada;3. Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University, Mainz D-55099, Germany;4. HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal H3T 2A7, Canada;5. CIRRELT, C.P. 6128, succursale Centre-ville, Montréal H3C 3J7, Canada;1. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA;2. Department of Industrial Engineering, Bilkent University, Ankara 06800, Turkey |
| |
| 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. |
| |
| Keywords: | Multiple commodities Vehicle routing problems Branch-price-and-cut algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
