A decision support framework towards a simulation model for the risk-constrained vehicle routing problem

[摘要] ENGLISH SUMMARY: The vehicle routing problem is a well-researched problem in the operations research literaturethat 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 securityassociated with the transportation of valuable commodities.Customers typically rely on companies within the cash-in-transit industry to transport valuablegoods between various locations. Due to the high value of these transported goods, the vehiclesare constantly exposed to large amounts of risk and the entire cash-in-transit process is thereforesusceptible to crime.In this thesis, a decision support system (DSS) framework is put forward for mitigating riskalong cash-in-transit routes. The risk along these routes is directly proportional to the amountof valuable goods on board a vehicle and the distance travelled by the vehicle. The proposedroutes should, therefore, minimise the risk of the routes and facilitate e ective trade-o s betweena variety of decision criteria that are con gurable by a user. Furthermore, it is envisioned thatthe 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 algorithmsthat are both based on the Clarke-Wright savings algorithm. Therst algorithm is for solvingthe 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 arisk-constrained variation on the vehicle routing problem and is based on a modi cation of theClarke-Wright algorithm. The risk constraint adopted in this thesis involves the speci cation ofa 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 constraintsin order to customise the problem according to his or her preference. After a problem instancehas been solved, the user interface provides a visual output to the user, which the user mayanalyse to draw certain conclusions.The DSS is tested and validated using two di erent methods. Therst method is a tracevalidation and the second method is a sensitivity analysis. The sensitivity analysis is performedin two parts, with therst part being based on test data from a benchmark library in the vehiclerouting literature and the second part involves parameter variation. The results obtained duringthese tests are analysed, con rming that the DSS functions correctly.The DSS is implemented in a modelling environment capable of solving both the capacitatedvehicle routing problem and its risk-constrained counterpart. The system may be used to observethe e ect of varying the risk threshold associated with a set of vehicle routes. It is found thatthe DSS produces good results when compared with results obtained from benchmark problemsin the literature.

[发布机构] Stellenbosch University