Optimization methodologies are particularly relevant nowadays due to the ever-increasing power of computers and the enhancement of mathematical models to better capture reality. These computational methods are used in many different fields and some of them, such as metaheuristics, have often been found helpful and efficient for the resolution of practical applications where finding optimal solutions is not straightforward. Many practical applications are multi-objective optimization problems: there is more than one objective to optimize and the solutions found represent trade-offs between the competing objectives. In the last couple of decades, several metaheuristics approaches have been developed and applied to practical problems and multi-objective versions of the main single-objective approaches were created. The Alliance Algorithm (AA) is a recently developed single-objective optimization algorithm based on the metaphorical idea that several tribes, with certain skills and resource needs, try to conquer an environment for their survival and try to ally together to improve the likelihood of conquest. The AA method has yielded reasonable results in several fields to which it has been applied, thus the development in this thesis of a multi-objective variant to handle a wider range of problems is a natural extension. The first challenge in the development of the Multi-objective Alliance Algorithm (MOAA) was acquiring an understanding of the modifications needed for this generalization. The initial version was followed by other versions with the aim of improving MOAA performance to enable its use in solving real-world problems: the most relevant variations, which led to the final version of the approach, have been presented. The second major contribution in this research was the development and combination of features or the appropriate modification of methodologies from the literature to fit within the MOAA and enhance its potential and performance. An analysis of the features in the final version of the algorithm was performed to better understand and verify their behavior and relevance within the algorithm. The third contribution was the testing of the algorithm on a test-bed of problems. The results were compared with those obtained using well-known baseline algorithms. Moreover, the last version of the MOAA was also applied to a number of real-world problems and the results, compared against those given by baseline approaches, are discussed. Overall, the results have shown that the MOAA is a competitive approach which can be used `out-of-the-box' on problems with different mathematical characteristics and in a wide range of applications. Finally, a summary of the objectives achieved, the current status of the research and the work that can be done in future to further improve the performance of the algorithm is provided.

An algorithm is presented that is capable of producing Pareto-optimal solutions for multi-objective infrastructure routing problems: the Multi-Objective Ant Colony Optimization (MOACO). This algorithm offers a constructive search technique to develop solutions to different types of infrastructure routing problems on an open grid framework. The algorithm proposes unique functions such as graph pruning and path straightening to enhance both speed and performance. It also possesses features to solve issues unique to infrastructure routing not found in existing MOACO algorithms, such as problems with multiple end points or multiple possible start points. A literature review covering existing MOACO algorithms and the Ant Colony algorithms they are derived from is presented. Two case studies are developed to demonstrate the performance of the algorithm under different infrastructure routing scenarios. In the first case study the algorithm is implemented into the Ice Road Planning module within the North Slope Decision Support System (NSDSS). Using this ice road planning module a case study is developed of the White Hills Ice road to test the performance of the algorithm versus an as-built road. In the second case study, the algorithm is applied to a raw water transmission routing problem in the Region C planning zone of Texas. For both case studies the algorithm produces a set of results which are similar to the preliminary designs. By successfully applying the algorithm to two separate case studies the suitability of the algorithm to different types of infrastructure routing problems is demonstrated.

In this thesis, we develop an evolutionary algorithm for approximating the Pareto frontier of multi-objective continuous and combinatorial optimization problems. The algorithm tries to evolve the population of solutions towards the Pareto frontier and distribute it over the frontier in order to maintain a well-spread representation. The fitness score of each solution is computed with a Tchebycheff distance function and non-dominating sorting approach. Each solution chooses its own favorable weights according to the Tchebycheff distance function. Some seed solutions at initial population and a crowding measure also help to achieve satisfactory results. In order to test the performance of our evolutionary algorithm, we use some continuous and combinatorial problems. The continuous test problems taken from the literature have special difficulties that an evolutionary algorithm has to deal with. Experimental results of our algorithm on these problems are provided. One of the combinatorial problems we address is the multi-objective knapsack problem. We carry out experiments on test data for this problem given in the literature. We work on two bi-criteria p-hub location problems and propose an evolutionary algorithm to approximate the Pareto frontiers of these problems. We test the performance of our algorithm on Turkish Postal System (PTT) data set (TPDS), AP (Australian Post) and CAB (US Civil Aeronautics Board) data sets. The main contribution of this thesis is in the field of developing a multi-objective evolutionary algorithm and applying it to a number of multi-objective continuous and combinatorial optimization problems.

Organizations providing home care services are inclined to optimize their activities in order to meet the constantly increasing demand for home care. In this context, home care providers are confronted with multiple, often conflicting, objectives such as minimizing their operating costs while maximizing the service level offered to their clients by taking into account their preferences. This paper is the first to shed some light on the trade-off relationship between these two objectives by modeling the home care routing and scheduling problem as a bi-objective problem. The proposed model accounts for qualifications, working regulations and overtime costs of the nurses, travel costs depending on the mode of transportation, hard time windows, and client preferences on visit times and nurses. A distinguishing characteristic of the problem is that the scheduling problem for a single route is a biobjective problem in itself, thereby complicating the problem considerably. A metaheuristic algorithm, embedding a large neighborhood search heuristic in a multi-directional local search framework, is proposed to solve the problem. Computational experiments on a set of benchmark instances based on reallife data are presented. A comparison with exact solutions on small instances shows that the algorithm performs well. An analysis of the results reveals that service providers face a considerable trade-off between costs and client convenience. However, starting from a minimum cost solution, the average service level offered to the clients may already be improved drastically with limited additional costs. (authors' abstract)

We consider multi-objective simulation optimization (MOSO) problems, that is, nonlinear optimization problems in which multiple simultaneous objective functions can only be observed with stochastic error, e.g., as output from a Monte Carlo simulation model. In this context, the solution to a MOSO problem is the efficient set, which is the set of all feasible decision points for which no other feasible decision<br>point is at least as good on all objectives and strictly better on at least one objective. We are concerned primarily with MOSO problems on integer lattices, that is, MOSO<br><div>problems where the feasible set is a subset of an integer lattice. <br></div><div><br></div><div>In the first study, we propose the Retrospective Partitioned Epsilon-constraint with Relaxed Local Enumeration (R-PεRLE) algorithm to solve the bi-objective simulation optimization problem on integer lattices. R-PεRLE is designed for sampling efficiency. It uses a retrospective approximation (RA) framework to repeatedly call<br></div>the PεRLE sample-path solver at a sequence of increasing sample sizes, using the solution from the previous RA iteration as a warm start for the current RA iteration.<br>The PεRLE sample-path solver is designed to solve the sample-path problem only to within a tolerance commensurate with the sampling error. It comprises a call to<br>each of the Pε and RLE algorithms, in sequence. First, Pε searches for new points to add to the sample-path local efficient set by solving multiple constrained single-<br>objective optimization problems. Pε places constraints to locate new sample-path local efficient points that are a function of the standard error away, in the objective space, from those already obtained. Then, the set of sample-path local efficient points found by Pε is sent to RLE, which is a local crawling algorithm that ensures the set is a sample-path approximate local efficient set. As the number of RA iterations increases, R-PεRLE provably converges to a local efficient set with probability one under appropriate regularity conditions. We also propose a naive, provably-convergent<br>benchmark algorithm for problems with two or more objectives, called R-MinRLE. R-MinRLE is identical to R-PεRLE except that it replaces the Pε algorithm with an<br>algorithm that updates one local minimum on each objective before invoking RLE. R-PεRLE performs favorably relative to R-MinRLE and the current state of the art, MO-COMPASS, in our numerical experiments. Our work points to a family of<br><div>RA algorithms for MOSO on integer lattices that employ RLE for certification of a sample-path approximate local efficient set, and for which the convergence guarantees are provided in this study.</div><div><br></div><div>In the second study, we present the PyMOSO software package for solving multi-objective simulation optimization problems on integer lattices, and for implementing<br></div>and testing new simulation optimization (SO) algorithms. First, for solving MOSO problems on integer lattices, PyMOSO implements R-PεRLE and R-MinRLE, which<br>are developed in the first study. Both algorithms employ pseudo-gradients, are designed for sampling efficiency, and return solutions that, under appropriate regularity<br>conditions, provably converge to a local efficient set with probability one as the simulation budget increases. PyMOSO can interface with existing simulation software and<br>can obtain simulation replications in parallel. Second, for implementing and testing new SO algorithms, PyMOSO includes pseudo-random number stream management,<br>implements algorithm testing with independent pseudo-random number streams run in parallel, and computes the performance of algorithms with user-defined metrics.<br>For convenience, we also include an implementation of R-SPLINE for problems with one objective. The PyMOSO source code is available under a permissive open source<br>license.

This thesis focuses on combining data envelopment analysis (DEA) and multi-objective linear programming (MOLP) methods to set targets by referencing peers' performances and decision-makers' (DMs) preferences. A large number of past papers have proven the importance of a company having a target; however, obtaining a feasible but challenging target has always been a difficult topic for companies. Since DEA was proposed in 1978, it has become one of the most popular performance assessment tools. The performance possibility set and efficient frontier established by DEA provide solid and scientific reference information for managers to evaluate an individual's efficiency. Based on the successful experience of DEA in performance assessment, many scholars have mentioned that DEA can be used to set appropriate targets as well; however, traditional DEA models do not include DMs' preference information that is crucial to a target-setting process. Therefore, several MOLP methods have been introduced to include DMs' preferences in the target-setting process based on the DEA efficient frontier and performance possibility set. The trade-off-based method is one of the most popular interactive methods that have been incorporated with DEA. However, there are several gaps in the current research: (1) the trade-off-based method could take so many interactions that no DMs could finish the interactive process; (2) DMs might find it very difficult to provide the preference information required by MOLP models; and (3) DMs cannot have an intuitive view in terms of the efficient frontier. Regarding the gaps above, this thesis proposes three new trade-off-based interactive target-setting models based on the DEA performance possibility set and efficient frontier to improve DMs' experience when setting targets. The three models can work independently or can be combined during the decision-making process. The piecewise linear model uses a piecewise linear assumption to simulate DMs' real utility function. It gradually narrows down the region that could contain DMs' most-preferred solution (MPS) until it reaches an acceptable range. This model could help DMs who have limited time for interaction but want to have a global view of the entire efficient frontier. This model has also been proven very helpful when DMs are not sensitive to close efficient solutions. The prioritized trade-off model provides a new way for a DM to know about the efficient frontier, which allows the DM to explore the efficient frontier following the preferred direction with a series of trade-off tables and trade-off figures as visual aids. The stepwise trade-off model focuses on situations where the number of objectives (outputs/inputs for the DEA model) is quite large and DMs cannot provide all indifference trade-offs between all the objectives simultaneously. To release the DMs' burden, the stepwise model starts from two objectives and gradually includes new objectives in the decision-making process, with the assumption that the indifference trade-offs between previous objectives are fixed, until all objectives are included. All three models have been validated through numerical examples and case studies of a Chinese state-owned bank to help DMs to explore their MPS in the DEA production possibility set.

Master of Engineering (Research) / In many multi-objective missions there are situations when actions based on maximum information gain may not be the `best' given the overall mission objectives. In addition to properties such as entropy, information also has value, which is situationally dependent. This thesis examines the concept of information value in a multi-objective mission from an information theory perspective. A derivation of information value is presented that considers both the context of information, via a fused world belief state, and a system mission. The derived information value is used as part of the objective function for control of autonomous platforms within a framework developed for human robot cooperative control. A simulated security operation in a structured environment is implemented to test both the framework, and information value based control. The simulation involves a system of heterogeneous, sensor equipped Unmanned Aerial Vehicles (UAVs), tasked with gathering information regarding ground vehicles. The UAVs support an e ort to protect a number of important buildings in the area of operation. Thus, the purpose of the information is to aid the security operation by ensuring that security forces can deploy e ciently to counter any threat. A number of di erent local controllers using information based control are implemented and compared to a task based control scheme. The relative performance of each is examined with respect to a number of performance metrics with conclusions drawn regarding the performance and exibility of information value based control.

Health Sciences Centre (HSC) in Winnipeg is the major healthcare facility serving Manitoba, Northwestern Ontario, and Nunavut. An evaluation of HSC’s adult surgical patient flow revealed that one major barrier to smooth flow was their Operating Room (OR) scheduling system. This thesis presents a new two-stage elective OR scheduling system for HSC, which generates weekly OR schedules that reduce artificial variability in order to facilitate smooth patient flow. The first stage reduces day-to-day variability while the second stage reduces variability occurring within a day. The scheduling processes in both stages are mathematically modelled as multi-objective optimization problems. An attempt was made to solve both models using lexicographic goal programming. However, this proved to be an unacceptable method for the second stage, so a new multi-objective genetic algorithm, Nondominated Sorting Genetic Algorithm II – Operating Room (NSGAII-OR), was developed. Results indicate that if the system is implemented at HSC, their surgical patient flow will likely improve. / October 2008

Subspace clustering identifies the attribute support for each cluster as well as identifying the location and number of clusters. In the most general case, attributes associated with each cluster could be unique. A multi-objective evolutionary method is proposed to identify the unique attribute support of each cluster while detecting its data instances. The proposed algorithm, Symbiotic Evolutionary Subspace Clustering (S-ESC) borrows from symbiosis in the sense that each clustering solution is defined in terms of a host, which is formed by a number of co-evolved cluster centroids (or symbionts). Symbionts define clusters and therefore attribute subspaces, whereas hosts define sets of clusters to constitute a non-degenerate clustering solution. The symbiotic representation of S-ESC is the key to making it scalable to high-dimensional datasets, while a subsampling process makes it scalable to large-scale datasets. Performance of the S-ESC algorithm was found to be robust across a common parameterization utilized throughout.

Health Sciences Centre (HSC) in Winnipeg is the major healthcare facility serving Manitoba, Northwestern Ontario, and Nunavut. An evaluation of HSC’s adult surgical patient flow revealed that one major barrier to smooth flow was their Operating Room (OR) scheduling system. This thesis presents a new two-stage elective OR scheduling system for HSC, which generates weekly OR schedules that reduce artificial variability in order to facilitate smooth patient flow. The first stage reduces day-to-day variability while the second stage reduces variability occurring within a day. The scheduling processes in both stages are mathematically modelled as multi-objective optimization problems. An attempt was made to solve both models using lexicographic goal programming. However, this proved to be an unacceptable method for the second stage, so a new multi-objective genetic algorithm, Nondominated Sorting Genetic Algorithm II – Operating Room (NSGAII-OR), was developed. Results indicate that if the system is implemented at HSC, their surgical patient flow will likely improve.