Partial Service Routes with Multiple Visits to Edges

This paper deals with searching for a "best" circular service route passing through a given road network represented by an undirected graph. Each edge is characterized by a generalized cost, e.g. the length or travel time, and by a benefit associated to the importance of serving that edge. All these parameters are positive. The service route should meet a cost limit constraint and maximize the route benefit. The route does not need to be elementary, since edges can be traversed multiple times. However, the benefit associated to each traversal of an edge decreases as the number of traversals increases. The total benefit of a service route is defined as the sum of the benefits provided by each individual traversal of each edge of the route.