Routing Problems with Profits

The key characteristic of the class of routing problems with profits is that, contrary to what happens in other classical routing problems, it may be decided whether or not to serve the given customers. Therefore, two different decisions have to be taken simultaneously: which customers to serve, and in which order they are visited (possibly, with more than one route). Customers may be located at nodes or arcs/edges of a graph. 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 can be measured both in terms of cost and in terms of profit. Then either the difference between route profit and cost is maximized, or just one of them is optimized possibly adding bounds on profit and cost.