Logo: to the web site of the Swedish Defence University

Network Interdiction-problem innehåller två mot varandra stående styrkor, en användare och en angripare, somär inbegripna i en krigsliknande konflikt. Användaren använder ett nätverk för att optimera en funktion, t.ex.att förflytta en underhållskonvoj så snabbt som möjligt, eller maximera mängden materiel som transporterasgenom nätverket. Det innebär att användaren vill använda den kortaste eller snabbaste vägen vid transporter,och han vill maximera flödet genom nätverket. Nätverket kan t.ex. vara ett vägnät, kraftförsörjningsnät eller ettdatornätverk. Angriparen försöker begränsa användarens möjlighet att optimera sin funktion. Angriparenssyftet är att maximera den kortaste/snabbaste vägen eller att minimera det maximala flödet genom nätverket.Angriparen uppnår detta genom att angripa bågar eller noder i nätverket och förstöra dem totalt eller reduceraderas kapacitet. Angriparens resurser är begränsade och det finns ett behov av att optimera användandet. Imånga fall är nätverket stort och många parametrar påverkar planeringen. Detta ger en komplexplaneringsförutsättning för angriparen. Genomförs planläggningen av Network Interdiction på traditionellt sätt,tvingas planeraren att använda sin intuition. Resultatet beror till stor del på planläggarens förmåga och tid tillförfogande. Om algoritmer kunde användas för att stödja planläggaren, skulle resursutnyttjandet och effektenav angreppen kunna optimeras. Uppsatsen undersöker om det är möjligt att använda Network Interdictionalgoritmervid planering av Network Interdiction.

Network interdiction problems involve two opposing forces, a user and anattacker, who are engaged in a warlike conflict. The user operates a network inorder to optimize a function such as moving a supply convoy through thenetwork as quickly as possible, or maximizing the amount of materieltransported through the network. This means that the user is trying to use theshortest or the fastest route to perform transports, and he is trying to maximizethe flow trough the network. The network could be a road net, an electric powergrid or a computer network system. The attacker attempts to limit the user’spossibility to optimize his function. The purpose is to maximize the shortest andfastest route or to minimize the maximum flow through the network. Theattacker obtains this by interdicting arcs or nodes, e.g. by attacking arcs or nodesin order to destroy them entirely or to reduce their capacity. The attacker’sresources are limited and there is a need to optimize the use of them. In manycases the network is big and numerous parameters influence the planning. Thismakes the conditions for planning complex and difficult for the attacker. If theplanning of network interdiction is performed in the traditional way, the planneris forced to use intuition. The result will depend on the planner’s capacity and thetime at his disposal. If algorithms could be used to support the planner, theresources and the effect of the attack would be optimized. This thesis examines ifit is possible to use network interdiction algorithms to plan network interdiction.