<p>In this thesis we focus resource allocation problems and electronic markets in particular. The main application area of ours is electricity markets. We present a number of algorithms and include practical experience.</p><p>There is an ongoing restructuring of power markets in Europe and elsewhere, this implies that an industry that previously has been viewed as a natural monopoly becomes exposed to competition. In the thesis we move a step further suggesting that end users should take active part in the trade on power markets such as <i>(i)</i> day-ahead markets and <i>(ii) </i>markets handling close to real-time balancing of power grids. Our ideas and results can be utilised <i>(a) </i>to increase the efficiency of these markets and <i>(b) </i>to handle strained situations when power systems operate at their limits. For this we utilise information and communication technology available today and develop electronic market mechanisms designed for large numbers of participants typically distributed over a power grid.</p><p>The papers of the thesis cover resource allocation with separable objective functions, a market mechanism that accepts actors with discontinuous demand, and mechanisms that allow actors to express combinatorial dependencies between traded commodities on multi-commodity markets. Further we present results from field tests and simulations.</p>

In this thesis we focus resource allocation problems and electronic markets in particular. The main application area of ours is electricity markets. We present a number of algorithms and include practical experience. There is an ongoing restructuring of power markets in Europe and elsewhere, this implies that an industry that previously has been viewed as a natural monopoly becomes exposed to competition. In the thesis we move a step further suggesting that end users should take active part in the trade on power markets such as (i) day-ahead markets and (ii) markets handling close to real-time balancing of power grids. Our ideas and results can be utilised (a) to increase the efficiency of these markets and (b) to handle strained situations when power systems operate at their limits. For this we utilise information and communication technology available today and develop electronic market mechanisms designed for large numbers of participants typically distributed over a power grid. The papers of the thesis cover resource allocation with separable objective functions, a market mechanism that accepts actors with discontinuous demand, and mechanisms that allow actors to express combinatorial dependencies between traded commodities on multi-commodity markets. Further we present results from field tests and simulations.

O presente trabalho trata do planejamento da movimentação de contêineres vazios ao longo de um conjunto de portos, buscando o balanceamento entre as demandas e ofertas dos mesmos em todos os portos ao menor custo, e considerando as restrições de capacidade de transporte dos modais envolvidos. Para isso será adotado um modelo de fluxo em rede multi-produto para representar o sistema de movimentação de contêineres vazios e que servirá de base para o desenvolvimento de uma formulação matemática, a qual, implementada através de uma ferramenta computacional de otimização, determina os fluxos de vazios no sistema. A verificação do modelo proposto deu-se através de testes em problemas reduzidos de movimentação de vazios, assim como em um problema cujos resultados foram publicados na literatura. Os resultados sugeriram a adequabilidade e confiabilidade do modelo proposto que pode, então, ser aplicado a um problema real da empresa de navegação Hamburg Süd, tendo seus resultados comparados aos resultados fornecidos pela mesma. / This dissertation deals with the empty containers movement planning throughout a set of ports, aiming the balancing between the demands and supplies in all the ports at minimal cost, and considering the capacity constraints of the transport modes considered. A multi-commodity network flow model will be adopted to represent the empty containers movement system. This model supports the development of a mathematical formulation which, through a computational optimization tool, determines the flows of empty containers throughout the system. The verification of the proposed model was given through tests in reduced problems, as well as in a problem which results had already been published in literature. The results had suggested the adequateness and trustworthiness of the proposed model, which could, then, be applied to a real problem of the navigation company Hamburg Süd, and the results could be compared with the ones given by the company.

A multi-commodity flow problem consists of moving several commodities from their respective sources to their sinks through a network where each edge has different costs and capacity constraints. This paper explores different linear programming algorithms and their performance regarding finding an optimal solution for multi-commodity flow problems. By testing several of different network constraints, we examine which algorithms are most suitable for specific network and problem structures. Furthermore, we implement our own multi-commodity solver and compare its performance against state-of-the-art linear programming solvers. The results show that for the methods we tested it is difficult to discern which class of linear programming methods are optimal solvers for multi-commodity flow problems and that their performance depends on how the network and commodities are structured.

Nesse trabalho apresentamos a modelagem matemática do Projeto de Rede da Cadeia de Suprimentos (Supply Chain Network Design) de uma empresa responsável pela produção e distribuição de commodities. O investimento em uma nova fábrica exige que a empresa tenha seu projeto logístico readequado. O desenvolvimento das formulações matemáticas é baseado no trabalho de Jayaraman e Pirkul (2001). Foram realizadas 3 (três) formulações matemáticas de diferentes abordagens para solução do projeto logístico. As implementações computacionais foram realizadas no CPLEX© Optimization Studio Academic Research versão 12.2. As experiências computacionais foram desenvolvidas através de cenários que buscaram representar problemas de dimensões reais. Ainda na etapa de experimentação foram realizadas análises de sensibilidade dos modelos. Um estudo para identificar as demandas de mercado e os custos de transporte foi realizado, sendo assim, foi possível aplicar os modelos no estudo de caso a partir de dados reais de demanda e custos. Para execução das instâncias reais foram selecionadas 2 (duas) abordagens distintas: Single-source e Arcbased. Diferentes market shares foram definidos para construção de novos cenários e instâncias reais foram executadas dentro de limites computacionais de tempo satisfatórios. Os resultados encontrados para cada cenário foram comparados e analisados em relação à resolução do problema proposto. A dissertação contribui para a área de modelagem da cadeia de suprimentos fornecendo modelos que apresentaram resultados satisfatórios para a tomada de decisão nessa fase do projeto logístico da indústria tema dessa pesquisa. / We present a mathematical modeling of the Supply Chain Network Design (SCND) for a company responsible for producing and distributing commodities. Investment in a new plant requires that the company has reconfigured its logistics project. The development of mathematical formulations is based on the work of Jayaraman and Pirkul (2001). Were performed three (3) mathematical formulations for different approaches to solving the logistics project. Computational implementations were done in CPLEX© Optimization Academic Research Studio version 12.2. Computational experiments were developed through scenarios that sought to represent problems of the real dimensions. Still in the experimentation fase were performed sensitivity analysis of models. A study to identify market demands and transportation costs was made, so the models could be applied in the case study data from actual demand and costs. For carrying out the actual instances were selected 2 (two) different approaches: Single-source-based and Arc. Different market shares were set to build new scenarios and actual instances have been implemented within limits satisfactory computational time. The results for each scenario were compared and analyzed for solving the proposed problem. The thesis contributes to modeling area of supply chain models that provide satisfactory results for decision making in this phase of the project's logistics industry theme of this research.

Nesse trabalho apresentamos a modelagem matemática do Projeto de Rede da Cadeia de Suprimentos (Supply Chain Network Design) de uma empresa responsável pela produção e distribuição de commodities. O investimento em uma nova fábrica exige que a empresa tenha seu projeto logístico readequado. O desenvolvimento das formulações matemáticas é baseado no trabalho de Jayaraman e Pirkul (2001). Foram realizadas 3 (três) formulações matemáticas de diferentes abordagens para solução do projeto logístico. As implementações computacionais foram realizadas no CPLEX© Optimization Studio Academic Research versão 12.2. As experiências computacionais foram desenvolvidas através de cenários que buscaram representar problemas de dimensões reais. Ainda na etapa de experimentação foram realizadas análises de sensibilidade dos modelos. Um estudo para identificar as demandas de mercado e os custos de transporte foi realizado, sendo assim, foi possível aplicar os modelos no estudo de caso a partir de dados reais de demanda e custos. Para execução das instâncias reais foram selecionadas 2 (duas) abordagens distintas: Single-source e Arcbased. Diferentes market shares foram definidos para construção de novos cenários e instâncias reais foram executadas dentro de limites computacionais de tempo satisfatórios. Os resultados encontrados para cada cenário foram comparados e analisados em relação à resolução do problema proposto. A dissertação contribui para a área de modelagem da cadeia de suprimentos fornecendo modelos que apresentaram resultados satisfatórios para a tomada de decisão nessa fase do projeto logístico da indústria tema dessa pesquisa. / We present a mathematical modeling of the Supply Chain Network Design (SCND) for a company responsible for producing and distributing commodities. Investment in a new plant requires that the company has reconfigured its logistics project. The development of mathematical formulations is based on the work of Jayaraman and Pirkul (2001). Were performed three (3) mathematical formulations for different approaches to solving the logistics project. Computational implementations were done in CPLEX© Optimization Academic Research Studio version 12.2. Computational experiments were developed through scenarios that sought to represent problems of the real dimensions. Still in the experimentation fase were performed sensitivity analysis of models. A study to identify market demands and transportation costs was made, so the models could be applied in the case study data from actual demand and costs. For carrying out the actual instances were selected 2 (two) different approaches: Single-source-based and Arc. Different market shares were set to build new scenarios and actual instances have been implemented within limits satisfactory computational time. The results for each scenario were compared and analyzed for solving the proposed problem. The thesis contributes to modeling area of supply chain models that provide satisfactory results for decision making in this phase of the project's logistics industry theme of this research.

Nesse trabalho apresentamos a modelagem matemática do Projeto de Rede da Cadeia de Suprimentos (Supply Chain Network Design) de uma empresa responsável pela produção e distribuição de commodities. O investimento em uma nova fábrica exige que a empresa tenha seu projeto logístico readequado. O desenvolvimento das formulações matemáticas é baseado no trabalho de Jayaraman e Pirkul (2001). Foram realizadas 3 (três) formulações matemáticas de diferentes abordagens para solução do projeto logístico. As implementações computacionais foram realizadas no CPLEX© Optimization Studio Academic Research versão 12.2. As experiências computacionais foram desenvolvidas através de cenários que buscaram representar problemas de dimensões reais. Ainda na etapa de experimentação foram realizadas análises de sensibilidade dos modelos. Um estudo para identificar as demandas de mercado e os custos de transporte foi realizado, sendo assim, foi possível aplicar os modelos no estudo de caso a partir de dados reais de demanda e custos. Para execução das instâncias reais foram selecionadas 2 (duas) abordagens distintas: Single-source e Arcbased. Diferentes market shares foram definidos para construção de novos cenários e instâncias reais foram executadas dentro de limites computacionais de tempo satisfatórios. Os resultados encontrados para cada cenário foram comparados e analisados em relação à resolução do problema proposto. A dissertação contribui para a área de modelagem da cadeia de suprimentos fornecendo modelos que apresentaram resultados satisfatórios para a tomada de decisão nessa fase do projeto logístico da indústria tema dessa pesquisa. / We present a mathematical modeling of the Supply Chain Network Design (SCND) for a company responsible for producing and distributing commodities. Investment in a new plant requires that the company has reconfigured its logistics project. The development of mathematical formulations is based on the work of Jayaraman and Pirkul (2001). Were performed three (3) mathematical formulations for different approaches to solving the logistics project. Computational implementations were done in CPLEX© Optimization Academic Research Studio version 12.2. Computational experiments were developed through scenarios that sought to represent problems of the real dimensions. Still in the experimentation fase were performed sensitivity analysis of models. A study to identify market demands and transportation costs was made, so the models could be applied in the case study data from actual demand and costs. For carrying out the actual instances were selected 2 (two) different approaches: Single-source-based and Arc. Different market shares were set to build new scenarios and actual instances have been implemented within limits satisfactory computational time. The results for each scenario were compared and analyzed for solving the proposed problem. The thesis contributes to modeling area of supply chain models that provide satisfactory results for decision making in this phase of the project's logistics industry theme of this research.

The focus of this thesis is to find, visualize and analyze the optimal flow of autonomous electric vehicles with charge constraints in urban traffic with respect to energy consumption. The traffic has been formulated as a static multi-commodity network flow problem, for which two different models have been implemented to handle the charge constraints. The first model uses a recursive algorithm to find the optimal solution fulfilling the charge constraints, while the second model discretizes the commodities’ battery to predetermined battery levels. An implementation of both methods is provided through simulations on scenarios of three different sizes. The results show that both methods are capable of representing the traffic flow with charge constraints, with limitations given by the size of the problem. In particular, the recursive model has the advantage of considering the charge as a continuous quantity. On the other hand the discretization of battery levels allows to handle charge constraint setups with higher complexity, that is when longer detours are needed to fulfill the charge constraints.

A typical problem in traffic control is the steering over a network of vehicles with different origins and destinations. In this report this scenario is formulated as a multi-commodity network flow problem, a linear programming problem whose objective is to transport, with minimum cost, different commodities from their respective sources to their sinks through a network, while respecting the capacity constraints of the roads. The dynamic network flow formulation of the problem is also presented, extending the network over time to incorporate the temporal dimension. Different algorithms for solving the multi-commodity network flow problem are examined. First, the simplex method, more precisely its revised version, is considered, and then the Dantzig-Wolfe decomposition is illustrated, an optimization algorithm which exploits specific block structures in the constraints. These methods are applied using state-of-the-art linear programming solvers and evaluated with a simulation based on the road network in central Stockholm. The results show that both methods allow for solving the traffic flow problem, with limitations given by the specifics of the solvers and by the space and time discretization of the problem. In particular, the revised simplex algorithm results the faster method.

In this study, the effect of implementing Network Coding on the aggregated throughput in Wireless Mesh Networks, was examined. Wireless Mesh Networks (WMNs) are multiple hop wireless networks, where routing through any node is possible. The implication of this characteristic, is that messages flow across the points where it would have been terminated in conventional wireless networks. User nodes in conventional wireless networks only transmit and receive messages from an Access Point (AP), and discard any messages not intended for them. The result is an increase in the volume of network traffic through the links of WMNs. Additionally, the dense collection of multiple RF signals propagating through a shared wireless medium, contributes to the situation where the links become saturated at levels below their capacity. The need exists to examine methods that will improve the utilisation of the shared wireless medium in WMNs. Network Coding is a coding and decoding technique at the network level of the OSI stack, aimed to improve the boundaries of saturated links. The technique implies that the bandwidth is simultaneously shared amongst separate message flows, by combining these flows at common intermediate nodes. The number of transmissions needed to convey information through the network, is decreased by Network Coding. The result is in an improvement of the aggregated throughput. The research approach followed in this dissertation, includes the development of a model that investigates the aggregated throughput performance of WMNs. The scenario of the model, followed a typical example of indoors WMN implementations. Therefore, the physical environment representation of the network elements, included an indoors log–distance path loss channel model, to account for the different effects such as: power absorption through walls; and shadowing. Network functionality in the model was represented through a network flow programming problem. The problem was concerned with determining the optimal amount of flow represented through the links of the WMN, subject to constraints pertaining to the link capacities and mass balance at each node. The functional requirements of the model stated that multiple concurrent sessions were to be represented. This condition implied that the network flow problem had to be a multi–commodity network flow problem. Additionally, the model requirements stated that each session of flow should remain on a single path. This condition implied that the network flow problem had to be an integer programming problem. Therefore, the network flow programming problem of the model was considered mathematically equivalent to a multi–commodity integer programming problem. The complexity of multi–commodity integer programming problems is NP–hard. A heuristic solving method, Simulated Annealing, was implemented to solve the goal function represented by the network flow programming problem of the model. The findings from this research provide evidence that the implementation of Network Coding in WMNs, nearly doubles the level of the calculated aggregated throughput values. The magnitude of this throughput increase, can be further improved by additional manipulation of the network traffic dispersion. This is achieved by utilising link–state methods, rather than distance vector methods, to establish paths for the sessions of flow, present in the WMNs. / Thesis (M.Ing. (Computer and Electronical Engineering))--North-West University, Potchefstroom Campus, 2012.