چكيده:

تحقیق حاضر به مطالعه و بررسی مسئله حمله به شبکه مسیریابی کالاهایی می‏پردازد که به دلیل ارزش کالای توزیعی و یا خسارات و آسیب‏هایی که توزیع نادرست این کالاها می‏تواند در پی داشته باشد، مورد تهاجم تصمیم‏گیرنده دیگری قرار می‏گیرد. در این دسته از مسایل، که تحت عنوان مسایل حمله به شبکه مسیریابی شناخته می‏شود، توزیع‏کننده به عنوان مدافع ناگزیر است تا تاثیر استراتژی‏های اتخاذشده از سوی مهاجم را در انتخاب مسیرهای مناسب برای تجهیزات نقلیه خود در نظر بگیرد. مسایلی از این دست که ارتباط بین دو تصمیم‏گیرنده از جنس پیش‏بینی و پاسخ است، در قالب بازی‏های استکلبرگ قابل مدلسازی است.

کاربردهای گسترده این دسته از مسایل در امور روزمره، اهمیت و ضرورت تحقیق را به روشنی بیان می‏کند. از جمله این کاربردها می‏توان به مسئله حمله به شبکه توزیع سوخت، حمله به خودروهای حامل محموله‏های ارزشمند از جمله خودروهای توزیع پول بانک‏ها، خودروهای حمل زندانیان وخودروهای توزیع تجهیزات نظامی و لوازم اساسی در شرایط جنگی و در حملات تروریستی اشاره کرد. علاوه‏براین، مسئله حمله به حامل‏های مواد خطرناک که مسیرهای انتخابی خود را از مناطق با ریسک و تراکم جمعیت بالا انتخاب می‏کنند و هم‏چنین در مواردی که خودروهای مورد استفاده برای توزیع کالا، خودروهای با سوخت دیزلی و آلوده‏کننده محیط زیست هستند نیز از جمله موارد کاربرد مسئله مورد مطالعه هستند که در این تحقیق به آن‏ها پرداخته می‏شود.

 بسته به نوع مسئله مورد مطالعه، مهاجم می‏تواند با استفاده از استراتژی‏های سختگیرانه و حملات تخریبی از ادامه مسیر توزیع‏کننده جلوگیری نماید و یا این که صرفا با استفاده از استراتژی حمله تداخلی با جریمه کردن حامل‏های خاطی، هزینه عبور از برخی کمان‏های حیاتی را افزایش داده و از این طریق، توزیع‏کننده را به سمت انتخاب کمان‏های مورد نظر خود هدایت می‏کند. از سوی دیگر به واسطه نوع درک و برداشت دو تصمیم‏گیرنده از اطلاعات شبکه، مسئله می‏تواند در دو حالت حمله با اطلاعات متقارن و نامتقارن مدلسازی شود. در این تحقیق، مسئله حمله به شبکه مسیریابی در شرایط حمله تخریبی و تداخلی و هم‏چنین برای دو حالت حمله با اطلاعات متقارن و نامتقارن مدلسازی می‏شود و الگوریتم‏های حل دقیق و فراابتکاری مناسب و کارایی برای مسایل مورد مطالعه پیشنهاد می‏شود.

واژه­ های کلیدی: مسئله حمله به شبکه، مسیریابی وسایل نقلیه، برنامه‏ریزی دوسطحی، بازی استکلبرگ، تجزیه بندرز، الگوریتم‏های فراابتکاری دوسطحی

Abstract:

In this thesis, routing of some special kinds of shipments is integrated for the first time into the network interdiction concepts, in which an interdictor disrupts some arcs of the network to prevent distributing more materials through the network. The associated problems are commonly referred to as network interdiction problem. Network interdiction studies how decisions made by two intelligent adversaries, called “defender” and “attacker,” affect a network’s functionality. One of these players seeks, for example, to maximize flow through the network, or to minimize cost to supply the demand, while the other player tries to disrupt the network by interdicting selected components. These prediction-response problems could be modeled as a stachelberg game.

There are some vital or expensive shipments such as fuel shipments, vehicles carrying money, prisoner transfer vehicles and so on that are being assassinated by some interdictors. This problem could be experienced in various other distribution problems such as distribution of hazardous material, illegal drugs, and military equipments in wars and under terrorist attacks. Also, this problem could be applied to inspect and evaluate the quality of serving the customers by retailers in supply chain management and in order to prohibit pollutant vehicles from traversing to reduce the greenhouse gasses emission in Green vehicle routing problem (GVRP). However, it is necessary to note that its application is not restricted to these cases.

There are two types of interdiction: (1) destructive network interdiction models in which the interdictor prevents the distributer from continuing to his route and (2) disruptive network interdiction in which the attacker only increases the distribution cost through some critical arcs of network via fining the distributer in these arcs.

On the other hand, two players may have the same or different perceptions about the network that result in symmetric or asymmetric information game, respectively. In this thesis, the vehicle routing network interdiction problem for destructive and disruptive interdictions and for symmetric and asymmetric information cases are modeled and some exact and bi-level meta-heuristic solution methods are proposed and evaluated for these problems.

Key Words: Vehicle routing problem; Network Interdiction; Bi-Level programming; Stachelberg Game; Benders Decomposition; Bi-level Meta-heuristic Algorithms.