The problem addressed in this paper is the integrated vehicle-crew-rostering problem (VCRP) aiming to define the schedules for the buses and the rosters for the drivers of a public transit company. The VCRP is described by a bi-objective mixed binary linear programming model with one objective function aggregating vehicle and crew scheduling costs and the other the rostering features. The VCRP is solved by a heuristic approach based on Benders decomposition where the master problem is partitioned into daily integrated vehicle-crew scheduling problems and the sub-problem is a rostering problem. Computational experience with data from a bus company in Lisbon shows the ability of the decomposition approach for producing a variety of potentially efficient solutions for the VCRP within low computing times.

This paper presents an evolutionary multi-objective optimization problem formulation for the anti-spam filtering problem, addressing both the classification quality criteria (False Positive and False Negative error rates) and email messages classification time (minimization). This approach is compared to single objective problem formulations found in the literature, and its advantages for decision support and flexible/adaptive anti-spam filtering configuration is demonstrated. A study is performed using the Wirebrush4SPAM framework anti-spam filtering and the SpamAssassin email dataset. The NSGA-II evolutionary multi-objective optimization algorithm was applied for the purpose of validating and demonstrating the adoption of this novel approach to the anti-spam filtering optimization problem, formulated from the multi-objective optimization perspective. The results obtained from the experiments demonstrated that this optimization strategy allows the decision maker (anti-spam filtering system administrator) to select among a set of optimal and flexible filter configuration alternatives with respect to classification quality and classification efficiency.

Reactive power compensation is an important problem in electrical distribution systems, involving the sizing and location of capacitors (sources of reactive power). The installation of capacitors also contributes to releasing system capacity and improving voltage level. A multi-objective simulated annealing approach to provide decision support in this problem is presented. This approach is able to compute a set of well-distributed and diversified solutions underlying distinct trade-offs, even for a challenging network. The characterization of the non-dominated front is relevant information for aiding planning engineers to select satisfactory compromise solutions (compensation schemes) to improve the network operation conditions.

Multi-objective optimization problems, which consider multiple objective functions to be optimized, can arise in many real-life scenarios, e.g., when trying to minimize both the cost and the time needed for traveling between two locations. In the last few decades, several algorithms have been proposed to solve multi-objective optimization problems. These algorithms can have very distinct behaviors, and their performance is often significantly affected by the problem instance to be solved, the time budget available, or the desirable solution quality. As such, which algorithm performs best often depends on the scenario that is being considered.This gives rise to the algorithm selection problem, which is concerned with the automatic selection of the best algorithm for a given scenario. In this thesis, we investigate the case of automatically selecting the best multi-objective optimization algorithm to solve a previously unseen problem instance, taking into account that the available time budget and desirable solution quality may be uncertain, and are only known when selecting the algorithm. We make several contributions in this line.First, we propose theoretical and empirical models to characterize the anytime performance of an algorithm, i.e., how solution quality improves over time, for previously unseen problem instances. Then, considering these models, we develop an offline selection methodology to select the best algorithm for a previously unseen problem instance given a utility function that describes the desirable time budget and solution quality. We also propose an online selection methodology that can swap between multi-objective branch and bound strategies to improve anytime performance. Lastly, we propose a scalarization technique and a branch and bound search strategy for multi-objective optimization problems to achieve a better anytime performance than previous approaches. Each contribution is backed by an experimental study on a multi-objective knapsack problem, and the results highlight the quality of the proposed models, selection methodologies, and algorithms.

Water supply systems are very important for societies. If these systems are to function properly uncertainty must be handled. Flexibility is essential when operating systems for long-term planning horizons where uncertainty is high. This work proposes a multi-objective framework based on Real Options with three objectives. A Pareto front of solutions is traced whilst satisfying the constraints of the model. The hydraulic constraints are checked using EPANET hydraulic simulator. The model is solved by means of a multi-objective simulated annealing algorithm and the results are presented through a visualization tool and by showing some water network designs for specific solutions.

O objetivo deste trabalho foi o estudo do problema de Steiner em grafos e sua aplicação na determinação de ligações multiponto-multiponto em redes de Telecomunicações, em particular em redes de transporte. Sendo assim, estudou-se mais profundamente uma heurística de referência para o problema de Steiner e ainda uma meta-heurística que obtém muito bons resultados para este problema. Em problemas reais, para além de se querer obter as árvores de menor custo (aditivo) para a interligação de um subconjunto de nós da rede envolvidos em cada ligação multipontomultiponto, custo esse que pode representar, por exemplo, a ocupação de cada link, também se pode pretender obter as árvores com um número mínimo de arcos, por forma a que as ligações multiponto-multiponto possam ser implementadas com o mínimo de recursos da rede. Assim formula-se um problema de Steiner bi-critério para o qual se propõe uma extensão da meta-heurística anterior de modo a resolver esse problema. Os resultados obtidos pela implementação da meta-heurística original (mono-critério) são comparados exaustivamente com os resultados obtidos pelos seus autores, o que permitiu tirar conclusões sobre a forma pouco clara como estes últimos resultados foram conseguidos, bem como identificar aspetos em que a meta-heurística poderia ser melhorada. Estas conclusões foram fundamentais para o desenvolvimento de uma meta-heurística, baseada em princípios idênticos à anteriormente referida, para a resolução do problema bi-critério. No problema bi-critério, a meta-heurística desenvolvida revelou-se bastante superior a três outras heurísticas desenvolvidas anteriormente para a resolução do mesmo problema. Os resultados obtidos permitem ainda identificar aspetos que podem vir a ser melhorados em trabalhos futuros.

The controversy raised around biofuels sustainability increased the pressure on biodiesel producers to be as cost efficient as possible and, simultaneously, ensure the sustainability of the biodiesel. As about 85% of biodiesel production costs are attributed to feedstock cost and each feedstock has a different environmental profile, operational level decision making about feedstock selection is crucial to reduce production costs and manage biodiesel environmental performance. This thesis explores opportunities to improve biodiesel cost effectiveness at the operational level, particularly in the feedstock selection process, by assessing the use of waste-based feedstocks (Waste Cooking Oil, WCO) in blends with conventional feedstocks (palm, rapeseed and soya) and hedging feedstock purchase, whilst managing environmental impacts. For this purpose, an uncertainty-aware decision aiding tool to assess economic and environmental tradeoffs of decisions at the operational level, addressing feedstock compositional and price uncertainty, was developed. The model combines environmental life-cycle assessment (LCA) with blending models using multi-objective optimization to assess water scarcity (WSI), water degradability – acidification (AA), eutrophication (EU), ecotoxicity (FT) and human toxicity (HT) – and Greenhouse Gas (GHG) emissions (CC). Data from different crop cultivation locations were considered: Colombia and Malaysia for palm; Argentina, Brazil and the United States (US) for soybean; and, Germany, France, Spain, Canada and the US for rapeseed. An approach was developed to facilitate the decision process that enables the decision-maker to select the best compromise feedstock blend based on an explicit overall environmental performance. Results show that incorporating feedstocks’ compositional uncertainty allows the use of WCO in blends with conventional feedstocks without compromising biodiesel technical performance. A reduction of total feedstock cost was obtained for blends with WCO relatively to equivalent (similar technical performance) blends composed only of virgin oils. The percentage of cost reduction depends on the relation among the prices of the feedstocks. Moreover, the use of WCO in the blends allows a reduction in cost variation reduction relatively to virgin oils blends because the price of that feedstock presents lower volatility comparatively to the conventional feedstocks. The differences observed in the environmental assessment of the various virgin oils systems are mainly related to water scarcity of the location, and the fertilization and pesticides schemes used in each crop/location. Results show that higher water scarcity footprint are due to both high water consumption and high water scarcity of the cultivation site. For the toxicity categories (HT and FT), the highest values are ascribed to the high quantity of pesticide used in the cultivation, while for CC, AA and EU the main contributor is the quantity of fertilizers. WCO presents the lowest values WSI, CC, EU and AA. The multi-objective analysis showed that lower CC and WSI solutions (blends) can be obtained at a lower cost if WCO is included in the biodiesel blend. The same conclusion is obtained when more environmental objectives (AA, EU, FT and HT) are considered in the analysis. The decision-aiding approach developed allows for the visualization of the tradeoff between cost and environmental impacts, facilitating the decision process when more than three objectives are at stake. This research shows that the inclusion of WCO in a diversified portfolio of feedstocks used in blending optimization models is an attractive approach to improve biodiesel cost effectiveness and environmental performance. The model developed can be further used to optimize the blending of alternative feedstocks and to assess the technical viability of other waste-based feedstock (e.g. animal fat) or emerging feedstocks such as algae. Although the tool was designed specifically for biodiesel production system, it can be adapted to other industries, particularly in the recycling sector, to support production planning at the operational level to enhance technical, economic and environmental performance of these industries.

Recent research has focused on the development of implicit enumeration techniques to efficiently solve multi-objective combinatorial optimization (MOCO) problems to optimality.This thesis aims at improving the state-of-the-art of implicit enumeration techniques for these problems, tackling two related research questions.First, it explores concepts of adjacency among solutions to find sets of solutions in problems with more than two objective functions.A new algorithm for computing the set of supported non-dominated points in the objective space and all the corresponding efficient solutions in the decision space for the multi-objective spanning tree (MOST) problem is proposed.This algorithm is based on the connectedness property of the weight set in the weighting space defined for a parametric version of the MOST problem.An indifference region for each supported non-dominated point is obtained by reducing the search space. An adjacency relation defined in the decision space is used to compute all the supported efficient spanning trees associated to the same non-dominated supported point as well as to define the indifference region of the next points.Second, this thesis explores how sets of solutions can be kept in memory as compressed as possible, with the least performance impact as possible.It proposes algorithmic techniques that extend and empirically improve the memory usage of a dynamic programming algorithm for computing the set of efficient solutions both in the objective and in the decision spaces for the bi-objective knapsack problem.In-depth computational analysis for both parts of the thesis are presented.

ABSTRACT The main goal of this paper is to propose a methodology for selecting investment portfolios designed to generate financial returns and a socio-environmental impact. This work suggests a seven-step protocol that prioritizes the use of scientific evidence, quality data sources and the interdependence of investment alternatives. In particular, it proposes a multi-objective evolutionary optimization model to estimate the efficient frontier and select the portfolio according to the decision maker’s preferences. By an innovative extension of the concept of portfolio diversification, already well understood in traditional portfolio management, this study concludes that it is possible for impact investors to build more efficient portfolios. Due to the scarcity of similar studies in the literature and the rare use of rigorous methods for implementing impact investments, this study, therefore, presents an academic contribution to the field and illustrates the use of the proposed methodology to improve management decisions.

In a typical image classification task, the analyst decides beforehand the number of classes and which image channels to use. If there is a need to modify the classes or data channels, it is necessary to start over. This paper proposes a scenario analysis tool for the task of image classification as a way of automating this process. Each scenario represents the parameters that will be used in a complete supervised classification task, including training and classification. The proposed method uses multi-objective optimization to evaluate different sets of attributes and classes, and presents the compromising solutions, regarding the user objectives. A class hierarchy structure is used to generate different class sets, and the system attempts to find the most appropriate combinations of class and attribute sets. In this work, the system is applied to remote sensing problems and we consider three objectives: the best classification accuracy, the smallest attribute set and the biggest class set. The system shows the compromising combinations of class and attribute sets, along with the accuracy on a testing sample. The user can then choose which combination to use for the image classification.