We model Pup Matching, the logistics problem of matching or pairing semitrailers known as pups to cabs able to tow one or two pups simultaneously, as an NP-complete version of the Network Loading Problem (NLP). We examine a branch and bound solution approach tailored to the NLP formulation through the use of three families of cutting planes and four heuristic procedures. Theoretically, we specify facet defining conditions for a cut family that we refer to as odd flow inequalities and show that each heuristic yields a 2-approximation. Computationally, the cheapest of the four heuristic values achieved an average error of 1.3% among solved test problems randomly generated from realistic data. The branch and bound method solved to optimality 67% of these problems. Application of the cutting plane families reduced the average relative difference between upper and lower bounds prior to branching from 18.8% to 6.4%. / Singapore-MIT Alliance (SMA)

[pt] Apresenta-se uma abrangente ferramenta de avaliação das condições de segurança de tensão, composta de índices com significado físico / matemático, propícia para uso na operação em tempo real. A ferramenta identifica se a solução de tensão para uma carga conectada à barra i está na parte superior, na inferior e a distância ao máximo carregamento da curva V x P,Q. Neste trabalho a enfâse está no desenvolvimento da margem de potência, distância em MVA do atual ao máximo carregamento, assim como na análise do ângulo entre os vetores-gradiente dos fluxos de potência ativa e reativa chegando / saindo de barras de carga / geração. Mostra-se a evolução desses índices durante um horizonte de tempo correspondente a uma rampa de carregamento do sistema. A área Rio do sistema brasileiro foi escolhida para observação por ter seu desempenho fortemente influenciado pela coordenação entre os diversos recursos de controle internos e externos e, também por ser um grande centro de carga com sistema de suprimento radial. A implementação das lógicas desses recursos de controle, caracterizada pela escolha das barras controladas e faixas de tensão, refletiram a experiência acumulada na operação do sistema, respeitando-se todos os limites operativos Verifica-se a ocorrência de situações extremas que levariam o sistema ao colapso de tensão. Apresenta-se ainda um estudo de barras associadas à compensação série no tronco de transmissão entre Itaipu a Tijuco Preto, barras que apresentam índices com valores atípicos. Conclui-se que o método computacional de avaliação das condições de segurança de tensão é adequado para a operação em tempo real, quando é monitorada a evolução dos índices relativos a uma seqüência de diferentes pontos de operação. / [en] This work presents a comprehensive and meaningful tool for voltage security assessment adequate for real time operational monitoring. With this tool it is possible to verify if the voltage is in the upper or in the lower region of the V, P,Q curve, as well as to quantify voltage stability margin. The emphasis of this work is on the development of margins, the distance in MVA from the current to the maximum loading, as well as on the analysis of the angle between the gradient vectors of active and reactive power flow leaving / arriving generation / load buses. It is shown the evolution of the indexes during a period of time that corresponds to a system-loading ramp. The Rio and Espírito Santo area of the Brazilian electric system was chosen for observation because its performance is strongly influenced by the co-ordination between the several types of internal and external existing controls. Also because this area represents a large load centre with an almost radial transmission system. The logic implementation of these control resources, characterised by controlled buses and voltage limits choice, respecting all the operational limits, reflected the operational experience acquired by system operators. It is verified the occurrence of extreme situations that could lead to voltage collapse in the network. It is also presented a study on the buses associated with series compensation on the Itaipu - Tijuco Preto bulk transmission path that present unusual values for the indexes. It is concluded that the computational method of voltage security assessment is adequate for real time operation, when the evolution of indexes related to different operation points are monitored.

Vast application of ITS and the availability of numerous on-road detection devices has resulted in variety of alternative data sources to be exploited and used in the field of traffic modelling. In this thesis, historical travel times, as an alternative data source, is employed on the developed method to perform dynamic network loading. The developed method, referred to as DNLTT, uses the share of each route available in the route choice set from the initial demand, as well as link travel times to perform the network loading. The output of the algorithm is time-dependent link flows. DNLTT is applied on Stockholm transportation network, where it is expected to have variation in link travel times in different time-periods, due to network congestion. In order to calculate the route shares, a time-sliced OD matrix is used. The historical travel times and the routes in the route choice set are extracted from an existing route planning tool. An available logit model, which considers the route travel time as the only logit parameter, is used for the route share calculation and the network loading is performed according to 2 different methods of DNLTT and DL. The evaluation of results is done for a toy network, where there happen different network states in different time-periods. Furthermore, the model output from Stockholm case study is analyzed and evaluated. The dynamic behavior of DNLTT is studied by analysis of link flows in different time-periods. Furthermore, the resulting link flows from both network loading methods are compared against observed link flows from radar sensors and the statistical analysis of link flows is performed accordingly. DNLTT exhibits a better performance on the toy network compared to DL, where the increasing link travel times cause the link flows to decline in different time-periods. However, the output of the developed method does not resemble the observed link flows for the investigated links in Stockholm case study. It is strongly believed, that the performance of DNLTT on the investigated transportation network potentially improves, in case the historical travel times better resemble the network dynamics. In addition to a more reliable data set, an OD adjustment process in all the time-periods is believed to generate better model output.