A branch-and-cut algorithm for the capacitated profitable tour problem

This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved through dynamic programming. In this paper we present an alternative framework based on a formulation for the undirected CPTP and solved through branch-and-cut. Valid inequalities are presented among which we introduce a new family of inequalities for the CPTP denoted rounded multistar inequalities and we prove their validity. Computational experiments are performed on a set of instances known from the literature and a set of newly generated instances. The results indicate that the presented algorithm is highly competitive with the dynamic programming algorithms. In particular, we are able to solve instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to serve as a platform for further development of branch-and-cut algorithms for CPTP hence also acting as a survey/tutorial.