Tariff Zone Assignment: Complexity Results ans Solution Approaches.


In the Tariff Zone Assignment problem, an operator is tasked with partitioning a transport network (i.e., a graph) into tariff zones in order to maximize revenue under a linear pricing model. In this model, customers pay a price proportional to the number of zones traveled through, up to some maximum accepted price. If this price gets exceeded, customers drop out of the model and thus generate no revenue at all.

In this talk, first we will look at the complexity of this problem and show APX-hardness on star graphs and strong NP-hardness on paths. These complexity results motivate the introduction of a variant of the problem, which we will show to be polynomial time solvable when restricted to paths. Finally, we will discuss an integer programming approach to the original formulation of the problem.

This is joint, ongoing work with Lennart Kauther, Sven Müller and Britta Peis.


Date: Apr 24, 2024 at 15:00:00 h
Venue: Sala de Seminario John Von Neumann, CMM, Beauchef 851, Torre Norte, Piso 7.
Speaker: Philipp Pabst
Affiliation: RWTH Aache, Germany.
Coordinator: José Verschae
More info at:
Event website

Posted on Apr 22, 2024 in ACGO, Seminars