Models and algorithms for integrated optimization problems in operations management and supply chain

• Author(s): Ramos, Bruna Silva
• Date: 2018
• Persistent ID: https://hdl.handle.net/1822/56802
• Origin: RepositóriUM - Universidade do Minho
• Document Type: Doctoral thesis
• Language: English
• Contributor(s): Universidade do Minho; Alves, Cláudio; Carvalho, José Valério de

Description

A presente tese aborda problemas de otimização integrados e está dividida em duas partes principais. A primeira, refere-se a uma variante particular do problema de localização e encaminhamento, enquanto a segunda se foca num caso particular de um problema de produção, inventário e distribuição de bens. As variantes dos problemas tiram partido da múltipla utilização de veículos que se torna importante quando existe, por exemplo, uma rede geográfica pequena e densa, de forma a não a congestionar. O problema de localização e encaminhamento com utilização múltipla de veículos combina dois problemas de otimização diferentes: um problema de localização e um problema de encaminhamento. A integração destes problemas é importante para que possam ser consideradas variáveis comuns aos dois problemas. O problema de localização e encaminhamento com utilização múltipla de veículos prevê a identificação de um determinado conjunto de instalações que devem funcionar e determina qual o conjunto de rotas que deve ser efetuado para satisfazer os pedidos de todos os clientes. Estas rotas estão associadas a uma frota homogénea de veículos, sendo esta frota atribuída a uma instalação funcional. Para a resolução do problema de localização e encaminhamento com utilização múltipla de veículos são utilizados três métodos exatos diferentes: um modelo de fluxo com três índices, um modelo de geração de colunas e um modelo de fluxo nos arcos. No modelo de fluxos com três índices é definido um grafo explícito que inclui um grande número de variáveis relacionadas com a utilização de um arco por um determinado veículo e com a quantidade de fluxo associada a esse mesmo arco. A geração de colunas é dividida no problema mestre que inclui as restrições associadas ao problema de localização de instalações e no sub-problema que agrupa restrições que têm uma estrutura especial, neste caso, o problema do caminho elementar mais curto. Estes problemas vão trocando informação de forma a encontrar a solução global ótima. O modelo de fluxo em arcos é uma abordagem baseada em grafos, mas menos intuitiva, uma vez que os nodos representam instantes de tempo, em vez de clientes. Foram ainda propostos dois métodos heurísticos para a resolução do problema de localização e encaminhamento com utilização múltipla de veículos. Foi proposta uma heurística de arredondamento onde os valores fracionários da relaxação linear das variáveis são arredondados de acordo com determinados critérios e técnicas de arredondamento, e uma heurística de pesquisa em vizinhança variável que explora um conjunto de estruturas de vizinhança de forma definida e sistemática. O problema de produção, inventário e encaminhamento com janelas temporais e utilização múltipla dos veículos é um problema integrado que concilia o problema de gestão da produção e encaminhamento com o problema de gestão de inventários. Neste problema integrado um conjunto de clientes, com pedidos que variam de acordo com o horizonte de planeamento finito, é servido por uma única instalação. A distribuição é feita por uma frota homogénea de veículos que entregam os pedidos de acordo com a janela temporal dos clientes. A gestão da produção é feita de acordo com os inventários existentes quer na instalação, quer no cliente. Para a resolução do problema de produção, inventário e encaminhamento com janelas temporais e utilização múltipla dos veículos foi proposto um modelo exato de fluxos em arcos que tem como base um grafo que considera que os nodos são instantes de tempo. Foram ainda apresentadas duas heurísticas de pesquisa em vizinhança variável baseadas no modelo de fluxo em arcos que de forma sistemática explora um conjunto de estruturas de vizinhança. O principal objetivo dos problemas abordados é minimizar o custo associado às decisões que envolvem todo o sistema. As abordagens propostas foram implementadas e testadas através de vários testes computacionais que tiveram por base um conjunto de instâncias da literatura. Os resultados finais são apresentados e analisados.