The application of the cross-entropy method for multi-objective optimisation to combinatorial problems

[摘要] ENGLISH ABSTRACT: Society is continually in search of ways to optimise various objectives.When faced with multiple and conicting objectives, humans are inneed of solution techniques to enable optimisation. This researchis based on a recent venture in theeld of multi-objective optimisation,the use of the cross-entropy method to solve multi-objectiveproblems. The document provides a brief overview of the twoelds,multi-objective optimisation and the cross-entropy method, touchingon literature, basic concepts and applications or techniques. Theapplication of the method to two problems is then investigated. The rst application is to the multi-objective vehicle routing problem withsoft time windows, a widely studied problem with many real-worldapplications. The problem is modelled mathematically with a transitionprobability matrix that is updated according to cross-entropyprinciples before converging to an approximation solution set. Thehighly constrained problem is successfully modelled and the optimisationalgorithm is applied to a set of benchmark problems. It wasfound that the cross-entropy method for multi-objective optimisationis a valid technique in providing feasible and non-dominated solutions.The second application is to a real world case study in blood managementdone at the Western Province Blood Transfusion Service. Theconceptual model is derived from interviews with relevant stakeholdersbefore discrete event simulation is used to model the system. Thecross-entropy method is used to optimise the inventory policy of thesystem by simultaneously maximising the combined service level of thesystem and minimising the total distance travelled. By integrating theoptimisation and simulation model, the study shows that the inventory policy of the service can improve signi cantly, and the use of thecross-entropy algorithm adequately progresses to a front of solutions.The research proves the remarkable width and simplicity of possibleapplications of the cross-entropy algorithm for multi-objective optimisation,whilst contributing to literature on the vehicle routing problemand blood management. Results on benchmark problems for the vehiclerouting problem with soft time windows are provided and animproved inventory policy is suggested to the Western Province BloodTransfusion Service.

[发布机构] Stellenbosch University