• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 2
  • 2
  • 2
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

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

Hauman, Charlotte 12 1900 (has links)
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.
2

Routing and Scheduling with Time Windows: Models and Algorithms for Tramp Sea Cargos and Rail Car-Blocks

Daniel, Aang 20 November 2006 (has links)
This thesis introduces a new model formulation to solve routing and scheduling problems, with the main applications in answering routing and scheduling problems faced by a sea-cargo shipping company and a railroad company. For the work in sea-cargo routing and scheduling, we focus on the tramp shipping operation. Tramp shipping is a demand-driven type of shipping operation which does not have fixed schedules. The schedules are based on the pickup and download locations of profitable service requests. Given set of products distributed among a set of ports, with each product having pickup and download time windows and a destination port, the problem is to find the schedule for a fleet of ships that maximizes profit over a specified time horizon. The problem is modeled as a Mixed Integer Non-Linear Program and reformulated as an equivalent Mixed Integer Linear Program. Three heuristic methods, along with computational results, are presented. We also exploit the special structure enjoyed by our model and introduce an upper-bounding problem to the model. With a little modification, the model is readily extendable to reflect soft time windows and inter-ship cargo-transfers. The other part of our work deals with train routing and scheduling. A typical train shipment consists of a set of cars having a common origin and destination. To reduce the handling of individual shipments as they travel, shipments are grouped into blocks. The problem is that given sets of blocks to be carried from origins to destinations, construct the most cost effective train routes and schedules and determine block-to-train assignments, such that the number of block transfers (block swaps) between trains, the number of trains used, and some other cost measures are minimized. Incorporating additional precedence requirements, the modeling techniques from the shipping research are employed to formulate a mixed integer nonlinear program for this train routing and scheduling problem. Computational results are presented.

Page generated in 0.0647 seconds