A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints

Abstract

In this paper we study the time-dependent profitable tour problem with resource constraints (TDPTPRC), a generalization of the profitable tour problem (PTP) which includes variable travel times to account for road congestion. In this problem, the set of customers to be served is not given and must be determined based on the profit collected when visited, keeping a balance with the total travel time. We propose a mixed integer linear programming (MILP) formulation that exploits the travel time function to reduce the size of a standard formulation from the literature. We derive four new families of valid inequalities and study the connections among them, as well as their associated separation problems. We develop a tailored Branch and Cut (BC) algorithm including these new families in addition to some well known valid inequalities from related problems. Computational results on four different problems, with alternative resources and objectives, show that the approach is flexible and effective. The algorithm achieves significant reductions in the computing times on benchmark instances from the related literature, and outperforms a recent method proposed for the time-dependent traveling salesman problem with time windows.