A Branch-and-Cut Algorithm for the Multi-Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints

We introduce a problem where a fleet of vehicles is available to visit suppliers offering various products at different prices and quantities, with the aim to select a subset of suppliers so to satisfy products demand at the minimum traveling and purchasing costs. Vehicles have a predefined capacity and pairs of products may be incompatible to be carried simultaneously on a same vehicle. We call this problem the multi-vehicle traveling purchaser problem with pairwise incompatibility constraints. We show how a three-index one-commodity flow formulation for the problem is easy to implement with a common MILP solver, but highly nonefficient when solving large size instances. We concentrate on a formulation using connectivity constraints to exclude subtours and introduce a branch-and-cut framework using a preprocessing routine and the separation of different valid inequalities. We also propose a four-step heuristic based on the solution of different subproblems and use it to provide an initial feasible solution. We run computational tests on a large set of instances with up to 50 suppliers, 100 products, and 20% of crossed incompatibility between products. Results show that two different streamlined versions of the proposed exact method largely outperform the plain solution by the commercial solver Cplex 12.3. Also, the heuristic approach is observed to be rather effective and efficient providing a valid solving alternative.