A decision support framework towards a simulation model for the risk-constrained vehicle routing problem
Date
2018-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH SUMMARY: The vehicle routing problem is a well-researched problem in the operations research literature
that typically involves the delivery of commodities to customers in a transportation network.
One particular aspect thereof, however, that has not received as much attention is the security
associated with the transportation of valuable commodities.
Customers typically rely on companies within the cash-in-transit industry to transport valuable
goods between various locations. Due to the high value of these transported goods, the vehicles
are constantly exposed to large amounts of risk and the entire cash-in-transit process is therefore
susceptible to crime.
In this thesis, a decision support system (DSS) framework is put forward for mitigating risk
along cash-in-transit routes. The risk along these routes is directly proportional to the amount
of valuable goods on board a vehicle and the distance travelled by the vehicle. The proposed
routes should, therefore, minimise the risk of the routes and facilitate e ective trade-o s between
a variety of decision criteria that are con gurable by a user. Furthermore, it is envisioned that
the DSS framework may be used as a basis for implementing a simulation model in the future.
The DSS contains three main components, namely a model base, a database and a user interface.
The model base forms the heart of the DSS and is responsible for housing two algorithms
that are both based on the Clarke-Wright savings algorithm. The rst algorithm is for solving
the capacitated vehicle routing problem, is based directly on the original Clarke-Wright algorithm,
and does not include any risk constraint, while the second algorithm is for solving a
risk-constrained variation on the vehicle routing problem and is based on a modi cation of the
Clarke-Wright algorithm. The risk constraint adopted in this thesis involves the speci cation of
a risk threshold to which each route must adhere. Furthermore, the user is able to provide speci
c input and parameter information through the user interface so as to con gure constraints
in order to customise the problem according to his or her preference. After a problem instance
has been solved, the user interface provides a visual output to the user, which the user may
analyse to draw certain conclusions.
The DSS is tested and validated using two di erent methods. The rst method is a trace
validation and the second method is a sensitivity analysis. The sensitivity analysis is performed
in two parts, with the rst part being based on test data from a benchmark library in the vehicle
routing literature and the second part involves parameter variation. The results obtained during
these tests are analysed, con rming that the DSS functions correctly.
The DSS is implemented in a modelling environment capable of solving both the capacitated
vehicle routing problem and its risk-constrained counterpart. The system may be used to observe
the e ect of varying the risk threshold associated with a set of vehicle routes. It is found that
the DSS produces good results when compared with results obtained from benchmark problems
in the literature.
AFRIKAANSE OPSOMMING: Die voertuigroeteringprobleem is 'n goed-nagevorsde probleem in die operasionele navorsingsliteratuur en behels tipies die a ewering van kommoditeite tussen kli ente in 'n vervoernetwerk. Een spesi eke aspek daarvan wat egter nog nie soveel aandag gekry het nie, is die veiligheid wat verband hou met die vervoer van waardevolle kommoditeite. Kli ente maak gewoonlik op maatskappye in die transito-bedryf staat om waardevolle goedere tussen verskillende plekke te vervoer. As gevolg van die ho e waarde van hierdie goedere word voertuie voortdurend aan groot risiko blootgestel en is die hele transito-proses dus vatbaar vir misdaad. In hierdie tesis word 'n besluitsteunstelsel (BSS) raamwerk vir die verlaging van risiko langs kontant-in-transito-roetes voorgestel. Die risiko langs hierdie roetes is direk eweredig aan die hoeveelheid waardevolle goedere aanboord 'n voertuig en die afstand wat die voertuig a ^e. Die voorgestelde roetes moet dus die risiko van die roetes verminder en 'n doeltre ende afruiling tussen 'n verskeidenheid besluitnemingskriteria wat deur 'n gebruiker kon gureerbaar is, fasiliteer. Daarbenewens word daar voorsien dat die BSS raamwerk as basis kan dien vir die toekomstige implementering van 'n simulasiemodel. Die BSS bevat drie hoofkomponente, naamlik 'n modelbasis, 'n databasis en 'n gebruikerskoppelvlak. Die modelbasis vorm die hart van die BSS en bevat implementasies van twee algoritmes wat op die Clarke-Wright spaaralgoritme gebaseer is. Die eerste algoritme kan ingespan word vir die oplossing van die gekapasiteerde voertuigroeteringprobleem, is direk op die oorspronklike Clarke-Wright-algoritme gebaseer, en bevat geen risikobeperking nie, terwyl die tweede algoritme gebruik kan word om 'n risiko-beperkte variasie op die voertuigroeteringsprobleem op te los, en gebaseer is op 'n wysiging van die Clarke-Wright-algoritme. Die risikobeperking wat in hierdie tesis oorweeg word, behels die spesi kasie van 'n risikodrempel waaraan elke roete moet voldoen. Verder kan die gebruiker spesi eke inset- en parameterinligting deur middel van die gebruikerskoppelvlak verskaf om beperkings daar te stel en die probleem volgens sy of haar voorkeur aan te pas. Nadat 'n probleemspesi kasie opgelos is, bied die gebruikerskoppelvlak 'n visuele uitset daarvan aan die gebruiker, wat die gebruiker dan kan analiseer om sekere gevolgtrekkings te maak. Die BSS word deur middel van twee verskillende metodes getoets en gevalideer. Die eerste metode is 'n spoorvalidering terwyl die tweede metode 'n sensitiwiteitsanalise is. Die sensitiwiteitsanalise word in twee dele uitgevoer. Die eerste gedeelte is gebaseer op toetsdata afkomstig van 'n maatstafbiblioteek in die voertuigroeteringsliteratuur en die tweede deel behels parametervariasie. Die resultate wat tydens hierdie toetse behaal word, word ontleed en bevestig dat die DSS korrek funksioneer. Die BSS word in 'n modelleringsomgewing ge mplementeer wat in staat is om beide die gekapasiteerde voertuigroeteringsprobleem en sy risikobeperkte eweknie op te los. Die stelsel kan gebruik word om die e ek van wisselvalligheid in die risikodrempel wat met 'n stel voertuigroetes gepaard gaan, waar te neem. Daar word bevind dat die BSS goeie resultate lewer in vergelyking met die resultate wat vir toetsprobleme in die literatuur verkry word.
AFRIKAANSE OPSOMMING: Die voertuigroeteringprobleem is 'n goed-nagevorsde probleem in die operasionele navorsingsliteratuur en behels tipies die a ewering van kommoditeite tussen kli ente in 'n vervoernetwerk. Een spesi eke aspek daarvan wat egter nog nie soveel aandag gekry het nie, is die veiligheid wat verband hou met die vervoer van waardevolle kommoditeite. Kli ente maak gewoonlik op maatskappye in die transito-bedryf staat om waardevolle goedere tussen verskillende plekke te vervoer. As gevolg van die ho e waarde van hierdie goedere word voertuie voortdurend aan groot risiko blootgestel en is die hele transito-proses dus vatbaar vir misdaad. In hierdie tesis word 'n besluitsteunstelsel (BSS) raamwerk vir die verlaging van risiko langs kontant-in-transito-roetes voorgestel. Die risiko langs hierdie roetes is direk eweredig aan die hoeveelheid waardevolle goedere aanboord 'n voertuig en die afstand wat die voertuig a ^e. Die voorgestelde roetes moet dus die risiko van die roetes verminder en 'n doeltre ende afruiling tussen 'n verskeidenheid besluitnemingskriteria wat deur 'n gebruiker kon gureerbaar is, fasiliteer. Daarbenewens word daar voorsien dat die BSS raamwerk as basis kan dien vir die toekomstige implementering van 'n simulasiemodel. Die BSS bevat drie hoofkomponente, naamlik 'n modelbasis, 'n databasis en 'n gebruikerskoppelvlak. Die modelbasis vorm die hart van die BSS en bevat implementasies van twee algoritmes wat op die Clarke-Wright spaaralgoritme gebaseer is. Die eerste algoritme kan ingespan word vir die oplossing van die gekapasiteerde voertuigroeteringprobleem, is direk op die oorspronklike Clarke-Wright-algoritme gebaseer, en bevat geen risikobeperking nie, terwyl die tweede algoritme gebruik kan word om 'n risiko-beperkte variasie op die voertuigroeteringsprobleem op te los, en gebaseer is op 'n wysiging van die Clarke-Wright-algoritme. Die risikobeperking wat in hierdie tesis oorweeg word, behels die spesi kasie van 'n risikodrempel waaraan elke roete moet voldoen. Verder kan die gebruiker spesi eke inset- en parameterinligting deur middel van die gebruikerskoppelvlak verskaf om beperkings daar te stel en die probleem volgens sy of haar voorkeur aan te pas. Nadat 'n probleemspesi kasie opgelos is, bied die gebruikerskoppelvlak 'n visuele uitset daarvan aan die gebruiker, wat die gebruiker dan kan analiseer om sekere gevolgtrekkings te maak. Die BSS word deur middel van twee verskillende metodes getoets en gevalideer. Die eerste metode is 'n spoorvalidering terwyl die tweede metode 'n sensitiwiteitsanalise is. Die sensitiwiteitsanalise word in twee dele uitgevoer. Die eerste gedeelte is gebaseer op toetsdata afkomstig van 'n maatstafbiblioteek in die voertuigroeteringsliteratuur en die tweede deel behels parametervariasie. Die resultate wat tydens hierdie toetse behaal word, word ontleed en bevestig dat die DSS korrek funksioneer. Die BSS word in 'n modelleringsomgewing ge mplementeer wat in staat is om beide die gekapasiteerde voertuigroeteringsprobleem en sy risikobeperkte eweknie op te los. Die stelsel kan gebruik word om die e ek van wisselvalligheid in die risikodrempel wat met 'n stel voertuigroetes gepaard gaan, waar te neem. Daar word bevind dat die BSS goeie resultate lewer in vergelyking met die resultate wat vir toetsprobleme in die literatuur verkry word.
Description
Thesis (MEng)--Stellenbosch University, 2019.
Keywords
Vehicle routing problem -- Computer simulation, Cash-in-transit -- Risk factors, Decision support system, Decision support framework, Delivery of goods -- Risk factors, UCTD