A Branch-Price-and-Cut Algorithm for the Capacitated Multiple Vehicle Traveling Purchaser Problem with Unitary Demand
Nicola Bianchessi (),
Stefan Irnich () and
Christian Tilk ()
Additional contact information
Nicola Bianchessi: University of Milan
Stefan Irnich: Johannes Gutenberg University Mainz
Christian Tilk: Johannes Gutenberg University Mainz
No 2003, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz
The multiple vehicle traveling purchaser problem (MVTPP) consists of simultaneously selecting suppliers and routing a ﬂeet of homogeneous vehicles to purchase diﬀerent products at the selected suppliers so that all product demands are fulfilled and traveling and purchasing costs are minimized. We consider variants of the MVTPP in which the capacity of the vehicles can become binding and the demand for each product is one unit. Corresponding solution algorithms from the literature are either branch-and-cut or branch-and-price algorithms, where in the latter case the route-generation subproblem is solved on an expanded graph by applying standard dynamic-programming techniques. Our branch-price-and-cut algorithm employs a novel labeling algorithm that works directly on the original network and postpones the purchasing decisions until the route has been completely defined. Moreover, we define a new branching rule generally applicable in case of unitary product demands, introduce a new family of valid inequalities to apply when suppliers can be visited at most once, and show how product incompatibilities can be handled without considering additional resources in the pricing problem. In comprehensive computational experiments with standard benchmark sets we prove that the new branch-price-and-cut approach is highly competitive.
Keywords: vehicle routing; multiple vehicle traveling purchaser problem; unitary demand; incompatible products; column generation; dynamic-programming labeling algorithm (search for similar items in EconPapers)
Pages: 29 pages
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2003.pdf First version, 2020 (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:2003
Access Statistics for this paper
More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().