Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
The application of the cross-entropy method for multi-objective optimisation to combinatorial problems
Thesis (MScEng)--Stellenbosch University, 2012.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2012
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613756841787392 |
|---|---|
| access_status_str | Open Access |
| author | Hauman, Charlotte |
| author2 | Bekker, James F. |
| author_browse | Bekker, James F. Hauman, Charlotte |
| author_facet | Bekker, James F. Hauman, Charlotte |
| author_sort | Hauman, Charlotte |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MScEng)--Stellenbosch University, 2012. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/71636 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:41:12.661Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2012 |
| publishDateRange | 2012 |
| publishDateSort | 2012 |
| 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/71636 The application of the cross-entropy method for multi-objective optimisation to combinatorial problems Hauman, Charlotte Bekker, James F. Stellenbosch University. Faculty of Engineering. Dept. of Industrial Engineering. Multi-objective optimisation Soft time windows Cross-entropy method Cross-entropy algorithm Western Province Blood Transfusion Service Dissertations -- Industrial engineering Theses -- Industrial engineering Thesis (MScEng)--Stellenbosch University, 2012. ENGLISH ABSTRACT: Society is continually in search of ways to optimise various objectives. When faced with multiple and con icting objectives, humans are in need of solution techniques to enable optimisation. This research is based on a recent venture in the eld of multi-objective optimisation, the use of the cross-entropy method to solve multi-objective problems. The document provides a brief overview of the two elds, multi-objective optimisation and the cross-entropy method, touching on literature, basic concepts and applications or techniques. The application of the method to two problems is then investigated. The rst application is to the multi-objective vehicle routing problem with soft time windows, a widely studied problem with many real-world applications. The problem is modelled mathematically with a transition probability matrix that is updated according to cross-entropy principles before converging to an approximation solution set. The highly constrained problem is successfully modelled and the optimisation algorithm is applied to a set of benchmark problems. It was found that the cross-entropy method for multi-objective optimisation is a valid technique in providing feasible and non-dominated solutions. The second application is to a real world case study in blood management done at the Western Province Blood Transfusion Service. The conceptual model is derived from interviews with relevant stakeholders before discrete event simulation is used to model the system. The cross-entropy method is used to optimise the inventory policy of the system by simultaneously maximising the combined service level of the system and minimising the total distance travelled. By integrating the optimisation and simulation model, the study shows that the inventory policy of the service can improve signi cantly, and the use of the cross-entropy algorithm adequately progresses to a front of solutions. The research proves the remarkable width and simplicity of possible applications of the cross-entropy algorithm for multi-objective optimisation, whilst contributing to literature on the vehicle routing problem and blood management. Results on benchmark problems for the vehicle routing problem with soft time windows are provided and an improved inventory policy is suggested to the Western Province Blood Transfusion Service. AFRIKAANSE OPSOMMING: Die mensdom is voortdurend op soek na maniere om verskeie doelwitte te optimeer. Wanneer die mens konfrontreer word met meervoudige en botsende doelwitte, is oplossingsmetodes nodig om optimering te bewerkstellig. Hierdie navorsing is baseer op 'n nuwe wending in die veld van multi-doelwit optimering, naamlik die gebruik van die kruisentropie metode om multi-doelwit probleme op te los. Die dokument verskaf 'n bre e oorsig oor die twee velde { multi-doelwit optimering en die kruis-entropie-metode { deur kortliks te kyk na die beskikbare literatuur, basiese beginsels, toepassingsareas en metodes. Die toepassing van die metode op twee onafhanklike probleme word dan ondersoek. Die eerste toepassing is di e van die multi-doelwit voertuigroeteringsprobleem met plooibare tydvensters. Die probleem word eers wiskundig modelleer met 'n oorgangswaarskynlikheidsmatriks. Die matriks word dan deur kruis-entropie beginsels opdateer voor dit konvergeer na 'n benaderingsfront van oplossings. Die oplossingsruimte is onderwerp aan heelwat beperkings, maar die probleem is suksesvol modelleer en die optimeringsalgoritme is gevolglik toegepas op 'n stel verwysingsprobleme. Die navorsing het gevind dat die kruis-entropie metode vir multi-doelwit optimering 'n geldige metode is om 'n uitvoerbare front van oplossings te beraam. Die tweede toepassing is op 'n gevallestudie van die bestuur van bloed binne die konteks van die Westelike Provinsie Bloedoortappingsdiens. Na aanleiding van onderhoude met die relevante belanghebbers is 'n konsepmodel geskep voor 'n simulasiemodel van die stelsel gebou is. Die kruis-entropie metode is gebruik om die voorraadbeleid van die stelsel te optimeer deur 'n gesamentlike diensvlak van die stelsel te maksimeer en terselfdetyd die totale reis-afstand te minimeer. Deur die optimerings- en simulasiemodel te integreer, wys die studie dat die voorraadbeleid van die diens aansienlik kan verbeter, en dat die kruis-entropie algoritme in staat is om na 'n front van oplossings te beweeg. Die navorsing bewys die merkwaardige wydte en eenvoud van moontlike toepassings van die kruis-entropie algoritme vir multidoelwit optimering, terwyl dit 'n bydrae lewer tot die afsonderlike velde van voertuigroetering en die bestuur van bloed. Uitslae vir die verwysingsprobleme van die voertuigroeteringsprobleem met plooibare tydvensters word verskaf en 'n verbeterde voorraadbeleid word aan die Westelike Provinsie Bloedoortappingsdiens voorgestel. 2012-11-30T09:02:50Z 2012-12-12T08:07:11Z 2012-11-30T09:02:50Z 2012-12-12T08:07:11Z 2012-12 Thesis http://hdl.handle.net/10019.1/71636 en_ZA Stellenbosch University 115 p. : ill. application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Multi-objective optimisation Soft time windows Cross-entropy method Cross-entropy algorithm Western Province Blood Transfusion Service Dissertations -- Industrial engineering Theses -- Industrial engineering Hauman, Charlotte The application of the cross-entropy method for multi-objective optimisation to combinatorial problems |
| title | The application of the cross-entropy method for multi-objective optimisation to combinatorial problems |
| title_full | The application of the cross-entropy method for multi-objective optimisation to combinatorial problems |
| title_fullStr | The application of the cross-entropy method for multi-objective optimisation to combinatorial problems |
| title_full_unstemmed | The application of the cross-entropy method for multi-objective optimisation to combinatorial problems |
| title_short | The application of the cross-entropy method for multi-objective optimisation to combinatorial problems |
| title_sort | application of the cross entropy method for multi objective optimisation to combinatorial problems |
| topic | Multi-objective optimisation Soft time windows Cross-entropy method Cross-entropy algorithm Western Province Blood Transfusion Service Dissertations -- Industrial engineering Theses -- Industrial engineering |
| url | http://hdl.handle.net/10019.1/71636 |
| work_keys_str_mv | AT haumancharlotte theapplicationofthecrossentropymethodformultiobjectiveoptimisationtocombinatorialproblems AT haumancharlotte applicationofthecrossentropymethodformultiobjectiveoptimisationtocombinatorialproblems |