Multiobjective metaheuristic approaches for mean-risk combinatorial optimisation with applications to capacity expansion

• Type: Thesis
• Date: 2008

Authors

João Alberto Vieira de Campos Pereira Claro (Author) FEUP; Jorge Pinho de Sousa (Author) FEUP; Jorge Pinho de Sousa (Technical adviser) FEUP

Scientific classification

FOS: Natural sciences > Mathematics

CORDIS: Physical sciences > Mathematics > Applied mathematics > Operations research

Other information

Resumo (PT): Muitas decisões em Gestão de Operaçõoes, em particular a um nível estratégico, são tomadas na presença de incerteza. Tendo em conta o impacto destas decisões, a questão do risco está surpreendentemente ausente da maioria da investigação e do trabalho aplicado nesta área. Tal poderá ser parcialmente explicado pela complexidade dos modelos de optimização para estes problemas, uma vez que necessitam de incluir parâmetros incertos, variáveis de decisão lógicas ou outras de natureza discreta, e mais do que um objectivo. Uma das áreas de decisão críticas no âmbito da Estratégia de Operações é a área da Expansão de Capacidade, que se ocupa das decisóes quanto ao tipo, dimensão, calendarização e localização dos investimentos em capacidade. Os modelos de capacidade têm de tratar diversas questões relacionadas com a complexidade acima referida, questões estas que conduzem a não-linearidades, não-convexidades, integralidade e objectivos múltiplos. Por outro lado, as meta-heurísticas multiobjectivo são algoritmos de optimização com características que favorecem uma aplicação extremamente eficiente em problemas com estas dificuldades, tendo, por este motivo, o potencial de vir a assumir um papel importante como abordagens genéricas para problemas de optimização combinatória simultaneamente envolvendo a optimização do valor médio dos resultados e a minimização do risco. O principal objectivo deste trabalho foi realizar uma avaliação preliminar deste potencial. Na primeira parte desta dissertação, apresenta-se uma abordagem de meta-heurísticas multiobjectivo baseadas em pesquisa local para uma formulação média-risco de um problema da mochila estocástico estático, considerando uma versão exacta e uma versão com aproximação amostral do problema, e a variância e o valor em risco condicional como medidas de risco. A segunda parte deste trabalho debruça-se sobre uma formulação média-risco para um problema de investimento em capacidade multi-período, com irreversibilidade, indivisibilidade e economias de escala nos custos de capacidade. É, para este problema, proposta uma abordagem de meta-heurísticas multiobjectivo baseadas em pesquisa local, considerando o valor em risco condicional como medida de risco. Na terceira parte da dissertação, introduz-se flexibilidade de processo no problema tratado na segunda parte, o que conduz, em cada período, a decisões de natureza discreta relativas ao investimento em expansão de capacidade, e decisões de natureza contínua relativas à utilização da capacidade disponível para satisfazer a procura. Os problemas de utilização de capacidade são resolvidos com programação linear, com o objectivo de determinar a capacidade mínima exigida para cada recurso, quando os restantes permanecem inalterados, disponibilizando, assim, informação sobre a admissibilidade das decisões de investimento. A este problema são aplicadas meta- heurísticas multiobjectivo baseadas em pesquisa local (em que novamente se considera o valor em risco condicional como medida de risco). Os estudos computacionais realizados indicam claramente que as abordagens desenvolvidas são capazes de produzir aproximações aos conjuntos eficientes média-risco de elevada qualidade, com um esforço computacional modesto. Fica, assim, validada a hipótese de que as meta-heurísticas multiobjectivo constituem uma classe de algoritmos apropriados para lidar com as dificuldades apresentadas pelos problemas de optimização combinatória média-risco.

Abstract (EN): Many decisions in Operations Management, in particular at a strategic level, are made in the presence of uncertainty. Considering the impact of these decisions, risk concerns are surprisingly absent in the majority of research and applied work in this area. This may be partially explained by the complexity of optimisation models for these problems, as they must include uncertain parameters, logical or other discrete decision variables, and more than one objective. One of the critical decision areas within Operations Strategy is Capacity Expansion, which is concerned with deciding the type, magnitude, timing, and location of capacity acquisition. Capacity models are required to address a variety of problem features related to the previously mentioned complexity, these features leading to nonlinearities, nonconvexities, integrality and multiple objectives. On the other hand, multiobjective metaheuristics are optimisation algorithms extremely well suited to efficiently tackle problems that present these difficulties. They have therefore the potential to play an important role as general approaches for combinatorial optimisation problems simultaneously dealing with the optimisation of mean results and the minimisation of risk. The primary objective of our work was to perform a preliminary assessment of this potential. In the first part of this dissertation, we present a multiobjective local search metaheuristic approach for both exact and sample approximation versions of a mean- risk static stochastic knapsack problem, considering both variance and conditional value-at-risk as risk measures. The second part of this work is concerned with a mean-risk multistage capacity investment problem with irreversibility, lumpiness and economies of scale in capacity costs. We propose a multiobjective local search metaheuristic approach for this problem, considering conditional value-at-risk as a risk measure. In the third part of the dissertation, we introduce process flexibility in the problem addressed in the second part, leading to the consideration, in each period, of discrete decisions concerning the investment in capacity expansion, and continuous decisions concerning the utilization of the available capacity to satisfy demand. We solve the capacity utilization problems with linear programming, in order to find the minimum capacity for each resource with the other resources remaining unchanged. In this way, information is provided on the feasibility of the discrete investment decisions. We apply a multiobjective local search metaheuristic to this problem, again considering conditional value-at-risk as a risk measure. Results of computational studies are presented, that clearly indicate the designed approaches are capable of producing high-quality approximations to the mean-risk efficient sets, with a modest computational effort, thus validating the hypothesis that multiobjective metaheuristics are a class of algorithms well suited to deal with the difficulties presented by mean-risk combinatorial optimisation problems.

Language: Portuguese

Type (Professor's evaluation): Scientific

No. of pages: 124