The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: A branch-and-price approach

Michel Gendreau, Daniele Manerba and Renata Mansini

European Journal of Operational Research, 2016, vol. 248, issue 1, 59-71

Abstract: In this work, we study a supplier selection and routing problem where a fleet of homogeneous vehicles with a predefined capacity is available for procuring different products from different suppliers with the aim to satisfy demand at the minimum traveling and purchasing cost. Decisions are further complicated by the presence of pairwise incompatibility constraints among products, implying the impossibility of loading two incompatible products on the same vehicle. The problem is known as the Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints. We study the special case in which the demand for each product is unitary and propose a column generation approach based on a Dantzig–Wolfe reformulation of the problem, where each column represents a feasible vehicle route associated with a compatible purchasing plan. To solve the pricing problem we propose a hybrid strategy exploiting the advantages of two alternative exact methods, a labeling algorithm solving a Resource-Constrained Elementary Shortest Path Problem on an expanded graph, and a tailored branch-and-cut algorithm. Due to the integrality request on variables, we embed the column generation in a branch-and-bound framework and propose different branching rules. Extensive tests, carried out on a large set of instances, show that our branch-and-price method performs well, improving on average, both in quality and in computational time, solutions obtained by a state-of-art branch-and-cut approach applied to a three-index connectivity constraints based formulation.

Keywords: Traveling purchaser problem; Multi-vehicle; Pairwise incompatibility constraints; Column generation; Branch-and-price (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171500627X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:248:y:2016:i:1:p:59-71

DOI: 10.1016/j.ejor.2015.06.073

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().