A new vehicle routing problem for increased driver-route familiarity

Simple item page
dc.contributor.advisorvan Vuuren, J. H.en_ZA
dc.contributor.advisorToth, P.en_ZA
dc.contributor.authorKing, Jacobus Coenraad Petrusen_ZA
dc.contributor.otherStellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering. Engineering Management (MEM).en_ZA
dc.date.accessioned2023-10-17T06:02:56Zen_ZA
dc.date.accessioned2024-01-08T13:18:17Zen_ZA
dc.date.available2023-10-17T06:02:56Zen_ZA
dc.date.available2024-01-08T13:18:17Zen_ZA
dc.date.issued2023-12en_ZA
dc.descriptionThesis (PhD)--Stellenbosch University, 2023.en_ZA
dc.description.abstractENGLISH ABSTRACT: Practical challenges often arise when implementing solutions that stem from solving vehicle routing problem instances. Unplanned external events can result in increased vehicle travel times and subsequent degradations in supply chain operational efficiency. Moreover, drivers tend to get lost and/or often travel on roads that are not suitable for their delivery vehicles when they are unfamiliar with delivery routes, especially when these routes differ significantly from one day to the next. A possible solution, aimed at streamlining the practical implementation of planned delivery routes, is therefore to attempt to increase driver-route familiarity. A novel framework, called the familiarity vehicle routing problem (FVRP) framework, is proposed in this dissertation for improving the practical implementation of planned delivery routes by introducing increased driver-route familiarity into vehicle delivery routes. The FVRP framework consists of two phases — a strategic phase and an operational phase. During the strategic phase, a set of standard delivery routes visiting each customer along a specified number of different approaches is generated for a depot and the customers it services. These routes are called master routes and are then used as blueprints for daily planning purposes when actual delivery routes are computed during the subsequent operational phase. Delivery vehicle drivers are thus afforded the opportunity to become familiar with the master routes, which is anticipated to increase the efficiency with which they will be able to perform deliveries in the long term (if their actual delivery routes do not deviate too much from these master routes). Two novel mathematical models and accompanying approximate solution approaches are proposed for the different phases of the FVRP. The (single-objective) mathematical model for the strategic phase is concerned with generating a minimum-cost set of master routes for a given depot and the customers it services. The set of arcs that form these master routes represent road links with which delivery vehicle drivers may become increasingly familiar as they continue to travel along them during future deliveries. The set of master route arcs are provided as input to the (bi-objective) mathematical model proposed for the operational phase of the FVRP. This model is concerned with computing multiple trade-off solutions which can serve as actual delivery routes along which the objectives are to minimise transportation cost and to maximise the portion of the total distance travelled along the master route arcs. Furthermore, a novel recycling heuristic is proposed which facilitates the use of historical solutions when generating initial solutions for the approximate solution approach of the operational phase. The framework and computerised implementations of its components are finally applied to a special case study, involving real-world data, in order to demonstrate the practical applicability of the work reported in this dissertation.en_ZA
dc.description.abstractAFRIKAANSE OPSOMMING: Praktiese uitdagings ontstaan dikwels wanneer oplossings ge¨ımplementeer word wat uit die oplossing van voertuigroeteringsprobleme voortspruit. Onbeplande eksterne gebeurtenisse kan lei tot verhoogde voertuigreistye en ’n gepaardgaande verswakking in die bedryfsdoeltreffendheid van die voorsieningsketting. Boonop is bestuurders geneig om te verdwaal en/of reis dikwels op paaie wat nie geskik is vir hul afleweringsvoertuie wanneer hulle nie vertroud is met afleweringsroetes nie, veral wanneer hierdie roetes aansienlik van een dag na die volgende verskil. ’n Moontlike oplossing, wat daarop gemik is om die praktiese implementering van beplande afleweringsroetes te stroomlyn, is dus om te poog om bestuurder-roete vertroudheid te verhoog. ’n Nuwe raamwerk, bekend as die vertroudheidsvoertuigroeteringsprobleem (VVRP)-raamwerk, word in hierdie proefskrif vir die verbetering van die praktiese implementering van beplande afleweringsroetes daargestel, wat bestuurder-roete vertroudheid in die beplanning van voertuigafleweringsroetes verhoog. Die VVRP-raamwerk bestaan uit twee fases — ’n strategiese fase en ’n operasionele fase. Tydens die strategiese fase word ’n versameling standaard afleweringsroetes vir ’n depot en die kli¨ente wat daardeur bedien word, bereken wat elke kli¨ent langs ’n bepaalde aantal verskillende benaderings besoek. Hierdie roetes word meesterroetes genoem en word as bloudrukke vir daaglikse beplanningsdoeleindes gebruik wanneer werklike afleweringsroetes tydens die daaropvolgende operasionele fase bereken word. Afleweringsvoertuigbestuurders word dus die geleentheid gebied om vertroud te raak met die meesterroetes, wat na verwagting die doeltreffendheid waarmee hulle aflewerings in die langtermyn sal kan uitvoer, sal verhoog (indien hul werklike afleweringsroetes nie te veel van hierdie meesterroetes afwyk nie). Twee nuwe wiskundige modelle en gepaardgaande benaderde oplossingstegnieke word vir die verskillende fases van die VVRP voorgestel. Die (enkeldoelwit) wiskundige model vir die strategiese fase hou verband met die generering van ’n minimum-koste versameling meesterroetes vir ’n gegewe depot en die kli¨ente wat daardeur bedien word. Die versameling bo¨e wat hierdie meesterroetes vorm, verteenwoordig padverbindings waarmee afleweringsvoertuigbestuurders al hoe meer vertroud kan raak soos wat hulle toekomstige aflewerings maak. Die versameling meesterroetebo¨e word as toevoer tot die (twee-doelwit) wiskundige model vir die operasionele fase van die FVRP gelewer. Hierdie model hou verband met die berekening van verskeie afruiloplossings wat as werklike afleweringsroetes kan dien waarlangs die doelwitte is om vervoerkoste te minimeer en om die breukdeel van die totale afstand langs die meesterroetebo¨e afgelˆe, te maksimeer. Verder word ’n nuwe herwinningsheuristiek voorgestel wat van historiese oplossings gebruik maak om aanvanklike oplossings vir die benaderde oplossingstegniek van die operasionele fase te genereer. Die raamwerk en gerekenariseerde implementerings van die komponente daarvan word uiteindelik in ’n spesiale gevallestudie toegepas, wat op werklike data berus, ten einde die praktiese toepaslikheid van die werk wat in hierdie proefskrif gerapporteer word, te demonstreer.af_ZA
dc.description.versionDoctorateen_ZA
dc.format.extentxxiv, 179 pages : illustrationsen_ZA
dc.identifier.urihttps://scholar.sun.ac.za/handle/10019.1/128849en_ZA
dc.language.isoen_ZAen_ZA
dc.language.isoen_ZAen_ZA
dc.publisherStellenbosch : Stellenbosch Universityen_ZA
dc.rights.holderStellenbosch Universityen_ZA
dc.subject.lcshVehicle routing problemen_ZA
dc.subject.lcshTravel time (Traffic engineering)en_ZA
dc.subject.lcshBusiness logisticsen_ZA
dc.subject.lcshDelivery of goodsen_ZA
dc.titleA new vehicle routing problem for increased driver-route familiarityen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
king_new_2023.pdf
Size:
3.82 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Doctoral Degrees (Industrial Engineering)