A clustering approach towards the identification of suitable waiting areas for drivers of transportation network companies

Rolo, Monica Celestina (2020-03)

Thesis (MEng)--Stellenbosch University, 2020.

Thesis

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.

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