aalto1 untyped-item.component.html
An alternative IP formulation for zone-based tariff planning
Loading...
Files
Aalto login required (access for Aalto Staff only).
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
Language
en
Pages
31
Series
Abstract
This thesis focuses on the optimization problem of zone-based tariff design in public transportation networks, as originally formulated by Otto and Boysen. The original model (ZTDP) integrates both the determination of zone structures and the assignment of tariffs into a single integer programming formulation. This approach suffers from scalability issues: the number of feasible zone configurations grows exponentially with the size of the transport network, making real-world instances practically unsolvable within reasonable time limits.
In this work, the original ZTDP model is modified to improve its computational efficiency. The key modification lies in decoupling the zone formation process from the optimization problem by introducing a predefined pool of feasible zone candidates. This restricted zone-pool is provided as input to the model, allowing the solver to focus solely on selecting the best combination of these zones and setting appropriate tariffs. This change transforms the original formulation into a more scalable solution, suitable for larger problem instances.
The performance and behavior of the modified model are evaluated using numerical experiments with Gurobi, a mixed-integer programming solver, in the LinTimenvironment. Multiple zone-pools of varying sizes and levels of structural restriction are tested to assess the impact on both solving times and objective value.
The results show that the restricted model significantly reduces solving times without notable losses in solution quality. When the zone-pool is limited to connected subgraphs of a given size range, solving time decreases significantly for moderate zone budgets. Additionally, the model demonstrates stable behavior across different customer population sizes, while retaining revenue outcomes compared to the original approach. The simplified zone selection strategy thus enables practical application of the ZTDP concept to more realistic transport networks.
In conclusion, the proposed reformulation offers a scalable and computationally efficient alternative to the original ZTDP model, without compromising key economic objectives. Future work may focus on heuristic zone-pool generation and integration of further pricing schemes.
Tämä työ keskittyy vyöhykkeisiin perustuvan hinnoittelusuunnittelun optimointiongelmaan joukkoliikenneverkoissa, alkuperäisenä mallina Otto ja Boysenin esittelemä ZTDP-malli (Zone-based Tariff Design Problem). Alkuperäinen malli yhdistää sekä vyöhykerakenteiden määrittelyn että hintojen asettamisen yhdeksi suurikokoiseksi kokonaisluku optimointitehtäväksi. Vaikka malli on teoreettisesti perusteltu, se ei skaalaudu hyvin: mahdollisten vyöhykeyhdistelmien määrä kasvaa eksponentiaalisesti verkon koon mukana, mikä tekee realististen tapausten ratkaisemisesta laskennallisesti käytännössä mahdotonta kohtuullisessa ajassa.
Tässä työssä alkuperäistä ZTDP-mallia muokataan parantaen sen laskennallista tehokkuutta. Keskeinen muutos on vyöhykkeiden muodostamisen irrottaminen itse optimointiongelmasta. Malliin syötetään valmiiksi muodostettu vyöhykeehdokasjoukko, josta malli valitsee optimaaliset vyöhykkeet ja määrittää hinnat.
Tämä yksinkertaistus tekee mallista paremmin skaalautuvan, mahdollistaen sen soveltamisen suurempiin ja realistisempiin verkkoihin.
Muokatun mallin suorituskykyä ja käyttäytymistä arvioitiin numeeristen kokeiden avulla käyttäen Gurobi-ratkaisinta LinTim-ympäristössä. Testit toteutettiin Mandlverkon pohjalta, joka on esimerkkiverkko LinTim-ympäristöstä. Useita vyöhykeehdokasjoukkoja testattiin, eri kokoisilla ja rakenteellisesti rajatuilla vyöhykkeillä, jotta voitiin arvioida vaikutusta ratkaisuaikaan ja kokonaistulokseen.
Tulokset osoittavat, että rajoitettu malli lyhentää ratkaisuaikaa merkittävästi ilman huomattavaa ratkaisun laadun heikkenemistä. Esimerkiksi, kun vyöhykejoukko rajoitettiin yhdistettyihin aliverkkoihin tietyn kokovälin sisällä, ratkaisuaika laski keskimäärin merkittävästi keskikokoisilla vyöhykebudjeteilla. Lisäksi malli osoitti vakaata käyttäytymistä asiakasmäärien kasvaessa ja säilytti kilpailukykyisen tulostason. Vyöhykkeiden valintaprosessin yksinkertaistaminen mahdollistaa siten ZTDP-idean käytännön soveltamisen laajempiin liikenneverkkoihin.
Yhteenvetona voidaan todeta, että ehdotettu muokkaus alkuperäiseen ongelman muotoiluun tarjoaa skaalautuvan ja laskennallisesti tehokkaan vaihtoehdon alkuperäiselle ZTDP-mallille ilman merkittäviä kompromisseja taloudellisten tavoitteiden suhteen. Tulevaisuuden tutkimus voisi keskittyä heuristisiin vyöhyke-joukon muodostusmenetelmiin.