A Cut-and-Branch algorithm for the Multicommodity Traveling Salesman Problem

This paper presents a Cut-and-Branch algorithm for the Multicommodity Traveling Salesman Problem (MTSP), a useful variant of the Traveling Salesman Problem (TSP). The MTSP presents a more general cost structure, allowing for solutions that consider the quality of service to the customers, delivery priorities and delivery risk, among other possible objectives. In the MTSP the salesman pays the traditional TSP fixed cost for each arc visited, plus a variable cost for each of the commodities being transported across the network. We present a strong mathematical formulation for this relevant problem. We implement a Cut-and-Branch algorithm for the MTSP which is able to find optimal solutions faster than stand-alone CPLEX codes.