Travel-time Optimal Line Plans on Trees

No Thumbnail Available
Files
Kangaslahti_Anna-Maija_2024.pdf (756.09 KB)
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | 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.
Date
2024-01-28
Department
Major/Subject
Matematiikka ja systeemitieteet
Mcode
SCI3029
Degree programme
Teknistieteellinen kandidaattiohjelma
Language
en
Pages
49
Series
Abstract
Due to the urban transformation of past decades, the need for efficient and effective public transportation systems continues to increase. Consequently, many methods have been developed to optimize different components of public transportation systems using various criteria. One often desired result for these methods is to create a line plan where the travel time of the passengers is minimal. Schobel and Scholl developed a formulation for the line optimization problem that achieves this result and manages to consider the total travel time for all passengers. However, due to the large size and the high complexity of the formulation, it cannot be solved in any straightforward manner. This thesis aims to expand on the work of Schöbel and Scholl by developing a formulation for star-shaped station networks that acts as a simpler alternative to their binary frequency formulation. The alternative formulation is developed by leveraging the special features of star-shaped networks and tree networks in general: There exists only one simple path between any two nodes of a tree. Thus, we show that the driving time of any passenger is constant for their trip, and the travel time only depends on the passenger’s transfers. Consequently, the developed formulation tracks only the transfers, not the entire route of the passengers, and optimizes the total travel time by minimizing the total number of said transfers. As part of this thesis, we prove the developed formulation to be equivalent to the binary frequency formulation of Schöbel and Scholl in star-shaped trees. It is also found that the developed formulation is significantly smaller than the formulation of Schöbel and Scholl, especially for larger star networks. This implies that the developed formulation is simpler to solve, as desired. The successfully developed formulation thus proves that the formulations of the line planning problems can be simplified by limiting the underlying networks to trees. Additionally, the developed formulation has limited practical applications and benefits.

Viime vuosikymmenten kaupungistumisen takia tarve tehokkaille ja toimiville julkisille liikennejärjestelmille kasvaa jatkuvasti. Täten, liikennejärjestelmien eri osien optimointiin on myös kehitetty useita metodeja, useille eri ptimaalisuuskriteereille. Yksi yleinen tavoite tällaiselle metodille on muodostaa järjestelmälle linjastosuunnitelma, jossa matkustajien matkustusaika on mahdollisimman pieni. Schöbel and Scholl ovat kehittäneet tähän optimointiongelmaan mallin, joka saavuttaa tämän tavoitteen minimoiden onnistuneesti kaikkien matkustajien yhteenlasketun matkustusajan. Kyseistä mallia ei kuitenkaan voida ratkaista ilman uudelleenmuotoilua sen suuren koon ja kompleksisuuden takia. Tämän työn tavoitteena täydentää Schöbelin ja Schollin työtä kehittämällä optimointiongelmaan vaihtoehtoisen mallin tähdenmuotoisissa pysäkkiverkostoissa, joka on Schöbelin ja Schollin mallia yksinkertaisempi ratkaista. Vaihtoehtoinen malli kehitettiin tähdenmuotoisten verkkojen ja yleisesti puu-verkkojen erikoisominaisuuksien avulla: Puun kahden solmun välille voidaan luoda täsmälleen yksi yksinkertainen polku. Tämän ominaisuuden pohjalta työssä osoitetaan, että aika, jonka matkustaja käyttää ajamiseen on aina tietylle matkalle vakio. Matkustajan matkustusaika siis riippuu vain hänen tekemistään vaihdoista. Täten, kehitetty malli pitää kirjaa vain matkustajien tekemistä vaihdoista, ei matkustusreitistä, ja optimoi yhteenlasketun matkustusajan minimoimalla tehtyjen vaihtojen summan. Todistamme tässä työssä, että kehitetty malli sekä Schöbelin ja Schollin malli ratkaisevat saman ongelman. Lisäksi huomataan, että kehitetty malli on kooltaan huomattavasti Schöbelin ja Schollin mallia pienempi, erityisesti suurien pysäkkiverkostojen tapauksissa. Tämä vihjaa kehitetyn mallin olevan myös helpompi ratkaista tavoitteiden mukaisesti. Tämä onnistuneesti kehitetty malli osoittaa siis, että linjastosuunnittelun ongelmiin voidaan muodostaa yksinkertaisempi malli, kun infrastuktuuria kuvaava pysäkkiverkko rajoitetaan puuverkkoihin. Kehitettyä mallia voidaan myös soveltaa ja hyödyntää linjastosuunnittelusta rajoitetusti.
Description
Supervisor
Schiewe, Philine
Thesis advisor
Schiewe, Philine
Keywords
line planning, travel time optimization, strar shaped trees
Other note
Citation