Bus route design and frequency setting for public transit systems

Husselmann, Gunther (2022-04)

Thesis (PhD)--Stellenbosch University, 2022.

Thesis

ENGLISH ABSTRACT: The availability of effective public transport systems is increasingly becoming an urgent problem in urban areas worldwide due to the traffic congestion caused by private vehicles. The careful design of such a transport system is important because, if well designed, such a system can increase the comfort of commuters and ensure that they arrive at their destinations timeously. A well-designed public transport system can also result in considerable cost savings for the operator of the system. The problem considered in this dissertation is that of designing three mathematical models for aiding a bus company in deciding upon efficient bus transit routes (facilitated by the first two models) and setting appropriate frequencies for buses along these routes (facilitated by the third model). The design criteria embedded in the first model (for designing bus routes) are the simultaneous pursuit of minimising the expected average passenger travel time and minimising the system operator’s cost (measuring the latter as the sum total of all route lengths in the system). The first model takes as input an origin-destination demand matrix for a specified set of bus stops, along with the corresponding road network structure, and returns as output a set of bus route solutions. The decision maker can then select one of these route sets subjectively, based on the desired trade-off achieved between the aforementioned transit system design criteria. This bi-objective minimisation problem is solved approximately in three distinct stages — a solution initialisation stage, an intermediate analysis stage and an iterative metaheuristic search stage during which high-quality trade-off solutions are sought. A novel procedure is introduced for the solution initialisation stage aimed at effectively generating high-quality initial feasible solutions. Two metaheuristics are adopted for the solution implementation, namely a dominance-based multi-objective simulated annealing algorithm and an improved non-dominated sorting genetic algorithm. The second model is a novel approach towards establishing high-quality bus routes resembling a reference set of bus routes (typically the currently operational bus routes) to varying degrees, providing the decision maker with bus route design alternatives that may be implemented incre mentally in order to limit the disruption experienced by passengers in the bus transit network. The objectives pursued in this model are the simultaneous minimisation of the expected aver age passenger travel time and the minimisation of a reference-route-to-design-route similarity measure. The second model takes the same input as the first model above, with the addition of a reference route set with which to compare alternative design routes in terms of similarity, and provides as output a set of trade-off solutions according to this model’s design criteria. The same three-stage approximate solution methodology described above is adopted for this model, and the same two metaheuristic implementations are utilised to solve instances of this new model. In the third model, high-quality bus frequencies are sought for each bus route in pursuit of min imising the expected average travel time for passengers (including waiting time, transfer time and travel time) and simultaneously minimising the total number of buses required by an operator to maintain the specified frequencies. The third model takes as input all the data required by the first model, along with a route set for which frequencies should be set, and returns as output a set of bus frequencies at which buses should operate along the various routes, based on a de sired trade-off between the aforementioned two design criteria. The solution approach adopted for this bi-objective minimisation problem again conforms to the three aforementioned distinct stages, with the exception that only a non-dominated sorting genetic algorithm is designed for solving it. The first and third models are finally applied to a special case study involving real data in order to showcase the practical applicability of the modelling approach.

AFRIKAANSE OPSOMMING: Die beskikbaarheid van doeltreffende openbare vervoerstelsels word wˆereldwyd toenemend ’n dringende probleem in stedelike gebiede as gevolg van die verkeersopeenhopings wat deur private voertuie veroorsaak word. Die noukeurige ontwerp van so ’n vervoerstelsel is belangrik, want as dit goed ontwerp is, kan so ’n stelsel die gemak van pendelaars verhoog en verseker dat hul betyds by hul bestemmings aankom. ’n Goed-ontwerpte openbare vervoerstelsel kan ook aansienlike kostebesparings vir die stelseloperateur tot gevolg hˆe. Die probleem wat in hierdie proefskrif oorweeg word, is die ontwerp van drie wiskundige modelle om ’n busonderneming daartoe in staat te stel om besluite oor doeltreffende busvervoerroetes (die eerste twee modelle) en die geskikte frekwensies vir busse langs hierdie roetes (die derde model) te neem. Die ontwerpkriteria in die eerste model (vir die ontwerp van busroetes) is die gelyktydige strewe daarna om die verwagte gemiddelde reistyd van passasiers te minimeer en die koste van die stelseloperateur te minimeer (laasgenoemde gemeet as die somtotaal van alle roetelengtes in die stelsel). Die eerste model neem as toevoer ’n oorsprong-bestemming aan vraagmatriks vir ’n spesifieke stel bushaltes, tesame met die ooreenstemmende padnetwerkstruk tuur, en lewer as afvoer ’n versameling busroetestelle. Die besluitnemer kan dan een van hierdie roetestelle subjektief kies, gebaseer op die gewenste afruiling tussen die bogenoemde ontwerpkri teria. Hierdie twee-doelige minimeringsprobleem word in drie verskillende fases benaderd opgelos — ’n oplossingsinisialiseringsfase, ’n intermediˆere analise-fase en ’n iteratiewe metaheuristiese soekfase waartydens afruilingssoplossings van ho¨e gehalte gesoek word. ’n Nuwe prosedure word vir die oplossingsinisialiseringsfase daargestel wat daarop gemik is om aanvanklike haalbare oplossings van ho¨e gehalte op ’n doeltreffende wyse te genereer. Twee meteheuristieke word vir die oplossing van die model gebruik, naamlik ’n dominansie-gebaseerde meer-doelige ge simuleerde temeperingsalgoritme en ’n verbeterde nie-gedomineerde sorteer-genetiese algoritme. Die tweede model is ’n nuwe benadering om busroetes van ho¨e gehalte te vestig wat in verskil lende mates ooreenkomste met ’n verwysingstel busroetes (tipies die huidige stel operasionele roetes) toon, en bied die besluitnemer alternatiewe vir busroetes wat geleidelik ge¨ımplementeer kan word om die ontwrigting van passasiers in die busvervoernetwerk te beperk. Die doele wat in hierdie model nagestreef word, is die gelyktydige minimering van die verwagte gemiddelde passas ier se reistyd en die minimering van ’n verwysingsroete-na-ontwerp-roete ooreenkomsmaatstaf. Die tweede model neem dieselfde toevoere as die eerste model hierbo, met die byvoeging van ’n verwysingsroete waarmee alternatiewe ontwerproetestelle in terme van ooreenkoms vergelyk kan word, en bied as afvoer ’n stel afruilingsoplossings volgens die model se ontwerpkriteria. Die selfde drie-fase benaderde oplos-singsmetode hierbo beskryf, word op hierdie model toegepas, en dieselfde twee metaheuristiese implementerings word gebruik om gevalle van hierdie nuwe model op te los. In die derde model word busfrekwensies van ho¨e gehalte vir elke busroete gesoek om die verwagte gemiddelde reistyd van passasiers (insluitend wagtyd, oorklimtyd en werklike reistyd) te minimeer en terselfdertyd die totale aantal busse wat ’n operateur benodig, te minimeer terwyl die gespesifiseerde frekwensies gehandhaaf word. Die derde model neem dieselfde toevoerdata as die eerste model, tesame met ’n roete waarvoor frekwensies vasgestel moet word, en lewer as afvoer ’n stel busfrekwensies waarteen busse langs die verskillende roetes ontplooi moet word, gebaseer op ’n gewenste afruiling tussen die bogenoemde twee ontwerpkriteria. Die oplossingsbenadering wat op hierdie tweedoelige minimeringsprobleem toegepas word, volg weer die bogenoemde drie fases, met die uitsondering dat slegs ’n nie-gedomineerde sorteer-genetiese algoritme ontwerp word om dit op te los. Die eerste en derde modelle word uiteindelik op ’n spesiale gevallestudie toegepas wat op werklike data gebaseer is om sodoende die praktiese toepaslikheid van die modelleringsbenadering te illustreer.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/124533
This item appears in the following collections: