یک روش کارآمد برای انتخاب مسیر قابل اعتماد مقید در شرایط عدم قطعیت

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

An Efficient Method for Selecting a Reliable Path under Uncertainty Conditions

In a network that has the potential to block some paths, choosing a reliable path, so that its survival probability is high, is an important and practical issue. The importance of this issue is very considerable in critical situations such as natural disasters, floods and earthquakes. In the case of the reliable path, survival or blocking of each arc on a network in critical situations is an uncertain parameter that is estimated and among all the paths that connect two distinct points, the route that is most likely to be survived is selected. Since decisions about choosing routes are dependent on other factors, such as distance, cost, or duration of the route, each of these indicators can be added to the problem as some constraints. For modeling the problem, considering the probability of survival of any arc, a reliable path is defined as a path that the product of probability of its arcs is as close as possible to one. Then the logarithm function is used to linearize the probability multiplication and the problem model is converted to the constrained shortest path model form. Finally, an algorithm is provided to solve the proposed model, which in any iteration using logical cuts, eliminates the obtained suboptimal paths and approaches the optimal solution. The results of applying this method on some networks with different structure and size show that the proposed algorithm is able to achieve a path that can be expected with high probability of surviving in critical conditions and its distant does not exceed the specified limit.