ارايه يك رويكرد ابتكاري نوين براي ساده سازي گراف اوليه مساله بيشينه جريان

A Novel Heuristic Approach to Simplify Initial Graph of Maximum Flow Problem

مساله بيشينه جريان شبكه به دنبال يافتن بيشترين جرياني است كه در شبكه مي‌تواند از ريوس منبع به ريوس چاه منتقل شود. هدف از اين تحقيق بهبود و ساده‌سازي گراف اوليه است كه به‌عنوان گراف پايه براي حل به الگوريتم‌هاي بيشينه جريان شبكه داده مي‌شود. در اين صورت زمان حل مساله كاهش مي‌يابد. بسياري از الگوريتم هاي بيشينه جريان با تكيه بر مفهوم سطح در گراف، بيشينه جريان را با پيدا كردن مسير و ارسال آن به‌دست آورده‌اند. در اين مقاله، با دقت به مفهوم عمق گراف در الگوريتم پيشنهادي، برآنيم از منظري جديد به مساله پرداخته شود تا از پيچيدگي زماني مساله كاسته شود. در الگوريتم پيشنهادي سعي شده است با استفاده از مفهوم عمق در گراف، ابتدا با ساده‌سازي مساله از طريق حذف كمان ها و ريوس، ابعاد و پيچيدگي محاسباتي مساله كاهش يابد. اين الگوريتم همچنين با مسايلي كه در آنها چندين چشمه و چاه وجود دارد سازگار است. تحليل روند و گام هاي حل، با استفاده از ماتريس تهيه شده از گراف مساله بسيار ساده است و با ديگر الگوريتم هاي ارايه شده در ادبيات نيز سازگاري دارد. لذا به‌راحتي مي توان پس از چند مرحله ساده‌سازي از ديگر روش ها، به ادامه حل مساله پرداخت. در نهايت، عملكرد روش حل ارايه شده بر روي مسايل آزمايشي توليد شده با ابعاد مختلف مورد تجزيه و تحليل قرار گرفته و الگوريتم هاي موجود در ادبيات مورد مقايسه قرار گرفته شده است.

Network maximum flow problem trying to find the maximum flow that can transmit from the source nodes to sink nodes. The purpose of this research is to improve and simplify the initial graph that given as a problem to solve by network maximum flow algorithm. Most of maximum flow algorithms solve the problem with finding route & transmitting based on basic feasible solution. In this paper, we attempt to present a new heuristic approach according to depth concept in graph to reduce the problem time complexity with removing arcs and nodes. This algorithm is compatible with multi-source multi-sink algorithms in the literature. Finally, to demonstrate applicability of the proposed approach, several test problems are first generated; then, the comparisons are carried out. The results show that the proposed heuristic can simplify the problem and consequently reduce the complexity of maximum flow problem.