A polyhedral study of the Network Pricing Problem with Connected Toll Arcs

Consider the problem that consists in maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, and where origin-destination flows are assigned to shortest paths with respect to the sum of tolls and initial costs. In this work, we address the instance where toll arcs must be connected, as occurs on highways. Our main results are concerned with the theoretical complexity of the problem and its variants, the design of valid inequalities, and facet description for the single commodity case.


To appear in Networks.