Vehicle Routing Problems with Profits

The key characteristic of the class of Vehicle Routing Problems with Profits (VRPPs) is that, contrary to what happens for the most classical vehicle routing problems, the set of customers to serve is not given. Therefore, two different decisions have to be taken: (i) which customers to serve, and (ii) how to cluster the customers to be served in different routes (if more than one) and order the visits in each route. In general, a profit is associated with each customer that makes such a customer more or less attractive. Thus, any route or set of routes, starting and ending at a given depot, can be measured both in terms of cost and in terms of profit. The difference between route profit and cost may be maximized, or the profit or the cost optimized with the other measure bounded in a constraint.