معصومه مسی بیدگلی - دانشکده فنی و مهندسی
جلسه دفاع از رساله برای دریافت درجه دکتری در رشته مهندسی صنایع
عنوان رساله:
مدلسازي و حل مسئله مسيريابي وسايل نقليه ظرفيتدار در شرايط حمله به شبکه با استفاده از نظريه بازيها
استادراهنما:
جناب آقای دکتر امیرسامان خیرخواه
استاد مشاور:
جناب آقای دکتر حمیدرضا نویدی
اساتید ممتحن خارجی:
جناب آقای دکتر مسعود یقینی
سرکار خانم دکتر مریم اسمعیلی
استاد ممتحن داخلی:
جناب آقای دکتر جواد بهنامیان
نگارش:
معصومه مسی بیدگلی
زمان: چهار شنبه 9/4/1395- ساعت 10-12
مکان: آمفی تئاتر دانشکده مهندسی
چكيده: تحقیق حاضر به مطالعه و بررسی مسئله حمله به شبکه مسیریابی کالاهایی میپردازد که به دلیل ارزش کالای توزیعی و یا خسارات و آسیبهایی که توزیع نادرست این کالاها میتواند در پی داشته باشد، مورد تهاجم تصمیمگیرنده دیگری قرار میگیرد. در این دسته از مسایل، که تحت عنوان مسایل حمله به شبکه مسیریابی شناخته میشود، توزیعکننده به عنوان مدافع ناگزیر است تا تاثیر استراتژیهای اتخاذشده از سوی مهاجم را در انتخاب مسیرهای مناسب برای تجهیزات نقلیه خود در نظر بگیرد. مسایلی از این دست که ارتباط بین دو تصمیمگیرنده از جنس پیشبینی و پاسخ است، در قالب بازیهای استکلبرگ قابل مدلسازی است. کاربردهای گسترده این دسته از مسایل در امور روزمره، اهمیت و ضرورت تحقیق را به روشنی بیان میکند. از جمله این کاربردها میتوان به مسئله حمله به شبکه توزیع سوخت، حمله به خودروهای حامل محمولههای ارزشمند از جمله خودروهای توزیع پول بانکها، خودروهای حمل زندانیان وخودروهای توزیع تجهیزات نظامی و لوازم اساسی در شرایط جنگی و در حملات تروریستی اشاره کرد. علاوهبراین، مسئله حمله به حاملهای مواد خطرناک که مسیرهای انتخابی خود را از مناطق با ریسک و تراکم جمعیت بالا انتخاب میکنند و همچنین در مواردی که خودروهای مورد استفاده برای توزیع کالا، خودروهای با سوخت دیزلی و آلودهکننده محیط زیست هستند نیز از جمله موارد کاربرد مسئله مورد مطالعه هستند که در این تحقیق به آنها پرداخته میشود. بسته به نوع مسئله مورد مطالعه، مهاجم میتواند با استفاده از استراتژیهای سختگیرانه و حملات تخریبی از ادامه مسیر توزیعکننده جلوگیری نماید و یا این که صرفا با استفاده از استراتژی حمله تداخلی با جریمه کردن حاملهای خاطی، هزینه عبور از برخی کمانهای حیاتی را افزایش داده و از این طریق، توزیعکننده را به سمت انتخاب کمانهای مورد نظر خود هدایت میکند. از سوی دیگر به واسطه نوع درک و برداشت دو تصمیمگیرنده از اطلاعات شبکه، مسئله میتواند در دو حالت حمله با اطلاعات متقارن و نامتقارن مدلسازی شود. در این تحقیق، مسئله حمله به شبکه مسیریابی در شرایط حمله تخریبی و تداخلی و همچنین برای دو حالت حمله با اطلاعات متقارن و نامتقارن مدلسازی میشود و الگوریتمهای حل دقیق و فراابتکاری مناسب و کارایی برای مسایل مورد مطالعه پیشنهاد میشود.
|
واژه های کلیدی: مسئله حمله به شبکه، مسیریابی وسایل نقلیه، برنامهریزی دوسطحی، بازی استکلبرگ، تجزیه بندرز، الگوریتمهای فراابتکاری دوسطحی |
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. |
Kheirkhah, A., Navidi, H., & Messi Bidgoli, M. (2016). A bi-level network interdiction model for solving the hazmat routing problem. International Journal of Production Research, 54(2), 459-471. |
Kheirkhah, A., Navidi, H., & Bidgoli, M. M. (2016). An Improved Benders Decomposition Algorithm for an Arc Interdiction Vehicle Routing Problem. IEEE Transactions on Engineering Management, 63(2), 259-273. |
Kheirkhah, A., Navidi, H., & Bidgoli, M. M. (2015). Dynamic Facility Layout Problem: A New Bilevel Formulation and Some Metaheuristic Solution Methods. IEEE Transactions on Engineering Management, 62(3), 396-410. |
Navidi, H., Bashiri, M., & Messi Bidgoli, M. (2012). A heuristic approach on the facility layout problem based on game theory. International Journal of Production Research, 50(6), 1512-1527. |
حمیدرضا نویدی، سعید کتابچی، معصومه مسی بیدگلی. کتاب مدخلی بر تئوری بازیها. انتشارات دانشگاه شاهد- 1390. |