Bus route design and frequency setting for public transit systems
Date
2022-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
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.
Description
Thesis (PhD)--Stellenbosch University, 2022.
Keywords
Incremental redesign, UCTD, Local transit, Urban transportation, Urban transportation -- Planning, Metaheuristics, Genetic algorithms, Transit systems