Return to results
Book chapters (2015), Arc Routing: Problems, Methods, and Applications, SIAM (12), pp. 281-300

Arc routing problems with profits


The class of routing problems with profits contains a large variety of problems which share the characteristic that, contrary to classical routing problems, the customers to serve have to be chosen from a set of potential customers. A profit is associated with each potential customer. The objective function may be the collected profit, the traveling cost, or a combination of both. The research activity has been mainly focused on node routing problems with profits, i.e., problems where customers are identified with specific locations which can be represented as vertices of a graph. The word “node” is usually not specified because having customers on nodes is the most common situation. We will specify it in this chapter as we will mention both classes of problems, with customers on nodes and on arcs. A first survey on single vehicle node routing problems with profits can be found in Feillet, Dejax, and Gendreau [21]. These problems are called Traveling Salesman Problems (TSPs) with profits. In this paper, the authors distinguish three classes of problems on the basis of the objective function. In the Orienteering Problem (OP) the objective is to maximize the collected profit with the constraint that the traveling time of the route does not exceed a given threshold. The Prize-Collecting Traveling Salesman Problem (PCTSP) is the problem of finding the route of minimum cost that collects a profit higher than a given lower bound. Finally, the Profitable Tour Problem (PTP) is the problem of finding the route that maximizes the difference between the total collected profit and the traveling cost. More recently, in Vansteenwegen, Souffriau, and Van Oudheusden [31] the authors focused on the OP and on its multiple vehicle version, i.e., the Team Orienteering Problem (TOP). A recent survey on node routing problems with profits, both with a single vehicle and with multiple vehicles, can be found in Archetti, Speranza, and Vigo. Link to the article

ARCHETTI, C. and SPERANZA, M.G. (2015). Arc routing problems with profits. In: Ángel Corberán, Gilbert Laporte eds. Arc Routing: Problems, Methods, and Applications. 1st ed. Philadelphia: SIAM, pp. 281-300.