view in publisher's site

Network Interdiction with Asymmetric Cost Uncertainty

Highlights•This research focuses on a variant of shortest-path interdiction problems•The interdictor may not have perfect information on data•A bounding-and-partitioning approach can solve expected-value interdiction problems•Computation time depends mostly on the number of uncertain arcsAbstractWe study a shortest-path interdiction problem in which the interdictor acts first to lengthen a subset of arcs, and an evader acts second to select a shortest path across the network. In this problem, the cost for an evader’s arc consists of a base cost if the arc is not interdicted, plus an additional cost that is incurred if the arc is interdicted. The interdictor is not aware of the base costs when the interdiction action is taken, but does know that the base cost values are uniformly distributed within given (arc-specific) intervals. The evader, on the other hand, observes the exact value of the base costs, plus the additional costs due to interdiction actions. The interdictor’s problem is thus to maximize the expected minimum cost attainable by the evader. We provide a partitioning algorithm for computing an exact optimal solution to this problem, leveraging bounds gleaned from Jensen’s inequality as proposed in an earlier study on a maximum-flow interdiction problem. We also provide several algorithmic strategies for accelerating the convergence of the algorithm and demonstrate their effectiveness on randomly generated instances.

تفسیر شبکه با عدم قطعیت هزینه نامتقارن

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


پر ارجاع‌ترین مقالات مرتبط:

  • مقاله Information Systems and Management
  • ترجمه مقاله Information Systems and Management
  • مقاله سیستم‌های اطلاعاتی و مدیریت
  • ترجمه مقاله سیستم‌های اطلاعاتی و مدیریت
  • مقاله Modelling and Simulation
  • ترجمه مقاله Modelling and Simulation
  • مقاله مدل‌سازی و شبیه‌سازی
  • ترجمه مقاله مدل‌سازی و شبیه‌سازی
  • مقاله Management Science and Operations Research
  • ترجمه مقاله Management Science and Operations Research
  • مقاله علوم مدیریت و پژوهش عملیاتی
  • ترجمه مقاله علوم مدیریت و پژوهش عملیاتی
سفارش ترجمه مقاله و کتاب - شروع کنید

با استفاده از افزونه دانلود فایرفاکس چکیده مقالات به صورت خودکار تشخیص داده شده و دکمه دانلود فری‌پیپر در صفحه چکیده نمایش داده می شود.