Dynamic location problems under uncertainty: models and optimization techniques

Abstract

This thesis is devoted to mathematical modelling and solution techniques for dynamic facility location problems under uncertainty. The uncertainty regarding the evolution of important problems' parameters along the planning horizon, such as setup and assignment costs, as well as level or location of demand, is explicitly incorporated into the dynamic models through a finite and discrete set of possible scenarios. In the present work we first propose a two-stage stochastic model for the uncapacitated problem. The first decisions to be made are the strategic ones, where and when to locate the facilities throughout the planning horizon. The second-stage decisions refer to the assignment of the existing customers to the open facilities over the whole planning horizon under each possible scenario. As opposite to location decisions, that must be made here and now and should be valid for all possible future scenarios, assignment can be decided after the uncertainty has been resolved and thus can be adjusted in each time period to each possible scenario. The objective is to find a solution that minimizes the expected total cost over all possible scenarios. This model is then extended to other situations, recognizing that other features should be included in the mathematical model to be able to generate other possible solutions. A set of robust constraints is incorporated into that model, that in spite of restricting the set of admissible solutions, it offers more informed and robust solutions under uncertainty. A multi-objective problem wherein each scenario gives rise to an objective is then developed, and relations with other known problems are established as well. For this latter model, requirements about scenarios probabilities or risk profiles are dropped. Within this context, it is emphasized that the Decision Maker will have a better picture of the compromises that exist among the possible scenarios. In terms of models, we conclude with several extensions considering capacitated facilities. The possibility of unmet demand appears naturally in this class of problems, giving rise to other interesting and challenging questions. We propose and discuss both mono and multi-objective approaches. We proceed with the description of the solution techniques that have been developed to tackle the uncapacitated problems. First we present a primal-dual heuristic approach inspired on classical works and a branch&bound scheme integrating this same heuristic. Afterwards, a Lagrangean relaxation approach developed to tackle the problem with robust constraints is detailed. The calculation of non-dominated solutions for the multi-objective problem is discussed and illustrated. Finally, as the models and algorithms were tested over sets of randomly generated problems, the computational experiments and results obtained are provided including comparisons with general solvers. The results of this work aim to help Decision Makers in the difficult process of decision making when dealing with location problems under uncertainty, and thus should be interpreted as decision support tools.

Esta tese versa sobre modelação matemática e algoritmos de resolução de problemas de localização dinâmica em contextos de incerteza. A incerteza acerca de como importantes parâmetros dos problemas irão evoluir ao longo do tempo, tais como custos de instalação de serviços e de afetação, localização ou nível da procura, é explicitamente incorporada nos modelos dinâmicos através de um conjunto finito e discreto de cenários. Na presente dissertação, propomos em primeiro lugar um modelo estocástico de duas fases para o problema de localização sem restrições de capacidades. As primeiras decisões a serem tomadas são as estratégicas, onde e quando localizar os serviços ao longo do horizonte temporal. As decisões de segunda fase referem-se à afetação dos clientes com procura aos serviços abertos ao longo do horizonte temporal para todos os cenários possíveis. Ao contrário das decisões de localização, tomadas no presente e válidas para todos os futuros possíveis, as decisões de afetação podem ser tomadas após a realização da incerteza e ajustadas em cada período temporal a cada cenário. O objetivo do problema é encontrar uma solução que minimize o custo total esperado para todos os cenários possíveis. Este modelo é depois alargado a outras situações, reconhecendo-se que outras características devem ser incluídas no modelo de modo a gerar outras soluções para o problema. Um conjunto de restrições de robustez é incorporado no modelo que, apesar de restringir o conjunto de soluções admissíveis, oferece soluções mais informadas e robustas em situações de incerteza. Um problema multi-objetivo em que cada cenário origina um objetivo é depois apresentado, assim como relações com outros problemas conhecidos. Requisitos acerca das probabilidades associadas aos cenários ou acerca de perfis de risco são desnecessários. É ainda sublinhado que neste contexto o Agente de Decisão terá um melhor retrato dos compromissos existentes entre os possíveis cenários. Em termos de modelos, concluímos com várias extensões considerando serviços com capacidades limitadas. A possibilidade de procura insatisfeita surge naturalmente nesta classe de problemas, dando lugar a outras interessantes e desafiantes questões. Propomos e discutimos abordagens mono e multi-objetivo. Procedemos à descrição dos algoritmos construídos para resolução dos problemas sem restrições de capacidades. Apresentamos uma heurística primal-dual inspirada em abordagens clássicas e um algoritmo branch&bound que integra aquela heurística. Uma técnica usando relaxação Lagrangeana é depois detalhada para resolução do problema com as restrições de robustez. O cálculo de soluções não dominadas para o problema multi-objetivo é discutido e ilustrado com um exemplo. Finalmente, como tanto os modelos como os algoritmos foram testados com instâncias geradas aleatoriamente, as experiências e resultados computacionais são apresentados, incluindo comparações com general solvers. Os resultados deste trabalho pretendem ajudar os Agentes de Decisão no difícil processo de decisão perante problemas de localização em contexto de incerteza, e assim devem ser interpretados como ferramentas de apoio à decisão.