The Undirected Capacitated General Routing Problem with Profits

In this paper we introduce and study the Undirected Capacitated General Routing Problem with Profits (UCGRPP). This problem is defined on an undirected graph where a subset of vertices and edges correspond to customers, which are associated with a given profit and demand. The profit of each customer can be collected at most once. A fleet of homogeneous capacitated vehicles is given to serve the customers. The objective is to find the vehicle routes that maximize the difference between the total collected profit and the traveling cost in such a way that the demand collected by each vehicle does not exceed the capacity and the total duration of each route is not greater than a maximum given time limit. We propose a mathematical formulation of the problem and introduce valid inequalities to strengthen the corresponding continuous relaxation. Moreover, we provide an aggregate formulation that allows us to introduce further inequalities. Then, we propose a two-phase exact algorithm for the solution of the UCGRPP. In the first phase, a branch-and-cut algorithm is used to solve the aggregate formulation and to identify a cut pool of aggregate valid inequalities to be used in the second phase, where a branch-and-cut algorithm is implemented to optimally solve the UCGRPP. Computational results on a large set of problem instances show that the use of the aggregate formulation is effective, making the two-phase exact algorithm able to optimally solve a large number of instances.