A new vehicle routing problem for increased driver-route familiarity
Date
2023-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH 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.
AFRIKAANSE 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.
AFRIKAANSE 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.
Description
Thesis (PhD)--Stellenbosch University, 2023.