The purpose of this research is to formulate a multi-commodity network flow model for vehicular traffic in a geographic area and develop a procedure for estimating traffic counts based on available partial traffic data for a selected subset of highway links. Due to the restriction of time and cost, traffic counts are not always observed for every highway link. Typically, about 50% of the links have traffic counts in urban highway networks. Also, it should be noted that the observed traffic counts are not free from random errors during the data collection process. As a result, an incoming flow into a highway node and an outgoing flow from the node do not usually match. They need to be adjusted to satisfy a flow conservation condition, which is one of the fundamental concepts in network flow analysis. In this dissertation, the multi-commodity link flows are estimated in a two-stage process. First, traffic flows of "empty" links, which have no observation data, are filled with deterministic user equilibrium traffic assignments. This user equilibrium assignment scheme assumes that travelers select their routes by their own interests without considering total cost of the system. The assignment also considers congestion effects by taking a link travel cost as a function of traffic volume on the link. As a result, the assignment problem has a nonlinear objective function and linear network constraints. The modified Frank-Wolfe algorithm, which is a type of conditional gradient method, is used to solve the assignment problem. The next step is to consider both of the observed traffic counts on selected links and the deterministic user equilibrium assignments on the group of remaining links to produce the final traffic count estimates by the generalized least squares optimization procedure. The generalized least squares optimization is conducted under a set of relevant constraints, including the flow conservation condition for all highway intersections.

In the oil industry, there is a special class of pipelines used for the transportation of refined products. The problem of sequencing the inputs to be pumped through this type of pipeline seeks to generate the optimal sequence of batches of products and their destination as well as the amount of product to be pumped such that the total operational cost of the system, or another operational objective, is optimized while satisfying the product demands according to the requirements set by the customers. This dissertation introduces a new modeling approach and proposes a solution methodology for this problem capable of dealing with the topology of all the scenarios reported in the literature so far. The system representation is based on a 1-0 multi commodity network flow formulation that models the dynamics of the system, including aspects such as conservation of product flow constraints at the depots, travel time of products from the refinery to their depot destination and what happens upstream and downstream the line whenever a product is being received at a given depot while another one is being injected into the line at the refinery. It is assumed that the products are already available at the refinery and their demand at each depot is deterministic and known beforehand. The model provides the sequence, the amounts, the destination and the trazability of the shipped batches of different products from their sources to their destinations during the entire horizon planning period while seeking the optimization of pumping and inventory holding costs satisfying the time window constraints. A survey for the available literature is presented. Given the problem structure, a decomposition based solution procedure is explored with the intention of exploiting the network structure using the network simplex method. A branch and bound algorithm that exploits the dynamics of the system assigning priorities for branching to a selected set of variables is proposed and its computational results for the solution, obtained via GAMS/CPLEX, of the formulation for random instances of the problem of different sizes are presented. Future research directions on this field are proposed.

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.

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.

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.

The purpose of this paper is to increase the routing efficiency of two previously separate commodity transports. By combining them in a common, multi-commodity network flow (MCNF). A Mixed Integer Linear Programming (MILP) model is used to minimize the mileage that is needed to fulfill demand in the different destinations of the transport network. Input needed for the model was mileage between destinations, which was obtained from open data. And the demand of respective commodity was received from documents and an estimation. To solve the stated problem approximations and simplifications was needed because it showed a NP-complete problem. The aim is to produce a result that shows a lower mileage than a reference measure from the present situation with separate transports. The result showed an optimized solution of 1939 km. Which was a difference of 1941 km from the reference measures, that summarized to 3880 km. Despite this the result from the model shows an effective optimization. Which makes the use of MILP for minimizing mileage inside a MCNF problem, a useful approach for solving the stated problem. / Syftet med arbetet var att effektivisera körsträckor för två tidigare separata transporter av olika produkter. Genom att kombinera dem till en gemensam transport i ett multi-commodity network flow (MCNF). Med en Mixed Integer Linear Programming (MILP) modell minimeras de körsträckor som krävs för att fylla efterfrågan i transportnätverkets adresser. In-data som krävdes för att en modell skulle kunna utföras var körsträckor mellan olika adresser, vilket hämtades från öppen data. Samt efterfrågan på produkter som erhölls från dokument och estimering.  Då problemet som skulle lösas visade på hög beräkningskomplexitet behövde ett antal approximationer och förenklingar verkställas. Målet var att visa på ett resultat där körsträckor hade förminskats relativt till ett referensmått från nuläget. Där resultatet visade på en optimerad lösning på 1939 km. Vilket var en differens på 1941 km från de referensmåttet som summerades till 3880 km. Modellens resultat visar trots det en effektiv optimering. Vilket gör att användningen av MILP för att minimera körsträckor inom MCNF problem, är ett effektivt tillvägagångssätt att lösa det motiverade problemet.