Dynamic programming approaches for the bus rapid transit investment problem

Abstract

Bus rapid transit (BRT) systems have gained significant attention as a solution to urban transportation challenges. The BRT system offers a faster and more reliable service compared to other transportation systems such as trams or subway, while providing lower investment costs. This thesis examines how the BRT system infrastructure can be optimized to maximize the number of passengers while minimizing investment costs. The focus is on the development of the BRT line by identifying which segments should be upgraded in order to maximise the number of passengers. Optimal upgrades to the bus line are established by creating dedicated bus lanes, renovating stations, and improving bus stops, as these factors impact the quality of the service and attract potential passengers to use the line.

This thesis simplifies single-objective optimization model in the planning of BRT system. The study demonstrates how strategic upgrades optimises systems efficiency and attracts passengers. The approach of dynamic programming, specifically the 0-1 Knapsack problem, determines the optimal line of segments to upgrade based on cost-effectiveness and increase of potential passengers within the budget constrains. The methodology uses data from the public transportation network (PTN) on 10 and 25 bus stops, information of connecting segments, and passenger demand to analyse the linear passenger response to the upgrades.

The results show that the approach of dynamic programming for calculating Pareto- fronts provides faster running times, particularly with linear passenger response. In instances involving large number of stops running time decreases significantly. This proves the knapsack algorithm to be an effective optimization model for minimizing investment costs and potentially applicable in developing the lines in urban planning.

Nopean bussiliikenteen kuljetus (eng. Bus Rapid Transit) järjestelmä on osoittautunut yhtenä tehokkaana ratkaisuna kaupungin liikenteen haasteisiin. Bussiliikenne järjestelmä tarjoaa nopean ja luotettavan palvelun muihin liikennekulkuvälineisiin kuten raitiovaunu ja metroon verrattuna, sillä se tarjoaa pienemmät investointi kustannukset. Työssä tutkitaan kuinka BRT järjestelmän infrastruktuurien kautta optimoidaan matkustajien lukumäärää suuremmaksi minimoiden investointikustannuksia. Työssä keskitytään BRT linjan kehittämiseen, aluksi tunnistamalla segmentit, joita uudistetaan maksimoimaan matkustajien lukumäärää. Optimaaliset uudistukset bussilinjaan luodaan kehittäen omat bussikaistat, päivittämällä bussiasemat sekä parantamalla bussipysäkkejä, sillä nämä tekijät vaikuttavat linjan palvelun laatuun houkuttaen matkustajia käyttämään linjastoa.

Tässä työssä yksinkertaistetaan yksitavoitteista optimointimallia, suunnitellessa BRT- järjestelmää. Tutkimus osoittaa, kuinka strategiset uudistukset optimoivat järjestelmän tehokkuutta ja matkustajien houkuttelemista. Tutkimuksessa käytetään dynaamisen ohjelmoinnin lähestymistapaa, erityisesti 0-1 Knapsack ongelmaa määrittämään optimaalisen osuuden linjaston segmenttien uudistuksille, mikä perustuu kustannusten tehokkuuteen ja mahdollisiin matkustajamäärien tehostamiseen budjetin asettamissa rajoissa. Metodologia käytetään dataa julkisesta liikenne verkosta (PTN) kerättyä tietoa 10 ja 25 bussipysäkistä sekä kyseisten pysäkkien yhdistävistä uudistuksista ja matkustajien kysynnästä, jotta lineaarinen matkustajavasteiden päivityksiin.

Työssä osoittautui, että dynaamisen ohjelmoinnin lähestymistavan laskemaan Pareto- frontin tuottaen nopeamman suoritusajan, erityisesti lineaarisella matkustajavasteella. Erityisesti suurien pysäkkimäärien tapauksissa suoritusaika laski merkittävästi. Tämä osoittaa knapsack algoritmin tehokkaaksi malliksi minimoimaan investointikustannuksia ja voidaan mahdollisesti soveltaa kehittämään linjastoa kaupunkien suunnittelussa.