Refine
Year of publication
- 2016 (2) (remove)
Document Type
- In Proceedings (1)
- ZIB-Report (1)
Language
- English (2)
Is part of the Bibliography
- no (2)
Keywords
- combinatorial optimization (1)
- graph segmentation (1)
- toll billing (1)
Institute
- Mathematics of Transportation and Logistics (2) (remove)
We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.
We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.