Vehicle Purchaser Problem with Exclusionary Side Constraints

In Vehicle Purchaser Problem (VPP) a fleet of vehicles is available to visit suppliers offering different products at different prices and quantities. The VPP aims at selecting a subset of suppliers so to satisfy products demand at the minimum traveling and purchasing costs, while ensuring that the quantity collected by each vehicle does not exceed a predefined capacity (see [1] for an application to school bus routing). We study a variant of the VPP characterized by the addition of exclusionary side constraints representing the impossibility of loading incompatible products on the same vehicle (e.g. food and chemicals). The problem finds application in a City Logistics context, where a major issue concerns the products distribution in city centers minimizing traffic congestion and air pollution (see [2]). In particular, the problem models the practical situation where a depot is placed on border of a city center and collects, from different suppliers, products addressed to customers located inside the city. Given the variety of products requested, incompatibility constraints represent a relevant aspect of the problem. We call this VPP variant Capacitated Vehicle Purchaser Problem with Exclusionary Side Constraints (CVPP-ESC). The problem is strongly NP-hard and to the best of our knowledge it has never been addressed in the literature. We propose both exact and heuristic approaches to solve the problem. Some preliminary results are in progress. References (1) J. Riera-Ledesma, J.J. Salazar-Gonz´alez, Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach, Computers & Operations Research 39:391–404 (2012). (2) T.G. Crainic, N. Ricciardi, G. Storchi, Models for Evaluating and Planning City Logistics Transportation Systems, Transportation Science 43:432-454 (2009).