In the so-called network pricing problem an authority owns some arcs of the network and tolls them, while users travel between their origin and destination choosing their minimum cost path. In this article, we consider a unit toll scheme, and in particular the cases where the authority is imposing either the same toll on all of its arcs, or a toll proportional to a given parameter particular to each arc (for instance a per kilometer toll). We show that if tolls are all equal then the complexity of the problem is polynomial, whereas in case of proportional tolls it is pseudo-polynomial, proposing ad-hoc solution algorithms and relating these problems to the parametric shortest path problem. We then address a robust approach using an interval representation to take into consideration uncertainty on parameters. We show how to modify the algorithms for the deterministic case to solve the robust counterparts, maintaining their complexity class.

Network pricing problem with unit toll

CASTELLI, LORENZO;VIOLIN, ALESSIA
2017-01-01

Abstract

In the so-called network pricing problem an authority owns some arcs of the network and tolls them, while users travel between their origin and destination choosing their minimum cost path. In this article, we consider a unit toll scheme, and in particular the cases where the authority is imposing either the same toll on all of its arcs, or a toll proportional to a given parameter particular to each arc (for instance a per kilometer toll). We show that if tolls are all equal then the complexity of the problem is polynomial, whereas in case of proportional tolls it is pseudo-polynomial, proposing ad-hoc solution algorithms and relating these problems to the parametric shortest path problem. We then address a robust approach using an interval representation to take into consideration uncertainty on parameters. We show how to modify the algorithms for the deterministic case to solve the robust counterparts, maintaining their complexity class.
2017
Pubblicato
http://onlinelibrary.wiley.com/doi/10.1002/net.21701
File in questo prodotto:
File Dimensione Formato  
Castelli_et_al-2017-Networks.pdf

Accesso chiuso

Descrizione: Articolo principale
Tipologia: Documento in Versione Editoriale
Licenza: Digital Rights Management non definito
Dimensione 241.59 kB
Formato Adobe PDF
241.59 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/2895968
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
social impact