Various kinds of optimization problems involve nonlinear functions of binary variables that exhibit a property of diminishing marginal returns. Such a property is known as submodularity. Vast amount of work has been devoted to the problem of submodular optimization. In this thesis, we exploit structural information for several classes of submodular optimization problems. We strive for polynomial time algorithms with improved approximation ratio and strong mixed-integer linear formulations of mixed-integer non-linear programs where the epigraph and hypograph of submodular functions of a specific form appear as a substructure together with other side constraints. In Chapter 2, we develop approximation algorithms for the expected utility knapsack problem. We use the sample average approximation framework to approximate the stochastic problem as a deterministic knapsack-constrained submodular maximization problem, and then use an approximation algorithm to solve the deterministic counterpart. We show that a polynomial number of samples are enough for a deterministic approximation that is close in relative error. Then, exploiting the strict monotonicity of typical utility functions, we present an algorithm that maximizes an increasing submodular function over a knapsack constraint with approximation ratio better than the classical $(1-1/e)$ ratio. In Chapter 3, we present polyhedral results for the expected utility knapsack problem. We study a mixed-integer nonlinear set that is the hypograph of $f(a'x)$ together together with a knapsack constraint. We propose a family of inequalities for the convex hull of the nonlinear set by exploiting both the structure of the submodular function $f(a'x)$ and the knapsack constraint. Effectiveness of the proposed inequalities is shown by computational experiments on expected utility maximization problem with budget constraint using a branch-and-cut framework. In Chapter 4, we study a mixed-integer nonlinear set that is the epigraph of $f(a'x)$ together with a cardinality constraint. This mixed-integer nonlinear set arises as a substructure in various constrained submodular minimization problems. We develop a strong linear formulation of the convex hull of the nonlinear set by exploiting both the submodularity of $f(a'x)$ and the cardinality constraint. We provide a full description of the convex hull of the nonlinear set when the vector a has identical components. We also develop a family of facet-defining inequalities when the vector a has nonidentical components. We demonstrate the effectiveness of the proposed inequalities by solving mean-risk knapsack problems using a branch-and-cut framework.

No description available.

Pessoas portadoras de deficiências encontram enormes dificuldades ao tentarem entrar no mercado de trabalho. De fato, sobretudo em países em desenvolvimento, esta parcela significativa da população representa uma fração ínfima dos trabalhadores empregados. Dentre as iniciativas que tentam reverter este quadro, destaca-se a criação de Centros de Trabalhadores Deficientes (CTDs), empresas sem fins lucrativos que empregam pessoas portadoras de deficiências, geralmente em linhas de produção. Um dos fins últimos dos CTDs é expor os trabalhadores a situações encontradas em uma gama diversa de contextos produtivos, de modo que eles possam, eventualmente, vir a compor o quadro de empresas convencionais. A organização e planejamento da operação de CTDs envolve uma série de dificuldades. Questões ligadas à ergonomia do trabalho ou ao gerenciamento de qualidade, por exemplo, adquirem características particulares neste ambiente. Da mesma forma, problemas clássicos de balanceamento de linhas de produção ganham novas particularidades devido, sobretudo, à enorme heterogeneidade existente entre os trabalhadores. Neste contexto, nos interessamos por problemas referentes ao balanceamento da linha de produção com trabalhadores deficientes, onde se busca obter a maior eficiência produtiva dadas as habilidades específicas de cada trabalhador. De maneira mais precisa, o problema de balanceamento de linhas de produção em CTDs, conhecido na literatura como problema de balanceamento e designação de trabalhadores em linhas de produção (ALWABP, na sigla em inglês) consiste em alocar tarefas e trabalhadores a estações de trabalho, de modo a minimizar o gargalo produtivo e levando em consideração que cada tarefa tem um tempo de duração que depende do trabalhador escolhido para sua execução. Isto dá ao problema um caráter de dupla alocação, aumentando seu caráter combinatório e, consequentemente, sua dificuldade de resolução. Nesta dissertação, estudamos uma variedade de técnicas de resolução do ALWABP. Os objetivos deste estudo são, primeiramente, obter métodos diversos para resolução do problema que sejam eficazes tanto em termos do tempo computacional necessário para sua utilização como em termos da qualidade da solução obtida. Dentre as abordagens propostas e testadas encontram-se versões de algoritmos com diferentes complexidades, indo desde heurísticas construtivas e estratégias de busca monotônica em vizinhança até meta-heurísticas como GRASP e Busca Tabu. A variedade de técnicas desenvolvidas permitiu a resolução de um problema ainda mais complexo que o ALWABP, que consiste em programar a linha para diversos períodos produtivos, levando em consideração a rotação de tarefas entre os trabalhadores. Deste modo, os trabalhadores podem ser expostos ao maior número de tarefas possível (atendendo, assim, o fim de treinamento almejado no ambiente dos CTDs). Para resolução do problema de rotação de tarefas, as técnicas desenvolvidas foram utilizadas em um esquema de otimização híbrido que faz uso de um pool de soluções (obtidas pelos métodos heurísticos) que são integradas através de modelos de otimização linear inteira mista. Os resultados obtidos sugerem que as técnicas desenvolvidas são eficientes e flexíveis para o problema ALWABP e que a sua integração permite a obtenção de soluções eficientes para o problema de rotação de tarefas. Deste modo, esta dissertação propõe um esquema completo para o balanceamento de linhas de produção em CTDs / Disabled workers face enormous difficulties when trying to enter to the labor market. At the present moment, in particular in developing countries, this group constitutes a small portion of the labor force in productive processes. Among the initiatives that attempt to reverse this situation, we highlight the creation of sheltered work centers for the disabled (referred to as SWD henceforth), which are non-profit companies that employ people with disabilities, often in assembly lines. The organization and planning of the operation of a SWD involves a number of challenges. Issues related to ergonomy or production quality management, for instance, acquire particular characteristics in this environment. Likewise, classic assembly lines balancing modeling and solving techniques have to be modified, due to the significant heterogeneity among workers. In this context, we are concerned with problems related to the assembly line balancing with disabled workers, which attempts to achieve the higher production efficiency as possible, given the specific skills of each worker. More precisely, the assembly line balancing problem in SWD, known in the literature as the assembly line worker assignment and balancing problem (ALWABP), consists in assigning tasks and workers to workstations, in order to minimize the bottleneck of the production line while considering that each task duration time depends on the worker chosen for its execution. This double assignment structure leads to a much more complex problem. In this dissertation, we study a variety of techniques for solving the ALWABP. The goals of this study are, first of all, the development of a number of efficient techniques for solving the problem, both in terms of computational time required for their use and in terms of the quality of the obtained solutions. Among the techniques proposed and tested, we have versions of algorithms with different complexities, ranging from constructive heuristics and monotonic neighborhood search strategies to metaheuristics such as Tabu Search and GRASP. The diversity of the developed techniques allowed the resolution of a problem even more complex than the ALWABP, which consists of programming the line for a set of periods, taking into account the rotation of tasks among workers. The objective of this new problem is to propose a solution for a given production period that considers the fact that it might be positive to expose the workers to as many tasks as possible (for training, therapeutical and motivational reasons). In order to solve this job rotation problem, the techniques developed were integrated into a hybrid optimization scheme that uses a pool of solutions (obtained with the heuristic methods) which become inputs of mixed integer linear optimization models. The results suggest that the techniques developed are efficient and flexible to the ALWABP and their integration allows the obtention of efficient solutions to the job rotation problem. Thus, this dissertation proposes a complete scheme for the resolution of the balancing problem in SWD production lines

Problemas de corte de estoque consistem em arranjar peças menores, em tamanhos e quantidades especificados, dentro de peças maiores. Tais problemas têm sido investigados intensamente nas últimas décadas, acrescidos de novas características e novos métodos de solução. Nesta tese abordamos o problema de corte de estoque multiperíodo que surge imerso no planejamento e programação da produção em empresas que têm um estágio de produção caracterizado pelo corte de peças. As demandas dos itens ocorrem em períodos diversos de um horizonte de planejamento finito, sendo possível antecipar ou não a produção de itens. Os objetos disponíveis em estoque não utilizados em um período ficam disponíveis no próximo período, juntamente com novos objetos adquiridos ou produzidos pela própria empresa. Um modelo de otimização linear inteira de grande porte é proposto, cujo objetivo pondera o custo das perdas nos cortes, os custos de estocagem de objetos e itens. O método simplex com geração de colunas foi especializado para resolver a relaxação linear do modelo proposto. Foram realizados experimentos computacionais com problemas de corte de estoque unidimensional e bidimensional. Tais experimentos mostram que ganhos efetivos podem ser obtidos usando-se o modelo de corte de estoque multiperíodo, quando comparado com a solução lote-por-lote, tipicamente utilizada na prática. Porém, na prática, a solução relaxada é de pouca, ou nenhuma, utilidade. Assim, nesta tese, desenvolvemos dois procedimentos de arredondamento da solução do problema multiperíodo, baseado em horizonte rolante, ou seja, determinamos uma solução inteira factível apenas para o primeiro período, a qual será, de fato, implementada. Enfim, concluímos que o modelo para o problema de corte de estoque multiperíodo permite flexibilidade na análise de uma solução a ser implementada e, portanto, é uma ferramenta que permite ao gerente de produção uma visão global do problema para auxiliá-lo na tomada de decisões / Cutting stock problems consist of cutting a set of available stock objects in order to produce smaller ordered items. Such problems have been intensively researched over the last decades, together with additional characteristics and new methods for solving them. In this thesis, we address the multiperiod cutting stock problem, which arises in the production planning and programming in many industries that have a cutting process as an important stage. Ordered items have different due date over a finite planning horizon. An integer linear optimization model of large scale is proposed. The model makes possible to anticipate or not the production of items. Unused objects in inventory in a period become available to the next period, added to new inventory, which are acquired or produced by the own company. The mathematical model\'s objective is to minimize the cost of waste in the cutting process and costs for holding objects and fInal items. The simplex method with column generation was specialized to solve its linear relaxation. Computational experiments were carried out to solve one-dimensional and two-dimensional cutting stock problems. Such experiments showed that the multiperiod model could obtain effective gains when compared with the lot-for-lot solution, which is typically used in practice. However, in practical problems, the fractional solution is useless. So, in this thesis, two rounding procedures are developed to determine integer solutions for multiperiod cutting stock problems. Such procedures are based on a rolling horizon scheme, which roughly means, find an integer solution only for the first period, since this is the solution to be, in fact, carried out. Finally, we conclude that the proposed model for multiperiod cutting stock problems allows flexibility on analyzing a solution to be put in practice. The multiperiod cutting problem can be a tool that provides the decision maker a wide view of the problem and it may help him/her on making decisions

Pessoas portadoras de deficiências encontram enormes dificuldades ao tentarem entrar no mercado de trabalho. De fato, sobretudo em países em desenvolvimento, esta parcela significativa da população representa uma fração ínfima dos trabalhadores empregados. Dentre as iniciativas que tentam reverter este quadro, destaca-se a criação de Centros de Trabalhadores Deficientes (CTDs), empresas sem fins lucrativos que empregam pessoas portadoras de deficiências, geralmente em linhas de produção. Um dos fins últimos dos CTDs é expor os trabalhadores a situações encontradas em uma gama diversa de contextos produtivos, de modo que eles possam, eventualmente, vir a compor o quadro de empresas convencionais. A organização e planejamento da operação de CTDs envolve uma série de dificuldades. Questões ligadas à ergonomia do trabalho ou ao gerenciamento de qualidade, por exemplo, adquirem características particulares neste ambiente. Da mesma forma, problemas clássicos de balanceamento de linhas de produção ganham novas particularidades devido, sobretudo, à enorme heterogeneidade existente entre os trabalhadores. Neste contexto, nos interessamos por problemas referentes ao balanceamento da linha de produção com trabalhadores deficientes, onde se busca obter a maior eficiência produtiva dadas as habilidades específicas de cada trabalhador. De maneira mais precisa, o problema de balanceamento de linhas de produção em CTDs, conhecido na literatura como problema de balanceamento e designação de trabalhadores em linhas de produção (ALWABP, na sigla em inglês) consiste em alocar tarefas e trabalhadores a estações de trabalho, de modo a minimizar o gargalo produtivo e levando em consideração que cada tarefa tem um tempo de duração que depende do trabalhador escolhido para sua execução. Isto dá ao problema um caráter de dupla alocação, aumentando seu caráter combinatório e, consequentemente, sua dificuldade de resolução. Nesta dissertação, estudamos uma variedade de técnicas de resolução do ALWABP. Os objetivos deste estudo são, primeiramente, obter métodos diversos para resolução do problema que sejam eficazes tanto em termos do tempo computacional necessário para sua utilização como em termos da qualidade da solução obtida. Dentre as abordagens propostas e testadas encontram-se versões de algoritmos com diferentes complexidades, indo desde heurísticas construtivas e estratégias de busca monotônica em vizinhança até meta-heurísticas como GRASP e Busca Tabu. A variedade de técnicas desenvolvidas permitiu a resolução de um problema ainda mais complexo que o ALWABP, que consiste em programar a linha para diversos períodos produtivos, levando em consideração a rotação de tarefas entre os trabalhadores. Deste modo, os trabalhadores podem ser expostos ao maior número de tarefas possível (atendendo, assim, o fim de treinamento almejado no ambiente dos CTDs). Para resolução do problema de rotação de tarefas, as técnicas desenvolvidas foram utilizadas em um esquema de otimização híbrido que faz uso de um pool de soluções (obtidas pelos métodos heurísticos) que são integradas através de modelos de otimização linear inteira mista. Os resultados obtidos sugerem que as técnicas desenvolvidas são eficientes e flexíveis para o problema ALWABP e que a sua integração permite a obtenção de soluções eficientes para o problema de rotação de tarefas. Deste modo, esta dissertação propõe um esquema completo para o balanceamento de linhas de produção em CTDs / Disabled workers face enormous difficulties when trying to enter to the labor market. At the present moment, in particular in developing countries, this group constitutes a small portion of the labor force in productive processes. Among the initiatives that attempt to reverse this situation, we highlight the creation of sheltered work centers for the disabled (referred to as SWD henceforth), which are non-profit companies that employ people with disabilities, often in assembly lines. The organization and planning of the operation of a SWD involves a number of challenges. Issues related to ergonomy or production quality management, for instance, acquire particular characteristics in this environment. Likewise, classic assembly lines balancing modeling and solving techniques have to be modified, due to the significant heterogeneity among workers. In this context, we are concerned with problems related to the assembly line balancing with disabled workers, which attempts to achieve the higher production efficiency as possible, given the specific skills of each worker. More precisely, the assembly line balancing problem in SWD, known in the literature as the assembly line worker assignment and balancing problem (ALWABP), consists in assigning tasks and workers to workstations, in order to minimize the bottleneck of the production line while considering that each task duration time depends on the worker chosen for its execution. This double assignment structure leads to a much more complex problem. In this dissertation, we study a variety of techniques for solving the ALWABP. The goals of this study are, first of all, the development of a number of efficient techniques for solving the problem, both in terms of computational time required for their use and in terms of the quality of the obtained solutions. Among the techniques proposed and tested, we have versions of algorithms with different complexities, ranging from constructive heuristics and monotonic neighborhood search strategies to metaheuristics such as Tabu Search and GRASP. The diversity of the developed techniques allowed the resolution of a problem even more complex than the ALWABP, which consists of programming the line for a set of periods, taking into account the rotation of tasks among workers. The objective of this new problem is to propose a solution for a given production period that considers the fact that it might be positive to expose the workers to as many tasks as possible (for training, therapeutical and motivational reasons). In order to solve this job rotation problem, the techniques developed were integrated into a hybrid optimization scheme that uses a pool of solutions (obtained with the heuristic methods) which become inputs of mixed integer linear optimization models. The results suggest that the techniques developed are efficient and flexible to the ALWABP and their integration allows the obtention of efficient solutions to the job rotation problem. Thus, this dissertation proposes a complete scheme for the resolution of the balancing problem in SWD production lines

Problemas de corte de estoque consistem em arranjar peças menores, em tamanhos e quantidades especificados, dentro de peças maiores. Tais problemas têm sido investigados intensamente nas últimas décadas, acrescidos de novas características e novos métodos de solução. Nesta tese abordamos o problema de corte de estoque multiperíodo que surge imerso no planejamento e programação da produção em empresas que têm um estágio de produção caracterizado pelo corte de peças. As demandas dos itens ocorrem em períodos diversos de um horizonte de planejamento finito, sendo possível antecipar ou não a produção de itens. Os objetos disponíveis em estoque não utilizados em um período ficam disponíveis no próximo período, juntamente com novos objetos adquiridos ou produzidos pela própria empresa. Um modelo de otimização linear inteira de grande porte é proposto, cujo objetivo pondera o custo das perdas nos cortes, os custos de estocagem de objetos e itens. O método simplex com geração de colunas foi especializado para resolver a relaxação linear do modelo proposto. Foram realizados experimentos computacionais com problemas de corte de estoque unidimensional e bidimensional. Tais experimentos mostram que ganhos efetivos podem ser obtidos usando-se o modelo de corte de estoque multiperíodo, quando comparado com a solução lote-por-lote, tipicamente utilizada na prática. Porém, na prática, a solução relaxada é de pouca, ou nenhuma, utilidade. Assim, nesta tese, desenvolvemos dois procedimentos de arredondamento da solução do problema multiperíodo, baseado em horizonte rolante, ou seja, determinamos uma solução inteira factível apenas para o primeiro período, a qual será, de fato, implementada. Enfim, concluímos que o modelo para o problema de corte de estoque multiperíodo permite flexibilidade na análise de uma solução a ser implementada e, portanto, é uma ferramenta que permite ao gerente de produção uma visão global do problema para auxiliá-lo na tomada de decisões / Cutting stock problems consist of cutting a set of available stock objects in order to produce smaller ordered items. Such problems have been intensively researched over the last decades, together with additional characteristics and new methods for solving them. In this thesis, we address the multiperiod cutting stock problem, which arises in the production planning and programming in many industries that have a cutting process as an important stage. Ordered items have different due date over a finite planning horizon. An integer linear optimization model of large scale is proposed. The model makes possible to anticipate or not the production of items. Unused objects in inventory in a period become available to the next period, added to new inventory, which are acquired or produced by the own company. The mathematical model\'s objective is to minimize the cost of waste in the cutting process and costs for holding objects and fInal items. The simplex method with column generation was specialized to solve its linear relaxation. Computational experiments were carried out to solve one-dimensional and two-dimensional cutting stock problems. Such experiments showed that the multiperiod model could obtain effective gains when compared with the lot-for-lot solution, which is typically used in practice. However, in practical problems, the fractional solution is useless. So, in this thesis, two rounding procedures are developed to determine integer solutions for multiperiod cutting stock problems. Such procedures are based on a rolling horizon scheme, which roughly means, find an integer solution only for the first period, since this is the solution to be, in fact, carried out. Finally, we conclude that the proposed model for multiperiod cutting stock problems allows flexibility on analyzing a solution to be put in practice. The multiperiod cutting problem can be a tool that provides the decision maker a wide view of the problem and it may help him/her on making decisions

The problem of risk-averse decision making under uncertainties is studied from both modeling and computational perspectives. First, we consider a framework for constructing coherent and convex measures of risk which is inspired by infimal convolution operator, and prove that the proposed approach constitutes a new general representation of these classes. We then discuss how this scheme may be effectively employed to obtain a class of certainty equivalent measures of risk that can directly incorporate decision maker's preferences as expressed by utility functions. This approach is consequently utilized to introduce a new family of measures, the log-exponential convex measures of risk. Conducted numerical experiments show that this family can be a useful tool when modeling risk-averse decision preferences under heavy-tailed distributions of uncertainties. Next, numerical methods for solving the rising optimization problems are developed. A special attention is devoted to the class p-order cone programming problems and mixed-integer models. Solution approaches proposed include approximation schemes for $p$-order cone and more general nonlinear programming problems, lifted conic and nonlinear valid inequalities, mixed-integer rounding conic cuts and new linear disjunctive cuts.

ARARUNA, Arthur Rodrigues. Caminho mínimo com restrição probabilística de atraso máximo. 2013. 88 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-01T19:53:59Z No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-01T19:54:22Z (GMT) No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Made available in DSpace on 2016-06-01T19:54:22Z (GMT). No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) Previous issue date: 2013 / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem. / No problema do Caminho Mínimo com Restrição Probabilística de Atraso Máximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viárias a custo mínimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observá-lo tendo em mente estratégias de qualidade de serviço, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da área de otimização em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual não tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeração de partições do espaço de soluções do problema, que utiliza uma decomposição em L para selecionar partições de forma inteligente, e que é auxiliado por soluções de relaxações do problema de forma a obter cotas para o custo ótimo. Além disso, desenvolvemos algumas estratégias de ramificação e de poda para um esquema de Branch-and-Bound, com uma fase de pré-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparação em instâncias de menor porte para o problema. Para as demais instâncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessário para a resolução.

Orientador: Silvio Alexandre de Araujo / Banca: Helenice de Oliveira Florentino Silva / Banca: Maria do Socorro Nogueira Rangel / Resumo: Este trabalho trata do problema de corte de estoque unidimensional inteiro, que consiste em cortar um conjunto de objetos disponíveis em estoque para a produção de itens menores demandados, de tal forma que se otimize uma ou mais funções objetivos. Foi estudado o caso em que existe apenas um tipo de objeto em estoque em quantidades suficiente para atender a demanda. Três adaptações de um método heurístico baseadas nos conceitos dos algoritmos evolutivos multiobjetivo são propostas para resolver o problema considerando duas funções objetivo conflitantes, a minimização do número de objetos cortados e a minimização do número de diferentes padrões de corte. As adaptações utilizam as idéias presentes no método da Soma Ponderada, no Vector Evaluated Genetic Algorithm e no Multiple Objective Genetic Algorithm. Estas heurísticas são analisadas resolvendo-se instâncias geradas aleatoriamente. / Abstract: This work deals with the one-dimensional integer cutting stock problem, which consist of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to optimize one or more objective functions. On the case studied there is just one type of object in stock available in sufficient quantity to satisfy the demand. Three adaptations of a heuristic method based on the multi-objective evolutionary algorithms concepts are proposed to solve the problem considering two conflicting objective functions, the minimization of the number of objects to be cut and the minimization of the number of different cutting patterns. The adaptations consider the ideas from the Weighted Sum method, the Vector Evaluated Genetic Algorithm and the Multiple Objective Genetic Algorithm. These heuristics are analyzed by solving randomly generated instances. / Mestre

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / No problema do Caminho MÃnimo com RestriÃÃo ProbabilÃstica de Atraso MÃximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viÃrias a custo mÃnimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observÃ-lo tendo em mente estratÃgias de qualidade de serviÃo, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da Ãrea de otimizaÃÃo em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual nÃo tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeraÃÃo de partiÃÃes do espaÃo de soluÃÃes do problema, que utiliza uma decomposiÃÃo em L para selecionar partiÃÃes de forma inteligente, e que à auxiliado por soluÃÃes de relaxaÃÃes do problema de forma a obter cotas para o custo Ãtimo. AlÃm disso, desenvolvemos algumas estratÃgias de ramificaÃÃo e de poda para um esquema de Branch-and-Bound, com uma fase de prÃ-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparaÃÃo em instÃncias de menor porte para o problema. Para as demais instÃncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessÃrio para a resoluÃÃo. / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem.