Utilize este identificador para referenciar este registo: https://hdl.handle.net/1822/56802

TítuloModels and algorithms for integrated optimization problems in operations management and supply chain
Autor(es)Ramos, Bruna Silva
Orientador(es)Alves, Cláudio
Carvalho, José Valério de
Data6-Jun-2018
Resumo(s)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.
The present thesis addresses integrated optimization problems and is divided into two main parts. The first refers to a particular variant of the location routing problem, while the second focuses on a particular case of a production, inventory, distribution and routing problem. The variants of the problems take advantage of the multiple use of vehicles that becomes important when, for example, there is a small and dense geographic network in an attempt to decongest the network. The multi-trip location routing problem combines two different optimization problems: a facility location problem and a multi-trip vehicle routing problem. The multi-trip location routing problem consists in the selection of a set of facilities to be opened and the determination of a set of routes used to serve a set of customers. These routes are associated to a homogeneous fleet of vehicles, which is associated to a given facility. To solve the multi-trip location routing problem three different exact methods are proposed: a three-index commodity flow model, a column generation and a network flow model. In the three-index commodity flow model the graph is defined in an explicit way which yields a higher number of variables. The model has variables related to the use of an arc and vehicle, and others representing the flow through the arcs. The column generation process includes two important problems. The restricted master problem that includes restrictions related to the facility location problem, and the sub-problem including constraints which have a special structure related to the elementary shortest path problem. These two problems exchange information in order to find the optimal solution. The network flow model is a graph-based approach, but less intuitive, since nodes represent instants of time instead of clients. Two heuristic methods to solve the multi-trip location routing problem are also proposed. An iterative rounding heuristic where the fractional value of the linear relaxation of the decision variable is rounded according to some parameters and rounding techniques, and a skewed variable neighborhood search heuristic which explores a set of neighborhood structures in a defined and systematic way. The multi-trip production, inventory, distribution and routing problem with time windows is an integrated problem that combines a production and distribution problem, a multi-trip vehicle routing problem and a inventory routing problem. In the multi-trip production, inventory, distribution and routing problem with time windows, a set of clients, which have a time varying demand during a finite planning horizon, is served by a single production facility. The distribution is accomplished by a fleet of homogeneous vehicles that deliver the clients orders within their specific time windows. Production management has to be done according to the inventories at the facility and at the customers. To solve the multi-trip production, inventory, distribution and routing problem with time windows an exact arc flow model based on a graph is proposed, where the nodes represent instants of time. Two model-based variable neighborhood search that systematically explores a set of neighborhood structures exchanging information with the arc flow model are also proposed. The main goal of the presented problems is to minimize the costs associated to the entire system. The proposed approaches were implemented and a set of experimental tests were conducted. Several computational tests were performed based on a set of benchmark instances from the literature. The final results are presented and analyzed.
TipoTese de doutoramento
DescriçãoTese de Doutoramento em Engenharia Industrial e de Sistemas
URIhttps://hdl.handle.net/1822/56802
AcessoAcesso aberto
Aparece nas coleções:BUM - Teses de Doutoramento
DPS - Teses de Doutoramento

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
Bruna Silva Ramos.pdfTese de Doutoramento1,36 MBAdobe PDFVer/Abrir

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID