In this paper, we concentrate on computing several critical budgets for interdiction of the multicommodity network flows, and studying the interdiction effects of the changes on budget. More specifically, we first propose general interdiction models of the multicommodity flow problem, with consideration of both node and arc removals and decrease of their capacities. Then, to perform the vulnerability analysis of networks, we define the function F(R) as the minimum amount of unsatisfied demands in the resulted network after worst-case interdiction with budget R. Specifically, we study the properties of function F(R), and find the critical budget values, such as , the largest value under which all demands can still be satisfied in the resulted network even under the worst-case interdiction, and , the least value under which the worst-case interdiction can make none of the demands be satisfied. We prove that the critical budget for completely destroying the network is not related to arc or node capacities, and supply or demand amounts, but it is related to the network topology, the sets of source and destination nodes, and interdiction costs on each node and arc. We also observe that the critical budget is related to all of these parameters of the network. Additionally, we present formulations to estimate both and . For the effects of budget increasing, we present the conditions under which there would be extra capabilities to interdict more arcs or nodes with increased budget, and also under which the increased budget has no effects for the interdictor. To verify these results and conclusions, numerical experiments on 12 networks with different numbers of commodities are performed.

Integer multicommodity network flow (MCNF) models have applications in various areas like logistics, freight transportation, telecommunication and manufacturing. In this thesis we study an extension of the integer MCNF problem (MCNF-FIFO) where commodities are handled (processed) in a first-in-first-out (FIFO) order at each transshipment location and resource capacities are shared across arcs in the network. The objective of the MCNF-FIFO model is to find feasible routes for all commodities from their origins to destinations while minimizing the total transportation and holding cost or the sum of delivery times. We formulate the MCNF-FIFO problem on a time-space network and develop three different integer-programming (IP) formulations for the FIFO constraints, and two IP formulations for the flow conservations requirements. Since these formulations have a very large number of variables and constraints, we develop various algorithmic strategies to obtain good quality solutions quickly. The first strategy is to reduce the problem size by using properties of the optimal solution. We develop novel problem reduction and decomposition techniques that eliminate variables and constraints, and decompose the problem into smaller components. To further reduce the problem size, we classify the FIFO constraints into different categories by utilizing the relationships between different commodities, and provide specialized formulations for each of these categories so as to reduce the number of FIFO constraints significantly. The second strategy is to develop heuristic algorithms that provide near-optimal solutions to the MCNF-FIFO problem. Our first algorithm is an optimization-based heuristic that solves a relaxed MCNF-FIFO model with a limited number of FIFO constraints. Then, it removes the remaining infeasibilities in the solution of the relaxed MCNF-FIFO model using a repair heuristic to obtain a feasible solution. We develop two other heuristic algorithms that are stand-alone construction heuristics that build a feasible solution from scratch. To assess the effectiveness of the modeling and algorithmic enhancements, we implement the methods and apply them to three real life test instances. Our tests show that the problem reduction techniques are very effective in reducing the solution times. Among the heuristic algorithms, the optimization-based heuristic performs the best to find near-optimal solutions quickly. / text

This article studies the linear multicommodity network flow problem. This kind of problem arises in a wide variety of contexts. A numerical implementation of the primal-dual interior-point method is designed to solve the problem. In the interior-point method, at each iteration, the corresponding linear system, expressed as a normal equations system, is solved by using the AINV algorithm combined with a preconditioned conjugate gradient algorithm or by the AINV algorithm for the whole normal equations. Numerical experiments are conducted for networks of different dimensions and numbers of products for the distribution problem. The computational results show the effectiveness of the interior-point method for this class of network problems.

O Problema do Multicorte Dirigido Mínimo é um problema clássico em otimização combinatória. Ele é NP-difícil mesmo para instâncias muito simples. Este trabalho faz uma análise dos algoritmos exatos e de aproximação para resolver o problema. Também implementa alguns desses algoritmos e compara seus desempenhos. / The directed multicut problem is a classical problem in combinatorial optimization. It is NP-hard even for very simple families of instances. This work makes an analysis of the exact and approximation algorithms for the problem. It also implements some of these algorithms and compares their performances.

O Problema do Multicorte Dirigido Mínimo é um problema clássico em otimização combinatória. Ele é NP-difícil mesmo para instâncias muito simples. Este trabalho faz uma análise dos algoritmos exatos e de aproximação para resolver o problema. Também implementa alguns desses algoritmos e compara seus desempenhos. / The directed multicut problem is a classical problem in combinatorial optimization. It is NP-hard even for very simple families of instances. This work makes an analysis of the exact and approximation algorithms for the problem. It also implements some of these algorithms and compares their performances.

We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all arc latency functions are linear and there is a single source and sink. Still, one can prove that an optimal flow and an equilibrium flow share a desirable property in this situation: all flow-carrying paths have the same length; i.e., these solutions are "fair," which is in general not true for the optimal flow in networks with nonlinear latency functions. In addition, the maximum latency of the Nash equilibrium, which can be computed efficiently, is within a constant factor of that of an optimal solution. That is, the so-called price of anarchy is bounded. In contrast, we present a family of instances that shows that the price of anarchy is unbounded for instances with multiple sources and a single sink, even in networks with linear latencies. Finally, we show that an s-t-flow that is optimal with respect to the average latency objective is near optimal for the maximum latency objective, and it is close to being fair. Conversely, the average latency of a flow minimizing the maximum latency is also within a constant factor of that of a flow minimizing the average latenc

The Diameter-Constrained Minimum Spanning Tree Problem seeks a least cost spanning tree subject to a (diameter) bound imposed on the number of edges in the tree between any node pair. A traditional multicommodity flow model with a commodity for every pair of nodes was unable to solve a 20-node and 100-edge problem after one week of computation. We formulate the problem as a directed tree from a selected central node or a selected central edge. Our model simultaneously finds a central node or a central edge and uses it as the source for the commodities in a directed multicommodity flow model with hop constraints. The new model has been able to solve the 20-node, 100-edge instance to optimality after less than four seconds. We also present model enhancements when the diameter bound is odd (these situations are more difficult). We show that the linear programming relaxation of the best formulations discussed in this paper always give an optimal integer solution for two special, polynomially-solvable cases of the problem. We also examine the Diameter Constrained Minimum Steiner Tree problem. We present computational experience in solving problem instances with up to 100 nodes and 1000 edges. The largest model contains more than 250,000 integer variables and more than 125,000 constraints.

L'objectif de ce travail consiste à réaliser un système dynamique d'aide aux déplacements multimodal pour les voyageurs équipés d'un système d'information tout en prenant en considération les usagers non équipés de ce type de système. Le travail est alors divisé en deux parties: Une partie conception et développement et une partie étude. La partie développement consiste à construire l'outil informatique d'aide aux déplacements grâce à une modélisation multi-agent et qui renvoie à l'usager un itinéraire qui satisfait ces besoins et ceux du réseau. La partie étude quant à elle, consiste en une approche plus théorique qui consiste à déterminer l'impact de l'information sur les coûts des itinéraires, l'impact de la réorientation des usagers vers les transports en commun sur le réseau routier ainsi que l'intérêt de passer vers des véhicules autonomes / The objective of this work consists on the realization of a dynamic guidance system in a multimodal network for users equipped with an information device while taking into account users that are not equipped with such devices. The work is organized into parts: a conception part and a theoretical study part. The conception part consists on the development of the guidance tool using a multi agent architecture. This tool assists users in their daily travels by giving them the itinerary that suits best not only their needs but also the overall network. The theoretical study emphasizes on how the performance of the network can be enhanced. To do so, three main studies will be presented: the impact of the information on the cost of the itineraries, the impact of the reorientation of users towards transportation systems on the road network and finally the benefits of introducing autonomous vehicles

abstract: This thesis addresses the following fundamental maximum throughput routing problem: Given an arbitrary edge-capacitated n-node directed network and a set of k commodities, with source-destination pairs (s_i,t_i) and demands d_i> 0, admit and route the largest possible number of commodities -- i.e., the maximum throughput -- to satisfy their demands. The main contributions of this thesis are three-fold: First, a bi-criteria approximation algorithm is presented for this all-or-nothing multicommodity flow (ANF) problem. This algorithm is the first to achieve a constant approximation of the maximum throughput with an edge capacity violation ratio that is at most logarithmic in n, with high probability. The approach used is based on a version of randomized rounding that keeps splittable flows, rather than approximating those via a non-splittable path for each commodity: This allows it to work for arbitrary directed edge-capacitated graphs, unlike most of the prior work on the ANF problem. The algorithm also works if a weighted throughput is considered, where the benefit gained by fully satisfying the demand for commodity i is determined by a given weight w_i>0. Second, a derandomization of the algorithm is presented that maintains the same approximation bounds, using novel pessimistic estimators for Bernstein's inequality. In addition, it is shown how the framework can be adapted to achieve a polylogarithmic fraction of the maximum throughput while maintaining a constant edge capacity violation, if the network capacity is large enough. Lastly, one important aspect of the randomized and derandomized algorithms is their simplicity, which lends to efficient implementations in practice. The implementations of both randomized rounding and derandomized algorithms for the ANF problem are presented and show their efficiency in practice. / Dissertation/Thesis / Masters Thesis Computer Science 2020

Minimum Concave Cost Multicommodity Network Design Problem arises in many application areas, such as transportation planning, distributed energy system and especially both circuit and packet switching backbone network design. Exact concave optimization algorithms have been developed, but these methods are applicable if the network size is small. Therefore, these problems are usually solved by non-exact iterative methods. In this thesis work, methods proposed for circuit switching and packet switching network design are evaluated in detail. After a comprehensive literate survey, Yaged&rsquo / s Linearization, Minoux greedy and Minoux accelerated greedy methods are found to be applicable to circuit switching network design when both solution quality and computational time is considered. Previously, it has been found that Minoux greedy methods may create routings with cycles and in order to eliminate these cycles a modification has been proposed. In this work, this modification is extended and evaluated in detail. Similarly, Gerla and Kleinrock&rsquo / s Concave Branch Elimination, Gersht&rsquo / s greedy and Stacey&rsquo / s Concave Link Elimination methods are investigated within the context of packet switching network design. All of these methods consider aggregate flows on each link simultaneously re-routing more than one commodity in one step. This thesis work also considers an alternative disaggregate approach, where only one commodity is handled at a time. Finally, algorithms proposed for circuit switching network design problem are adapted to the packet switching case and an extensive comparative computational study is performed to point out the best method with respect to time and solution quality for a number of networks and cost structure. Computational results have shown that modification on Minoux greedy to eliminate cycles leads to considerable improvements and the disaggregate approach gives the best result in some networks and cost structure.