Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Heuristic and metaheuristic approaches to the multi-period vehicle routing problem with time windows and rolling planning horizon
Thesis (MCom)--Stellenbosch University, 2025.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Stellenbosch : Stellenbosch University
2025
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613973882339328 |
|---|---|
| access_status_str | Open Access |
| author | Harmse, Greg |
| author2 | Visagie, S. E. |
| author_browse | Harmse, Greg Visagie, S. E. |
| author_facet | Visagie, S. E. Harmse, Greg |
| author_sort | Harmse, Greg |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MCom)--Stellenbosch University, 2025. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/134627 |
| institution | Stellenbosch University (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:44:39.798Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2025 |
| publishDateRange | 2025 |
| publishDateSort | 2025 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/134627 Heuristic and metaheuristic approaches to the multi-period vehicle routing problem with time windows and rolling planning horizon Harmse, Greg Visagie, S. E. Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics. Vehicle routing problem -- South Africa Logistics -- Mathematical models Freight and freightage -- Mathematical models Inventory control -- Mathematical models Delivery of goods -- Mathematical models UCTD Thesis (MCom)--Stellenbosch University, 2025. Harmse, G. 2025. Heuristic and metaheuristic approaches to the multi-period vehicle routing problem with time windows and rolling planning horizon. Unpublished masters thesis. Stellenbosch: Stellenbosch University [online]. Available: https://scholar.sun.ac.za/items/9ac043fc-f104-4517-b71f-820beeb4d8fc ENGLISH SUMMARY: The increasing demand for efficient goods distribution to retail outlets across vast geographical areas, particularly in South Africa’s retail landscape, necessitates optimised vehicle routing solu-tions. This research investigates solution methods for the multi-period vehicle routing problem with time windows (MPVRPTW) to minimise transportation costs and improve distribution efficiency from distribution centers to retail outlets over extended planning periods. A dynamic optimisation approach was developed using a rolling planning horizon methodology to address realistic inventory dynamics in retail distribution networks, where store inventories fluctuate daily based on customer demand and delivery schedules. Three algorithm approaches were implemented and evaluated: an ant colony optimisation algorithm, the slack induction by string removals (SISR) algorithm, and a hybrid combination of both methods. Multi-period extensions were incorporated into each algorithm to handle temporal constraints and delivery fre-quency requirements. Test cases were generated from established Solomon benchmark instances while preserving optimal objective function values. Parameter calibration was performed using grid search methodology with literature-derived values. Algorithm performance was analysed across test case groups characterised by geographical distribution, planning horizon length, and time window constraints. Interventions were added in the dynamic problem to further reduce travel times. These interventions include a penalty for vehicle underutilisation, planning for average daily inventory increases and vehicle capacity reduction. The multi-period SISR algorithm outperforms the other two algorithms in stability and objective function values for all test cases, followed by the hybridisation of the two algorithms. The average percentage error of the multi-period SISR algorithm across all test cases is 4.70%, while the average percentage error of the best of 5 runs for each test case is 2.09%. The inclusion of the vehicle capacity reduction intervention with a planning horizon of 2 days leads to an average of 5.22% reduction in total route travel time over a period of 30 days as well as a 6.45% reduction in the number of vehicles used during the same time period. AFRIKAANSE OPSOMMING: Die toenemende behoefte aan doeltreffende verspreiding van goedere na kleinhandelwinkels regoor uitgestrekte geografiese gebiede, soos in die Suid-Afrika se kleinhandellandskap, vereis geoptimeerde voertuigroetebepaling. Hierdie tesis ondersoek oplossingsmetodes vir die multi-periode voertuigroetebepalingsprobleem met tydvensters (MPVRPTW) om vervoerkoste te minimeer en verspreidingsdoeltreffendheid vanaf verspreidingsentrums na kleinhandelwinkels te verbeter oor uitgebreide beplanningsperiodes. ’n Dinamiese optimeringsbenadering is ontwikkel deur gebruik te maak van ’n rollende beplanningshorison-metodologie om realistiese voorraaddinamika in kleinhandelverspreidingsnetwerke aan te spreek. Winkelvoorrade wissel daagliks gebaseer op klientevraag en afleweringskedules. Drie algoritmiese benaderings is geimplementeer en geevalueer, naamlik ’n mierkolonie-algoritme, die “speling geınduseer deur reeks verwyderings” (Eng.: slack induction by string removals) of SISR algoritme, en ’n hibriede kombinasie van beide hierdie metodes. Multi-periode uitbreidings is vir elke algoritme geınkorporeer om temporale beperkings en afleweringsfrekwensievereistes te hanteer. Toetsgevalle is gegenereer vanaf die gevestigde Solomon toets-instansies terwyl optimale doelfunksiewaardes behou is. Parameterkalibrering is uitgevoer deur gebruik te maak van ’n roostersoekingmetodologie rondom literatuur-afgeleide waardes. Algoritmeprestasie is ontleed oor toetsgevalgroepe wat verskil in terme van geografiese verspreiding, beplanningshorison-lengte, en tydvensterbeperkings. Intervensies is by die dinamiese probleem gevoeg om reistye verder te verminder. Hierdie intervensies sluit in ’n boete vir voertuigonderbenutting, beplanning vir gemiddelde daaglikse voorraadtoenames, en voertuigkapasiteitvermindering. Die multi-periode SISR algoritme doen beter as die ander twee algoritmes in terme van stabiliteit en doelfunksiewaarde vir alle toetsgevalle, en word gevolg deur die hibriede benadering. Die gemiddelde persentasie fout van die multi-periode SISR algoritme oor al die toesgevalle is 4.70%, terwyl die gemiddelde persentasie fout oor vyf lopies vir elke toetsgeval 2.09% is. Deur die vermindering van die voertuig kapasiteit oor ’n beplannings horison van 2 dae te implementeer lewer ’n 5.22% vermindering in die totale afstand afgele oor 30 dae en lewer ook ’n 6.45% vermindering in die aantal voertuie wat gebruik word in hierdie periode. Masters 2025-12-19T08:47:49Z 2025-12-19T08:47:49Z 2025-12 Thesis https://scholar.sun.ac.za/handle/10019.1/134627 en Stellenbosch University xii, 84 pages : illustrations, includes annexures application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Vehicle routing problem -- South Africa Logistics -- Mathematical models Freight and freightage -- Mathematical models Inventory control -- Mathematical models Delivery of goods -- Mathematical models UCTD Harmse, Greg Heuristic and metaheuristic approaches to the multi-period vehicle routing problem with time windows and rolling planning horizon |
| title | Heuristic and metaheuristic approaches to the multi-period vehicle routing problem with time windows and rolling planning horizon |
| title_full | Heuristic and metaheuristic approaches to the multi-period vehicle routing problem with time windows and rolling planning horizon |
| title_fullStr | Heuristic and metaheuristic approaches to the multi-period vehicle routing problem with time windows and rolling planning horizon |
| title_full_unstemmed | Heuristic and metaheuristic approaches to the multi-period vehicle routing problem with time windows and rolling planning horizon |
| title_short | Heuristic and metaheuristic approaches to the multi-period vehicle routing problem with time windows and rolling planning horizon |
| title_sort | heuristic and metaheuristic approaches to the multi period vehicle routing problem with time windows and rolling planning horizon |
| topic | Vehicle routing problem -- South Africa Logistics -- Mathematical models Freight and freightage -- Mathematical models Inventory control -- Mathematical models Delivery of goods -- Mathematical models UCTD |
| url | https://scholar.sun.ac.za/handle/10019.1/134627 |
| work_keys_str_mv | AT harmsegreg heuristicandmetaheuristicapproachestothemultiperiodvehicleroutingproblemwithtimewindowsandrollingplanninghorizon |