The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost. This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP.

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

O presente trabalho aborda a temática da modelagem de redes de transporte para terminais multialocados e capacitados de carga parcelada através de métodos quantitativos aplicados em Pesquisa Operacional, onde o objetivo principal é minimizar o custo total, além de determinar a configuração ótima da rede, levandos e em consideração os custos de transporte ponto a ponto, a capacidade de processamento de carga dos hubs e os custos de alocação dos mesmos. Uma rede Hub and Spoke é configurada de forma que as estações geradoras de cargas (spoke) se comunicam única e exclusivamente com os terminais consolidadores (hubs) que, por sua vez, direcionam as cargas para as estações destino. Esta operação de consolidação gera economia de escala e é o princípio utilizado em muitos modelos de localização de redes de transporte de carga. Os modelos matemáticos utilizados para a resolução pertencem à família dos problemas de localização com custos fixos e particularmente será utilizado o método CMAHLP (Capacitated Multiple Allocation Hub Location Problem), onde para a sua resolução será utilizado o software AIMMS (Advanced Integrated Multidimensional Modeling Software) como ferramenta de apoio. / This paper addresses the issue of modeling transportation networks for multi allocated and capacitated terminals for parcel cargos through quantitative methods applied in Operational Research, where the main objective is to minimize the total cost and to determine the optimal configuration of the network, taking into account the transportation costs, the loading capacity of the hubs and the cost of allocation thereof. A Hub and Spoke network is configured in a way that the generating stations (spokes) communicate solely with consolidators terminals (hubs) which dispatch the cargo to the destination stations. This consolidation operation generates economies of scale and it is the principle used in many models of location problems. The mathematical models used for the settlement belongs to the family of location problems with fixed costs and particularly the CMAHLP (Capacitated Multiple Allocation Hub Location Problem) method is used with the AIMMS (Advanced Integrated Multidimensional Modeling Software) software, which will be used will be used as a support tool.

We study a specialized version of network design problems that arise in telecommunication, transportation and other industries. The problem, a generalization of the shortest path problem, is defined on an undirected network consisting of a set of arcs on which we can install (load), at a cost, a choice of up to three types of capacitated facilities. Our objective is to determine the configuration of facilities to load on each arc that will satisfy the demand of a single commodity at the lowest possible cost. Our results (i) demonstrate that the single-facility loading problem and certain "common breakeven point" versions of the two-facility and three-facility loading problems are polynomially solvable as a shortest path problem; (ii) show that versions of the twofacility loading problem are strongly NP-hard, but that a shortest path solution provides an asymptotically "good" heuristic; and (iii) characterize the optimal solution (that is, specify a linear programming formulation with integer solutions) of the common breakeven point versions of the two-facility and three-facility loading problems. In this development, we introduce two new families of facets, give geometric interpretations of our results, and demonstrate the usefulness of partitioning the space of the problem parameters to establish polyhedral integrality properties. Generalizations of our results apply to (i) multicommodity applications and (ii) situations with more than three facilities.

O presente trabalho aborda a temática da modelagem de redes de transporte para terminais multialocados e capacitados de carga parcelada através de métodos quantitativos aplicados em Pesquisa Operacional, onde o objetivo principal é minimizar o custo total, além de determinar a configuração ótima da rede, levandos e em consideração os custos de transporte ponto a ponto, a capacidade de processamento de carga dos hubs e os custos de alocação dos mesmos. Uma rede Hub and Spoke é configurada de forma que as estações geradoras de cargas (spoke) se comunicam única e exclusivamente com os terminais consolidadores (hubs) que, por sua vez, direcionam as cargas para as estações destino. Esta operação de consolidação gera economia de escala e é o princípio utilizado em muitos modelos de localização de redes de transporte de carga. Os modelos matemáticos utilizados para a resolução pertencem à família dos problemas de localização com custos fixos e particularmente será utilizado o método CMAHLP (Capacitated Multiple Allocation Hub Location Problem), onde para a sua resolução será utilizado o software AIMMS (Advanced Integrated Multidimensional Modeling Software) como ferramenta de apoio. / This paper addresses the issue of modeling transportation networks for multi allocated and capacitated terminals for parcel cargos through quantitative methods applied in Operational Research, where the main objective is to minimize the total cost and to determine the optimal configuration of the network, taking into account the transportation costs, the loading capacity of the hubs and the cost of allocation thereof. A Hub and Spoke network is configured in a way that the generating stations (spokes) communicate solely with consolidators terminals (hubs) which dispatch the cargo to the destination stations. This consolidation operation generates economies of scale and it is the principle used in many models of location problems. The mathematical models used for the settlement belongs to the family of location problems with fixed costs and particularly the CMAHLP (Capacitated Multiple Allocation Hub Location Problem) method is used with the AIMMS (Advanced Integrated Multidimensional Modeling Software) software, which will be used will be used as a support tool.

An optimal ordering scheme for the capacitated, finite-horizon, multi-period, multiproduct newsvendor problem was proposed by cite {shao06} using a hedging point policy. This solution requires the calculation of a central curve that divides the different ordering regions and a vector that defines the target inventory levels. The central curve is a nonlinear curve that determines the optimal order quantities as a function of the initial inventory levels. In this paper we propose a method for calculating this curve and vector using spline functions, infinitesimal perturbation analysis (IPA), and convex optimization. Using IPA the derivatives of the cost with respect to the variables that determine the spline function are efficiently calculated. A convex optimization algorithm is used to optimize the spline function, resulting in a optimal policy. We present the mathematical derivations and simulation results validating this solution.

No description available.

Made available in DSpace on 2016-12-23T14:21:18Z (GMT). No. of bitstreams: 1 Andre Manhaes Machado.pdf: 1039285 bytes, checksum: 2b356c4d0279c975232bd92c5e2ab326 (MD5) Previous issue date: 2013-11-16 / O petróleo é a principal fonte energética do mundo contemporâneo, insumo básico de diversos setores econômicos. Com a descoberta do Pré-sal, o Brasil tem a oportunidade de tornar-se um dos maiores produtores de petróleo. Entretanto, para que isso seja alcançado, vários desafios deverão ser superados e, dentre eles, encontra-se o problema de transporte de empregados para operarem as plataformas offshore, distantes até 300km de distância da costa brasileira. Os problemas referentes ao deslocamento de empregados por meio de helicópteros são usualmente tratados como o Capacitated Helicopter Routing Problem (CHRP). Com base nas restrições de origem e de destino de cada cliente, no número de veículos e na capacidade e restrições de voo dos helicópteros, neste tipo de problema deseja-se minimizar os custos de aluguel de helicópteros mais o custo total de quilômetros voados. A presente dissertação propõe um modelo de Programação Linear Inteira Mista (PLIM) para o problema de roteirização de helicópteros com base no Dial-a-Ride Problem (DARP). Além do modelo apresentado, foram apresentados duas abordagens para a execução do modelo de forma exata: i) abordagem sem agrupamento, na qual as requisições que possuem origens iguais e destinos iguais são modeladas como requisições distintas e ii) abordagem com agrupamento, na qual requisições que possuem origens iguais e destinos iguais são aglutinados numa nova e única requisição. O modelo matemático foi executado no software CPLEX e os resultados mostraram que instâncias com até 25 requisições podem ser resolvidas pela abordagem com agrupamento / Oil is the main energy source of contemporary world; it is basic inputs of various economic sectors. With the discovery of Brazil pre-salt, there is an opportunity to become one of the largest oil producers. However, to achieve her own goals, Brazil must overcome several challenges, including the problem of transporting employees to operate offshore platforms 300km distant away from the Brazilian coast. Problems related to displacement of employees by helicopters are usually treated as Capacitated Helicopter Routing Problem (CHRP). Based on source and destination restrictions of each client, the number of vehicles, capacity and helicopter flight constraints, this type of problem proposes to minimize the cost of renting helicopters and the total cost of flown kilometers. This dissertation proposes a model of Mixed Integer Linear Programming (MILP) for the helicopters routing problem based on a Dial-a-Ride Problem (DARP). Besides the presented model, we presented two approaches to implementing the model in an exact way: i) non-clustered approach, in which requests that have the same origin and destination are equal modeled as separate requests; and ii) clustered approach, in which requests that have the same origins and destinations are clumped together in a new single request. The mathematical model was implemented in software CPLEX and results showed that instances with up to 25 requests can be resolved in the clustered approach

In this study, three different algorithms are implemented to solve thecapacitated vehicle routing problem with and without time windows:ant colony optimization, a genetic algorithm and a genetic algorithmwith self-organizing map. For the capacitated vehicle routing problemthe Augerat et al’s benchmark problems were used and for the capaci-tated vehicle routing problem with time windows the Solomon’sbenchmark problems. All three algorithms were tuned over thirtyinstances per problem with the tuners SPOT and ParamILS. The tuningresults from all instances were combined to the final parameter valuesand tested on a larger set of instances. The test results were used tocompare the algorithms and tuners against each other. The ant colonyoptimization algorithm outperformed the other algorithms on bothproblems when considering all instances. The genetic algorithm withself-organizing map found more best known solutions than any otheralgorithm when using parameters, on the capacitated vehicle routingproblem. The algorithms performed well and several new best knownresults were discovered for the capacitated vehicle routing problem andnew best solutions found by heuristics were discovered for the 100customer Solomon problems. When comparing the tuners they bothworked well and no clear winner emerged.