ABSTRACT Network försvar och attacker problem kan modelleras som nätverk interdictions. I detta dokument överväger vi en ny version av problemet med interdiktion av nätet som optimerar interdiktorns resursförbrukning samtidigt som nätkapaciteten (t.ex. den kortaste vägen) begränsas till en angiven tröskel. Interdiktorer skulle balansera interdiction prestanda och resursförbrukning när maximering prestandakostnader för mycket. Den mest använda tekniken är att slappna av maximeringsfasthållningen till vissa angivna tröskelvärden; men de kända algoritmerna ger föga hjälp vid beräkning av tröskelfasthållningen. Vi presenterar en ny modell som heter minimera interdiction resurs med måltröskel baserat på den kortaste vägen interdiction problem och föreslår två grundläggande algoritmer för att lösa det baserat på Benders nedbrytning respektive Lagrange dualitet, respektive. För att ta hänsyn till situationen med fullständig interdiktion och situationen med en stor tröskel, presenteras en motsvarande set-covering algoritm och en Lagrange ungefärlig algoritm. Beräkningsförsök visar att nedbrytningsbaserade algoritmer i allmänhet presterar bättre på småvärldsnätverk medan dualitetsbaserade algoritmer presterar bättre på vanliga nätnätverk. Analyser av nätfastighetskänslighet visar att de nedbrytningsbaserade algoritmerna är känsliga för tröskelvärdet medan dualitetsbaserade algoritmer blir svagare när interdiction-ökningen växer. Dessutom utvärderar vi prestandan för dessa två grundläggande algoritmer på en verklig Chicago transportnätverk. Resultatet illustrerar ett betydande framsteg; båda algoritmerna kan beräkna en optimal strategi för problem som skalar upp till verkliga storlekar.
Wei och Al. REF införde ett tröskelvärde för ett näts kapacitet och föreslagna algoritmer baserade på nedbrytning och dualitetsformulering för att optimera interdiktorns resursförbrukning.
Shortest Path Network Interdiction With Goal Threshold
{'venue': 'IEEE Access', 'journal': 'IEEE Access', 'mag_field_of_study': ['Computer Science']}