A Branch-Price-and-Cut Algorithm for the Capacitated Multiple Vehicle Traveling Purchaser Problem with Unitary Demand

Nicola Bianchessi (nicola.bianchessi@unimi.it), Stefan Irnich (irnich@uni-mainz.de) and Christian Tilk (tilk@uni-mainz.de)
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

Abstract: The multiple vehicle traveling purchaser problem (MVTPP) consists of simultaneously selecting suppliers and routing a fleet of homogeneous vehicles to purchase different 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
Date: 2020-01-23
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2003.pdf First version, 2020 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

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 (ipp-mainz@uni-mainz.de).