Network pricing problem with unit toll

Castelli, Lorenzo; Labbé, Martine; Violin, Alessia

Document type :

Article dans une revue scientifique

DOI :

10.1002/net.21701

Title :

Network pricing problem with unit toll

Author(s) :

Castelli, Lorenzo [Auteur]
Labbé, Martine [Auteur]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]
Integrated Optimization with Complex Structure [INOCS]
Violin, Alessia [Auteur]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]

Journal title :

Networks

Pages :

83--93

Publisher :

Wiley

Publication date :

2017-01

ISSN :

0028-3045

HAL domain(s) :

Informatique [cs]/Recherche opérationnelle [cs.RO]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Network pricing problem with unit toll BibTeX CSV Excel RIS

Network pricing problem with unit toll

BibTeX

CSV

Excel

RIS