Multi-Vehicle Traveling Purchaser Problem with Exclusionary Side Constraints

Recently, an interesting variant of the Vehicle Routing Problem (VRP), where a fleet of vehicles is available to visit suppliers offering different products at different prices and quantities, has been studied. The problem, called Multi-Vehicle Travelling Purchaser Problem (MVTPP), aims at selecting a subset of suppliers so to satisfy products demand at the minimum travelling and purchasing costs, while ensuring that the quantity collected by each vehicle does not exceed a predefined capacity (see Riera-Ledesma and Salazar-Gonzalez [1] for an application to school bus routing). More recently, Bianchessi et al. [2] study the Distance-Constrained MVTPP where a constraint ensures that the distance travelled by each vehicle does not exceed a predefined upper bound. We introduce a generalization of the MVTPP characterized by the presence of exclusionary side constraints representing the impossibility of loading products on the same vehicle when incompatible (e.g. food and chemicals) and call it Multi-Vehicle Travelling Purchaser Problem with Exclusionary Side Constraints (MVTPP-ESC). Exclusionary constraints have been slightly studied in the literature (see e.g. Sun [3] where such constraints are added to the Transportation Problem) but, to the best of our knowledge, the complete MVTPP-ESC has never been addressed before. The problem typically finds application in distribution logistics, more specifically in a City Logistics context where a major issue concerns the products distribution in city centers, while minimizing traffic congestion and air pollution together with purchasing cost. 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 and the similarity of the available vehicles, incompatibility constraints represent a relevant aspect of the problem. We develop new classes of valid inequalities for the problem and propose a B&C algorithm. We also introduce a heuristic procedure that exploits some structural properties of the problem. Preliminary results on new benchmark instances seem to be very promising. References [1] J. Riera-Ledesma, J.J. Salazar-Gonzalez, Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach, Computers and Operations Research 39 (2012) 391-404. [2] N. Bianchessi, M.G. Speranza, R. Mansini, The Distance-Constrained Vehicle Purchaser Problem, In proceedings of Odysseus 2012 - 5th International Workshop on Freight Transportation and Logistics (2012). [3] M. Sun, The transportation problem with exclusionary side constraints and two branch-and-bound algorithms, European Journal of Operational Research 140 (2002) 629-647.