A clustering approach towards the identification of suitable waiting areas for drivers of transportation network companies
Date
2020-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Technological innovation has transformed transportation into a more personal and customer driven experience. Traditional public transport, e.g. trains and busses, is limited to pre-defined
routes that are fixed. Consequently, riders (i.e. passengers) have to travel along one of these
routes regardless of their destination. Technology-driven companies, such as Uber, Bolt and Lyft,
are so-called transportation network companies (TNCs) that provide riders with the option of
selecting any pick-up and drop-off location. The nearest available driver (to the rider's pick-up location) is then assigned to the rider, thereafter the driver proceeds to pick up the rider who is then dropped off at their destination. The customer-driven approach of TNCs necessitates that the time elapsed between when a rider requests a ride and when they are picked up should be
minimised. The rider's waiting time could be reduced by identifying suitable areas for drivers to wait between ride-requests.
In this thesis, clustering is adopted as a technique towards identifying waiting areas with the
aim of reducing passenger waiting time. After an extensive review of the literature of popular
clustering algorithms, K-means clustering is deemed best suited for the problem considered.
The K-means algorithm is employed by clustering historical pick-up locations experienced by
a well-known TNC in New York City in order to determine suitable waiting areas. Thereafter, the identified waiting areas are applied in the context of a developed agent-based model which represents the working of TNCs. The aim is to demonstrate the effectiveness of the areas
identified by the clustering algorithm. The developed model simulates the movement of drivers
together with the interactions between drivers and riders. The agent-based simulation model is subjected to the process of verification and validation, including parameter variation and a face validation by a subject matter expert.
Experimentation of eleven scenarios are simulated using the developed model. Two of the scenarios contain parking areas (i.e. openly accessible areas for drivers to park their vehicles) each employing a different strategy in respect of the driver's selection of parking areas. The
other nine scenarios include the waiting areas discovered via clustering, where each scenario
includes different parameter combinations for the clustering method employed. Thereafter, the
scenarios are evaluated by means of statistical comparisons in order to determine if the differences
between the outputs of the scenarios are statistically significant. Improvements in respect of the
average and maximum waiting times as well as the average assignment times were identified as
statistically significant.
AFRIKAANSE OPSOMMING: Tegnologiese innovasie het vervoer in ’n meer persoonlike en klantgedrewe ervaring omskep. Tradisionele openbare vervoer, byvoorbeeld treine en busse, is beperk tot voorafbepaalde roetes wat vas is. Gevolglik moet ruiters (d.w.s. passasiers) op een van hierdie roetes reis ongeag hul bestemming. Tegnologie-gedrewe ondernemings, soos Uber, Bolt en Lyft, is sogenaamde vervoernetwerkondernemings wat aan die ruiters die opsie bied om enige afhaal- en aflaaiplek te kies. Die naaste beskikbare bestuurder (na die plek van die ruiter) word dan aan die ruiter toegewys, waarna die bestuurder voortgaan om die ruiter op te tel wat dan by hul bestemming afgelaai word. Die klante-gedrewe benadering van vervoernetwerkondernemings noodsaak dat die tyd wat verloop tussen die tydstip wanneer ’n ruiter ’n rit vra en wanneer hulle opgetel word, tot die minimum beperk word. Die wagtyd van die ruiter kan verminder word deur geskikte gebiede te identifiseer vir bestuurders om tussen ritversoeke te wag. In hierdie tesis word groepering gebruik as ’n tegniek om wagareas te identifiseer met die doel om die wagtyd van passasiers te verminder. Na ’n uitgebreide oorsig van die literatuur van gewilde groepering-algoritmes, word K-gemiddelde groepering as die beste geskik beskou vir die probleem wat oorweeg word. Die algoritme van K-gemiddelde groepering word gebruik om historiese oplaaiplekke van ‘n bekende vervoernetwerkonderneming in New York te groepeer om geskikte wagareas te bepaal. Daarna word die ge¨ıdentifiseerde wagareas toegepas in die konteks van ’n ontwikkelde agentgebaseerde model wat die werking van vervoernetwerkondernemings verteenwoordig. Die doel is om die doeltreffendheid van die gebiede wat deur die groeperingalgoritme ge¨ıdentifiseer is, te demonstreer. Die ontwikkelde model simuleer die beweging van bestuurders tesame met die wisselwerking tussen bestuurders en ruiters. Die agentgebaseerde simulasiemodel word onderwerp aan die proses van verifikasie en validering, insluitend parametervariasie en ’n gesigvalidering deur ’n vakkundige. Eksperimentering van elf scenario’s word gesimuleer met behulp van die ontwikkelde model. Twee van die scenario’s bevat toeganklike gebiede vir bestuurders om hul voertuie te parkeer wat elkeen ’n ander strategie gebruik ten opsigte van die keuse van die bestuurder van parkeerareas.Die ander nege scenario’s bevat die wagareas wat deur groepering ontdek is, waar elke scenario verskillende parameterkombinasies bevat vir die gebruik van die groepering algoritme. Daarna word die scenario’s aan die hand van statistiese toetse ge¨evalueer om te bepaal of die verskille tussen die uitsette van die scenario’s statisties beduidend is. Verbeteringe in die gemiddelde en maksimum wagtydperk asook die gemiddelde toekennings tyd is as statisties beduidend geïdentifiseer.
AFRIKAANSE OPSOMMING: Tegnologiese innovasie het vervoer in ’n meer persoonlike en klantgedrewe ervaring omskep. Tradisionele openbare vervoer, byvoorbeeld treine en busse, is beperk tot voorafbepaalde roetes wat vas is. Gevolglik moet ruiters (d.w.s. passasiers) op een van hierdie roetes reis ongeag hul bestemming. Tegnologie-gedrewe ondernemings, soos Uber, Bolt en Lyft, is sogenaamde vervoernetwerkondernemings wat aan die ruiters die opsie bied om enige afhaal- en aflaaiplek te kies. Die naaste beskikbare bestuurder (na die plek van die ruiter) word dan aan die ruiter toegewys, waarna die bestuurder voortgaan om die ruiter op te tel wat dan by hul bestemming afgelaai word. Die klante-gedrewe benadering van vervoernetwerkondernemings noodsaak dat die tyd wat verloop tussen die tydstip wanneer ’n ruiter ’n rit vra en wanneer hulle opgetel word, tot die minimum beperk word. Die wagtyd van die ruiter kan verminder word deur geskikte gebiede te identifiseer vir bestuurders om tussen ritversoeke te wag. In hierdie tesis word groepering gebruik as ’n tegniek om wagareas te identifiseer met die doel om die wagtyd van passasiers te verminder. Na ’n uitgebreide oorsig van die literatuur van gewilde groepering-algoritmes, word K-gemiddelde groepering as die beste geskik beskou vir die probleem wat oorweeg word. Die algoritme van K-gemiddelde groepering word gebruik om historiese oplaaiplekke van ‘n bekende vervoernetwerkonderneming in New York te groepeer om geskikte wagareas te bepaal. Daarna word die ge¨ıdentifiseerde wagareas toegepas in die konteks van ’n ontwikkelde agentgebaseerde model wat die werking van vervoernetwerkondernemings verteenwoordig. Die doel is om die doeltreffendheid van die gebiede wat deur die groeperingalgoritme ge¨ıdentifiseer is, te demonstreer. Die ontwikkelde model simuleer die beweging van bestuurders tesame met die wisselwerking tussen bestuurders en ruiters. Die agentgebaseerde simulasiemodel word onderwerp aan die proses van verifikasie en validering, insluitend parametervariasie en ’n gesigvalidering deur ’n vakkundige. Eksperimentering van elf scenario’s word gesimuleer met behulp van die ontwikkelde model. Twee van die scenario’s bevat toeganklike gebiede vir bestuurders om hul voertuie te parkeer wat elkeen ’n ander strategie gebruik ten opsigte van die keuse van die bestuurder van parkeerareas.Die ander nege scenario’s bevat die wagareas wat deur groepering ontdek is, waar elke scenario verskillende parameterkombinasies bevat vir die gebruik van die groepering algoritme. Daarna word die scenario’s aan die hand van statistiese toetse ge¨evalueer om te bepaal of die verskille tussen die uitsette van die scenario’s statisties beduidend is. Verbeteringe in die gemiddelde en maksimum wagtydperk asook die gemiddelde toekennings tyd is as statisties beduidend geïdentifiseer.
Description
Thesis (MEng)--Stellenbosch University, 2020.
Keywords
Cluster analysis, Technology-driven companies, Transportation network companies -- Waiting areas, Terminals (Transportation), UCTD, K-means clustering