Article ID: | iaor20053332 |
Country: | United States |
Volume: | 46 |
Issue: | 1 |
Start Page Number: | 57 |
End Page Number: | 67 |
Publication Date: | Jun 2005 |
Journal: | Networks |
Authors: | Marcotte Patrice, Savard Gilles, Roch Sbastien |
We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of