To improve the performance of the transportation network operation, traffic assignment problems require more reliable results. Disregard the solution method, o ne factor that leads to more accurate results in traffic assignment problems is considering the link capacity constraints. In traffic assignment pr oblems, techniques such as the F rank-Wolfe (FW) algorithm has extensive applications, but not consi dering link capacity in these methods results in inaccurate outputs. In every iteration of FW, move direction is obtained by solving the minimum cost flow problem for the network without considering the capacity constraints, which is named the all or nothi ng assignment algorithm. On the contrary, there is another algorithm called the Out of kilter (OFK) algorithm that solves the traffic assignment problem by minimizing the cost flow problem in networks with link capacity constraints. In this dissertation, th e movement direction of the FW algorithm is obtained by the OFK algorithm. Therefore, in every iteration, link flows are lower than or equal to their capacities. In this method, we assume that the network has a circulation form, meaning that all origins ar e pure origin, and all destinations are the pure destination. Moreover, the results of the proposed algorithm for the Hearn and Sioux Falls transportation networks are presented and compared to the condition that link capacities are considered infinite. Keywords: Traffic Assignment, Capacity Constraint, Frank -Wolf Algorithm, Out of Kilter Algorithm Abstract To improve the performance of the transportation network operation , traffic assignment problems require more reliable results . Disregard the solution method , one factor that lead s to more accurate results in traffic assignment problems is considering the link capacity constraints. In traffic assignment problems, technique s such as the frank -Wolfe (FW) algorithm has extensive applications, but not considering link capacity in these methods results in inaccurate outputs. In every iteration of FW, move direction is obtained by solving the mi nimu m cost flow problem for the network without considering the capacity constraints, which is named the all or nothing assignment algorithm. On the contrary , there is another algorithm n amed the Out of kilter (OFK) algorithm that solves the traffic assignment problem by minimizing the cost flow problem in networks with link capacity constraints. In this dissertation, the move ment direction of the FW algorithm is obtained by the OFK algorithm. Therefore, in every iteration, link flows are lower than or equal to their capacities. In this method , we assume that the network has a circulation form, meaning that all origins are pure origin, and all destinations are the pure destination. Moreover, the results of the proposed algorithm for the Hearn and Sioux Fa lls transportation networks are presented and compared to the condition that link capacities are considered infinite. Keywords: Traffic Assignment, Capacity Constraint, Frank -Wolf Algorithm, Out of Kilter Algorithm أ 1 فصل اول مقدمه ................................................................ ......................................................... 1 1-1- مقدمه ................................................................ ................................................................ ......................................... 2 1-2- اهميت مسأله ................................................................ ................................................................ ............................ 3 1-3- مروري بر فصول ................................................................ ................................................................ ........................ 3 2 فصل دوم ................................................................ ................................................................ ..... 2 ادبیات مساله تخصیص ................................................................ ..................................................... 2 2-1- مقدمه ................................................................ ................................................................ ......................................... 3 2-2- مروري بر مدل هاي تخصيص ترافيک ................................................................ ................................................. 3 2-3- مدل بهينه سازي تخصيص ترافيک ................................................................ ...................................................... 9 2-3-1-روش هاي نزول ................................................................ ................................................................ .................................. 11 2-3-2- الگوريتم فرانک-ولف ................................................................ ................................................................ ......................... 11 2-3-2- روش ميانگين گيري متوالي ................................................................ ................................................................ .......... 11 2-4- مدل تخصيص ترافيک با ظرفيت محدود ................................................................ ........................................... 11 2-5- الگوريتم شهپر و همکاران ................................................................ ................................................................ .....11 3 فصل سوم مسئله جریان با هزینه منیمم درشبكه ............................................................... 23 3-1- مقدمه ................................................................ ................................................................ ....................................... 24 3-2- مسئله جريان با هزينه مينيمم ................................................................ ............................................................ 25 3-3- الگوريتم بلمن-فورد ................................................................ ................................................................ ............... 21 3-4- الگوريتم دايجسترا ................................................................ ................................................................ .................. 21 3-5- الگوريتم درخت heap ................................ ................................ ................................ ................................ ........... 32 3-5-1-هرم ماكزيمم ( (max -heap ................................ ................................ ................................ ................................ .......... 32 3-5-2-هرم مينيمم ( (min -heap ................................ ................................ ................................ ................................ ........... 33 3-1- الگوريتم Out of Kilter ................................ ................................ ................................ ................................ ......39 3-1- مسئله تخصيص همه يا هيچ ................................................................ ................................................................ 54 3-1- مقايسه الگوريتم هاي بل و دايجسترا ................................................................ ................................................. 54 4 فصل چهارم اثر اعمال محدودیت ظرفیت کمان بر مسئله تخصیص ترافیک ..................... 65 4- 1- مقدمه ................................................................ ................................................................ ................................... 51 4-2- شبکه هاي حمل و نقل ................................................................ ................................................................ ......... 51 4-2-1-شبکه هرن ................................................................ ................................................................ ........................................... 51 4-2-2- شبکه سوفالز ................................................................ ................................................................ ...................................... 59 4-2-3- شبکه آناهايم ................................................................ ................................................................ ..................................... 15 ب 4-3- مقايسه تحليلي نتايج مسئله تخصيص ترافيک با محدوديت ظرفيت و بدون محدوديت ظرفيت ........... 15 4-3-1- ظرفيت و عوامل تاثير گذار بر آن ................................................................ ................................................................ .. 11 4-3-2-روش برچسب گذاري سه گانه ................................................................ ................................................................ ....... 11 4-3-3- ساختار شبکه ................................................................ ................................................................ .................................... 11 4-3-4- استفاده از اطالعات پيشين ................................................................ ................................................................ ............ 11 4-3-5- روند پيمايش و برچسب گذاري ................................................................ ................................................................ .... 19 4-3-1- اعمال تغييرات جريان ................................................................ ................................................................ ..................... 11 4-3-1- اعمال تغييرات هزينه تقليل يافته ................................................................ ................................................................ 11 4-3-1- شرط چرخشي بودن شبکه ................................................................ ................................................................ ............ 11 4-3-9- نحوه انتخاب كمان هاي Out of Kilter ................................ ................................ ................................ .................. 12 4-3-11- تحليل و مقايسه نتايج ................................................................ ................................................................ .................. 12 6 فصل پنجم خالصه و پیشنهادات ................................................................ ........................... 111 5-1- مقدمه ................................................................ ................................................................ ..................................... 111 5-2- خالصه ................................................................ ................................................................ ................................... 111 5-3- پيشنهادات ................................................................ ................................................................ ............................ 111 پیوست ................................................................ ................................................................ .......... 112 منابع و مراجع ................................................................ ............................................................... 131 ج فهرست اشكال شکل3-1- شبکه4 گره اي الگوريتم دايجسترا................................ ................................................................ ................... 82 شکل3-2- درخت هيپ ماكزيمم................................ ................................................................ ........................................ 38 شکل3-2- درخت هيپ مينيمم ................................................................ ................................................................ ......... 33 شکل3-4- شبکه4 گره اي الگوريتم هيپ ................................................................ ....................................................... 35 شکل 3-5-درخت مرحله اول الگوريتم هيپ مينيمم ................................................................ ...................................... 35 شکل3-1- درخت مرحله دوم الگوريتم هيپ مينيمم ................................................................ ..................................... 36 شکل3-1- درخت مرحله سوم الگوريتم هيپ مينيمم ................................................................ .................................... 33 شکل3-1- شبکه مطلوب الگوريتمOFK ................................ ................................ ................................ .............................. 14 شکل3-9- شبکه4 گره اي الگوريتم OFK ................................ ................................ ................................ ....................... 18 شکل3-11- درخت مرحله اول الگوريتم OFK ................................ ................................ ................................ ................ 13 شکل3-11- درخت مرحله دوم الگوريتم OFK ................................ ................................ ................................ .............. 15 شکل3-12- درخت مرحله سوم الگور يتم OFK ................................ ................................ ................................ .............. 15 شکل3-13- درخت مرحله چهارم الگوريتمOFK ................................ ................................ ................................ .............. 16 شکل3-14- مقايسه جريان در كمان ها براي الگوريتم هاي FW وOFK ................................ ................................ .. 12 شکل3-15- مقايسه جرياندر كمان ها براي الگوريتم هاي FW وOFK ................................ ................................ .. 54 شکل3-11- مقايسهتعداد كمان هاي داراي جريان براي الگوريتم هايFW وOFK ................................ ................. 58 شکل4-1- نمايي از شبکه هرن ................................................................ ................................................................ .......... 53 شکل4-2- نمايي از شبکه سوفالز ................................................................ ................................................................ ........ 55 شکل4-3- نمودار رابطه بين جريان و زمان سفر ................................................................ .............................................. 65 شکل4-4- مراحل الگوريتمOFK ................................ ................................ ................................ ................................ ......... 38 شکل4-5- مقايسه جريان در كمان ها براي الگوريتم هايFW و FW-OFK-INFINTECAP .............................. 32 شکل4-1- مقايسه هزينه كمان ها براي الگوريتم هايFW و FW-OFK-INFINTECAP ................................ ..... 35 شککل4-1- مقايسه جريان در كمان ها براي دوالگوريتم FW-OFK -CAPAITATED و FW-OFK -INFINITECAP ................................ ................................ ................................ ................................ ................................ ................................ .... 28 شکککککل 4-1- مقککايسکککه هزينکه سکککفر كمکان هککا براي دو الگوريتم FW-OFK -CAPACITATED و FW-OFK - INFINITECAP ................................ ................................ ................................ ................................ ................................ ....... 11 شککل4-9- مقايسکه نسبت جريان به ظرفيت براي الگوريتم هاي FW ، FW-OFK -CAPACITATED و FW-OFK - INFINITECAP ................................ ................................ ................................ ................................ ................................ ................................ ........................ 24 شکل4-11- مقايسه تغييرات هزينه كل براي دو الگوريتمFW و FW-OFK در حالت بدون ظرفيت .................. 28 د شککل 4-11- مقايسکه تغييرات هزينه مصکرک كننده براي دو الگوريتمFW و FW-OFK در حالت بدون ظرفيت. ................................................................ ................................................................ ................................................................ .... 28 شکل 4-12- مقايسه جريان بدست آمده از دو الگوريتمFW و FW-OFK -INFINITECAP ................................ .......... 26 شککککل 4-13- مقايسکککه هزينه سکککفر بدسکککت آمده از الگوريتم هاي FW و FW-OFK -INFINITECAP INFINITECAP ................................ ................................ ................................ ................................ ................................ ........ 23 شکککککل 4-14- مقکايسکککه جريکان هاي بدسکککت آمده از دو الگوريتم FW-OFK -CAPACITATED و FW-OFK - INFINITECAP ................................ ................................ ................................ ................................ ................................ ................................ ......... 22 شکککککل 4-15- مقکايسکککه هزينکه هاي بدسکککت آمده از دو الگوريتم FW-OFK -CAPACITATED و FW-OFK - INFINITECAP ................................ ................................ ................................ ................................ ................................ ...... 11 شککل4--11 مقايسه مقادير جريان بر ظرفيت براي الگوريتم هاي FW ، FW-OFK -CAPACITATED و FW-OFK - INFINITECAP ................................ ................................ ................................ ................................ ................................ ...... 25 شکل4-11- تغييرات هزينه كل براي دو الگوريتمFW و FW-OFK-INFINTECAP ................................ ................. 58 شکل4-11- تغییرات هزینه مصرف کننده برای دو الگوریتم FW و FW-OFK -INFINTECAP ............................ 54 شکل4-19- مقايسه جريان هاي بدست آمده از الگوريتم هايFW و FW-OFK -INFINTECAP ............................ 51 شکل4-21- مقايسه هزينه هاي بدست آمده از الگوريتم هايFW و FW-OFK -INFINTECAP .......................... 55 شکککککل 4-21- مقکايسکککه بين جريکان هککاي بکدسکککت آمککده از الگوريتم هککاي FW-OFK-CAPACITATED و FW-OFK- INFINITECAP ................................ ................................ ................................ ................................ ................................ ........ 56 شکل 4-22- مقايسه تغييرات هزينه كل براي دو الگوريتمFW و FW-OFK -INFINTECAP ................................ ... 56 شکل4-23- مقايسه مقادير جريان بر ظرفيت براي الگوريتم هايFW، FW-OFK-CAPACITATED و FW-OFK- INFINITECAP ................................ ................................ ................................ ................................ ................................ ...... 53 شکل 4-24- مقايسه تغييرات هزينه كل براي دو الگوريتمFW و FW-OFK-INFINTECAP ................................ . 52 شکل 4-25- مقايسه تغييرات هزينه مصرک كننده براي دو الگوريتمFW و FW-OFK -INFINTECAP ......... 52 ه فهرست جداول صفحه جدول1-الگوريتم هاي كوتاهترين مسير ................................................................ ............................................................ 24 جدول 2- كوتاه ترين مسير در مرحله 1 ................................ ................................ ................................ ........................... 29 جدول 3- كوتاه ترين مسير ................................................................ ................................................................ .................. 29 جدول 4- كوتاه ترين مسير ................................................................ ................................................................ .................. 31 جدول 5- كوتاه ترين مسير ................................................................ ................................................................ .................. 31 جدول 1 -كوتاه ترين مسير ................................................................ ................................................................ .................. 31 جدول 1- كوتاه ترين مسير ................................................................ ................................................................ .................. 31 جدول 1- مينيمم مسير گره هاي درخت هيپ ماكزيمم ................................................................ ............................... 33 جدول 9 -اعداد كيلتر ................................................................ ................................................................ ............................ 41 جدول 11- جهت مطلوب تغيير جريان ................................................................ ............................................................. 41 جدول 11- جهت مطلوب تغيير هزينه تقليل يافتن ................................................................ ....................................... 41 جدول 12- اطالعات كمان هاي شبکه ................................................................ ............................................................... 43 جدول 13- اطالعات گره هاي شبکه ................................................................ ................................................................ .. 44 جدول 14- جريان هاي بروز شده ................................................................ ................................................................ ....... 45 جدول 15-پتانسيل هاي بروز شده ................................................................ ................................................................ ..... 45 جدول 11-پتانسيل هاي بروز شده ................................................................ ................................................................ ......41 جدول 11-پتانسيل هاي بروز شده ................................................................ ................................................................ ..... 41 جدول 11- نتايج بدست آمده از الگوريتم هاي FW و OFK ................................ ................................ ...................... 41 جدول 19-مقايسه هزينه كل بدست آمده از دوالگوريتم ................................................................ ................................ 49 جدول 21 - اطالعات شبکه 12گره اي ................................................................ ............................................................... 51 جدول 21- عرضه و تقاضا درمبدا-مقصد شبکه ................................................................ ............................................... 51 جدول 22-مقايسه نتايج بدست امده از الگوريتم هاي FW و OFK ................................ ................................ .......... 51 جدول 23-مقايسه هزينه كل بدست آمده از دو الگوريتم ................................................................ .............................. 54 جدول 24-مقايسه زمان حل الگوريتم هاي بل و دايجسترا براي شبکه شيکاگو ....................................................... 55 جدول 25- عرضه و تقاضا درمبدا-مقصد شبکه هرن ................................................................ .................................... 51 جدول 21- ظرفيت باال و پايين و زمان سفر آزاد كمان هاي شبکه هرن ................................................................ .... 51 جدول 21- عرضه و تقاضا در مبدا-مقصدها ي شبکه سوفالز ................................................................ .......................... 11 جدول 21-ظرفيت و زمان سفر آزاد كمان هاي شبکه سوفالز ................................................................ ........................ 12 جکدول 29-جريکان هاي بدسکککت آمده از سکککه الگوريتم FW، FW-OFK -INFINITECAP ، FW-OFK - CAPACITATED براي شبکه هرن ................................................................ .............................................................. 14 و جدول 31-هزينه سفرهاي بدست آمده از بدست آمده از سه الگوريتم FW، FW-OFK -INFINITECAP ،FW- OFK -CAPACITATED براي شبکه هرن ................................................................ ................................................. 15 جدول 31- نتايج بدست آمده براي شبکه هرن ................................................................ ............................................... 11 جکدول 32-مقککا يسکککه نتککا يج حکاصکککل از سکککه الگوريتم FW، FW-OFK -INFINITECAP ، FW-OFK - CAPACITATED در تکرار هاي مختلف براي شبکه هرن ................................................................ ....................... 11 جدول 33- نتايج بدست آمده براي شبکه سوفالز تک مبدايي ................................................................ ...................... 15 جکدول 34- مقکايسکککه نتکايج حاصکککل از سکککه الگوريتم FW، FW-OFK -INFINITECAP ، FW-OFK - CAPACITATED در تکرار هاي مختلف براي شبکه سوفالز تک مبدايي .............................................................. 11 جدول 35-نتايج بدست آمده براي شبکه سوفالز دو مبدايي................................ .......................................................... 93 جکدول 31- مقکايسکککه نتکايج حاصکککل از سکککه الگوريتم FW، FW-OFK -INFINITECAP ، FW-OFK - CAPACITATED در تکرار هاي مختلف براي شبکه سوفالز دو مبدايي ............................................................... 94 جکدول 31- جريان هاي بدسکککت آمده از سکککه الگوريتم FW، FW-OFK -INFINITECAP ، FW-OFK - CAPACITATED براي شبکه سوفالز تک مبدايي ................................................................ .................................. 113 جدول 31- هزينه سککفرهاي بدسککت آمده از سککه الگوريتم FW، FW-OFK -INFINITECAP ، FW-OFK - CAPACITATED براي شبکه سوفالز تک مبدايي ................................................................ .................................. 111 جکدول 39- جريان هاي بدسکککت آمده از سکککه الگوريتم FW، FW-OFK -INFINITECAP ، FW-OFK - CAPACITATED براي شبکه سوفالز دو مبدايي ................................................................ .................................... 111 جدول 41- هزينه سککفر هاي بدسککت آمده از سککه الگوريتم FW، FW-OFK -INFINITECAP ، FW-OFK - CAPACITATED براي شبکه سوفالز دو مبدايي ................................................................ .................................... 115 جدول 41- مشخصات كمان هاي شبکه سوفالز تک مبدايي ................................................................ ....................... 119 جدول 42-عرضه و تقاضا در مبدا-مقصدها ي شبکه سوفالز تک مبدايي ................................................................ .. 123 جدول 43- مشخصات كمان هاي شبکه سوفالز دو مبدايي ................................................................ ......................... 124 جدول 44-عرضه و تقاضا در مبدا اول شبکه سوفالز دو مبدايي ................................................................ ................. 121 جدول 45- عرضه و تقاضا در مبدا دوم شبکه سوفالز دو مبدايي ................................................................ ............... 129 ز چكیده كاربرد وسيع مدل تخصيص ترافيک در ارزيابي و انتخاب راه كارهاي مناسب براي بهبود عملکرد شبکه حمل ونقل نيازمند واقعي تر شدن هرچه بيشتر نتايج حاصل از آن است. يکي از عوامل واقعي تر شدن نتايج اين مدل ،مستقل از روش حل آن،در نظر گرفتن محدوديت ظرفيت كمان ها است. در مسائل تخصيص ترافيک، روش هايي مانند الگوريتم فرانک-ولف كارايي زيادي دارند ولي در نظر نگرفتن ظرفيت براي كمان ها در اين روش ها باعث غير دقيق شدن نتايج بدست آمده مي شود. در اين نوشتار الگوريتم فرانک-ولف با اعمال محدوديت ظرفيت اصالح شده است با اين تفاوت كه جهت حركت توسط الگوريتم Out Of Kilter به دست مي آيد. همچنين نتايج كاربرد اين روش براي دو شبکه با زمان سفر ثابت و شبکه هرن و سوفالز با زمان سفر وابسته به جريان از نقطه نظر جريان در كمان و هزينه هاي سفر ارائه شده است كلمات كليدي:تخصيص ترافيک، محدوديت ظرفيت، الگوريتم فرانک-ولف 1 1 فصل اول مقدمه 2 1-1- مقدمه سکيسکتم حمل و نقل كاال و مسافر به عنوان يکي از زيرساخت هاي مهم شهري نقش بسزايي در كيفيت زندگي انسان ها دارد. از طرفي، افزايش روز افزون تقاضاي سفر با وسايل نقليه باعث افزايش مسايل ناشي از حمل و نقل از جمله آلودگي و تصادفات خواهد شد. از اين رو انجام مطالعات حمل و نقل مستمر براي اصکالح يا جايگزيني سکيسکتم هاي حمل ونقل شکهري توصيه مي شود. بخش عمده اين مطالعات شامل مدلسکازي عملکرد ترافيکي شبکه حمل و نقل در هر وضعيت از تقاضاي سفر و تحت هر سيستم حمل و نقل پيشنهادي است. براي ارزيابي عملکرد يک شبکه بايد بتوان ميزان جريان عبوري در معابر آن را پيش بيني و متناسککب با آن معيارهاي عملکردي را محاسککبه نمود. به طور كلي، براي هر وضککعيت مشککخص تقاضکاي سکفر (مشاهده يا برآورد شده ) ارزيابي هر وضعيت شبکه حمل و نقل(يا هر نوع سيستم حمل و نقل) شامل دو مرحله زير است: 1- پيش بيني الگوي جريان در شبکه 2- استفاده از الگوي جريان براي تخمين معيارهاي عملکردي شبکه در مرحله اول با استفاده از يک سري فرضيات در مورد چگونگي انتخاب مسير حركت توسط استفاده كنندگان از شبکه، جريان در كمان هاي شبکه تعيين ميشود. در مرحله دوم با استفاده از الگوي جريان، معيارهاي عملکردي شبکه مثل شلوغي، سطح سرويس، نشر آلودگي محاسبه مي شوند. سپس، با مقايسه معيارهاي حاصل از سيستم هاي پيشنهادي و با استفاده از روش هاي اقتصاد مهندسي، راه حل هايي مناسب براي مشکالت سيستم تعيين ميشوند. جريان در كمانهاي شبکه با حل يک مدل رياضي به نام "مسئله تخصيص ترافيک " حاصل مي شوند. با دانستن مقدار تقاضاي سفر بين زوج هاي مبدا- مقصد در شبکه، مسئله تخصيص ترافيک عبارت از چگونگي توزيع تقاضا بين مسيرهاي موجود بين هر زوج مبدا - مقصد است. آنچه كه در اين پژوهش مورد نظر قرار گرفته شامل مقايسه روش هاي موجود تخصيص ترافيک و ارايه روشي كارا براي شبکه هاي بزرگ مقياس است. روش هاي مختلفي براي حل مسئله تخصيص ترافيک وجود دارد كه به طور كلي مي توان آنها را به سه دسته الگوريتم هاي بر پايه كمان، بر پايه مسير و بر پايه مبدا تقسيم كرد. الگوريتم فرانک-ولف از معروک ترين الگوريتم هاي بر پايه كمان است كه به خاطر مصرک حافظه بسيار كم براي بيش از پنج دهه كاربردي ترين الگوريتم تخصيص ترافيک بوده است. اين الگوريتم ،علي رغم مزاياي زيادي كه دارد، ظرفيت محدودي براي هركمان در نظر نمي گيرد و آن را نا محدود فرض ميکند. اين فرض باعث مي شود كه جواب هاي به دست آمده از اين الگوريتم دقيق و نزديک به واقعيت نباشد. با پيشرفت رايانه ها در دو دهه اخير، الگوريتم هاي بر پايه مسير بيشتر مورد توجه قرار گرفته و توانسته اند با نرخ همگرايي باال به دقتهايي در جواب مسئله دست پيدا كنند كه الگوريتم فرانک -ولف هرگز توانايي رسيدن به آنها را نداشته است. در دهه اخير نيز الگوريتم هاي بر پايه مبدا كه به حافظه كمتري نسبت به الگوريتم هاي بر پايه 3 مسير نياز دارند و از نرخ همگرايي نسبتاً خوبي نيز برخوردار ميباشند به ادبيات تخصيص ترافيک معرفي شده اند حافظه قابل دسترس در رايانه هاي امروزي به حدي زياد است كه مي توان با استفاده از آنها الگوريتم هاي با حافظه مصرفي زياد را برا ي شبکه هاي بزرگ مقياس نيز اجرا كرد. به همين دليل كاهش حافظه مصرفي الگوريتم ها جزو اهداک اين پژوهش نمي باشد هدک اين پژوهش اين است كه با درنظر گرفتن ظرفيت محدود براي كمان ها در الگوريتم فرانک-ولف، تاثير آن را درجواب هاي مسئله را بدست آورد. 1-2- اهمیت مسأله دقت نتايج الگوريتم هاي تخصکيص ترافيک تاثير بسکزايي در پيش بيني و كنترل ترافيک در شبکه هاي حمل و نقلي دارد. واضکح اسکت كه كمان ها در يک شبکه حمل و نقلي داراي ظرفيت محدودي هستند ودر نظر گرفتن اين ظرفيت ها باعث افزايش دقت نتايج بدست آمده مي شود و مي توان با استفاده از اين نتايج تخمين بهتري از شرايط بدست آورد 1-3- مروری بر فصول اين پايان نامه از پنج فصل تشکيل شده است كه پس از اين فصل، چهار فصل آينده بدين شرح مي باشند. فصل دوم نگرش هاي گوناگوني كه درب اره مسئله تخصيص ترافيک وجود داشته و همچنين روش هاي مختلفي كه محققين براي حل اين مسئله بکار برده اند بيان مي شود. در اين فصل گام هاي مربوط به الگوريتم هاي فرانک-ولف و همچنين الگوريتم هاي تخصيص ترافيک با محدوديت ظر فيت تشريح مي شوند. در فصل سوم، الگوريتم هاي پيدا كردن كوتاه ترين مسير بين دوگره با ذكر مثال تشريح و مقايسه شده و الگوريتم Out of Kilter نيز با ذكر مثالي تبيين، نتايج حاصل از اجراي اين الگوريتم و الگوريتم فرانک-ولف بر روي دو شبکه با زمان سفر ثابت و همچنين مقايسه زمان حل اعمال الگوريتم هاي كوتاه ترين مسير بل و دايجسترا نشان داده مي شود. در فصل چهارم ، ابتدا به توضيح روش هاي به كار برده شده براي كدنويسي الگوريتم OFK پرداخته و سپسالگوريتم هاي Out of Kilter و فرانک-ولف براي شبکه هاي هرن و سوفالز با زمان سفرهاي وابسته به جريان اعمال و نتايج بدست آمده از آنها مقايسه مي شود. فصل پنجم نيز به خالصه اي از نتايج حاصل از اين پژوهش و پيشنهاداتي براي مطالعات آينده اختصاص داده شده است 2 2 فصل دوم ادبیات مساله تخصیص ترافیک 3 2-1- مقدمه در اين فصکل نخسکت به تشريح مسئله تخصيص ترافيک 1 (TAP) و مفاهيم اوليه آن و مرور مقاالت و تحقيقات انجام شکده پيرامون مسکئله تخصکيص ترافيک مي پردازيم. سکپس مدل بهينه سازي تخصيص ترافيک در حالت ظرفيت نامحدود كمان ها ارائه و چند الگوريتم سکککاده ولي كاربردي براي حل آن بيان مي شود. در انتها مدل تخصيص ترافيک با در نظر گرفتن محدوديت ظرفيت كمان ها بيان شده و يکي از الگوريتم ها حل آن ارائه مي شود. 2-2- مروری برمدل های تخصیص ترافیک مطابق آشکتياني ]1 [يکي از مناسکب ترين معيارها به منظور ارزيابي عملکرد ترافيکي كمان ها در شبکه هاي حمل و نقل، زمان سکفر كمان ها مي باشد. زمان سفر هر كمان در حالت كلي تابعي از حجم جريان در آن كمان و نيز حجم ديگر كمان هاي شکبکه در اطراک كمان اسکت. در مسککئله تخصکيص ترافيک به منظور ساده سازي حل آن اغلب فرض ميشود كه زمان سفر هر كمان تنها تابعي از جريان در همان كمان بوده و به جريان در ديگر كمان ها وابسکته نيسککت . همچنين زمان سککفر هر مسککير از مجموع زمان سککفر كمان هاي واقع در همان مسککير به دسککت مي آيد. واضککح اسککت كه با افزايش جريان در يک كمان ابتدا سکرعت عملکردي آن به طور ماليمي كاهش يافته و سکپس با افزايش تراكم وسکايل نقليه و ايجاد صف، كاهش سکرعت شدت يافته و زمان سفر به سرعت افزايش مي يابد. در عمل فرض مي شود كه تابع زمان سکفر-حجم تابعي پيوسکته، مشتق پذير، غير منفي و صعودي از جريان در كمان است. توابع زمان سفر- حجم متفاوتي براي شکرايط مختلف، توسکط پژوهشکگران ارايه شکده است. توابع زمان سفر- حجم مورد استفاده در اين پژوهش همان تابع BPR است. در يک سکککيسکککتم حمل ونقل مثل يک بازار رقابتي دو گروه وجود دارند . گروه اول اسکککتفاده ك نندگان (رانندگان ) كه رفتارشان با تابع تقاضا معرفي مي شود و گروه دوم عرضه كنندگان(توليدكنندگان س يستم) كه رفتارشان با تابع عرضه يا كارايي معرفي مي شود. سکيسکتم حمل ونقل نوعي خدمت است كه توسط عرضه كنندگان آن ارائه مي گردد. اين سيستم شامل انواع ها راه ها ، طريقه ي سفر و غيره مي شود كه جزئي از شبکه محسوب مي گردند. ميزان كارايي اين سکيستم توسط سطح سرويس 2 اندازه گيري مي شود كه مي تواند شامل زمان و هزينه سفر، ايمني سفر 1 Traffic Assignment Problem 2 Level of Service 4 و غيره باشکد[1 .] تابع تقاضکا نشکان مي دهد كه با تغييرات سکطح سرويس، تقاضا چگونه كم يا زياد مي شکود. جريان توزيع شکده در شکبکه پس از رسکيدن سکيستم حمل و نقل به تعادل بين كارايي و تقاضا، جريان تعادلي ناميده مي شککود . مطابق آشککتياني [1] مسککئله تخصککيص ترافيک تعادلي، نوعي مسککئله تخصيص ترافيک براي تعيين جريان تعادلي در شبکه است. مسئله تخصيص ترافيک تعادلي بر پايه قانون تعادل اسکتفاده كننده1 (UE) اسکتوار مي باشکد و طبق اين قانون در شرايط تعادل هيچ راننده اي نمي تواند با تغيير يک جانبي2 مسير خود، زمان سفرش را كاهشدهد. [ براساس شفي2 ] در اين قانون فرض مي شکود كه اوالً تمام رانندگان اطالع دقيقي از همه مسکيرهاي موجود و زمان سفرهاي آنها دارند، دوماً الگوي جريان در شکککبکه در بازه زماني مورد نظر ثابت اسکککت . فرض اول يعني اطالع دقيق رانندگان از مسکيرها، مي تواند دسکت كم براي همه رانندگان صکادق نباشک د. بر اين اساس مدل هاي تعادلي به مدل هاي قطعي3 و تصکادفي4 تقسکيم مي شکوند. در مدل قطعي اطالعات رانندگان از مسيرها يکسان، ولي در مدل تصککادفي اين اطالعات ناقص و متفاوت هسککتند. به عالوه، هريک از اين دو مدل، اگر تقاضککا سککفر با زمان تغيير كند مدل پويا5 و اگر تقاضا نسبت به زمان ثابت باشد مدل ايستا1 ناميده مي شوند . مدلهاي تخصيص ترافيک تعادلي از نوع ايستا و قطعي، از كاربردي ترين مدل هاي تخصيص ترافيک به خصککوص در برنامه ريزي هاي بلند مدت محسککوب مي شککوند. در ادامه اين پايان نامه، منظور از مدل تخصکيص ترافيک همان مدل تخصکيص ترافيک تعادلي ايستا و قطعي خواهد بود. فرضياتي در اين مدل وجککود دارنککد . در فککرض اول نککرخ تککقککاضککککا در دوره زمککانککي مککور د نککظککر ثککابککت اسککککت، در فرض دوم رانندگان اطالعات دقيقي از مسيرها دارند و در فرض سوم هر راننده سعي ميکند زمان سفر خود را كاهش دهد، كه به معني بر قراري تعادل استفاده است. واردراپ[4 ]براي اولين بار به وضعيت تعادل در شبکه اشاره كرد كه بعد ها به اصل اول واردراپ معروک شکد. بر اسکاس اين اصل، در شرايط تعادل، زمان سفر مسيرهاي استفاده شده با هم برابر بوده و كمتر يا 1 User Equilibrium 2 Unilaterally 3 Deterministic 4 stochastic 5 Dynamic 6 Static 5 مسکاوي با زمان سکفر مسيرهاي استفاده نشده هستند. اين اصل، قانون تعادل ترافيکي 1 نيز نام دارد. در اينجا از دو نام استفاده كننده و ترافيکي براي مفهوم تعادل استفاده شده است تا بتوان تفاوت بين آنها را نشکان داد. در ادبيات تخصکيص ترافيک، تعادل اسکتفاده كننده و ترافيکي با فرض آنکه جريان پيوسته و تابع زمان- سفر غير نزولي و پيوسته باشد، يکسان در نظر گرفته مي شون[د1]. در اين پژوهش نيز اين دو مفهوم يکسان در نظر گرفته شده اند. مسکک ئله تخصککيص ترافيک براي اولين بار در دهه چهل ميالدي مطرح شککده و اولين روش براي حل آن امروزه به عنوان روش همه يا هيچ 2 شناخته مي شود. اين روش بر اين فرض غير واقعي استوار بوده است كه زمان سفر هر كمان مستقل از جريان در شبکه مي باشد. پس از پيشرفت هاي حاصله درالگور يتم هاي كوتاه ترين مسکير و معرفي مسکئله تعادل اسکتفاده كننده توسط واردراپ، تحول بزرگي در فرمول بندي مسکئله تخصکيص ترافيک به وجود آمد[3 .] امروزه الگوريتمهاي حل اين مسکئله را ميتوان به سه گروه اصلي تقسيم كرد: 1 - الگوريتمهايبر پايه كمان 3 2 - الگوريتمهاي بر پايه مسير4 3 - الگوريتمهاي بر پايه مبدا 5 عالوه بر طبقه بندي باال، روش هاي ابتکاري كه بر پايه فرمول بندي رياضي نمي باشند را نيز ميتوان به عنوان دسته اي جدا به حساب آورد. مسئله تخصيص ترافيک با ظرفيت محدود1 (CTAP) همان مسئله تخصيص ترافيک استاندارد است با اين تفاوت كه محدوديت هاي ظرفيت كمان به آن اضافه شده است.به طوركلي، روش هاي حل مسئله تخصيص ترافيک با ظرفيت محدود به دو دسته كلي تقسيم مي شو د. دسته اول الگوريتم هايي كه از 1 Traffic Equilibrium 2 All or Nothing 3 Link -Based Algorithms 4 Path-Based Algorithms 5 Origin -Based Algorith ms Capacitated Traffic Assignment Problem 6 1 توابع زمان سفر مجانبي1 .استفاده مي كنند دسته دوم الگوريتم هايي كه مسئله اصلي را به يک سلسله مسائل تخصيص ترافيک بدون محدوديت همراه با استراتژي جريمه/ همزاد2 .تبديل مي كنند اين دو اسککتراتژي ميتواند به طور هم زمان با جداگانه اعمال شککوند. اولين اسککتراتژي رفتار ذاتي ترافيک است. يعني هر استفاده كننده از راه سعي بر حداقل كردن زمان سفر خود دارد و بنابراين به عنوان قانون تعادل شناخته مي شود. اگر بردار توابعي كه كه زمان سفر در كمان هاي شبکه را توضيح مي دهند قابل انتگرال گيري و يکنواخت باشکند، قانون بهينه سکازي واردراپ موجب به يک مسککئله رياضي محدب مي شود. توابع زمان سفر غيرقابل انتگرال گيري ماتريس ژاكوبين نامتقارن دارند و در نتيجه مسئله تخصيص ترافيک به دست آمده به بي نهايت ميل مي كند. پاول[21 ]و هسککتنز [21 ]به طور جداگانه از روش ضککرايب الگرانژ تقويت شککده 3 (ALM) براي حل مسکائل برنامه ريزي غيرخطي اسکتفاده كردند. ميلر و همکاران [43] همچنين يک روش توليد ستون4 با در نظر گرفتن هزينه سکفر (زمان سفر) ثابت ارائه كردند كه در آن مسائل اصلي با محدوديت ظرفيت با اسککتفاده از تکنيک تعميم يافته كران بندي باال5 حل شککده اند. دگنزو[21[]29 ]اولين كسککي بود كه محدوديت هاي ظرفيت كمان را با استفاده از توابع زمان سفر مجانبي در نظر گرفت و آن را براي شبک ه اي با 3 گره و5 .كمان اجرا كرد اين روش همواره جواب هاي امکان پذير دارد ولي مشکالتي نيز دارد، كه نتايج تحقيقات انجام شکده توسکط بويس و همکاران[31 ]نشکان مي دهد كه استفاده از اين توابع ممکن اسکت هزينه سفر را به طور غير واقعي زياد نشان دهد و باعث مشکالت عددي در نزديکي ظرفيت كمان شکود. وندراسترايتن و تيلکويين [31 ] با استفاده ازروش ضرايب الگرانژ تقويت شده و همچنين استفاده از روش غير خطي Out of Kilter براي زيرمسائل 1 بدون محدوديت، مسائل تک-كااليي را حل كردند. Asymptotical function 1 penalty/dual strategy 2 3 Augmented Lagrange Multipliers 4 Column Generation A pproach 5 Genera lized Upper Bounding Technique 6 Sub-problems 1 مينوكس [41] از روش شککاخه و كران 1 با اسککتفاده از آزادسککازي الگرانژي 2 مسککئله برنامه نويسککي عدد صکحيح وآزادسکازي برنامه نويسکي خطي3 براي حل شبکه با محدوديت و هزينه ثابت استفاده كرد و اين الگوريتم را براي شبکه اي با 5 گره و1 .كمان اجرا كرد خانگ و [ فوجيوارا41 ]از آزاد سازي الگرانژي و بهينه سازي زير گراديان ها4 براي به دست آوردن كران پايين تر و مقياس گذاري ابتکاري براي به دست آوردن يک كران باالتر اسککتفاده كردند. جاياكريشککان و همکاران [32] و همچنين چن و لي [22 ]نشککان دادند كه مسکائل با مقياس بزرگ مي توانند با استفاده از الگوريتم هاي بر مبناي مسير حل شوند. براي اولين بار هرن [33] مسکئله تخصيص ترافيک با ظرفيت محدود را با استفاده از تبديل آن به يک سلسله زير مسائل تخصيص ترافيک بدون محدوديت ظرفيت حل كرد. او از يک تابع جريمه خارجي5 براي تبديل مسائل با محدوديت ظرفيت به مسائل بدون محدوديت ظرفيت استفاده كرد و زير مسائل را با استفاده از الگوريتم فرانک-ولف حل كرد. او اين روش را براي شکبکه اي با 9 گره و11 كمان اجرا كرد كه به شبکه هرن معروک شد. اينوي [42] روش مشابه را با استفاده از توابع جريمه كه در آن هزينه سفر به بي نهايت ميل مي كنند ارائه داد و اين روش را توابع جريمه داخلي ناميد1 و مانند هرن با اسککتفاده از الگوريتم فرانک-ولف زيرمسائل را حل كرد. يانگ و ياگر [44] نتايج اعمال اين روش را با در نظر گرفتن محدوديت ظرفيت ارائه دادند و آن را بر روي شبکه اي با 9 كمان و1 .گره اعمال كردندهرن و ريبرا [34 ]از روش ALM براي حل مسکئله تخصکيص ترافيک با محدويت ظرفيت استفاده كردند. آن ها الگوريتم فرانک- ولف را براي حل زير مسائل به كار بردن و نتايج را براي تعدادي شبکه كوچک ارائه كردند. آنها دو نوع از توابع الگرانژ را در نظر گرفتند .الرسککون وپاتريکسککون [35] روش ALM ا براي حل شککبکه سککوفالز پيشککنهاد و ارزيابي كردند. آنها در اين روش، روش توابع جريمه خارجي معمول با رويه همزاد الگرانژ1 تركيب شکده كردند و نتايج به دسکت آمده از اعمال روش ALM را براي شبکه هاي كوچک تا متوسط Bound-and- Branch 1 2 Lagrangean R elaxations 3 Linear Programming R elaxations 4 subgradients 5 Exterior Penalty F unction 6 Inner Penalty F unctions 7 Lagrangean Dual S chemes 1 ارائه كردند. در اين روش زيرمسائل با استفاده از الگوريتم تجزيه غيرتجمعي ساده شده1 حل شده اند. آنها از روش توليد سککتون براي حل مسککائل با محدوديت هاي خطي اسککتفاده كردند. براي بهبود عملکرد محاسککباتي،آنها از رويه تثبيت همزاد2اسککتفاده كردند. اين روش نرخ خطي همگرايي را نشککان مي دهد. بارگرا [31] روش جديدي براي حل زيرمسککائل بدون محدوديت ظرفيت ارائه داد و آن را روش مبتني بر مبدا3 (OB) ناميد. در اين روش تمام محاسککبات تحت يک روند مکان نگر بر روي شکبکه سککوفالز اعمال شده است. همان طور كه در[31] نشان داده شده است اين روش زمان محاسبات را به طور قابل مالحظه اي كاهش مي دهد يکي از مزاياي اصلي روش OB اين است كه جواب هاي به دست آمده تفسير جريان ساده اي دارند و مقدار حافظه مورد نياز متوسط است[31] . پرشکار و تولدو [31] از روش IPF براي حل كردن زير مسککائل بدون محدوديت ظرفيت اسککتفاده كردند و نتايج را با الگوريتم هاي يانگ و ياگر[44] مقايسکه كردند. جواب هاي سکلسکله زيرمسائل هنگامي به جواب بهينه مسئله اصلي همگرا مي شوند كه عبارت هاي جريمه به صفر ميل كنند. اين الگوريتم در مقايسه با الگوريتم يانگ و ياگر[44 ]سريع تر و با رفتار پايدارتري همگرا مي شود و بر روي شبکه اي با 11 گره و41 .كمان اعمال شده استني و همکاران [93] روشIPF را براي شککبکه هاي هرن، سککوفالز و آ ناهايم اعمال كردند و از روش تصککوير گراديان4 (GP) براي حل زيرمسائل بدون محدوديت استفاده كردند. آنها روشIPF را با الگوريتم ALM مقايسه كردند و نتيجه ها نشان مي دهد كهIPF در به تعادل رساندن زير مسائل كارايي كمتري از ALM دارد اما ALM نسکبت به سکرعت همگرايي ، حسکاس تر از IPF است. هردو الگوريتم IPF و ALM نتايج مشکابه و واقعي قابل قبولي را به دست آوردند. نگويان و همکاران [41 ]فرض كردند كه وضعيت سيستم وابسکته به جريان است و رفتار استفاده كننده بيشتر به وسيله استراتژي هاي سفر به او تحميل مي شود تا انتخاب مسکير. تعادل اسکتراتژيک زماني به دست مي آيد كه تمام استفاده كننده ها از استراتژي هاي حداقل كردن تاخير مورد انتظار اسککتفاده كنند. در اين پژوهش براي حل كردن زير مسککائل از الگوريتم فرانک-ولف استفاده شده است و اين الگوريتم بر روي شبکه اي با 5 گرهو 1 كماناجرا شده است. كورآ وهمکاران[41] تعادل اسککتفاده كننده در شککبکه هاي با ظرفيت را با حاالت كلي توابع تاخير معرفي و آناليز كردند. آن ها فرض كردند كه توابع تاخير توابعي پيوسککته، غير منفي و غير كاهشککي هسککتن د و از ظرفيت كمان ها به عنوان محدوديت هاي اضافي استفاده كردند. نتايج آن ها يک روش استقرايي براي به 1 Disaggregate Simpli cial Decomposition Algorithm 2 Dual Stabilization Scheme 3 Origin -Based Method 4 Gradient P rojection 9 كار بردن تعادل اسکتفاده كننده در مدل هاي تخصککيص ترافيک فراهم كرد. شککهپر و همکاران [45] يک الگوريتم تکراري براي حل TAP با محدويت خطي ارائه دادند. اين الگوريتم بر مبناي اضککافه كردن يک تابع جريمه ديناميک1 (DPF) براي زمان سفر كمان ها است و نتايج آن همگرايي مناسب اين روش را نشان مي دهد. DPF با كارايي بيشترينسبت به روش هايIPF و ALM به نتايج ممکن توابع بکمن دسکت مي يابد چون تعداد تکرارهاي روش DPF همواره از دو روش ذكر شده كمتر است. اين الگوريتم بر روي شکبکه هاي هرن، سکوفالز و آناهايم اعمال شده است. شليلوند و همکاران[41 ] الگوريتمي را ارائه دادند كه مسئله اصلي را با يک سلسله TAP تقريب مي زند. اين زير مسائل با الگوريتم هاي OB كه در آن اصکالحاتي انجام گرفته است حل مي شوند. اين الگوريتم اصالح شده، الگوريتم مبتني بر مبدا توسعه يافته2 (EOB) نام دارد و بر روي شکبکه هاي كوچک تا بزرگ اعمال شکده اسکت. روش پيشکنهاد شده تفسککير جريان مسککير سککاده اي دارد و براي شککبکه هاي بزرگ كارا اسککت و همچنين باعث كاهش زمان محاسبه و مقدار حافظه مورد نياز مي شود. 2-3- مدل بهینه سازی تخصیص ترافیک همان طور كه اشاره شد اولين بار واردراپ [4] وضعيت تعادل در شبکه را بررس ي كرد كه بعدها با نام او با عنوان اصل واردراپ معروک شد. بر اساس آن، زمان سفر مسيرهاي استفاده شده در شرايط تعادل با هم برابر بوده و كمتر يا مساوي زمان سفر مسيرهاي استفاده نشده است. اصولي كه عملکرد رانندگان را در انتخاب مسير نشان مي دهند غالباً بر مبناي موارد اشاره شده، بيان مي شوند. در سال 1952 واردراپ اين دو اصل اساسي را به نامهاي اصول اول و دوم به شرح زير بيان نمود. اصل اول واردراپ به عنوان يک اصل منطقي و ساده براي تشريح نحوه توزيع تقاضا بين مسيرهاي مختلف در شرايط تراكم پذيرفته شده است. مطابق اين اصل، در شرايط تعادل استفاده كننده هيچ مسافري نمي تواند با تغيير مسير، هزينه سفر خود (كه مي تواند زمان سفر او باشد) را كاهش دهد. جريان ترافيکي كه اين اصل را ارضا كند غالباً تحت عنوان جريان تعادل استفاده كننده يا جريان تعادلي ناميده مي شود. زيرا هر راننده بهترين مسير را انتخاب كرده است. از اصل اول واردراپ به سادگي مي توان نتيجه گرفت كه در شرايط تعادل استفادهكننده در شبکه هاي بدون محدوديت ظرفيت، زمان سفر مسيرهاي استفاده شده بين هر زوج مبدا مقصد با هم برابر و كمتر يا مساوي با زمان سفر مسيرهاي استفاده نشده هستند. اين مساله بهينه سازي كه مدل بکمن ناميده مي شود به شرح رابطه 2-1 .است 1 Dynamic Penalty F unction 2 Extended Origin -Based algorithm 11 (2-1 ) 0 ( min ( ) ( ) .. , 0 , , ax a a rs rs k k rs k rs rs a k ak rkz x t d st f q r s f r s k x f a A         ,)s          در اين مدل ax جريان در كمان a، ()atx تابع زمان سفر كمان a ، rs kf جريان در مسير kبراي زوج مبدا مقصککد rs و rsq تقاضککاي بين زوج مبدا مقصککد rs مي باشککد. همچنين پارامتر  rs ak برابر يک اسککت اگر كمان a روي مسکير k مربوط به زوج مبدا مقصد rs واقع باشد و در غير اين صورت برابر برابر صفر است. در مدل بکمن (2-2 ) تابع هدک عبارت اسکت از مجموع انتگرال هاي توابع زمان سفر كمان ها. اين تابع [ هدک همان گونه كه شفي2 بيان مي كند هيچ تعبير اقتصادي يا رفتاري ندارد. در اين مدل محدوديت] اول بيان مي دارد كه مجموع جريان عبوري از مسکککير هاي مربوط به يک زوج مبدا مقصکککد بايسکککتي با تقاضاي مربوط به آن زوج برابر باشد. محدوديت دوم به دليل اطمينان از منطقي بودن جواب نهايي مساله بيان شکده و محدوديت سوم نشان دهنده رابطه بين جريان در مسير k مربوط به زوج مبدا مقصد rs و جريان در كمان a مي باشد. 2-3-1- روش های نزول روش هاي نزول براي مينيمم سککازي توابع محدب غيرخطي چندمتغيره به كار مي روند. اين الگوريتم ها از جريکان در هر كمکان بکه دسکککت آمکده در هر مرحلکه 1 ( ( ,..., ))n n n I x x x جريکان در مرحلکه بعد 1 1 1 1 ( ( ,..., ))n n n I x x x   را بدست مي آورند. مرحله اصککلي روش هاي نزول محاسککبه 1nx از nx اسککت. اين مرحله را مي توان به صککورت اسککتاندارد مطابق رابطه 2-2 .بيان كرد (2-2) 1n n n n x x d  كه در اين رابطهnd بردار نزول و n كميتي غيرمنفي به نام جهت حركت است. اين رابطه بيان مي كند كه در نقطه nx ، جهتي به نام nd وجود دارد كه تابع در آن نزولي است. در رابطه2-2 ، هر عضو از بردار متغير به روزرساني مي شود، كه به صورت رابطه 2-3 :بيان مي شود 11 (2-3) فرمول هاي بيان شده در روابط2-2 و2-3 براي تمام روش هاي نزول براي مينيمم سازي بدون محدوديت استفاده مي شود. روش هاي نزول عمدتا در قواعدي كه براي يافتن جهت نزول است با هم تفاوت دارند. اندازه حركت معموال طوري انتخاب مي شود كه تابع هدک را در جهت نزول مينيمم كند. اگر تابع هدک داراي محدوديت باشد، الگوريتم هاي مينيمم سازي بايد طوري اصالح شوند كه جهت مورد نظر باتوجه به قواعد موردنظر تغيير كند. به طور مشابه، اگر اندازه حركت طوري باشد كه تابع به خارج ار محدوده امکان پذير وارد شود، بايد طوري اصالح شود كه امکان پذيري نقض شود. 2-3-2- الگوریتم فرانک-ولف فهم آسان، سادگي در اجرا، حافظه مصرفي كم و كارايي مناسب در تکرارهاي اوليه باعث محبوبيت فراوان الگوريتم فرانک-ولف در ميان محققان شده است، به طوري كه در نرم افزارهاي تخصصي تخصيص ترافيک از جمله EMME2 [1 ] .از اين روش استفاده شده است براي به دست آوردن جهت، ابتدا مسئله محدب را در نظر بگيريم. (2-4) min z(x) .. j Jij i j ist h x b     در تکرارn ام، جواب راnx در نظر ميگيريم. بيشتر روش هاي يافتن جهات امکان پذير از اطالعات شيب تابع هدک در همسايگي nx براي تعيين جهات نزول استفاده ميکند. بنابراين، جهت نزول براساس عکس جهت گراديان يا جهت تندترين شيب نزول امکان پذير تعيين مي شود. معيار انتخاب جهات براساس ضرب نرخ نرول در همسايگيnx در جهت داده شده و طول منطقه امکان پذير در آن جهت مي باشد. اين حاصلضرب كه به عنوان افت شناخته مي شود، حد باالي كاهش در تابع هدک مي باشد. اين الگوريتم از جهت حركت استفاده ميکند تا مقدار افت را ماكزيمم كند. براي بدست آوردن جهت نزول، الگوريتم از كل منطقه امکان پذير براي بدست آوردن يک جواب كمکي 1 ( ( ,....,.... ))n n n I y y y طوري استفاده ميکند كه جهت ازnx بهny بيشترين مقدار افت را فراهم كند. جهت ازnx به هر جواب ممکن(y) برد)nx -(y (يا بردار واحد () || ||n nyx yx  ( است. شيب )nZ(x درجهت)nx-(y با استفاده از تصويرسازي عکسگراديان ()nzx كه به صورت رابطه 2-5 .بيان ميشود، به دست مي آيد (2-5) ()( ). || ||nT n nyxzxyx 1 i =1,2, ...., In n n i i n ix x d    12 مقدار افت در تابع هدک در جهت)nx-(y با استفاده از ضربشيب در فاصله بين nx وy ،||nx-y|| ، به دست مي آيد و مطابق رابطه 2-1 .محاسبه ميشود (2-1) رابطه2-1 بايد با توجه به امکان پذيري y مينيمم شود. مي توان اين رابطه را در(1-) ضرب و آن را مينيمم كرد كه يه صورت رابطه 2-1 بدست مي آيد. (2-1) ()min z(x ).( ) ( ) .. j Jn n n n ii i i ij i j izxy x y xx st h x b          جواب اين مسئله n y و جهت نزول بردار متصل كنندهnx بهn y ،n x-n=ynd ، است. پيدا كردن جهت نزول شامل مينيمم سازي برنامه خطي ذكر شده در رابطه 2-1 مي باشد. جهت نزول را مي توان با درنظر گرفتن الگوريتم فرانک-ولف به عنوان يک روش تقريب خطي درنظر گرفت. اين روش براساس يافتن جهت نزول با استفاده از مينيمم سازي تقريب خطي تابع هدک در نقطه جواب كنوني مي باشد. مينيمم سازي اين تابع خطي شده با محدوديت هاي خطي يک مسئله برنامه نويسي خطي مي باشد كه جواب هاي آن در گوشه هاي منطقه امکان پذير است. خطي كه نقاط جواب كنوني nx را به جوابمسئله خطي شده ny متصل مي كند جهت جستجو مي باشد. براي اثبات اين مسئله، ()n LZy را تقريب خطي ار مقدار تابع هدک در نقطهy .در نظر ميگيريم تقريب خطي را مي توان به صورت رابطه 2-1 .بيان كرد (2-1) ( ) ( ) ( ).( )n n n n T LZ y z x z x y x   تابع خطي y بايد باتوجه به م حدوديت هاي تابع اصلي مينيمم شود كه به صورت رابطه 2-9 مي توان آن را بيان كرد. (2-9) min ( ) ( ) ( ).( ) .. n n n n T L ij i j iZ y z x z x y x st h y b j J       در نقطهnx=x مقدار تابع هدک ثابت است، پس مي توان مقدار ()nzx را از رابطه 2-9 حذک كرد. رابطه باقيمانده همان رابطه 2-1 مي باشد و جواب هاي آن مي توانند در پيدا كردن جهت نزول براي الگوريتم فرانک-ولف استفاده شوند. تابع هدک مسئله خطي شده را مي توان ساده سازي كرد. مقدار ()nzx در ( ). ( )n n Tz x y x  13 نقطهnx ثابت مي باشد، پس مي توان عبارت ( ).( )n n Tz x x را از رابطه 2-9 حذک كرد و رابطه2-11 .را بدست آورد (2-11) جواب هاي اين مسئله 1 ( ( ,....,.... ))n n n I y y y براي بدست آوردن جهتت نزول استفاده مي شوند. اندازه حركت در جهت nd برابر با فاصله با نقطه اي است كه Z(x) را مينيمم مي كند. الگوريتمفرانک-ولف به گام ويژه اي براي بدست آوردن اندازه گام بهينه نياز ندارد. جواب جديد n+1 x بايد بينnx وny .قرار گيرد به عبارت ديگر، جستجو براي جهت نزول به طور اتوماتيک مرزي براي جستجوي خطي با درنظر گرفتن همه محدوديت ها ايجاد مي كند. چون بازه جستجو مشخص است، تمام روش هاي كاهش بازه جستجو براي مينيمم سازي z(x) در جهت نزول ، كه براي حل رابطه2-11 .مي باشد، مناسب مي باشند (2-11) min z[x + (y -x )] 01n n n   زماني كه جواب بهينه جستجوي خطي ()n بدست آمد، جواب بعدي را ميتوان با استفاده از رابطه 2-12 .بدست آورد (2-12) 1()n n n n n x x y x    حال براي آنکه رابطه اثبات شده را براي شبکههاي حمل و نقلي به كار ببريم، تابع هدک قانون تعادل استفاده كننده را درنظر مي گيريم. (2-13) 0min z(x)= ( ) .. r,s 0 , ,ax a a rs k rs k rs kt w dw st fq f k r s         كهax جريان در كمان a و krs f جريان در مسيرk متصل كننده مبداr و مقصدs است. حال با توجه به رابطه 2-11 :داريم (2-14) ()min z ( ) ( ).n n n T a a azxy z x y yx  ()min ( ) ( ). ( ) .. n n n T Li i i ij i j izxZ y z x y yx st h y b j J         14 گراديانz(x) نسبت به جريان هاي كمان در تکرارn ام برابر با بردار زمان سفر كمان است زيرا كه ()n n a azxtx . بنابراين تابع هدک خطي شده برابر است با : (2-15) min z ( ) .. r,s 0 r,s,k nn aa a rs k rs k rs ky t y st gq g       كه در آن ., ars rs a k ak r s kyg   و ()n n a a a nt t x مي باشد. در اين مسئله خطي، ay متغير كمکي نشان دهنده جريان در كمان a و rs kg متغير جريان كمکي براي مسير k كه مبدا-مقصدs -r را به هم متصل مي كند، مي باشد. اين مسئله زمان سفر كلي را در يک شبکه با زمان سفر ثابت مينيمم مي كند. زمان سفر كلي در شبکه با تخصيص تمام جريان به مسير با كوتاه ترين زمان سفر مينيمم مي شود. اين تخصيص با روش تخصيص همه يا هيج انجام مي شود. براي اثبات اين موضوع كه جواب رابطه 2-15 با استفاده از تخصيص همه با هيج بدست مي آيد، گام خطي سازي الگوريتم فرانک-ولف با گرف تن گراديان تابع هدک با توجه به جريان هاي در مسير بدست مي آيد. بنابراين مسئله خطي شده به صورت رابطه 2-11 نوشته ميشود. (2-11) ,min z ( ) z[x(f )]. .. r,s 0 r,s,kn n T rs rs f k k r s k rs k rs k rs kg g c g st gq g        كه nrs kc زمان سفر در مسير k كه مبدا-مقصدs -r را به هم متصل مي كند در تکرارn ام مي باشد. اين مسئله علت ثابت بودن زمان سغر مي تواند به تفکيک مبدا-مقصد جدا شود. زيرمسئله هاي حاصل براي هر زوج مبدا-مقصد r-s به صورت رابطه2-11 .مي باشد (2-11) زماني كه جريان در مسير ( rs kg) پيدا شد، جريان در كمان ها با استفاده از رابطه 2-11 .بدست مي آيد min z ( ) .. 0 kn rs rs rs kk k rs k rs k rs kg c g st gq g       15 (2-11) و جواب اين مسئله جهت نزول،nx-n=ynd .، را به ما ميدهد جستجوي خطي براي يافتن اندازه گام بهينه را مي توان با استفاده از روش دوبخشي 1 انجام داد. علت آن اين است كه مشتق تابع هدک نسبت به  كه معادل با رابطه 2-19 است، به آساني براي هر مقدار  قابل محاسبه است. (2-19) ( ) ( ) ( )n n n n n n n n a a a a a a az x y x y x t x y x            مراحل اين الگوريتم به طور خالصه در زير آمده است : گام (1)- )(مقداردهي اوليه قرار دهيد 0n. با انجام يک تخصيص همه يا هيچ مقادير اوليه جريان در كمان هاي n ax را بيابيد.. گام(2)-( آزمون توقف) زمان سفركمان هاي شبکه ()a a at t x را بهنگام كنيد. اگر x جواب با دقت مورد نظر است،پايان. گام (3)- )(تعيين جهت يک تخصيص همه يا هيچ را براي يافتن جوابهاي كمکي n ay ها براي همه كمان هاي شبکه انجام دهيد. جهات نزول ()a a ad y xرا محاسبه كرده گام (4)- )(تعيين اندازه گام اندازه گام () را از طريق حل مسئله بهينه سازي تک متغيره زير بدست آوريد. (2-21) 1 0 . . 0 1n ax a Min Z t v dv st       گام (5) -( حركت) bisection1 . ars rs a k ak r s kyg   11 جريان در كمان ها را به صورتd  +a=xn+1ax محاسبه كني. قرار دهيد n=n+1 و به گام2 .برويد لبالنک و همکاران [1] روش فرانک- ولف [1] را براي حل مسکئله تخصکيص ترافيک مورد استفاده قرار دادند. اين الگوريتم، كه معروک ترين روش براي حل مسککئله تخصککيص به شککمار ميرود، شککبيه روش ميانگين گيري متوالي اسککت با اين تفاوت كه از يک نوع جسککتجوي خطي براي يافتن اندازه گام در هر تکرار استفاده ميکند. طبق لبالنک [9 وفلورين] [11 ] نرخ پايين همگرايي الگوريتم فرانک - ولف عليرغم مزيت هاي ذكر شده باعث شد تا تالش هاي بسياري براي بهبود آن از طريق بهبود جهت نزول و يا اندازه گام صککورت گيرد .از جمله روش هايي كه با تصککحيح جهت نزول سککعي در بهبود الگوريتم داشککت روش PARTAN ميباشککد. در اين روش، با تركيب جواب حاصککل از هر مرحله با جواب مرحله قبل و انجام يک جستجوي خطي اضافي در هر تکرار، جهت حركت نسبت به الگوريتم فرانک- ولف تصحيح و با اين كار سعي شده است تا از شدت حركت زيگزاگي كاسته شود. فوكوشيما[12] نيز با تصحيح جهت حركت سکعي در بهبود الگوريتم فرانک- ولف داشته است. او با ذخيره كردن جواب هاي حاصل از تخصيص همه يا هيچ مراحل قبل، جهت حركت هر تکرار را از تركيب محدب آنها بدسککت مي آورد. وينتراب و همکاران [13] سککعي كردند تا با انتخاب اندازه گام هاي بزرگتر نسککبت به اندازه گام حاصککل از جسککتجوي خطي، حركت زيگزاگي را حذک كنند. در صککورتيکه اندازه گام انتخابي بيش از حد بزرگ مي شککد و بهبودي در تابع هدک حاصکل نمي شد، همان اندازه گام معمول براي آن تکرار در نظر گرفته مي شد. لي و ني [14] با ايجاد تغييراتي در الگوريتم فوكوشيما، روش كاراتري را پيشنهاد كردند. در هر دو اين روش ها با ذخيره كردن جواب هاي تخصککيص همه يا هيچ تکرارهاي قبل، يک جهت نز ول جايگزين در هر تکرار محاسککبه مي شکود. سکپس اين جهت با جهت حاصکل از تخصيص همه يا هيچ همان تکرار مقايسه ميگردد، بدين شرح كه مشتق تابع هدک در اين دو جهت محاسبه و جهتي كه مقدار مشتق سويي كمتري داشته باشد به عنوان جهت حركت انتخاب ميگردد. فرق اسکاسي اين الگوريتم با الگوريتم فوكوشيما در اين است كه الگوريتم دوم از تعداد جواب هاي كمتري براي سککاختن جهت نزول جايگزين اسککتفاده ميکند. مقايسککه الگوريتم پيشکککنهادي با ديگر روش هاي بهبود الگوريتم فرانک- ولف نشکککان داد كه اين الگوريتم داراي بهترين كکارايي، و پس از آن بکه ترتيکب كکارايي الگوريتم هکاي فوكوشکککيمکا، وينتراب، فرانک - ولف و PARTAN بهتر است. در ادامه روش ميانگين گيري متوالي كه از الگوريتم هاي تخصيص ترافيک است توضيح داده مي شود. 2-3-2- روش میانگین گیری متوالی اين روش كه توسکط شفي[2] براي حل مسئله تخصيص ترافيک ارائه شده استمانند روش فر انک-ولف مي باشکککد با اين تفاوت كه مقدار  را در هر گام ثابت در نظر مي گيرد و آن را مي توان با مراحل زير بيان كرد: 11 گام (1)- )(مقدار دهي اوليه براي ايجاد يک بردار مقدار جريان اوليه 0x تخصککيص ترافيک همه يا هيچ با زمان هاي =t(a)a0t انجام دهيد. قرار دهيد n=1. گام(2)-( به روز رساني زمان سفر) با مقدار جريان nx زمان سفر كمان هاan t . را به روز رساني كنيد گام (3)-( جهت يابي) با مقادير an t تخصيص ترافيک همه يا هيچ را انجام دهيد و مقادير بردار جريانany .را بدست آوريد گام (4)-( حركت) جواب بعدي n+1ax كه بينnx وny :مي باشد به صورت زير بدست مي آيد (2-21) مقدارn :را يک واحد افزايش دهيد n=n+1 و به گام2 .برويد 2-4- مدل تخصیص ترافیک با ظرفیت محدود كاربرد وسکيع مدل تخصکيص ترافيک در ارزيابي و انتخاب راه كارهاي مناسب براي بهبود عملکرد شبکه حمل ونقل نيازمند واقعي تر شکدن هرچه بيشکتر نتايج حاصل از آن است. يکي از عوامل واقعي تر شدن نتايج اين مدل ، مستقل از روش حل آن،در نظر گرفتن محدوديت ظرفيت كمان ها است. اضافه شدن محدوديت ظرفيت به مدل بهينه سازي تخصيص ترافيک سبب ازبين رفتن كارايي روش هاي حل ديگر مي شکود. زيرا د ر اين حالت زير مسکئله خطي شده مدل بهينه سازي شده –كه معادل مسئله كوتاه ترين مسيراست –به مسئله جريان چند كااليي با هزينه كمينه درشبکه تبديل مي شود كه حل آن نسکبت به مسکئله كوتاه ترين مسکير بسکيار دشکوارتر و زمان برتر است. به طور كلي در اغلب روش هاي مسئله تخصيص ترافيک با م حدوديت ظرفيت تالش مي شود تا از حل مسئله چند كااليي پرهيز شود. فرمول بندي مسئله فرانک-ولف با ظرفيت محدود براي هر كمان به شکل فرمول 2-22 مي باشد. 111()n n n nx x y xn   11 (2-22) تابع هدک و محدوديت هاي1 و2 در اين فرمول بندي مشابه فرمول2-1 است و محدوديت3 رابطه بين جريان در كمان ax و ظرفيت هر كمانac .را بيان مي كنند 2-6- الگوریتم شهپر و همكاران در اين پژوهش، شهپر و همکاران از يک تابع جريمه ديناميکي براي تبديل مسئله تخصيص ترافيک با محدوديت ظرفيت براي هر كمان به زيرمسائل بدون ظرفيت استفاده كردند. آنها فرض كردند كه تابع زمان سفر مثبت، پيوسته و صعودي مي باشد و توابع محدوديت ( كه براي اجزايي از شبکه مانند گره ها و مسيرها) داراي مدل بهينه سازي محدب مي باشند. در اين الگوريتم زمان سفر كلي به صورت فرمول 2- 23 :تعريف ميشود (2-23) ()( , ) ( ( ) )j rs rs k a a j ak a A j J agxC x t xx    كه در اين مدل ( , )rs kCx برابر با كوتاه ترين زمان سفر از مسير k بين زوج مبدل-مقصد ( , )rs ، ()jgx برابر با j امين تابع محدوديت،a x جريان در كمان a، jضريب الگرانژي مربوط به j امين تابع محدوديت و rs akدر صورتي كه كمان a روي مسير k باشد برابر با1 و در غير اين صورت صفراست، مي باشند. در فرمول 2-23 عبارت ()j j jJ agx x   تاخير ناشي از محدوديت جانبي در هر كمان مي باشد. تابع جريمه به صورت ( , )jPx تعريف مي شود كه در آن  متغيري است كه دامنه آن بين (0, ) مي باشد. فرض اول كه براي تابع جريمه در اين الگوريتم وجود دارد عبارتست از مشتق پذير ، يکنواخت و غيرمنفي بودن اين تابع. فرض دوم بيان ميکند كه اگر ( ) 1jgx باشد، مقدار اين تابع برابر است با j است. در فرض سوم اگر ( ) 1jgxمقدار تابع جريمه به اندازه قابل توجهي بزرگ مي باشد و اگر 0 min ( ) ( ) .. , 0 , , a ax a a rs rs k k rs k rs rs a k ak cz x t d st f q r s f r s k x f a A        ( , )r s k          19 ( ) 1jgx مقدار تابع جريمه به طور قابل توجهي كوچک مي باشد. در اين پژوهش تابع جريمه به صورت فرمول 2-24 .بيان مي شود در اين مقاله تابع جريمه به توابع زمان سفر اضافه مي شوند. (2-24) ( , ) ( ( ))j j jP x g x كه ( ( ))jgx مانند فرمول 2-25 .بيان ميشود (2-25) كه  متغيري با دامنه (0,1) مي باشد. كه j در هر مرحله به صورت زير به روز رساني مي شود: (2- 21) 11( , ) ( ( ))n n n n n j j j j jP x g x     در اين الگوريتم معيار توقف به صورت رابطه 2-21 .بيان ميشود (2-21) 0( ) 1 j J (1 ( )) j J, ( ) 1n j n n n j j j jgx g x g x            اگر 0 زير مسئله را مي توان به زير مسائل بدون محدوديت تبديل كرد كه در آنها زمان سفر كلي را مي توان به صورت فرمول 2-21 :بيان كرد (2-21) ()( ) ( ) ( , )j a a a a j j jJ agxt x t x P xx  بدين صورت مي توان j را با ( , )jj jJPx  تقريب زد و اگر جريان در مسير را مطابق فرمول 2-29 بيان كرد، آنگاه با جايگذاري ( , )jj jJPx  در فرمول 2-23، به رابطه 2-31 .خواهيم رسيد (2-29) ()rs rs a k ak r s kx f f   (2-31) بنابراين مسئله ما به صورت رابطه2-31 تعريف مي شود. y<1-2(1 ( ))( ( )) 11 y 1-2j jgxgx y    ()( , ) ( ( ) )j rs rs k a a j ak a A j J agxC x t xx    21 (2-13) ( ( , ) ) 0 ( , ) 0 ( ) 0 0 0rs rsrs rs k rs k rs k rs rs k rs rs kK rs k rs kK rsc f u f c f u f q u fq u             بهاين مسئله، مسئله تکميلي غيرخطي1 ميگويند. در هر تکرار ، مسئله تکميلي غيرخطي به تفکيک مبدا-مقصد به زيرمسائل بدون محدوديت تبديل مي شود. براي رفع مشکالت زياد بودن تعداد زيرمسائل از روش توليد مسير2 استفاده مي شوند. درهرتکرار، تنها مسيرهايي كه جواب مثبت دارند كنترل مي شوند. [ آشتياني1 اين مسيرها را مسيرهاي كاري]3 ناميده و آن را با w rsK نشان داد. معيار توقف در روش توليد مسير به صورت رابطه 2-32 .بيان مي شود (2-32) min ( , ) rsrs k k k rs rsc f u u  كه  دقت موردنظر مي باشد. حتي در صورت كم بودن تعداد مسيرهاي كاري، بدست آوردن مسيرهاي كاري با استفاده از الگوريتم [ هاي تکميلي غيرخطي بهينه نيست. آشتياني1 با استفاده از الگوريتم خطي سازي تکراري] سعي بر حل اين مشکل كرد. با استفاده از اين روش ، در هر تکرار، مدل در جريان فعلي ()f خطي مي شود. مدل خطي شده شامل فرمول 2-33 .مي باشد (2-33) ( , )( ( , ) ( ) ) 0 k k ( , )( , ) ( ) 0 k k rs rsrs rs rs k k k k rs k rs kk k rs rs k k k k rs rs kk kcfC f f f u ff cfC f f f uf                       معيار توقف در اين روش برابر با رابطه2-34 .ميباشد 1non-linear complementarity problem 2 Path generation 3 Working paths 21 (2-34) :0 :0max c ( , ) max c ( , )w rs k w rs krs k rs k k f rs k k k ffu f    الگوريتم زماني تمام مي شودكه متوسط خطاي جواب كنوني كمتر از  باشد. يعني: (2-35) rs rs r R s S rs r R s Sq q   كه در آن rs براي هر زوج مبدا-مقصد ( , )rs به صورت رابطه 2-31 .تعريف ميشود (2-31) :0max c ( , )w rs krs k rs k k f rs rsfu u   :گام هاي اين الگوريتم عبارتست از گام (1)- )(مقداردهي اوليه مقادير مثبتي براي و  و همچنين بردار 0 در نظر بگيريد. براي هر زوج مبدا-مقصد بردار w rsK قرار دهيد. و ساير پارامترها را به صورت زير مقداردهي كنيد: 0 () 0rs k af x x f n   گام (2)-( تجزيه و خطي سازي) n=n+1 .را قرار دهيد. براي هر مقصد گام هاي زير را انجام دهيد 2-1- كوتاه ترين مسير بين هر زوج مبدا-مقصد را با استفاده از زمان سفر مرحله قبل بدست آوريد. زمان سفر بين زوج مبدا-مقصد (r,s) را rsu مي ناميم. 2-2- :براي هر مقصد با تقاضاي مثبت گام هاي زير را انجام دهيد 2-2-1- اگر رابطه2-32 با مقدار 1n برقرار نبود، قرار دهيد ww rs rs rsk k k و 0 rskf 2-2-2- براي w rs kk قرار دهيد kkff 2-2-3- براي بدست آوردن ( , )rs rs fu مسيرهاي كاري را براي مسئله تکميلي غيرخطي در نقطه kf بدست آوريد. 22 2-2-4- اگر رابطه2-34 براي 1n برقرار نبود، آن گاه به گام 2-2-2 .برويد 2-2-5- براي 1n مقدار rs را بيابيد. گام (3)- )(به روز رساني جريان كمان ها و ضرايب الگرانژ قرار دهيد =x(f)nx و 1( , )n n nPx گام (4)- )(كنترل توقف اگر رابطه 2-35 برقرار نبود به گام2 برويد. در غير اين صورت، اگر رابطه 2-21 با مقادير 00 و 1n برقرار بود، توقف كنيد . در غير اين صورت به گام 2 .برويد 23 3 فصل سوم مسئله جریان با هزینه منیمم درشبكه 24 3-1- مقدمه از بين الگوريتم هاي اشاره شده در فصل قبل، الگوريتم فرانک-ولف (كه از الگوريتم هاي بر مبناي كمان اسککت) به علت فهم آسککان، سککادگي در اجرا، حافظه مصککرفي كم و كارايي مناسککب در تکرارهاي اوليه محبوبيکت فراواني در بين محققان د ارد. با اين وجود، نتايج اين الگوريتم به علت در نظر نگرفتن ظرفيت هاي مربوط به كمان كمابيش نزديک به واقعيت نيستند. به همين دليل، يکي از اهداک اصلي اين پژوهش در نظر گرفتن محدوديت ظرفيت كمان ها براي دقيق تر كردن هرچه بيشتر نتايج حاصل از اين الگوريتم است. دراين فصکل ابتدا مسکئله جريان با هزينه مينيمم توضکيح داده ميشود و سپس به توضيح الگوريتم هاي بلمن-فورد ، دايجسترا ، درخت هيپ دوتايي كه كوتاه ترين مسير بين دو گره را با فرض ثابت بودن زمان سکفر كمان ها در يک شکبکه تعيين مي كنند، پرداخته مي شکود . سکپس به توضيح الگوريتم Out of Kilter وهمه يا هيچ كه جهت جريان در كمان هاي يک شککبکه را مشککخص مي كن ند پرداخته ونتايج حاصکل از اجراي الگوريتم Out of Kilter .را بر روي دو شکبکه با زمان سکفر ثابت نشان مي دهيمدر انتها نيز به مقايسه زمان حل الگوريتم هاي بل و دايجسترا براي شبکه شيکاگو مي پردازيم. جدول 1- الگوريتم هاي كوتاهترين مسير ردیف نام الگوریتم پژوهشگر سال انتشار پژوهش 1 بلمن-فورد بلمن،فورد 1951 2 دايجسترا دايجسترا 1951 3 درخت هيپ دوتايي ويليامز 1914 4 Out of Kilter فولکرسون 1911 25 3-2- مسئله جریان با هزینه مینیمم مسئله جريان با هزينه مينيمم به شکل رابطه 3-1 :زير نوشته مي شود (3-4) ( , )min ( ) .. 0ij ij i j N ij ji i ij ij a ijz x t x st x x b xc x         دراين مدل ijx جريان دركمان بين گره هاي i وj ، ijt زمان سکککفر در كمان بين گره هاي i وj ، ib تقاضککاي جريان از گره i بهj وac ظرفيت كمانa مي باشککد . در رابطه 3-1 تابع هدک عبارت اسککت از مجموع حاصککلضککرب زمان سککفر هر كمان در جريان همان كمان. در اين مدل محدوديت اول بيانگر آن است كه تفاضل مجموع جريان دركمان ij و كمانji برابر با تقاضاي جريان ازi بهj مي باشد. محدوديت دوم براي اطمينان از بيشتر نشدن جريان در هر كمان از ظرفيت آن كمان و محدوديت سوم براي منطقي بودن جواب ها و مثبت بودن جريان در هر كمان مي باشکد. در صککورت در نظر نگرفتن شرط محدوديت ظرفيت در فرمول 3-1 ، مسککئله تبديل به مسککئله تخصککيص همه يا هيچ تبديل مي شککود كه انتهاي اين بخش اين مسئله توضيح داده مي شود. زماني كه تابع زمان سفر تابعي ثابت است، يعني 0a)=ta(xat ، در اين صورت حل مسئله تخصيص تقاضا به مسئله كوتاه ترين مسير بين زوج هاي مبدا و مقصد خواهد بود. براي اثبات اين مسئله، رابطه 3-2 كه همان مسئله بکمن است را در نظر بگيريد. (3-2) :اگر زمان سفر ثابت باشد، خواهيم داشت 0 ( min ( ) ( ) .. , 0 , , ax a a rs rs k k rs k rs rs a k ak rkz x t d st f q r s f r s k x f a A         ,)s          21 (3-3) با جايگذاري محدوديت3 :در تابع هدک،خواهيم داشت ..min ( ) rs rs rs rs a k k k a k a r s k r s k aZ x t f f t      چون عبارت .rs ak at برابر با زمان سفركوتاه ترين ()rs kc است،پس عبارت باال برابر است با: min ( )rs rs kk r s kZ x f c پس مسئله باال برابر با تخصيص تقاضاي جريان به كوتاه ترين مسير بين زوج هاي مبدا و مقصد است. 3-3- الگوریتمبلمن-فورد الگوريتم بلمن-فورد الگوريتم پيمايش گراک اسککت كه مسککئله كوتاه ترين مسککير از مبدأ واحد را براي گراکهاي وزنداري كه وزن يالها ممکن اسککت منفي باشککد حل ميكند. الگوريتم بلمن-فورد راهكاري براي پيدا كردن كم وزن ترين مسککير از رأس مشککخص آغاز به بقيه رئوس در گراک جهتدار و وزندار ميدهد. وزن يک مسککير در گراک وزندار برابر مجموع وزن يالهاي آن اسککت . جهتدار نبودن يالها هم مشکلي ايجاد نميكند و ميتوان براي يالهاي غير جهتدار دو يال فرض كرد. يکي از مزيت هاي اين الگوريتم نسبت توانايي اجرا شدن روي گراکها با يال منفي است. اجراي الگوريتم 1-|V| دنباله d چنان تعريف مي شککود كه براي هر رأس |V| ، مقدار vd در پايان مرحله i ام برابر وزن كوتاه ترين گذر از مبدأ به |V| اسککت با اين شککرط اضککافه كه تعداد يالهاي اين گذر حداكثر i باشککد . بنابراين در پايان مرحله 1-|V| ام vd برابر وزن كوتاهترين مسککير از مبدأ به |V| خواهد بود .در واقع چون دور با مجموع وزن منفي نداريم، كوتاه ترين گذر با حداكثر |V|-1 يال از مبدأ به |V|، همان كوتاه ترين مسير از مبدأ به |V| در گراک خواهد بود. . ( , ) , 0 , , min ( ) .. rs k rs k rs k rs rs aka ak rka sa f q r s f r s k xZ x t x st f a A               21 اسککاس كار الگوريتم آزادسککازي همه يالهاي گراک در هر مرحله اسککت . آزادسککازي يال (u,v) به اين معناسکککت كه اگر  , uvd weight u v d آنگاه قرار ميدهيم ,vud d weight u v با اين اوصاک اگر آزادسازي همه يالها را براي بار |V|ام هم تکرار كنيم و بعد از اين مرحله هم دنباله d تغيير كند، آنگاه ميتوان نتيجه گرفت كه گراک دور منفياي دارد كه از مبدأ قابل دستيابي است. مشخص است كه در 1-|V| مرحله، در هر مرحله E عمليات بر روي يالها انجام مي شود . پس m * n پيچيدگي زماني الگوريتم بلمن-فورد خواهد بود ، كه در آن n متوسط ورود هر گره و m تعداد كمان ها است. در اين الگوريتم از دو مجموعه استفاده مي شود.مجموعه اول مجموعه D استكه اعضاي ان به صورت id نمايش داده شده است و بيانگر كوتاه ترين مسير از مبدا به گرهiv در پايان هر تکرار الگوريتم است. اين مقدار در ابتدا به ازاي تمامي گره ها برابر  است. 12 , ,.....ni For v v v d   مجوعه دوم مجموعه p اسککت كه اعضککاي آن به صککورت ip نمايش داده شککده و در پايان هر تکرار گره پيشککين گره iv را كه گره مبدا از طريق ان به اين گره در كوتاه ترين مسککير دسککترسککي دارد، مشککخص ميکند. اين مقادير در ابتدا براي هيچ كدام از گره ها تعربف نشده است و در تکرارهاي آن مقداردهي مي شوند. 3-4- الگوریتمدایجسترا الگوريتم دايجسکترا يک راهکار براي يافتن كوتاه ترين مسکير از مقصد ثابت به ساير گره هاي گراک وزن دار اسکت. اين گراک ميتواند معرک مسيرهاي يک شهر و تقاطع هاي آن و هدک اين الگوريتم پيدا كردن كوتاه ترين مسکير بين گره هاي مختلف اين شکهر باشد. طبيعتا اين الگوريتم در يافتن كوتاه ترين م سير بين دو گره مشکککخص نيز كاربرد دارد. تنها شکککرط الزم اسکککتفاده از اين الگوريتم نامنفي بودن وزن يال هاست. الگوريتم دايجسترا به صورت حريصانه عمل كرده و در تکرارهاي متوالي،كوتاه ترين مسير از مبدا به يکي از گره هاي گراک را بدسکت مي آورد. در اين الگوريتم از سه مجموعه استفاده مي شود. مجموعه D كه اعضکاي ان به صکورتiD نمايش داده شده است و بيانگر كوتاه ترين مسير از مبدا به گرهiv در پايان هر تکرار الگوريتم است. اين مقدار در ابتدا به ازاي تمامي گره ها برابر  است. 12, ,.....ni v v v d   For مجموعهدوم مجموعه اسکت p كه اعضکاي آن به صکورتi p نمايش داده شده و در پايان هر تکرار گره پيشککين گره iv را كه گره مبدا از طريق ان به اين گره در كوتاه ترين مسککير دسککترسککي دارد، مشککخص ميکند. اين مقادير در ابتدا براي هيچ كدام از گره ها تعربف نشککده اسککتو در تکرارهاي آن مقداردهي مي 21 شکوند. مجموعه سکوم مجموعه U اسکت كه اعضکاي آن گره هاي بررسکي نشکده در الگوريتم است. اين مجموعه در ابتدا شامل تمامي گره هاي گراک است. مراحل الگوريتم دايجسترا براي يافتن كوتاه ترين مسير از گره هاي 0v به ساير گره به اين شرح است: گام(1)- )(انتخاب گره مبدا گره 0v را بکه عنوان گره جاري ازU حذک كرده،مقدار0d را برابر صکککفر قرار داده و گام هاي 2 تا4 را تکراركنيد. گام(2)- )(محاسبه كوتاه ترين زمان سفر به هر گره به ازاي هر يال خروجي از گره جاري )jv( به يک گره از مجموعهU مانندkv مقدار jk+ejd را محاسککبه كرده و اگر مقدار آن از kd كوچکتر باشد، مقدارkd را با jk+ejd .جايگزين كنيد j jk k k j jkd e d d d e     If (گام3)- )(انتخاب گره بعدي از مجموعهU گره هاي عضککو گره با كوچکترين d را به عنوان گره جاري انتخاب كنيد و از مجموعهU .حذک كنيد گام (4)- )(كنترل اگر U تهي اسکککت با در مرحله 3 هيچ گره اي براي انتخاب به عنوان گره جديد وجود ندارد، به گام بعد برويد. مقدار id راي گرهiv ،كوتاه ترين مسککير از مبدا به آن گره را مشککخص كرده اسککت كه از طريق گره ip براي گره مبدا در دسترس است. مثال براي توضيح نحوه عملکرد الگوريتم دايجسترا، در شکل 3- 1 كوتاه ترين مسير از گره شماره 1 به ساير گره ها در گراک را بدست مي آوريم. اين شبکه 4 گره و1 كمان دارد. اعداد روي هر كمان بيان گر زمان سفر آن كمان مي باشند. 29 شکل3-1- شبکه4 گره اي الگوريتم دايجسترا مقادير d براي تمامي گره ها مطابق جدول2 بينهايت قرار داده و همچنين مجموعه U شامل تمامي گره ها مي باشد. جدول 2- كوتاه ترين مسير در مرحله1 4 3 2 1 گره     كوتاه ترين مسير از مبدا به گره(d)  1,2,3,4 U ( گام1)- )(انتخاب گره مبدا گره 1 را بکه عنوان گره جکاري ازU حذک كرده،مقدار1d را برابر صکککفر قرار داده و گام هاي 2 تا4 را تکراركنيد. جدول 3- كوتاه ترين مسير 4 3 2 1 گره    0 كوتاه ترين مسير از مبدا به گره(d) 31  2,3,4 U ( گام2)- (محاسبه كوتاه ترين زمان سفر به هرگره ) گره هاي مجاور گره 1 :را بررسي ميکنيم 2 1 12 1 0 1 d d t     3 1 13 0 3 3 d d t     جدول 4- كوتاه ترين مسير 4 3 2 1 گره  3 1 0 كوتاه ترين مسير از مبدا به گره(d) (گام3)- )(انتخاب گره بعدي گره با كمترين d (گره2 ) انتخاب ميشود: 3,4 U گام (2)- (محاسبه كوتاه ترين زمان سفر به هرگره ) زمان گره هاي منتهي به كمان هاي خروجي از گره 2 را محاسبه مي كنيم.: 4 2 24 1 7 8 d d t     3 2 23 1 3 4 d d t     جدول 5- كوتاه ترين مسير 4 3 2 1 گره 8 3 1 0 كوتاه ترين مسير از مبدا به گره(d) (گام3)- )(انتخاب گره بعدي 31 گره با كمترينd (گره3 ) انتخاب ميشود. {4} U گام (2)- (محاسبه كوتاه ترين زمان سفر به هرگره ) زمان گره هاي منتهي به كمان هاي خروجي از گره 3 :.را محاسبه ميکنيم 2 3 32 3 4 7 d d t     4 3 34 3 2 5 d d t     جدول 6 - كوتاه ترين مسير 4 3 2 1 گره 5 3 1 0 كوتاه ترين مسير از مبدا به گره(d) (گام3)- )(انتخاب گره بعدي گره با كمترين d (گره4 ) انتخاب ميشود: U گام (2)- (محاسبه كوتاهترين زمان سفر به هرگره ) زمان گره هاي منتهي به كمانهاي خروجي از گره 4 :.را محاسبه ميکنيم 1 4 41 5 6 11 d d t     جدول 7- كوتاه ترين مسير 4 3 2 1 گره 5 3 1 0 كوتاه ترين مسير از مبدا به گره(d) 32 3-6- الگوریتم درخت heap يک درخت دودويي كامل اسککت، هرگاه تمام ي سککطوح درخت به غ ير از احتماال آخرين سککطح پر بوده و برگهاي سطح آخر از سمت چپ قرار گرفته باشند. نمايش با اسکتفاده از ليسکت پيوندي و آرايه دو شکل مشهور نمايش درخت دودويي در ساختمان دادهها است. در حالت عادي انتخاب يکي از اين دو روش براي نمايش بهينه و با مصرک حافظهي كمتر بسته به چيدمان عناصککر درخت دارد. به عنوان مثال، در درخت هاي مورب روش نمايش با آرايه بدترين بازدهي و بيشترين مصرک حافظه را دارد. اما در درخت دودويي كامل اين روش در مقايسه با روش ليست پيوندي بسکيار بهينهتر اسکت. در روش اسکتفاده از آرايه براي نمايش درخت دودويي، گره هاي درخت با شروع از ريشکه و در هر سکطح از چپ به راست به ترتيب شمارهگذاري شده و مقدار هر كدام از گره ها با توجه به شککمارهي آن در يکي ا ز خانههاي آرايه قرار مي گيرد. در آرايهي متناظر درخت دودويي كامل، از همه ي عناصر به صورت كامل استفاده شده و هيچ حافظهي هرزي وجود ندارد .به همين خاطر اين روش نمايش براي درخت كامل مناسککب اسککت. فرض كنيم توابع Left ، Parent و Right شککماره ي يک گره را گرفته و به ترتيب شمارهي گره والد، فرزند چپ و فرزند راست را برگرداند. در اين صورت : (3-4) ( ) 2 ( ) [ ]2 ( ) 2 1Left i iiparent i Right i i      . جزء صحيح (كف) عدد است][ كه منظور از 3-6-1- ( هرم ماکزیمم (max-heap درخت دودويي كاملي اسکت كه مقدار هر گره بيشتر يا مساوي فرزندان خود است. شکل 3-1 نمايشي از هرم ماكزيمم است. 33 شکل3-2- درخت هيپ ماكزيمم و نمايش آرايه اي در جدول 1 نشان داده شده است. جدول 8- مينيمم مسير گره هايدرخت هيپ ماكزيمم 10 9 8 7 6 5 4 3 2 1 Max Heap 6 2 3 1 9 12 10 11 12 15 3-6-2- ( هرم مینیمم (min -heap درخت دودويي كاملي اسکت كه مقدار هر گره كمتر يا مساوي فرزندان خود است . شکل 3-3 نمايشي از هرم مينيمم است. 34 شکل3-3- درخت هيپ مينيمم سککاختن يک درخت heap در واقع وارد كردن متوالي گرهها در آن اسککت. برا ي وارد كردن يک گره به درخت heap، طي دو مرحله به صورت زير عمل ميكنيم: گام( 1)- )(اضافه كردن گره گره مفروض را در محلي از درخت كه شرط كامل بودن آن به هم نخورد (بدون در نظر گرفتن شرط يا بودن) درج ميكنيم. گام( 2) – )(مرتب سازي گره ها اگر گره مذكور بر اسکککاس موقع يت خود در درخت، شکککرط max-heap يا min-heap بودن را نقض نکند، نياز به انجام كاري نيسکت و عمليات درج تمام شکده است. در غير اينصورت، با جابجا كردن گره با والد خود، درخت جديدي حاصل مي شود كه بايد مرحلهي 2 در مورد آن تکرار شود. حذک گره از درخت هيپ عموما از ريشکهي آن صکورت ميگيرد. حذک گره اي غير از گره ريشه، ممکن اسکت هزينهاي معادل سکاخت مجدد درخت تحميل كند. چرا كه با حذک يک گره غير ريشه و جايگزين 35 كردن گرهي ديگر با آن، نه تنها شککرط min-heap با max-heap بودن كه شککرط درخت كامل بودن هم ممکن است نقض شود. اكثر كاربردهاي اين نوع درخت نيز تنها با حذک گره از ريشه سر و كار دارند. براي حذک گره ر يشهي درخت دو مرحله زير را اجرا ميكنيم: گام (1)- )(حذک گره گره ريشه را حذک و سمت راستترين برگ سطح آخر را جايگزين آن ميكنيم. گام(2)- )(مرتب سازي گره ها در صورتي كه گره درج شده جديد شرط heap بودن را نقض نکند عمليات حذک تمام مي شود. در غير اينصورت اين گره با فرزند مناسب جايگزين شده و اين مرحله براي درخت جديد مجددا اجرا مي شود. با اجراي مرحلهي اول و جايگزين كردن آخرين گره آخرين سککطح درخت، شککرط كامل بودن درخت پا يدار ميماند. اما عموما شرط heap بودن نقضمي شود . در مرحلهي دوم، گره تازه وارد را با يکي از فرزندان خود جايگزين ميكنيم، تا به شرط heap بودن نزديک شويم. مثال براي توضيح نحوه عملکرد الگوريتم هيپ، در شکل 3-4 كوتاه ترين مسير از گره شماره 1 به ساير گره ها در گراک را بدسکت مي آوريم. اين شکل، همان مثال ذكر شده در شکل 3-1 مي باشد و ما درخت هيپ مينمم را بدست مي آوريم. شکل 3-4- شبکه4 گره اي الگوريتم هيپ 31 گره مبدا ما گره1 مي باشککد . مقدار d را براي گره مبدا برابر با صککفر قرار مي دهيم. گره هاي منتهي به كمان هاي خروجي از گره 1 شامل گره هاي2 و3 .مي باشند و بايد آن ها را به درخت اضافه كنيم گام( 1)- )(اضافه كردن گره گره 2 را به درخت اضافه كنيم و بنابراين درخت ما شامل گره هاي 1 و2 .مي شود گام( 2) – )(مرتب سازي گره ها مقدار زمان سفر گره 2 :برابر است با 2 1 12 1 0 1 d d t     چون زمان سکفر گره 2 بيشتر از زمان سفر گره1 مي باشد، پس اضافه كردن گره2 شرط مينيمم بودن درخت را به هم نميزند. شکل 3-5- درختمرحله اول الگوريتم هيپ مينيمم گام( 1)- )(اضافه كردن گره گره 3 را به درخت اضافه كنيم و درخت ما شامل گره هاي1 و2 و3 .مي شود گام( 2) – )(مرتب سازي گره ها مقدار زمان سفر گره 3 :برابر است با 3 1 13 0 3 3 d d t     31 زمان سفر گره 3 از گره2 و1 بيشتر است . بنابراينشرط مينيمم بودن درخت را به هم نمي زند. شکل 3-1- درخت مرحله دوم الگوريتم هيپ مينيمم در گام بعد گره اي كه مينيمم زمان سکککفر را دارد (گره 2 ) را انتخاب مي كنيم.گره2 به گره هاي3 و4 .متصل است. پس بايد زمان سفرهاي آنها را در اين مرحله حساب كنيم گام( 1)- (اضافهكردن گره) زمان سفر گره 3 :برابر است با 3 2 23 1 3 4 d d t     چون زمان سفر در اي مرحله بيشتر از زمان سفر در مرحله قبل است، آن را تغيير نمي دهيم. گام( 1)- )(اضافه كردن گره زمان سفر گره 4 :برابر است با 4 2 24 1 7 8 d d t     31 شکل3-1- درخت مرحله سوم الگوريتم هيپ مينيمم گره با مينيم زمان سفر (گره 3 .) را انتخاب كرده و كمان هاي خروجي از آن را بررسي ميکنيم گام( 1)- )(اضافه كردن گره گره 3 به گره هاي2 و4 متصل است. پس زمان سفر گره2 .را بدست مي آوريم 2 3 32 3 4 7 d d t     چون زمان سکفر به دست آمده براي گره 2 در اين مرحله بيشتر از زمان سفر قبلي آن است، آن را تغيير نمي دهيم. گام( 1)- )(اضافه كردن گره زمان سفر گره 4 :برابر است با 4 3 34 3 2 5 d d t     چون زمان سکفر اين گره كاهش يافته است ، زمان سفر گره 4 را كاهش مي دهيم. چون زمان سفر گره 4 بيشتر از گره ها 2 و3 .است، پس نيازي به مرتب سازي گره ها وجود ندارد گره 4 .را به عنوان گره بعدي انتخاب ميکنيم گام( 1)- )(اضافه كردن گره گره 4 تنها به گره1 متصل است. زمان سفر گره1 :در اين مرحله برابر است با 1 4 41 5 6 11 d d t     39 چون زمان سکفر به دست آمده براي گره 1 در اين مرحله بيشتر از زمان سفر قبلي آن است، آن را تغيير نمي دهيم 3-5- الگوریتم Out of Kilter جريان در هر شبکه به فرم بسته را مي توان به صورت فرمول 3-3 .بيان كرد (3-5) كه در آنijc هزينه سکککفر از i بهj ،ijx جريان در كمان بينi وj ،ijl حد پايين ظرفيت كمان بين i وj و ijq حد باالي ظرفيت كمان بينi وj .است فرض كنيد muR باشد. شرط بهينگي عبارتست از : (3-1) ( , ) ( , ) ij ki i j A k i AX X o  (3-1) كهiu برابر با كمترين هزينه گرهi .است براي مسکاله جريان در شبکه به فرم بسته، اين الگوريتم در هر تکرار شرط رابطه 3-1 را حفظ مي كند و به دنبال برقراري شرط رابطه 3-1 است. اين الگوريتم با يکX كه در شرطرابطه 3-1 صدق كند و يک u دلخواه شروع ميکند. كمان هايي كه در شرط رابطه 3-1 صدق ميکنند in-kilter )(در شرايط مناسب و در غير اين صورت Out of Kilt er ناميدهمي شوند . ( , )min .. 1, .., ij ij i j A ij kj jk ij ij ijimz C X st X X o l X q          0 0 0ij ij i j ij ij ij ij i j ij ij ij ij ij i j ij ijC C u u X q C C u u l X q C C u u l X                   41 جدول9 مقياسکي از ميزان OFK بودن هركمان را نشان ميدهد، كه مقدار Kilter ناميدهمي شود . اگر اين عدد براي يک كمان صکفر باشد كمان in-kilter و اگر مثبت باشد OFK .است M يک عدد بزرگ است. جدول 9 - اعداد كيلتر ij ijXq ij ijXq ij ij ijl X q ij ijXl ij ijXl ()ijij ij C X q 0 0 ()ijij ij C q X ()ijij ij C q X 0 ijC ()ij ij M X q 0 0 0 ()ij ij M l X 0 ijC ()ijij ij C X l ()ijij ij C X l ()ijij ij C X l 0 ()ijij ij C l X 0 ijC به دو طريق ميتوان مقدار Kilter يک كمانرا به نحوي كه اين مقادير براي سکاير كمان ها اضافه نشود كاهش داد. روش اول تغيير جريان است كه در آن ijX به نحويتغيير مي كند كه شرط رابطه 3-1 باقي بماند و مقادير Kilter سککاير كمان ها اضککافه نشککود. روش دوم تغيير هزينه هاي تقل يل يافته اسککت كه عبارت است از تغيير مقادير ijC (يا مقادير iu ) به نحوي كه مقادير Kilter .ساير كمان ها اضافه نشود درجدول 11 جهت جريان )ij(X به نحوي كه مقادير Kilter .كمان اضافه نشود،نشان داده شده است جدول 10- جهت مطلوب تغيير جريان ij ijXq ij ijXq ij ijXl ij ijXl ij ijXl ijq كاهش ثابت ijq افزايش ijq افزايش ij q افزايش 0 ijC ijl كاهش ijlثابت ijl ثابت ijq افزايش ijq ثابت ijq افزايش 0 ijC ijl كاهش ijl كاهش ijl افزايش ثابت افزايش qij 0 ijC 41 در جدول11 جهت تغيير هزينه تقليل به نحوي كه مقدار Kilter كمان اضکافه نشکود نشکان داده شده است: جدول 11- جهت مطلوب تغيير هزينه تقليل يافتن ij ijXq ij ijXq ij ijXl ij ijXl ij ijXl  كاهش  ثابت 0 افزايش  افزايش  افزايش 0 ijC  كاهش ثابت ثابت ثابت  افزايش 0 ijC  كاهش كاهش 0 كاهش  ثابت  افزايش 0 ijC گام هاي اين الگوريتم به صورت زير مي باشد: گام 1- )(مقدار دهي اوليه يک جريان دلخواه كه در شرط رابطه 3-1 .صدق كند و يک شبه قيمت دلخواه انتخاب كنيد گام(1)- )(كنترل اگر تمام كمانها in-kilter هسککتند، توقف كنيد ، وگرنه يک ك مان OFK مثل(k,l) انتخاب كنيد و به گام (2 .) برويد گام (2)- )(تغيير جريان از گره l شکککروع بکه سکککاختن درختي كنيد كه در كمان هاي آن بتوان جريان را تغيير داد ( در جهت مطلوب) به طوريکه مقدار Kilter هيچ كماني اضافه نشود.اگربه گرهk رسيديد، يک مسير تغيير جريان پيدا شکده كه مي توان در آن مسير و كمان (k,l) را به ميزان  تغيير داد و شرط رابطه 3-1 راحفظ كرد. به گام (1 ) برويد. اگر به گرهk نرسيديد به گام 3 .برويد گام(3)- )(تغيير هزينه تقليل يافته اگرمجموعه گره هاي درخت را با 1N و بقيه را2N نشکککا ن دهيد، كمان هاي بين 1N و2N در يکي از حاالت جدول 9 هسکتند. زيرا در غير اي صورت به درخت اضافهمي شوند ، در اين صورت ميتوان ijC اين كمکان ها را كاهش( يا افزايش) داد ، كه معادل افزايش ( يا كاهش) iu مربوطه به گره هاي در1N است، بدون اينکه مقادير Kilter آنها اضافه شود. با تغييرiu ها به اندازه كافي بزرگ (  ) يا كمان l-k به In-kilter تبديلمي شود كه در اين صورت به گام (1 ) برويد، يا يک كمان به درخت اضافهمي شود كه در اين صورت به گام (2 ) برويد. در غير اين صورت حل مساله امکان ناپذير است، توقف كنيد. 42 از آنجا كه پس از هر تغيير جريان يا تغيير هزينه تقليل يافته، مقادير Kilter حداقل يک كمان كاهش مي يابد، الگوريتم پس از تعداد محدودي تکرار متوقف مي شود. اين الگوريتم زماني ازكارايي مناسب برخوردار خواهد بود كه از اطالعات مربوطه به درختي كه در يک تکرار ساخته مي شود، در تکرارهاي بعدي هم استفاده شود. براي اين منظور، ميتوان يک جنگل گسترش كه زير شاخه هاي آن نشان دهنده مسيرهاي تغيير جريان باشند ساخت و بعد از هر تغيير جريان يا انتخاب كمان OFK آن را بهنگام كرد. همچنين نحوه نمايش ساختار جنگل گسترش، جهت سهولت حركت آن ، نقش مهمي در كارايي الگوريتم دارد. در شبکه هايي كه به فرم بسته نيستند و بردار عرضه و تقاضا در آنها صفر نباشد، براي تبديل مساله به فرم بسته ميتوان دو گره مصنوعي و چند كمان مصنوعي مطابق شکل زير به شبکه اضافه كرد. شکل 3-1- شبکه مطلوب الگوريتم OFK اطالعات كمان هاي مصنوعي يعني )ijc,ijl,ijq( را ميتوان به شکل هاي مختلفي تعريف كرد. تجربه نشان داده است كه اگر اين اطالعات به نحوه رابطه 3-1 تعريف شوند، به طوريکه فقط كمان هاي مصنوعي مربوط به گره هاي عرضه OFK شوند،الگوريتم OFK به نحو كاراتري عمل خواهد كرد. در رابطه 3-1 عبارت اول براي كمان هاي متصل به گره هاي مبدا، رابطه دوم براي كمان هاي متصل به گره هاي مقصد و رابطه سوم براي كمان متصل كننده گره مجازي مبدا به گره مجازي مقصر مي باشد. (3-1 ) , 0, ( , ,( ) ( , ,0) ) ( ,0,0) ( , , ) ( , 0,0) iij ij ijij ij ij i i ij ij ij i bi q l Cq l c b b b q l C b        معيار همگرايي در اين الگوريتم براي كمان هاي با زمان سفر متغير به صورت رابطه3-9 بيان مي شود 43 (3-9) a a a a aa aa at x t y RGtx   در اين رابطه متغيرهايax وay همان متغيرهاي الگوريتم فرانک-ولف كه در رابطه 2-12 تعريف شکککده اند، مي باشند. مثال براي درک بيشتر از نحوه به دست آوردن كوتاه ترين مسير در يک شبکه مثالي از الگوريتم OFK را در شککبکه شکککل 3-9 زير با4 گره و هفت كمانآورده شککده اسککت . اعداد روي هركمان شککماره كمان ها را مشکخص ميکندو همانطوركه قبال توضيح داده شده است q حدباالي ظرفيت كمان، l حد پايين ظرفيت كنان، c ظرفيت كمان وx جريان در هر كمان اسککت. اطالعات مسککئله شککامل حد باال و پايين ظرفيت، هزينه، جريان اوليه كمان ها و پتانسيل اوليه گره ها در جدول 12 و13 .آمده است شکل3-9- شبکه4 گره اي الگوريتم OFK جدول12- اطالعات كمان هاي شبکه 7 كمان حد باالي ظرفيت(q) (حدپايين ظرفيتl) (هزينهC) (جريان اوليهx) 44 جدول13- اطالعات گره هاي شبکه 4 3 2 1 گره 0 0 0 2 كمترين هزينه گره(u) ( گام1)- )(كنترل با محاسککبه عددهاي Kilter و با اسککتفاده از فرمول3-1 كمان هاي2 و4 و5 كمان هاي OFK و بقيه كمان ها In-kilter هستند.كمان2 راانتخاب مي كنيم كه جريان در آن بايد كاهش يابد. در نتيجه يک مسير افزايش از 1 به3 .بايد پيدا كنيم گام (2)- )(تغيير جريان از گره 1 شکککروع به سککک اختن درخت افزايش مي كنيم.( مي توان از همان درخت مرحله قبل شکککروع كرد).درخت جديد به صورت زير مي باشد. شکل 3-11- درخت مرحله اول الگوريتم OFK در نتيجه يک مسير افزايش پيدا شده ، 1 مي شود و جريان هاي جديد عبارتند از: 45 جدول14- جريان هاي بروز شده 7 6 5 4 3 2 1 كمان 3 1 2 0 0 1 2 x ( گام1) - )(كنترل كمان 2 هنوز OFK .است و جريان در آن بايد كاهش يابد گام(2)- )(تغيير جريان از گره 1 شروع به ساختن درخت مي كنيم. چون گره اي به درخت اضافه نمي شود به گام 3 مي رويم. گام(3)- )(تغيير هزينه تقليل يافته اگرمجموعه گره هاي درخت را با 1N و بقيه را2N نشکککان دهيد، كمان هاي بين 1N و2N در يکي از حاالت جدول 2-1 هستند. زيرا در غير اي صورت به درخت اضافهمي شوند ، در اين صورت ميتوان ijC اين كمکان ها را كاهش( يا افزايش) داد ، كه معادل افزايش ( يا كاهش) iu مربوطه به گره هاي در1N است، بدون اينکه مقادير Kilter آنها اضافه شود. با تغييرiu ها به اندازه كافي بزرگ (  ) يا كمان l-k به In-kilter تبديلمي شود . ={1}1N و= {2,3,4}2N اسککت. كمان هاي بين دو مجموعه 1N و2N روي شکککل نشککان داده شککده است. در نتيجه: 1 2 3 45, 0u u u u     min 3, 3    جدول 15- پتانسيل هاي بروز شده 4 3 2 1 گره 0 0 0 5 u 41 شکل3-11- درخت مرحله دوم الگوريتم OFK كمان2 In-kilter مي شود. به گام ( 1) .برويد گام(1)- )(كنترل تنهکا كمکان 5 در حالت OFK اسکککت و جريان در آن بايد كاهش يابد. در تکرارهاي بعدي، نمي توان مسيرهاي افزايش جريان پيدا كرد و تنها هزينه ها به صورت زير تغيير مي يابد. گام (3)- )(تغيير هزينه تقليل يافته 1 2 3 45, 1, 0u u u u     min 1, 1    جدول 16 - پتانسيل هاي بروز شده 4 3 2 1 گره 0 0 1 5 u شکل3-12- درخت مرحله سوم الگوريتم OFK 41 ( گام1)- )(كنترل كمان 5 در تکرار بعدي نيز OFK .است گام (3)- (تغيير هزينه تقليل يافته) 1 2 3 47, 3, 2, 0u u u u      min 2, 2    جدول 17- پتانسيل هاي بروز شده 4 3 2 1 گره 0 2 3 7 u شکل3-13- درخت مرحلهچهارم الگوريتم OFK ( گام1)- )(كنترل تمامي كمان ها In-kilter هستند. توقف كنيد. مثال براي مقايسه نتايج الگوريتم هاي Out of Kiter و فرانک-ولف ، شبکه شکل 3-9 را درنظر بگيريد. نتايج حاصل از اجراي الگوريتم هاي Out of Kilter و فرانک-ولف در جدول 11 و شکل3-15 نشان داده شده است. مقايسه شکل 3-14 به وضوح نشان مي دهد كه الگوريتم فرانک-ولف با در نظر نگرفتن ظرفيت نتايج غير منطقي از جريان در كمانها را به ما مي دهد. كمان 1 ظرفيتي برابر با2 واحد دارد . در حالي كه در الگوريتم فرانک-ولف جريان اختصاص داده شده به اين كمان 3 واحد است كه در اين صورت جريان از ظرفيت بيشتر است و هزينه سفر به بي نهايت ميل مي كند. اما الگوريتم فرانک-ولف ه زينه سفر 41 در اين كمان را1 واحد به دست داده است. اين نتايج باعث غير صحيح و غير منطقي شدن تحليل هاي انجام شده مي شود. الگوريتم Out of kilter با در نظر گرفتن ظرفيت هر كمان، جريان در هر كمان را با توجه به ظرفيت آن تنظيم مي كند و اگر جريان اوليه ورودي به يک كمان از ظرفيت ان بيشتر شود آن را بين كمان هاي ديگر پخش مي كند. يکي ار داليلي كه معموال تعداد كمان هاي بيشتري در الگوريتم Out of Kilter داراي جريان مي شوند نيز همين تنظيم جريان كمان ها مي باشد. الزم به ذكراست كه در الگوريتم OFK با هزينه سفر ثابت چون ميزان جريان از ظرفيت بيشتر نمي شود هزينه سفر برابر با هزينه ثابت كمان مي باشد. جدول 19 نيز به مقايسه هزينه كل دو الگوريتم كه برابر با مجموع حاصلضرب هزينه در جريان مي باشد، مي پردازد. همانطور كه مشاهده مي شود هزينه كل براي الگوريتم OFK بيشتر از الگوريتم فرانک-ولف استکه به علت اضافه شدن يک محدوديت به تابع هدک مي باشد. مشاهده مي شود كه تعداد كمان هاي داراي جريان در الگوريتم OFK برابر با5 كمان و در الگوريتم FW برابر با 2 كمان است كه اين نشان از توزيع جريان در الگوريتم OFK .مي باشد جدول 18- نتايج بدست آمده از الگوريتم هاي FW وOFK ( محدودیت ظرفیتq) جریان OFK FW کمان 2 2 3 1 4 1 0 2 1 0 0 3 4 2 3 4 1 0 0 5 2 1 0 6 3 3 0 7 49 شکل3-14- مقايسه جريان كمان هابراي الگوريتم هايFW وOFK جدول19- مقايسه هزينه كل بدست آمده از دوالگوريتم OFK Frank -wolfe 20 9 هزينه كل مثال براي مقايسکه بهتر دو الگوريتم، دو الگوريتم را بر شبکه اي با 12 گره و21 كمان نيزمقايسه ميکنيم. در جدول 21 اطالعات مورد نياز درباره اين شبکه را مشاهده ميکنيد. همچنين جدول21 اطالعات عرضه و تقاضا را در گره هاي اين شبکه نشان مي دهد. 51 جدول20 - اطالعات شبکه12 گره اي جريان اوليه(ax) حکککدپکککايکککيکککن ظرفيت(al) حکککککدبکککککاالي ظرفيت(aq) هزينه(aC) كمانa 0 8 8 0 1 0 7 7 0 2 0 5 5 0 3 0 0 10 2 4 0 0 5 3 5 0 0 5 2 6 0 0 5 1 7 0 0 4 2 8 0 0 5 4 9 0 0 4 2 10 0 0 10 5 11 0 0 4 2 12 0 0 4 2 13 0 0 5 3 14 0 0 10 3 15 0 0 3 1 16 0 0 3 1 17 0 0 5 2 18 0 7 7 0 19 0 6 6 0 20 0 7 7 0 21 51 جدول21- عرضه و تقاضا درمبدا-مقصد شبکه 12 مبدا-مقصد 20 1 در اين مثال به اين دليل كه شبکه به فرم چرخشي نيست يک كمان مجازي خروجي از گره 22 و ورودي به گره 1 .را به شبکه اضافه كرده ايم كه اطالعات خروجي آن نشان نداده شده است شکککل 3-15 مقايسککه بين جريان هاي كمان و ظرفيت هر كمان را به صککورت نمودار نشککان مي دهد و جدول 22 نتايج حاصل از اجراي الگوريتم هاي Out of Kilter و فرانک-ولف بر روي شبکه را نشان مي دهند. مانند مثال قبل در الگوريتم فرانک-ولف جريان در كمان هاي 3 ،14 و21 بيشتر از ظرفيت كمان ها مي باشککد . همچنين مقايسککه تعداد كمان هاي داراي جريان در شکککل 3-11 نيز نشککان مي دهد كه تعداد كمان هاي داراي جريان در الگوريتم Out of Kilter بسکککيار بيشکککتر از تعداد كمان هاي داراي جريان در الگوريتم فرانک-ولف مي باشکد. هر چه مقياس شبکه بزرگتر باشد، تفاوت در تعداد كمان هاي داراي جريان بيشتر مي شود. جدول 23 نيز به مقايسککه هزينه كل دو الگوريتم مي پردازد كه مانند مثال قبل هزين ه كل براي الگوريتم فرانک-ولف كمتر از الگوريتم OFK .مي باشد جدول 22- مقايسه نتايج بدست امده از الگوريتم هاي FW وOFK ( محدوديت ظرفيتq) جريان OFK جريان فرانک-ولف كمان 8 8 0 1 7 7 0 2 5 5 20 3 10 7 0 4 5 1 0 5 5 3 0 6 5 4 0 7 52 4 2 0 8 5 5 0 9 4 0 0 10 10 0 0 11 4 4 0 12 4 4 0 13 5 5 20 14 10 2 0 15 3 0 0 16 3 2 0 17 5 2 0 18 7 7 0 19 6 6 0 20 7 7 20 21 53 شکل3-15- مقايسه جريان در كمان ها براي الگوريتم هايFW وOFK شکل 3-11- مقايسه تعداد كمان هاي داراي جريان براي الگوريتم هاي FW وOFK 54 جدول 23 - مقايسه هزينه كل بدست آمده از دو الگوريتم OFK Frank -wolfe 94 60 هزينه كل 3-7- مسئله تخصیص همه یا هیچ در اين مسئله فرض بر اين است كه زمان سفر كمان ها ثابت و مستقل از جريان درآنها است و همچنين تمام اسکتفاده كندگان اطالع دقيقي از زمان سفر در كمان ها دارند. بر اساس اين فرضيات و اين واقعيت كه استفاده كنندگان مسيري را انتخاب مي كنند كه زمان سفر آنها را مينيمم مي كند، اين مسئله تمام جريان بين يک مبدا و مقصد مشخص را به مسيري كه كمترين هزينه سفر را دارد اختصاص ميدهد. در اين روش هربار يک زوج مبدا -مقصکد مثل (r,s) انتخاب مي شکود و سککپس همه تقاضککاي جريان به كوتاه ترين مسير از r بهs تخصيص داده مي شود. ( يعني جريان در كمان هاي روي كوتاه ترين مسير به اندازه جريان تخصيص داده شده) افزايش مي يابد. اين روش وقتي كاربرد دارد كه ميزان تراكم در شبکه بسيار كم باشد زيرا زمان سفر در كمان ها را ثابت و مستقل از جريان در نظر گرفته ايم. حال اگربخواهيم مسکئله مطرح شده در شکل 3-11 را با الگوريتم همه يا هيچ حل كنيم، فرض ميکنيم تقاضا ازگره 1 به گره4 برابر با11 واحد است. همانطور كه توسط الگوريتم هاي بلمن -فورد، دايجسترا و هيپ نشککان داديم كوتاه ترين مسککير از گره 1 به4 به ترتيب از گره هاي3،1 و4 ميگذرد. بنابراين تمام 11 .واحد جريان به اين مسير اختصاص مي يابد 3-8- مقایسه الگوریتم های بل و دایجسترا الگوريتم هاي كوتاه ترين مسير داراي مرتبه هاي مختلفي براي حل مسئله دارند. همان طور كه در فصل سوم اشاره شد الگوريتم دايجسترا از مرتبه 2()On و الگوريتم بل از مرتبه ( * )O n m است كه n برابر در سا][ با متوسط ورود هر گره به الگوريتم مي باشد. گلدنل 1911 نشان داده است كه براي شبکه هاي داراي كمتر از 1111 گره مقدار n به طورمتوسط برابر 2 مي باشد. او در اين پژوهش به مقايسه زمان حل الگوريتم هاي بل و دايجسترا درختي كه از مرتبه ( *log )O n n پرداخته است و نتيجه گيري كرده است كه زمان حل الگوريتم بل سريع تر از الگوريتم دايجسترا درختي ميباشد. نتايج حاصل از اجراي الگوريتم بل بر روي شبکه با شيکاگو 12912 گره نشان داده است كه مقدار متوسط n براي اين شبکه برابر با 4.3 55 مي باشد. جدول24 زمان حل مسئله كوتاه ترين مسير را براي 14 تکرار در الگوريتم هاي بل و دايجسترا مقايسه مي كند. الزم به ذكر است كه ساختار الگوريتم دايجسترا به گونه اي است كه در هر تکرار ، هر گره فقط يک بار كنترل مي شود. جدول 24- مقايسه زمان حل الگوريتم هاي بل و دايجسترا براي شبکه شيکاگو الگوريتم دايجسترا الگوريتم بل تکرار زمان حل هر تکرار متوسط ورود هر گره براي الگوريتم زمان حل هر تکرار تعداد ورود هر گره 23.024700 4.360036974 0.024000 56602 0 22.046100 5.712139886 0.031000 74155 1 25.018900 3.416807888 0.019000 44357 2 22.013900 5.41341858 0.029000 70277 3 23.058700 4.589431521 0.024000 59580 4 24.014900 3.911955015 0.021000 50785 5 25.072700 4.186951163 0.023000 54355 6 23.034600 4.440224927 0.024000 57643 7 22.096500 3.343013403 0.018000 43399 8 23.023700 4.2743 02881 0.023000 55489 9 24.029400 3.604914497 0.020000 46799 10 23.055600 5.317516561 0.029000 69032 11 22.087700 4.4450778 0.024000 57706 12 23.076200 3.271914959 0.018000 42476 13 همان طور كه مشکاهده ميشکود مقدار n براي شکبکه بزرگ مقياس شيکاگو بزرگ تر از عدد 2 كه در مقاله گلدن تخمين زده شککده اسککت، مي باشککد. بنابراين براي شککبکه هاي واقعي مقايسککه الگوريتم بل و دايجسکترا درختي در مقاله گلدن دقيق نمي باشکد. براي واقعي و دقيق شدن نتايج الگوريتم كوتاه ترين مسکير، اسکتفاده از الگوريتم دايجسککترا درختي براي شکبکه هاي بزرگ مقياس مانند شکبکه شککيکاگو در پژوهش هاي آينده پيشنهاد مي شود. 51 4 فصل چهارم اثر اعمال محدودیت ظرفیت کمان بر مسئله تخصیص ترافیک 51 4- 1- مقدمه همان طور كه اشککاره شککد در نظر گرفتن ظرفيت براي كمان هاي يک شککبکه حمل و نقلي باعث دقيق و واقعي تر شکدن نتايج به دسکت آمده از تحليل شکبکه مي شکود. به دليل پيچيدگي هاي ناشي از در نظر گرفتن ظرفيت براي كمان ها، تاكنون پژوهش هاي نسککبتا كمي در اين زمينه انجام گرفته اسککت. در اين فصل ابتدا به معرفي شبکه هاي حمل و نقلي كه تاكنون مسئله تخصيص ترافيک با محدوديت ظرفيت بر آنها اعمال شکده اسکت مي پردازيم،. سکپس به توضکيح سکاختارهاي اسکتفاده شکده در كد برنامه نويسي الگوريتم OFK .ميپردازيمدرنهايت نتايج حاصل از الگوريتم Out of Kilter بر روي شبکههاي هرن و سکوفالز با هزينه سکفر وابسکته به جريان مورد بررسي و تحليل قرار مي گيرند. الزم بذكر است در تعريف ساختارهاي مورد استفاده در كد برنامه نويسي الگوريتم OFK [ از پايان نامه آشتياني51 استفاده شده] .است 4-2- شبكه های حمل و نقل شبکه هاي متعددي در مسئله تخصيص ترافيک درنظرگرفته شده و مورد بررسي و تحليل قرار گرفته اند. در ادامه به معرفي ويژگي هاي سکه شکبکه كه بيشکتر از ساير شبکه در مسئله تخصيص ترافيک شناخته شده اند مي پردازيم. همانطور كه گفته شد مسئله تخصيص ترافيک با محدوديت ظرفيت داراي پيچيدگي هاي رياضي و برنامه نويسي مي باشد به همين دليل شبکه هايي كه در اين مسئله به كار گرفته شده اند معموال كوچک مقياس مي باشند. 4-2-1- شبكه هرن يکي از محبوب ترين شککبکه هاي به كارگرفته شککده در مسککئله تخصککيص ترافيک با محدوديت ظرفيت، [ شبکه هرن و ريبرا33 مي باشد. اين شبکه از]9 گره،11 كمان و4 زوج مبدا-مقصد تشکيل شده است. نمايي از اين شکبکه را در شککل 4-1 مشککاهده م ي كنيد. تقاضکا بين زوج هاي مبدا- [ مقصککد 45 در اين] شکککبکه مطابق جدول 25 [ و اطالعات ظرفيت و زمان سکککفر آزاد 45 هر كمان مطابق با جدول]21 مي باشد. 51 شکل4-1- نمايي از شبکه هرن جدول 25- عرضه و تقاضا درمبدا-مقصد شبکه هرن 4 3 مبدا/ مقصد 20 10 1 40 30 2 جدول26- ظرفيت باال و پايين و زمان سفر آزاد كمان هاي شبکه هرن حدپايين ظرفيت(al) حکککککدبکککککاالي ظرفيت(aq) هزينه(aC) كمانa 0 12.02 5 1 0 18.02 6 2 0 43.59 3 3 0 26.59 9 4 0 50.00 1 5 59 0 25.00 5 6 0 35.00 2 7 0 50.00 1 8 0 25.00 5 9 0 35.00 2 10 0 25.00 3 11 0 24.00 6 12 0 50.00 1 13 0 39.00 8 14 0 43.00 6 15 0 50.00 1 16 0 35.00 2 17 0 25.00 2 18 4-2-2- شبكه سوفالز شکبکه سوفالز به عنوان يکي از شناخته شده ترين و محبوب ترين شبکه هاي حمل و نقلي، همواره مورد توجه پژوهشکگران بوده اسکت. اين شبکه، همانطور كه در شکل 4-2 نشان داده شده است،از24 گره،11 كمان و552 زوج مبدا-مقصکد تشککيل شکده است. تقاضا در اين شبکه نيز مطابق جدول 21 [49 مي] .باشد اطالعات زمان سفر آزاد وظرفيت كمان ها نيز در جدول 21 .آورده شده است 11 شکل4-2- نمايي از شبکه سوفالز 11 جدول 27- عرضه و تقاضا در مبدا-مقصدهاي شبکه سوفالز مبدا/مقصد 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 0 1 1 5 2 3 5 8 5 13 5 2 5 3 5 5 4 1 3 3 1 4 3 1 2 1 0 1 2 1 4 2 4 2 6 2 1 3 1 1 4 2 0 1 1 0 1 0 0 3 1 1 0 2 1 3 1 2 1 3 3 2 1 1 1 2 1 0 0 0 0 1 1 0 4 5 2 2 0 5 4 4 7 7 12 14 6 6 5 5 8 5 1 2 3 2 4 5 2 5 2 1 1 5 0 2 2 5 8 10 5 2 2 1 2 5 2 0 1 1 1 2 1 0 6 3 4 3 4 2 0 4 8 4 8 4 2 2 1 2 9 5 1 2 3 1 2 1 1 7 5 2 1 4 2 4 0 10 6 19 5 7 4 2 5 14 10 2 4 5 2 5 2 1 8 8 4 2 7 5 8 10 0 8 16 8 6 6 4 6 22 14 3 7 9 4 5 3 2 9 5 2 1 7 8 4 6 8 0 28 14 6 6 6 9 14 9 2 4 6 3 7 5 2 10 13 6 3 12 10 8 19 16 28 0 40 20 19 21 40 44 39 7 18 25 12 26 18 8 11 5 2 3 15 5 4 5 8 14 39 0 14 10 16 14 14 10 1 4 6 4 11 13 6 12 2 1 2 6 2 2 7 6 6 20 14 0 13 7 7 7 6 2 3 4 3 7 7 5 13 5 3 1 6 2 2 4 6 6 19 10 13 0 6 7 6 5 1 3 6 6 13 8 8 14 3 1 1 5 1 1 2 4 6 21 16 7 6 0 13 7 7 1 3 5 4 12 11 4 15 5 1 1 5 2 2 5 6 10 40 14 7 7 13 0 12 15 2 8 11 8 26 10 4 16 5 4 2 8 5 9 14 22 14 44 14 7 6 7 12 0 28 5 13 16 6 12 5 3 17 4 2 1 5 2 5 10 14 9 39 10 6 5 7 15 28 0 6 17 17 6 17 6 3 18 1 0 0 1 0 1 2 3 2 7 2 2 1 1 2 5 6 0 3 4 1 3 1 0 19 3 1 0 2 1 2 4 7 4 18 4 3 3 3 8 13 17 3 0 12 4 12 3 1 20 3 1 0 3 1 3 5 9 6 25 6 5 6 5 11 16 17 4 12 0 12 24 7 4 21 1 0 0 2 1 1 2 4 3 12 4 3 6 4 8 6 6 1 4 12 0 18 7 5 22 4 1 1 4 2 2 5 5 7 26 11 7 13 12 26 12 17 3 12 24 18 0 21 11 23 3 0 1 5 1 1 2 3 5 18 13 7 8 11 10 5 6 1 3 7 7 21 0 7 24 1 0 0 2 0 1 1 2 2 8 6 5 7 4 4 3 3 0 1 4 5 11 7 0 12 جدول28- ظرفيت و زمان سفر آزاد كمان هاي شبکه سوفالز ظرفيت زمان سفر آزاد كمان 25.90 0.06 1 23.40 0.04 2 25.90 0.06 3 4.96 0.05 4 23.40 0.04 5 17.11 0.04 6 23.40 0.04 7 17.11 0.04 8 17.78 0.02 9 4.91 0.06 10 17.78 0.02 11 4.95 0.04 12 10 0.05 13 4.96 0.05 14 4.95 0.04 15 4.96 0.02 16 7.84 0.03 17 23.40 0.02 18 4.90 0.02 19 7.84 0.03 20 13 5.05 0.1 21 5.04 0. 05 22 10 0.05 23 5.05 0.1 24 13.91 0.03 25 13.91 0.03 26 10 0.05 27 13.51 0.06 28 4.85 0.04 29 4.99 0.08 30 4.91 0.06 31 10 0.05 32 4.91 0.06 33 4.88 0.04 34 23.40 0.04 35 4.91 0.06 36 25.90 0.03 37 25.90 0.03 38 5.09 0.04 39 4.88 0.04 40 5.12 0.05 41 4.92 0.04 42 14 13.51 0.06 43 5.12 0.05 44 14.56 0.03 45 9.59 0.03 46 5.04 0.05 47 4.85 0.04 48 5.23 0.02 49 19.68 0.03 50 4.99 0.08 51 5.23 0.02 52 4.82 0.02 53 23.40 0.02 54 19.68 0.03 55 23.40 0.04 56 14.56 0.03 57 4.82 0.02 58 5.00 0.04 59 23.40 0.04 60 5.00 0.04 61 5.06 0.06 62 5.07 0.05 63 5.05 0.06 64 15 5.22 0.02 65 4.89 0.03 66 9.59 0.03 67 5.07 0.05 68 5.22 0.02 69 5 0.04 70 4.92 0.04 71 5 0.04 72 5.07 0.02 73 5.09 0.04 74 4.88 0.03 75 5.08 0.02 76 4-2-3- شبكه آناهایم اين شبکه ار 411 گره،915 كمان و 1411 مبدا-مقصد تشکيل شده است. اين شبکه به دليل بزرگ - مقياس بودن و دشواري هاي تحليل آن براي مسئله تخصيص ترافيک با محدوديت ظرفيت ، بسيار كم مورد استفاده قرار گرفته است. 4-3- مقایسههه تحلیلی نتایم مسههئله تخصههیص ترافیک با محدودیت ظرفیت و بدون محدودیت ظرفیت هدک اين بخش بررسکي اثرات درنظر گرفتن محدوديت ظرفيت براي كمان هاي يک شبکه بر جريان در آن شککبکه مي باشککد. براي اين منظور ابتدا به تعريف ظرفيت و عوامل تاثير گذار بر آن و سککپس به نحوه 11 تعريف متغيرهاي الگوريتم Out of Kilter و ساختار داده اي آن مي پردازيم. در اين پژوهش، از روش برچسککب گذاري سککه گانه 1 براي پيمايش درخت، جداكردن يک شککاخه ا ز درخت و متصککل كردن يک شاخه به درخت استفاده شده است. 4-3-1- ظرفیت و عوامل تاثیر گذار بر آن ظرفيت هر كمان به مقدار ماكزيمم جرياني است كه آن كمان مي تواند از خود عبور دهد. واضح است كه هر مسير ظرفيت محدودي دارد كه به ويژگي هايي مانند قدرت مانور وسايل نقليه، تعداد تقاطعات مسير، عرض مسکير و مشخصات سطح راه بستگي دارد. يک كمان نمي تواند ظرفيت بي نهايت داشته باشد و به در نظر گرفتن اين ظرفيت بي نهايت براي كمان ها غير منطقي باشککد. هرچقدر جرياني كه از يک كمان عبور مي كند به ظرفيت آن كمان نزديک تر باشکد، زمان سفر در آن كمان افزايش مي يابد. همانطور كه در شککل 4-3 نشکان داده شکده اسکت اگر جريان برابر با ظرفيت كمان شود، زمان سفر آن كمان به بي نهايت ميل مي كند شکل4-3- نمودار رابطه بين جريان و زمان سفر ble Methodla- Triple 1 11 4-3-2- روش برچسب گذاری سه گانه در روش برچسککب گذاري سککه گانه به هر گره سککه برچسککب تعلق مي گيرد. ي ک جد1، يک فرزند2 و يک برادر3 براي هر گره تعريف مي شود. در هر درخت، دقيقا يک گره ريشه4 ناميده مي شود كه براي آن پدر تعريف نمي شکود. ازآنجا كه ممکن اسکت به غير از گره ريشه ، براي گره هاي ديگري نيز در درخت پدر تعريف نشککده باشککد، ما اين گره ها را ريشککه هاي يتيم 5 مي ناميم. بنابراين هر درخت از يک ريشککه و تعدادي ريشه يتيم تشکيل شده است. در هنگام اعمال الگوريتم Out of Kilter ، اين درخت را با اضافه كردن درخت هاي يتيم به درخت موجود گسترش داده مي شود. 4-3-3- ساختار شبكه در اين بخش ابتکدا به تعريف دو مفهوم نام ظرفيت بهينه1 و كمان تقويتي مي پردازيم. ظرفيت بهينه هر كمان برابر با ماكزيمم ميزان جرياني اسکت كه مي توان به يک كمان اضافه كرد و يا از آن كم كرد بدون آن كه آن كمان وارد حالت جديدي ااز Out of Kilter شود. كمان تقويتي نيز به كماني گفته مي شود كه در آن بتوان جريان را كم يا زياد كرد. در سکاختار شبکه اين الگوريتم، ما به طور مداوم اطالعات هر كمان را با توجه به نقطه ابتدا و انتهاي گره را بروز رسکاني مي كنيم. چون جستجوي يک كمان يا گروهي از كمان ها در تمام كمان هاي يک شبکه زمان بر اسککت، ما به سککاختاري كه اين عمليات را تسککريع كند نياز دا ريم. براي اين منظور از دو سککاختار براي تعريف گره ها و كمان ها استفاده مي كنيم. در ساختار اول، براي هر گره دو آرايه تعريف مي كنيم. آرايه اول به شکماره اولين كماني كه از گره خارج مي شکود و آرايه دوم به شماره اولين كماني كه به گره Predecessor 1 Successor 2 Brother 3 Root 4 Orphan roots 5 Effective Capacity 6 11 وارد مي شککود اشککاره مي كند. در سکک اختار دوم، براي هر كمان دو آرايه تعريف مي كنيم. اولين آرايه به كمان بعدي در ليسکت كه گره ابتدايي يکساني با اين كمان دارد و دومين آرايه به كمان بعدي در ليست كه گره انتهايي يکسککاني با اين كمان دارد اشککاره مي كند. اين دو سککاختار تمام كمان ها با گره ابتدايي مشترک و همچنين تمام كمان ها با گره انتهايي مشترک را به هم متصل ميکند. 4-3-4- استفاده از اطالعات پیشین در ضمن پيدا كردن يک مسير تغيير جريان از گره اي مانند l به گرهk ، ممکن است تعداد بسيار زيادي مسککير تغيير جريان يافت شککود كه به گره k ختم نمي شککوند. عالوه بر اين، ب عد از هر تغيير جريان، تنها عدد kilter تعداد كمي از كمان هاي مسککير تغيير جريان از گره l بهk كاهش مي يابد. به عبارت ديگر، يک مسکيرتغيير جريان از تعدادي مسير تغيير جريان كوچکتر تشکيل شده است. نگهداري اطالعات اين مسکيرها و استفاده از آن براي پيدا كردن يک مسير تقويتي جديد، الگوريتم را بهينه مي كند. به همين دليل، استفاده از جنگل براي استفاده از اين اطالعات مناسب به نظر مي رسد. يک جنگل از يک درخت و تعدادي درخت يتيم تشککيل شده است. ريشه درخت زماني كه در پي يافتن مسير تغيير جريان براي كمان k-l ازl بهk هستيم برابر با l مي باشد. با پيمايش در طول درخت، سعي بر اضافه كردن كمان هاي بيشتري به درخت براي يافتن گره k مي باشيم. بنابراين، براي بهبود عملکرد، زماني كه در يک درخت يتيم يک كمان تقويتي از گره i به گرهj يافت مي شود ، تمام فرزندان گرهj را نيزمي توان به درخت اضکککافه كرد. اما براي اطمينان از اينکه هر گره در جنگل تنها يک جد دارد ( هيچ حلقه اي در جنگل وجود ندارد) گره j .ابتدا بايد از جد خود جدا شکککود تا تبديل به يک گره يتيم شکککود زماني كه يک مسکککير تغيير جريان از گره l بهk يافت شکککد، براي تغيير جريان ،جريان را در همه كمان هاي تقويتي مستقيم مسير افزايش و در كمان هاي تقويتي معکوس كاهش مي دهيم ( ميران اين تغيير برابر با ماكزيمم ظرفيت بهينه يک چرخه اسکککت.). بعد از تغييرات جريان، گره فرزند هر كمان موجود در مسير كه به ظرفيت بهينه خود مي رسد بايد از جد خود جدا شود و تبديل به يک ريشه يتيم جديد شود. 19 4-3-6- روند پیمایش و برچسب گذاری زمان حل الگوريتم Out of Kilter به چگونگي و نحوه پيمايش درخت و برچسب گذاري گره ها بسيار حسکاس اسکت. دو روند كلي براي پيمايش و برچسکب گذاري در اين پژوهش اسکتفاده شده است كه در ادامه توضيح داده مي شود. يک گره زماني برچسکب گذاري مي شکود كه براي اولين بار در پيمايش درخت به آن رسيده باشيم. يک گره برچسب گذاري شده زماني اسکن مي شود كه هيچ كماني ار آن به يک گره برچسب گذاري نشده را بتوان به درخت اضکافه كرد.در روند اول، ما با توجه به سکطح پيمايش مي كنيم و به اين روند "برچسب گذاري شده در اول، اسکن شده در اول1" مي گوييم. در روند دوم، ما به سمت راست پيمايش مي كنيم و به اين روند " برچسکب گذاري شکده در آخر، اسککن شده در اول2 " مي گوييم. نتايج نشان داده است كه هرچند طول مسککير تغيير جريان براي روند اول نسککبت به روند دوم كوتاه تر اسککت ولي اين روند بسککيار كندتر از روند دوم است. در ادامه گام هاي روند دوم، كه به آن پيمايش به راست نيز گفته مي شود، توضيح داده مي شود. منظور از گره فعلي گره است كه در حال اسکن آن براي اضافه كردن كمان هاي ممکن هستيم. گام(1)- )(برچسب گذاري به راست تا حد ممکن برچسککب گذاري را به سککمت پا يين و راسککت با حركت از يک گره به تمام ف رزندانش انجام دهيد. اين كار را تا زماني كه گره j با هيچ فرزند برچسب گذاري نشده پيدا شود ادامه دهيد. گام(2)- )(جستجو كمان تقويتي اگر كمان تقويتي جديدي در شککبکه از گره فعلي به به يک گره برچسککب گذاري نشککده وجود دارد، به جستجو براي پيدا كردن كمان تقويتي جديد ادامه دهيد. در غير اين صورت به گام 3 .برويد گام(3)- )(اسکن كردن گره فعلي First Scanned- First labeled 1 First Scanned - Last labeled 2 11 گره فعلي هيچ فرزند برچسب گذاري نشده اي ندارد و در نتيجه هيچ مسير تقويتي جديد ايجاد نمي كند پس اسککن شکده اسکت. اگر گره فعلي برادر داشته باشد، از گام يک براي برادر اين گره عمليات را انجام دهيد. در غير اين صورت به گام 4 .برويد گام(4)- )(كنترل اگر گره فعلي جکد دارد از گکام يکک براي جد اين گره عمليات را انجام دهيد.در غير اين صکککورت هيچ مسيرتغيير جريان جديدي وجود ندارد و u .كمان ها بايد تغيير كند چندين گزينه براي بهبود روند جسککتجوي مسککير تغيير جريان وجود دارد. اول آنکه زماني كه يک كمان تقويتي مانند j-m ( به درخت اضافه مي شود، براي تشخيص آنکه گره موردنظرk ) در زيردرختj وجود دارد الزم است كه از گره k به سمت جدش پيمايش كنيم. يک راه براي خودداري از اين عمل استفاده از آرايه منطقي طول گره 1 براي پيگيري گره هايي در مسير بين گرهk و ريشه يتيم درخت است. دوم آنکه اين روش مي توانکد همرمان روي چندين كمان Out of Kilter به طور همزمان اعمال شکککود. ما مي توانيم به دنبال تمام مسکيرهاي تغيير جريان كه از گره l شروع مي شوند و به گرهj در كمان Out of Kilter مربوطکهl-j ختم مي شکککوند باشکککيم. اين روش نياز به كار بيشکککتري براي هر تکرار دارد ولي مسيرهاي تغيير جريان سريع تر يافت مي شوند. 4-3-5- اعمال تغییرات جریان بعد از پيدا كردن مسککير تغيير جريان از گره l به گرهk ، يک روند دو مرحله اي براي تغيير جريان مورد نياز اسکت. در مرحله اول ماكزيمم تغييرات مسکير ( ) محاسبه مي شود. در مرحله دوم تغييرات جريان اعمال مي شکود. كماني كه در مسکير به تغييرات ماكزيمم خود مي رسد از درخت تغيير جريان جدا مي شود و فرزند آن يک ريشه يتيم مي شود. length logical array- Node 1 11 4-3-7- اعمال تغییرات هزینه تقلیل یافته مکاننکد تغييرات جريکان، تغييرات هزينه مي تواند با يک روند دو مرحله اي اعمال شکککود. در مرحله اول ماكزيمم تغييرات هزينه مجاز( ) محاسبه مي شود و در مرحله دوم تغييرات هزينه اعمال مي شود. در هر مرحله همان روند پيمايش كه براي پيدا كردن مسير تغيير جريان استفاده شد را مي توان براي دست يافتن به تمام كمان هاي مياني بين گره هاي برچسب گذاري شده و برچسب گذاري نشده به كار برد. 4-3-8- شرط چرخشی1 بودن شبكه اين كد فرض مي كند كه شبکه در فرم چرخشي است. چرخشي بودن شبکه به اين معنا است كه شبکه متصککل اسککت و حداقل يک كمان به هر گره وارد مي شککود و يک كمان از آن خارج مي شککود. به عالوه، جريان خروجي از هر گره با جريان ورودي به آن برابر است. اگر يک شبکه متصل و غير چرخشي با تعدادي گره منبع2 و چاه3 باشد، مي توان آن را با اضافه كردن دو گره مصنوعي به عنوان منبع و چاه مجازي و تعدادي كمان مصنوعي آن را به يک شبکه چرخشي تبديل كرد. هر گره منبع به گره منبع مجازي با يک كمان مصنوعي متصل مي شود. مشخصات اين كمان برابر است با: 1 ). هزينه دلخواه كم (معموال يک عدد منفي بزرگ 2 . حد باالي ظرفيت معادل با مقدار عرضه گره منبع 3 .جريان اوليه و حد پايين ظرفيت صفر به طور مشابه كمان مصنوعي از گره چاه به گره چاه مجازي با پارامترهاي باال ايجاد مي شود. تنها تفاوت آن اين است كه حد باالي ظرفيت معادل با مقدار تقاضا در گره چاه است. در نهايت، يک كمان مصنوعي Circulation 1 Source 2 Sink 3 12 گره چاه مجازي و منبع مجازي را با ظرفيت باالي معادل با كل عرضه و ساير پارامترهاي مشابه باال متصل مي كند. 4-3-9- نحوه انتخاب کمان های Out of Kilter چندين روش برايچگونگي و ترتيب انتخاب الگوريتم هاي Out of Kilter ،به خصوص زماني كه كمان هاي مصکنوعي براي تبديل مسکئله به فرم گردشکي اضکافه مي شوند، وجود دارد. ما مي توانيم هزينه و ظرفيت كمان هاي مصنوعي را طوري اضافه كنيم كه 1 .تنها يک كمان Out of Kilter .بين گره چاه مجازي و گره منبع مجازي وجود داشته باشد 2 .تنها كمان هاي Out of Kilter بين گره چاه مجازي و گره منبه مجازي وجود داشته باشد 3.تنها كمان هاي مصنوعي بين گره هاي منبع و چاه وجود داشته باشد. نتايج نشکان داده اسکت كه گزينه دوم بهينه تر اسکت. دليل آن شکايد اين است كه درخت بين گره هاي بيشتري گسترش مي يابد و سريع تر عمل مي كند. 4-3-11- تحلیل و مقایسه نتایم همانطور كه در فصل دوم توضيح داده شد، در الگوريتم فرانک-ولف ابتدا با الگوريتم /A به كوتاه ترين مسکير بين زوج هاي مبدا و مقصکد تقاضکاي اوليه را اختصاص داده، و سپس بر اساس اندازه گام و جهت حركت كه براي مينيمم كردن تابع هدک به دسکت مي آيند، جريان بعدي براي هر كمان را به دست مي آوريم. اما در الگوريتم Out of Kilter ( ابتدا به هر كمان يک جريانax ( ) و هزينهac ) اختصاص داده و سکککپس در هر تکرار جريان يا هزينه تقليل يافته كمان ها طوري تغيير مي كند كه آنها را به كمان هاي In-Kilter .تبديل كند در فصل سوم نتايج حاصل از اجراي الگوريتم هاي OFK و فرانک-ولف را بر روي دو شبکه با زمان سفر ثابت نشکان داديم. اما در واقعيت زمان سکفر در كمان ها وابسته به جريان مي باشند و با افزايش جريان، افزايش مي يابند. بنابراين در ادامه نتايج حاصل از اجراي اين الگوريتم را بر روي شبکه هايي كه در آن ها زمان سفر وابسته به جريان مي باشند نشان مي دهيم. 13 همانطور كه در فصل3 اشاره شد معيار همگرايي در اين الگوريتم براي كمان هاي با زمان سفر متغير به صورت رابطه 4-1 بيان مي شود (4-1) در شکل4-4 نمايي كلي از گام هاي الگوريتمOFK .براي شبکه هاي با زمان سفر متغير آمده است شکل 4-4- مراحل الگوريتم OFK a a a a aa aa at x t y RGtx   14 همانطوركه مشاهده مي كنيد جريان هاي اوليه الگوريتم با الگوريتم همه يا هيچ بدست مي آيد و الگوريتم OFK اين قابليت را دارد كه جريان هايي را كه بيشتر از ظرفيت يک كمان باشد را به حالت امکان پذير تبديل كند و سپس الگوريتم فرانک-ولف اين جريان ها را به عنوان ورودي گرفته وجريان هاي امکان پذير از لحاظ جهت حركت را بدست مي آورد. (4-1) 0(1 ( ) )afttQ در اين رابطه0t برابر با زمان سفر آزاد،f جريان در كمان،Q ظرفيت كمان و  و  ضرايب ثابت با توجه به ويژگي هاي كمان ميباشند. در اين پژوهش 0.15 و 4 مي باشد. شبکه اول كه مورد بررسي قرار مي گيرد شبکه هرن مي باشد كه مشخصات آن در جدول 25 و21 و ساختار آن در شکل 4-1 .آمده است جريان ها و هزينه سفرهاي كمان هاي اين شبکه بدست آمده براي الگوريتم هاي مختلف در جدول 29 و31 .ارائه شده استدو الگوريتم FW و FW-OFK-INFINITECAP جريان ها و هزينه سفرهاي نزديک بهم براي كمان ها را بدست آورده اند زيرا كه ظرغيت در هر دو بي نهايت در نظر گرفته شده است. همچنين مقايسه بين هزينه كل و هزينه مصرک كن نده براي هفت الگوريتم در جدول 31 .آمده استاين الگوريتم ها برابر با الگوريتم هاي فرانک-ولف، فرانک -ولف با ظرفيت بي نهايت، تابع جريمه ديناميک براي ظرفيت بي نهايت(51) ،الگوريتم فرانک-ولف با در نظرگرفتن ظرفيت محدود براي هر كمان،تاب ع جريمه ديناميک با در نظرگرفتن ظرفيت محدود براي هر كمان(51 ) ، ALM(39 ) وIPF (39 ) .مي باشند جدول 29- جريان هاي بدست آمده از سه الگوريتمFW، FW-OFK-INFINITECAP ، FW-OFK- CAPACITATED براي شبکه هرن FW-OFK - CAPACITATED FW-OFK - INFINITECAP FW ظرفيت جريان ظرفيت جريان ظرفيت جريان 12.02 12.02 00 400 12.3517 400 12.3350 18.02 17.98 00 400 17.6482 400 17.6641 43.59 43.59 00 400 70.0000 400 70.00000 15 26.59 26.41 00 400 0.00000 400 0.00000 50.00 0.000 0 400 10.6669 400 10.5914 25.00 20.61 00 400 23.5546 400 23.57257 35.00 35.00 00 400 48.1302 400 48.1710 50.00 0.0000 400 0.000 0 400 0.00000 25.00 20.40 55 400 3.2565 400 3.2899 35.00 23.98 44 400 25.0586 400 24.9665 25.00 25.0000 400 40.000 400 40.0000 24.00 24.0000 400 23.6905 400 23.7115 50.00 5.5944 400 0.0000 400 0.00000 39.00 15.0000 400 0.0000 400 0.00000 43.00 36.0000 400 36.3094 400 36.28848 50.00 0.0000 400 0.0000 400 0.10783 35.00 33.98 44 400 40.1359 400 40.03112 25.00 25.00 00 400 33.0529 400 33.10643 جدول30-هزينه سفرهاي بدست آمده از بدست آمده از سه الگوريتم FW، FW-OFK- INFINITECAP، FW-OFK-CAPACITATED براي شبکه هرن FW-OFK - CAPACITATED FW-OFK - INFINITECAP FW 5.7500 5.8363 5.8318 6.89204 6.8280 6.8315 3.4500 5.9927 5.8812 10.313 9.0000 9.00000 1.0000 1.0003 1.0002 11 5.3438 5.5910 5.5928 2.2953 3.0728 3.0769 1.0000 1.0000 1.00000 5.4994 5.0002 5.0002 2.0466 2.0788 2.0777 3.4500 5.9491 5.9440 6.9000 6.8545 6.8566 1.000 1.0000 1.00000 8.0262 8.0000 8.00000 6.4421 6.4575 6.4509 1.0000 1.0000 1.0000 2.2055 2.5188 2.5135 2.3000 2.9166 2.9250 همان طور كه در فصل سوم عنوان شد اضافه كردن محدوديت ظرفيت به كمان ها باعث افزايش هزينه كل و هزينه مصرک كننده مي شود. اين موضوع را مي توان در جدول 31 نيز مشاهده كرد.مقدار هزينه كل و هزينه مصرک كننده براي الگوريتم هايي كه محدوديت ظرفيت كمان ها را در نظر گرفته اند بيشتر از الگوريتم هايي است كه ظرفيت را بي نهايت در نظر گرفته اند. همچنين چون در الگوريتم FW-OFK با ظرفيت بي نهايت، ظرفيت مانند الگوريتمFW درنظر گرفته نميشود، هزينه كل و هزينه مصرک كننده در اين دو الگوريتم تقريبا مشابه يکديگر مي باشد. مقايسه هزينه كل، هزينه مصرک كننده، جريان ها و هزينه هاي سفر براي اطمينان از درستي الگوريتم پيشنهادي مي باشد. همانطور كه در جدول 31 مشاهده مي كنيد الگوريتم FW-OFK در تعداد تکرار بسيار كمتري نسبت به الگوريتم FW در حالت بدون ظرفيت بهشکاک نسب ي 4-11 .ميرسد در حالت با محدوديت ظرفيت الگوريتم FW-OFK تابع هدک و هزينه كل كوچکتري نسبت به الگوريتم هاي ALM وIPF دارد. اين مقادير با مقادير بدست آمده از الگوريتم DPF .برابر است 11 جدول31- نتايجبدست آمده براي شبکه هرن Iteration RG UC TC Algorithm بدون ظرفيت 2424 4-10 1396.83 1803.59 FW 133 4-10 1396.71 1803.03 FW-OFK 56 6-10 1396.71 NA DPF 3 4-10 1572.27 1709.16 FW-OFK با ظرفيت 1682 6-10 1572.27 NA DPF 65 6-10 1572.36 1716.68 ALM 19 6-10 1572.31 1709.53 IPF در جدول23 مقادير هزينه كل، هزينه مصرک كننده،شکاک نسبي،  براي الگوريتم فرانک-ولف و ماكزيمم جريان بر ظرفيت را براي چند تکرار الگوريتم هاي FW، FW-OFK-INFINITECAP ، FW-OFK- CAPACITATED براي شبکه هرن مشاهده مي كنيد. همانطور كه مشاهده ميکنيد در دو الگوريتم اول 11 مقادير جريان برظرفيت بيشتر از يک مي باشد ولي در الگوريتم سوم حداكثر اين مقدار برابر يک مي باشد كه اين نشان از منطقي بودن جواب هاي اين الگوريتم مي باشد. همچنين نرخ همگرايي و كاهش شکاک نسبي در الگوريتم اول بسيار كمتر از الگوريتم دوم و سوم مي باشد. جدول 32- مقايسه نتايج حاصل از سه الگوريتمFW، FW-OFK-INFINITECAP ، FW-OFK- CAPACITATED در تکرار هاي مختلف براي شبکه هرن Max(v/C)  شکاک نسبي هزينه مصرک كننده هزينه كل شماره تکرار الگوريتم 2.857 0.250 0.686 2067.17 5375.85 1 FW 2.142 0.375 0.308 1520.55 2532.74 2 1.862 0.156 0.103 1426.07 1936.61 3 1.606 0.078 0.051 1410.19 1831.23 4 1.606 0.117 0.028 1406.54 1833.30 5 1.606 0.003 0.00008 1396.83 1803.59 2424 2.400 0.078 0.482 1677.88 3029.41 1 FW-OFK-INFINITECAP 1.606 0.055 0.060 1407.32 1811.60 2 1.606 0.039 0.018 1399.50 1807.02 3 1.606 0.058 0.016 1398.71 1815.70 4 1.606 0.035 0.012 1398.15 1801.08 5 1.606 0.000 3 0.0000 8 1396.71 1803.03 133 19 1.000 1.000 0.023 5 1603.30 1756.27 1 FW-OK- CAP ACITATED 1.000 0.003 0.0003 1572.33 1709.43 2 1.000 0.004 0.00004 1572.27 1709.16 3 در شکل4-5 مقايسه بين جريان هاي و شکل 4-1 مقايسه بين هزينه سفرهاي بدست آمدهاز الگوريتم هاي مختلف را در حالت بدون ظرفيت داده شده است. همانطوركه مشاهده مي كنيد جريان در اين حالت براي دو الگوريتم بسيار نزديک به هم و درچند مورد منطبق بر يکديگر است.. به علت اينکه جريان در كمان ها نزديک به هم مي باشد هزينه سفر كمان ها نيز كه در شکل 4-1 آمده است نيز به هم نزديک مي باشند. شکل 4-5- مقايسه جريان در كمان ها براي الگوريتم هايFW و FW-OFK-INFINTECAP 11 شکل4-1- مقايسه هزينهكمان ها براي الگوريتم هاي FW و FW-OFK-INFINTECAP شکل4-1 و4-1 نيز به مقايسه جريان و هزينه سفر كمان ها در حالت محدوديت ظرفيت و با محدوديت ظرفيت پرداخته اسککت . در شکککل 4-9 نسککبت جريان به ظرفيت براي الگوريتم هاي فرانک-ولف، FW- OFK .بدون ظرفيت و با ظرفيت نشان داده شده استهمانطور كه مشاهده مي كنيد جريان هاي بدست آمده از الگوريتم فرانک-ولف در بعضکي كمان ها از ظرفيت آن ها بيشکتر است كه اين نشان از غير دقيق بودن جواب هاي فرانک-ولف مي باشد. نمي توان از يک كمان با ظرفيت م حدود انتظار داشت كه جريان بيشکتري از ظرفيت خود عبور دهد بدون آنکه هزينه سکفر آن به صورت تصاعدي باال نرود.در شکل 4-1 نيزهزينه سفر براي دوحالت بدون ظرفيت و با ظرفيت آورده شده است. همانطور كه در ابتداي اين فصل گفته شککد اگر جريان از ظرفيت بيشککتر شکککود، هزينه سککفر به سکککمت بي نهايت ميل مي كند. اما در الگوريتمFW با وجود اينکه جريان از ظرفيت بيشتر شده است، هزينه سفر مقدار محدودي است كه اين نيز دليلي بر غيردقيق بودن نتايج حاصل از الگوريتم FW .دارد 11 شکل4-1- مقايسه جريان در كمان ها براي دو الگوريتم FW-OFK-CAPACITATED و FW-O FK-I N FI N I TECAP شکل4-1- مقايسه هزينه سفر كمان ها براي دو الگوريتم FW-OFK-CAPACITATED و FW-O FK-I N FI N I TECAP 12 شکل4-9- مقايسه نسبت جريان به ظرفيت براي الگوريتم هاي FW، FW-OFK-CAPACITATED و FW-OFK-I N FI N I TECAP در شکل4-11 ميزان تغييرات هزينه كل نسبت به تکرار الگوريتم در حالت بدون ظرفيت نشان داده شده اسکت. الگوريتمFW با هزينه كل اوليه بزرگتري نسبت به الگوريتم FW-OFK شروع شده و همچنين در تعداد تکرارهاي بيشتري نسبت به الگوريتم FW-OFK به جواب نهايي همگرا شده است كه دليلي بر كارايي كمتر اين الگوريتم نسبت به الگوريتم FW-OFK .دارد. شکککل 4-11 نيز تغييرات هزينه مصککرک كننده را براي دو الگوريتم FW و FW-OFK در حالت بدون ظرفيت نشککان ميدهد. مشککاهده مي شککود كه الگوريتم FW-OFK در تعداد تکرار كمتري و با هزينه مصرک كننده اوليه كمتري نسبت به الگوريتمFW به جواب نهايي همگرا مي شود 13 شکل4-11- مقايسه تغييرات هزينه كل براي دو الگوريتمFW و FW-OFK در حالت بدون ظرفيت . شکل 4-11- مقايسه تغييرات هزينه مصرک كننده براي دو الگوريتمFW و FW-OFK در حالت بدون ظرفيت در ادامه به بررسي نتايج الگوريتم OFK بر روي شبکه سوفالز مي پردازيم. همانطور كه در اين فصل ذكر شکد، شکبکه مورد اسکتفاده در الگوريتم OFK بايد چرخشکي باشد بدين معنا كه به هر گره حداقل يک كمان وارد شود و حداقل يک كمان خارج شود. بنابراين براي شبکه سوفالز كه يک سري از گره ها مبدا و يک سکري از گره ها مقصکد مي باشکند، بايد كمان هايي مجازي اضافه كرد كه به مشخصات كمان هاي اضافه شده به صورت زير مياشد: 14  براي كمان هاي مجازي ورودي به گره مبدا و خروجي از گره مبدا اصلي،حد باال، حد پايين ظرفيت و جريان كمان برابر با عرضه گره مبدا و هزينه كمان صفر تعريف مي شود.  براي كمان هاي مجازي خروجي از گره مقصککد و ورودي به گره مقصککد اصککلي ،حد باال، حد پايين ظرفيت و جريان كمان برابر با تقاضا گره مقصد و هزينه كمان صفر تعريف مي شود.  براي كمان هاي مجازي خروجي از گره مقصکد اصلي و ورودي به گره مبدا اصلي،حد باال، حد پايين ظرفيت و جريان كمان برابر با عرضه يا تقاضاي كل شبکه و هزينه كمان صفر تعريف مي شود. يکي از مشککالتي كه در حل شکبکه سکوفالز با الگوريتم OFK وجود داشت را مي توان عدم توانايي اين الگوريتم در تشکککخيص تقاضکککا به تفکيک مبدا نام برد. جريان هاي اوليه كمان هاي اين الگوريتم همان جريان هاي اوليه اي اسکت كه از الگوريتم تخصيص همه يا هيج در الگوريتم فرانک-ولف بدست مي آيد، مي باشکد. بنابراين تقاضکا در اين الگوريتم به تفکيک مبدا-مقصکد اعمال نمي شود و اين عامل باعث مي شکود كه نتايج نهايي صحيح نباشد يکي ديگر از مشکالت اين الگوريتم آن است كه در شبکه بايد به گره هاي مبدا هيج تقاضکايي وجود نداشکته باشکد و همچنين گره هاي مقصکد هيج عرضه اي نداشته باشند. براي حل اين مشکل شبکه سوفالز كوچک شده، ابتدا نتايج را براي يک مبدا و سپس براي بررسي بيشتر شکبکه را براي دو مبدا كه تقاضکاي آنها به طورجداگانه به شبکه اعمال مي شود، بدست آورده شده است در اين حالت جواب اوليه جريان كمان هاي اصلي همان جريان هاي بدست آمده از الگوريتم همه يا هيچ در فرانک-ولف مي باشکد كه به صکورت اطالعات ورودي به الگوريتم OFK .داده مي شکودبراي بدست آوردن ظرفيت كمان ها در شبکه با يک مبدا چون ظرفيت ها بسيار كوچک وغير منطقي بدست مي آمد، عرضه و تقاضا پنج برابر شده و نتايج را براي اين تقاضا ب دست آمده است. مشخصات اين شبکه در جدول 41 و42 پيوست آمده است. در اين شبکه مبدا فقط گره 1 .وبقيه گره ها مقصد مي باشند در جدول 41 تنها ظرفيت كمان هاي 39،31،34،29،11،13،11،1،4،2 افزايش يافته است و ظرفيت باقي كمان ها همان ظرفيت قبلي اسکت. در جدول 33 به مقايسکه نتايج بدست آمده از الگوريتم هايFW و OFK -FW .پرداخته شکده اسکت مانند مثال شکبکه هرن، در اين حالت نيز هزينه كل و هزينه مصرک كننده براي حالتي كه ظرفيت كمان ها محدود در نظرگرفته شده است بيشتر از حالتي است كه ظرفيت بي نهايت اسکت. همچنين در حالت بدون ظرفيت تعداد تکرارهاي الگوريتم FW-OFK براي رسيدن به دقت مورد نظر كمتر از الگوريتم هاي مشابه مي باشد كه نشان از كارا بودن اين الگوريتم است. در حالت 15 .بدون ظرفيت تعداد تکرارهاي الزم براي رسککيدن به دقت موردنظر تقريبا يکي مي باشککد در اين جدول همان طور كه قبال گفته شکد مقدار هزينه كل و هزينه مصرک كننده براي الگوريتم هاي FW وFW- OFK بدون محدوديت ظرفيت بايد يکسان باشند. در حالت با محدوديت ظرفيت نيز مقدار هزينه مصرک كننکده براي دو الگوريتم FW و FW-OFK برابر بکا هم مي باشکککند.علت بيشکککتر بودن هزينه كل در الگوريتم DPF .در نظر رفتن اثر عامل تاخير در هزينه كل در اين الگوريتم مي باشد جدول 33- نتايج بدست آمده براي شبکه سوفالز تک مبدايي Iteration RG UC TC Algorithm بدون ظرفيت 557 4-10 7.695 9.605 FW 571 4-10 7.695 9.605 FW-OFK 2 4-10 7.931 9.856 FW-OFK با ظرفيت 100 6-10 7.931 11.071 DPF در جدول34 مقادير هزينه كل، هزينه مصرک كننده،شکاک نسبي،  براي الگوريتم فرانک-ولف و ماكزيمم جريان بر ظرفيت را براي چند تکرار الگوريتم هاي FW، FW-OFK-INFINITECAP ، FW-OFK- CAPACI TATED براي شبکهسوفالز مشاهده مي كنيد. همانطور كه مشاهده ميکنيد در دو الگوريتم اول 11 مقادير جريان برظرفيت بيشتر از يک مي باشد ولي در الگوريتم سوم حداكثر اين مقدار برابر يک مي باشد كه اين نشان از منطق بودن جواب هاي اين الگوريتم مي باشد. جدول 34- مقايسه نتايج حاصل از سه الگوريتمFW، FW-OFK-INFINITECAP ، FW-OFK- CAPACITATED در تکرار هاي مختلف براي شبکه سوفالز تک مبدايي Max(v/C)  شکاک نسبي هزينه مصرک كننده هزينه كل شماره تکرار الگوريتم 3.227 0.250 0.628 10.37 24.07 1 FW 2.420 0.312 0.244 8.23 12.13 2 1.940 0.141 0.037 7.84 9.87 3 1.869 0.351 0.022 7.81 9.74 4 1.714 0.117 0.030 7.78 9.71 5 1.746 0.0005 0.0000 9 7.69 9.61 557 4.481 0.25 0.906 25.09 92.66 1 FW-OFK -INFINITECAP 3.361 0.25 0.695 12.24 29.02 2 2.521 0.375 0.390 9.16 14.71 3 2.039 0.312 0.128 8.17 10.27 4 1.781 0.0005 0.059 7.98 10.15 5 1.746 0.000 5 0.0000 9 7.69 9.61 571 1.000 1.000 0.018 8.11 10.1 1 FW-OK- CAPACI TATED 1.000 1.000 0.000 7.93 9.86 2 11 شککککل 4-12 به مقايسکککه جريان هاي بدسکککت آمده از دوالگوريتم FW و FW-OFK در حالت بدون ظرفيت مي پردازد. همانطور كه در شکککل مشککخص اسککت ، چون ظرفيت بي نهايت در نظرگرفته شککده است،جريان كمان ها در دوالگوريتم بسيار نزديک به هم و در بسياري از كمان ها برابر هم مي باشد. نتايج عددي جريان ها در جدول 31 پيوست آمده است. شکل 4-12- مقايسه جريان بدست آمده از دو الگوريتمFW و FW-OFK-INFINITECAP شککل4-13 نيز به مقايسه هزينه هايبدست آمده از دو الگوريتم FW و FW-OFK در حالت بدون ظرفيت مي پردازد. به علت نزديک بودن جريان كمان ها، هزينه هاي بدست آمده نيز بهم نزديک هستند. نزديک شدن نتايج عددي جريان و هزينه كمان ها در حالت ظرفيت بي نهايت نشان مي دهد كه الگوريتم FW-OFK بکه درسکککتي عمل مي كند زيرا كه در اين حالت در الگوريتم FW-OFK ظرفيت را مانند الگوريتم FW معمولي بي نهايت در نظر مي گيريم وبنابراين جواب ها بايد يکسکان باشکد. براي مقايسه دقيق تر، نتايج عددي هزينه كمان ها در جدول 31 .پيوست آمده است 11 شکل 4-13- مقايسه هزينه سفر بدست آمده از الگوريتم هايFW و FW-OFK-INFINITECAP در شکل4-14 مقايسه بين جريان كمان هاي بدست آمده از الگوريتم هاي FW-OFK - CAPACITATED و FW-OFK -INFINITECAP آمده است. در شکل 4-15 نيز مقايسه بين هزينه هاي بدست آمده از اين دو الگوريتم آمده است. مانند مثال هاي قبل در الگوريتم دوم در كمان هايي كه جريان از ظرفيت بيشتر مي باشد، هزينه سفر كمان ها بايد به بي نهايت ميل كند ولي ازآنجايي كه ظرفيت بي نهايت در نظر گرفته شده است هزينه سفر اين كمان ها مقدار محدودي مي باشد. اين موضوع اهميت در نظرگرفتن ظرفيت را به خوبي نشان مي دهد چرا كه در صورت در نظر نگرفتن ظرفيت تخمين شرايط براي طراحي شبکه، بهبود معابر و ساير موارد دقيق نمي باشد. نتايج عددي جريان كمان هاي بدست آمده از الگوريتم FW-OFK -CAPACITATED در جدول31 و هزينه هاي سفر در جدول 31 .پيوست آمده است 19 شکل4-14- مقايسه جريان هاي بدست آمده از دو الگوريتم FW-OFK-CAPACITATED وFW- OFK-INFINITECAP شکل4-15- مقايسه هزينه هاي بدست آمده از دو الگوريتم FW-OFK-CAPACITATED و FW-OFK- INFINITECAP 91 در شککککککل 4-11 نسکککبککت جريککان بککه ظرفيککت كمککان هککا براي سکککه الگوريتم FW، FW-OFK - INFINITECAP و FW-OFK -CAPACITATED .به نمايش گذاشکته شککده اسککت همان طور كه مشکاهده مي شکود، اين نسبت در دو الگوريتم اول، براي بعضي از كمان ها بيشتر از يک مي باشد كه كه در نتيجه بايد زمان سککفرآن ها را عدد بسککيار بزرگي بدسککت بياورد ولي از آنجا كه به دليل سککهولت ظرفيت بي نهايت در نظر گرفته شکده اسکت زمان سکفر اين كمان ها مقدار محدودي بدست آمده است. عالوه بر زمان سکک فر كمان ها ، بزرگتر بودن جريان از ظرفيت روي هزينه كل و هزينه مصککرک كننده نيز تاثير دارد و مقادير آنها را نيز بايد بسککيار بزرگ بدسککت بيايد كه در نتيجه هاي بدسککت آمده از الگوريتم هاي بدون محدوديت ظرفيت مشاهده نمي شود. شکل 4-11- مقايسه مقادير جريان بر ظرفيت براي الگوريتم هايFW، FW-OFK- CAPACITATEDو FW-OFK-INFINITECAP 91 شکل4-11 به مقايسه تغييرات هزينه كل براي دو الگوريتمFW و FW-OFK -INFINITECAP براي تکرارهاي الگوريتم مي پردازد. الگوريتم FW-OFK-INFINTECAP در شبکه سوفالز هزينه كل اوليه بيشتري نسبت به الگوريتمFW .دارد و در تعداد تکرارهاي بيشتري به دقت مورد نظر مي رسد بنابراين در مورد شبکه سوفالز با يک مبدا مي توان گفت كه الگوريتم FW كاراتر از الگوريتم FW-OFK - INFINITECAP مي باشد.در ادامهبراي اجر اي الگوريتم بر روي شبکه با ابعاد واقعي تر، به تحليل و بررسي نتايج حاصل از اعمال الگوريتم FW-OFK .بر روي شبکه سوفالز با دو مبدا مي پردازيم شکل 4- 11 نيز تغييرات هزينه مصرک كننده را براي دو الگوريتم FW و FW-OFK -INFINITECAP نشان مي دهد. در شکل 4-11 نيز مشاهدهمي شود كه الگوريتم FW با سرعت بيشتر و هزينه مصرک كننده اوليه كمتري نسبت به الگوريتم FW-OFK .همگرا مي شود شکل 4-11- مقايسهتغييرات هزينه كل براي دو الگوريتم FW و FW-OFK-INFINTECAP 92 شکل4-11- تغييرات هزينه مصرک كننده براي دو الگوريتمFW و FW-OFK-INFINTE CAP همانطور كه پيش از اين گفته شدالگوريتم OFK قادر به تشخيص تقاضا به تفکيک مبدا-مقصد نمي باشد. براي حل اين مشکل ما تقاضا را در دو مرحله به الگوريتم اعمال مي كنيم. در مرحله اول جواب هاي اوليه الگوريتم همه با هيج ناشي ار تقاضا مبدا اول به عنوان ورودي الگوريتم OFK داده مي شود وجريان ها به روز رساني مي شود و در آرايه اي جدا ذخيره مي شود. در مرحله دوم همين اقدامات براي مبدا دوم اجرا مي شود. جريان هاي بدست آمده ار مرحله اول و دوم با هم جمع شده و به عنوان ورودي به الگوريتم فرانک-ولف داده مي شود. مشخصات كمان هاي شبکه سوفالز در حالت دومبدايي در جدول 52، 53 و54 پيوستآمده است. در اين حالت نيز عرضه و تقاضا در مبدا و مقصدها پنج برابر شده است. جدول 35 نتايج اعمال الگوريتم هاي FW ، FW-OFK -INFINITECAP و FW-OFK - CAPACITATED رانشان مي دهد. در شبکه سوفالز دو مبدايي الگوريتم FW و OFK -FW- INFINTECAP با تعداد تکرارهاي نزديک به هم به دقت4-11 .مي رسند در مورد الگوريتم FW-OFK -CAPACITATED بايد اشاره كرد كه براي حل شبکه سوفالز دومبدايي همانطور كه اشاره شد ابتدا جريان هاي اوليه ناشي از تقاضا مبدا اول را به الگوريتم داده و جريان ها را بروز رساني شده سپس همين موارد براي مبدا دوم انجام مي شود. ولي بعد از اعمال الگوريتم براي مبدا اول بايد حد باالي ظرفيت اصالح شود چرا كه بعد از اعمال الگوريتم OFK براي مبدا اول جريان هايي از كمان عبور مي كنند باعث مي شوند كه حد باال كاهش يابد. اين روش براي دو مبدا قابل اجرا نيست چرا كه نمي توان حد باالي ظرفيت را تجزيه كرد. حد باالي ظرفيت را نمي توان به صورت دو عدد جدا براي دو مبدا تعريف كرد. بنابراين در اين پژوهش حد باالي ظرفيت به صورت يک عدد ثابت و بدون تغيير براي دو مبدا درنظر گرفته مي شود. در نتيجه اعدا د بدست آمده ار الگوريتم FW-OFK - CAPACITATED با الگوريتمDPF .متفاوت مي باشد هزينه مصرک كننده در اين حالت بين هزينه 93 مصرک كننده بدست آمده از الگوريتمFW وDPF مي باشد. در نتيجه جواب هاي بدست آمده از جواب هاي FW به واقعيت نزديک تر مي باشند چرا كه در اين حالتظرفيت ما بي نهايت نمي باشد بلکه ظرفيت ما يک عدد محدود مي باشد كه در بعضي كمان ها از جريان كوچکتر مي باشد. جدول 35- نتايج بدست آمده براي شبکه سوفالز دو مبدايي Iteration RG UC TC Algorithm بدون ظرفيت 1318 4-10 13.366 24.681 FW 1326 4-01 13.366 24.680 FW-OFK 637 4-10 13.402 24.511 FW-OFK با ظرفيت 500 6-10 13.688 26.964 DPF در جدول34 مقادير هزينه كل، هزينه مصرک كننده،شکاک نسبي،  براي الگوريتم فرانک-ولف و ماكزيمم جريان بر ظرفيت را براي چند تکرار الگوريتم هاي FW، FW-OFK-INFINITECAP ، FW-OFK- CAPACITATED براي شبکه سوفالز مشاهده مي كنيد. در جدول مشاهده مي كنيد كه مقدار جريان بر ظرفيت نهايي در دو الگوريتم FW و FW-OFK -INFINITECAP برابر با2.4 مي باشد در حاليکه همين مقدار در الگوريتم FW-OFK -CAPACITATED برابر با1.41 مي باشد كه نشان دهنده آن است كه جواب هاي بدست آمده از اين الگوريتم بهتر و نزديکتر به واقعيت هستند چرا كه مقدار آن ها نزديکتر به ظرفيت مي باشند. 94 جدول36- مقايسه نتايج حاصل از سه الگوريتمFW، FW-OFK-INFINITECAP ، FW-OFK- CAPACITATED در تکرار هاي مختلف براي شبکه سوفالز دو مبدايي Max(v/C)  شکاک نسبي هزينه مصرک كننده هزينه كل شماره تکرار الگوريتم 3.22 0.125 0.407 16.40 35.22 1 FW 2.82 0.187 0.197 15.19 28.55 2 2.29 0.094 0.087 14.78 25.80 3 2.53 0.094 0.087 14.68 26.08 4 2.38 0.719 0.063 14.55 25.63 5 2.40 0.000 8 0.00003 13.37 24.68 1318 4.79 0.25 0.918 39.80 148.53 1 FW-OFK -INFINITECAP 3.59 0.25 0.647 21.58 58.24 2 2.69 0.375 0.275 16.30 31.40 3 2.65 0.156 0.088 14.70 26.36 4 2.41 0.061 0.093 14.55 26.56 5 2.40 0.000 3 0.000009 13.37 24.68 1326 1.63 0.625 0.399 19.45 47.15 1 FW- OK- CAP ACI TAT ED 95 1.59 0.187 0.157 14.58 27.43 2 1.56 0.156 0.071 14.27 25.19 3 1.49 0.172 0.047 14.12 25.37 4 1.49 0.109 0.045 14.03 24.82 5 1.46 0.001 0.00009 13.40 24.51 673 در شکل 4-19 به مقايسه جريان هاي بدست آمده از الگوريتم هاي FW و FW-OFK - INFINITECAP پرداخته شده است . در اين حالت مانند شبکه هاي قبل چون ظرفيت را براي شبکه بي نهايت در نظر گرفته ايم ، جريان هاي به دست آمده از الگوريتم FW-OFK -INFINITECAP بسيار نزديک و در چندين مورد مطابق جريان هاي بدست آمده از الگوريتمFW .مي باشد نتايج عددي جريان ها در جدول 39 .پيوست آمده است شکل 4-19- مقايسه جريان هاي بدست آمده از الگوريتم هايFW و FW-OFK-INFINTECAP شکل4-21 مقايسه هزينه هاي بدست آمده از الگوريتم هايFW و FW-OFK-INFINITECAP را نشان ميدهد . در اين حالت مانند شبکه هاي قبل چون جريان هاي بدست آمده بسيار نزديک بهم مي باشد، هزينه ها نيز تفاوت كمي باهم دارند. نتايج عددي هزينه ها در جدول 41 .پيوست آمده است بدين ترتيب مي توان گفت در الگوريتم FW-OFK در صورتي كه تقاضا رادر شبکه هايي كه چند مبدا دارند 91 يا يک يا چند مبدا درآن ها جريان ورودي و يک يا چند مقصد در آن ها جريان خروجي داشته باشند به صورت مرحله اي اعمال كرد، نتايج بدست آمده را مي توان قابل استناد يافت همان طوركه در جدول 35 نيزهمين نتايج را نشان ني دهد . شکل 4-21- مقايسه هزينه هاي بدست آمده از الگوريتم هايFW و FW-OFK-INFINTECAP در شک ل 4-21 مقايسه بين جريان هاي بدست آمده از الگوريتم هاي FW-OFK - CAPACITATED و FW-OFK -INFINITECAP انجام شده است. در شکل4-22 نيز مقايسه بين هزينه سفر هاي بدست آمده از اين دو الگوريتم انجام شده است. در شکل 4-23 نيز مقادير جريان بر ظرفيت براي كمان هاي شبکه به نمايش گذاشته شده است . در اين حالت نيز مي توان گفت با و جود آنکه جريان از ظرفيت بيشتر شده است هزينه ها مقدار محدودي مي باشد. بايد توجه داشت كه براي كمان ها مقدار جريان بر ظرفيت بدست آمده از الگوريتم FW-OFK -CAPACITATED كمتر از الگوريتم FW مي باشد. نتايج عددي جريان ها و هزينه سفرهاي بدست آمده از الگوريتم FW-OFK - CAPACITATED به ترتيب در جدول39 و41 .پيوست آمده است 91 شکل4-21- مقايسه بين جريان هاي بدست آمده از الگوريتم هاي FW-OFK-CAPACITAT ED و FW-OFK-INFINITECAP شکل4-22- مقايسه بين هزينه سفر هاي بدست آمده از الگوريتم هاي FW-OFK-CAPACITATED و FW-OFK-INFINITECAP 91 شکل4-23- مقايسه مقادير جريان بر ظرفيت براي الگوريتم هايFW، FW-OFK- CAPACITATEDو FW-OFK-INFINITECAP در شکل4-24 مقايسهبين تغ ييرات هزينه كل براي دو الگوريتم FW و FW-OFKINFINITECAP را نشان مي دهد. همان طور كه در شکل مشاهده مي شود الگوريتمFW با هزينه اوليه كمتر و تعداد تکرار كمتر نسبت به الگوريتم ديگر به جواب نهايي همگرا مي شود. با توجه به اين شبکه و شبکه قبل مي توان چنين استنباط كرد كه الگوريتم FW-OFK در شبکه هايي كه ظرفيت كمان ها بينهايت باشد كارايي چنداني نسبت به الگوريتم FW ندارد چراكه هزينه اوليه بيشتري دارد و در تعداد تکرارهاي بيشتري نيز همگرا مي شود. از الگوريتم FW-OFK -INFINITECAP مي توان براي درستي اطالعات ورودي و ... استفاده كرد. 99 شکل 4-24- مقايسه تغييرات هزينه كل براي دو الگوريتمFW و FW-OFK-INFINTECAP در شکل4-25 تغييرات هزينه مصرک كننده مقايسه شده است. هزينه مصرک كننده نيز مانند هزينه كل در الگوريتم FW با تعداد تکرار كمتر و مقدار اوليه كمتري نسبت به الگوريتم FW-OFK همگرا مي شود. شکل 4-25- مقايسه تغييرات هزينه مصرک كننده براي دو الگوريتمFW و FW-OFK-INFINTECAP 111 6 فصل پنجم خالصه و پیشنهادات 111 6-1- مقدمه در اين فصل ابتدا خالصه اي از كارهاي انجام شده در اين پايان نامه ارايه شده و سپس پيشنهاداتي براي كارهاي آتي مطرح مي شوند. 6-2- خالصه هدک اين پژوهش بررسککي اهميت در نظرگرفتن ظرفيت براي كمان هاي شککبکه حمل و نقلي بر مسککئله تخصيص ترافيک مي باشد. ، تا كنون پژوهش هاي بسيار كمي به اين مسئله توجه كردند كه شايد دليل آن مشککالتي كه برنامه نويسي پيچيده و زمان حل زياد اين مسئله براي شبکه هاي بزرگ مقياس دارد، باشد . در اين پايان نامه ابتدا مسئله تخصيص ترافيک با ظرفيت محدوديت به صورت رياضي تعريف شده و نتايج حل مسکئله طراحي شکبکه براي دو شکبکه كوچک-مقياس با هزينه سکفر كمان ثابت ارائه شکد . سکپس نحوه تعريف سکاختار شبکه مورد استفاده در الگوريتم Out of Kilter بيان شده ومسئله براي شکبکه هاي معروک هرن و سوفالز با هزينه سفر كمان وابسته به جريان اعمال شده و نتايج مورد بحث و بررسککي قرار گرفته اند. نتايج نشککان داد در نظرگرفتن ظرفيت براي كمان هاي شککبکه مي تواند بر جواب مسئله بسيار موثر باشد. 6-3- پیشنهادات انجام پژوهش هاي زير در مطالعات آتي پيشنهاد مي شوند.  حل مشکل چند مبدايي الگوريتم OFK و مقايسه نتايج آن با الگوريتمFW  اعمال الگوريتم OFK براي شبکه بزرگ و مقايسه زمان حل با الگوريتم هاي DPF وFW  استفاده از جواب هاي اوليه بدست آمده از الگوريتم OFK براي الگوريتمDPF 112 پیوست 113 جدول31- جريان هاي بدست آمده از سه الگوريتمFW، FW-OFK-INFINITECAP ، FW-OFK- CAPACITATED براي شبکه سوفالز تک مبدايي FW-OFK - CAPACITATED FW-OFK - INFINITECAP FW ظرفيت جريان ظرفيت جريان ظرفيت جريان 25.90 7.16 400 9.154 400 9.156 36.84 36.84 400 34.846 400 34.844 25.90 0.00 400 0 400 0.00 7.60 6.66 400 8.653 400 8.660 23.40 0.00 400 0 400 0.00 20.91 20.91 400 19.20 400 19.173 23.40 15.42 400 15.167 400 15.171 17.11 0.00 400 0 400 0 17.78 12.81 400 13.054 400 13.053 6.51 5.60 400 3.625 400 3.619 17.78 0.00 400 0.00 400 0.00 4.95 0.00 400 1.017 400 1.01 11.81 11.81 400 11.039 400 11.043 4.96 0.00 400 0.00 400 0.00 4.95 0.00 400 0.001 400 0.00 5.16 5.16 400 8.169 400 8.166 7.84 0.00 400 0.00 400 0.00 23.40 0.00 400 0.502 400 0.502 4.90 0.00 400 0.00 400 0.00 7.84 2.30 400 3.00 400 3.00 5.05 0.00 400 0.00 400 0.00 114 5.04 0.00 400 1.172 400 1.168 10 0.00 400 0.003 400 0.00 5.05 1.14 400 8.536 400 0.002 13.91 8.17 400 0.00 400 8.541 13.91 0.00 400 0.00 400 0.00 10 0.00 400 0.00 400 0.00 13.51 0.00 400 3.336 400 0.00 5.20 5.20 400 0.00 400 3.338 4.99 0.00 400 0.00 400 0.00 4.91 0.00 400 0.00 400 0.00 10 3.53 400 1.300 400 1.297 4.91 0.00 400 0.00 400 0.00 5.50 5.50 400 5.000 400 4.993 23.40 0.00 400 0.00 400 0.00 5.92 5.92 400 5.172 400 5.171 25.90 8.50 400 8.994 400 9.00 25.90 0.00 400 0.00 400 0.00 6.00 6.00 400 6.494 400 6.500 4.88 0.00 400 0.00 400 0.00 5.12 4.00 400 3.50 400 3.493 4.92 0.00 400 0.00 400 0.00 13.51 0.00 400 0.00 400 0.00 5.12 0.00 400 0.00 400 0.00 14.56 1.50 400 1.496 400 1.496 9.59 0.00 400 0.00 400 0.00 115 5.04 0.00 400 0.00 400 0.00 4.85 0.00 400 0.001 400 0.00 5.23 2.00 400 2.004 400 2.004 19.68 0.70 400 0.003 400 0.002 4.99 0.00 400 0.00 400 0.00 5.23 0.00 400 0.00 400 0.00 4.82 0.00 400 0.004 400 0.004 23.40 0.20 400 0.001 400 0.001 19.68 0.00 400 0.00 400 0.00 23.40 0.00 400 0.003 400 0.003 14.56 0.00 400 0.001 400 0.00 4.82 0.00 400 0.00 400 0.00 5.00 0.00 400 0.00 400 0.00 23.40 0.00 400 0.00 400 0.00 5.00 0.00 400 0.00 400 0.00 5.06 0.00 400 0.00 400 0.00 5.07 0.00 400 0.00 400 0.00 5.05 1.50 400 1.50 400 1.497 5.22 2.00 400 2.50 400 2.503 4.89 0.00 400 0.00 400 0.00 9.59 0.00 400 0.480 400 0.501 5.07 0.00 400 0.00 400 0.00 5.22 0.00 400 0.00 400 0.00 5 0.00 400 0.00 400 0.00 4.92 0.00 400 0.00 400 0.00 111 5 0.00 400 0.00 400 0.00 5.07 0.00 400 0.00 400 0.00 5.09 0.00 400 0.00 400 0.00 4.88 4.00 400 4.494 400 4.50 5.08 1.50 400 1.50 400 1.50 111 جدول38- هزينه سفرهاي بدست آمده از سه الگوريتمFW، FW-OFK-INFINITECAP ، FW-OFK- CAPACITATED براي شبکه سوفالز تک مبدايي FW-OFK - CAPACITATED FW-OFK - INFINITECAP FW 0.0600 0.0601 0.0601 0.0768 0.0694 0.0695 0.0600 0.060 0 0.0600 0.0744 0.1190 0.1200 0.0400 0.0400 0.0400 0.0533 0.0495 0.0495 0.0411 0.0412 0.0411 0.0400 0.0400 0.0400 0.0208 0.0209 0.0209 0.0753 0.0627 0.0627 0.0200 0.0200 0.0200 0.0400 0.0400 0.0400 0.0646 0.0611 0.0612 0.0500 0.0500 0.0500 0.0400 0.0400 0.0400 0.0237 0.0432 0.0432 0.0300 0.0300 0.030 0.0200 0.0200 0.020 0.0200 0.0200 0.020 0.0300 0.0301 0.0301 0.1000 0.1000 0.1000 0.0500 0.0500 0.0500 111 0.0500 0.0500 0.0500 0.1000 0.1000 0.1000 0.0305 0.0306 0.0306 0.0300 0.0300 0.0300 0.0500 0.0500 0.0500 0.0600 0.0600 0.0600 0.0479 0.0413 0.0413 0.0800 0.0800 0.0800 0.0600 0.0600 0.0600 0.0501 0.0500 0.0500 0.0600 0.0600 0.0600 0.0497 0.0466 0.0466 0.0400 0.0400 0.0400 0.0791 0.0711 0.0711 0.0300 0.0300 0.0300 0.0300 0.0300 0.0300 0.0516 0.0559 0.0559 0.0400 0.0400 0.0400 0.0528 0.0516 0.0516 0.0400 0.0400 0.0400 0.0600 0.0600 0.0600 0.0500 0.0500 0.0500 0.0300 0.0300 0.0300 0.0300 0.0300 0.0300 0.0500 0.0500 0.0500 119 0.0400 0.0400 0.0400 0.0200 0.0201 0.0200 0.030 0 0.0300 0.0300 0.0800 0.0800 0.0800 0.0200 0.0200 0.0200 0.0200 0.0200 0.0200 0.0200 0.0200 0.0200 0.0300 0.0300 0.0300 0.0400 0.0400 0.0400 0.0300 0.0300 0.0300 0.0200 0.0200 0.0200 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.040 0 0.0600 0.0600 0.0600 0.0500 0.0500 0.0500 0.0600 0.0601 0.0601 0.0200 0.0202 0.0202 0.0300 0.0300 0.0300 0.0300 0.0300 0.0300 0.0500 0.0500 0.0500 0.0200 0.0200 0.0200 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 111 0.0200 0.0200 0.0200 0.0400 0.0400 0.0400 0.0320 0.0332 0.0332 0.0200 0.0200 0.0200 111 جدول39- جريان هاي بدست آمده از سه الگوريتمFW، FW-OFK-INFINITECAP ، FW-OFK- CAPACITATED براي شبکه سوفالز دو مبدايي FW-OFK - CAPACITATED FW-OFK - INFINITECAP FW ظرفيت جريان ظرفيت جريان ظرفيت جريان 25.90 1.3625 400 0.5131 400 0.5160 51.99 51.1200 400 51.075 400 51.0746 25.90 8.9824 400 8.0879 400 8.0906 11.04 11.8801 400 11.9252 400 11.9254 23.40 0.0000 400 0.0000 400 0.0000 28.80 27.9747 400 27.9530 400 27.9559 23.40 22.1452 400 22.1226 400 22.1186 17.11 0.0000 400 0.0009 400 0.0000 19.03 18.3704 400 18.4546 400 18.4542 7.76 6.1048 400 6.0005 400 6.0022 17.78 0.0005 400 0.0030 400 6.0005 4.95 4.9413 400 6.6631 400 6.6627 16.06 13.9588 400 13.7053 400 13.7066 4.96 0.0000 400 0.0000 400 0.0000 4.95 2.0302 400 3.4168 400 3.4157 7.75 11.2911 400 11.6715 400 11.6725 7.84 0.0000 400 0.0000 400 0.0000 23.40 0.4972 400 0.0112 400 0.0114 4.90 0.000 400 0.0000 400 0.0000 7.84 3.5218 400 3.089 2 400 3.0924 5.05 0.0000 400 0.0000 400 0.0000 112 5.04 3.4966 400 3.4939 400 3.4945 10 0.0000 400 0.0000 400 0.0000 5.05 1.7279 400 0.9107 400 0.9123 13.91 7.8320 400 9.2946 400 0.2943 13.91 0.0004 400 0.0000 400 0.0000 10 0.0000 400 0.0000 400 0.0000 13.51 0.0004 400 0.0020 400 0.0005 6.49 5.4741 400 5.4249 400 5.4222 4.99 0.0021 400 0.0005 400 0.0004 4.91 0.0000 400 0.00 400 0.0000 10 6.2445 400 5.6316 400 5.6288 4.91 0.0000 400 0.0000 400 0.0000 4.92 4.2301 400 4.6914 400 4.6978 23.40 0.0000 400 0.0000 400 0.0000 8.46 7.8698 400 7.8224 400 7.8244 25.90 12.7754 400 12.8002 400 12.7943 25.90 0.0000 400 0.0000 400 0.0000 8.55 8.7754 400 8.8002 400 8.7943 4.88 0.0000 400 0.00 400 0.00 5.12 2.2304 400 2.6914 400 2.6953 4.92 0.0000 400 0.0000 400 0.0028 13.51 0.0000 400 0.0000 400 0.0000 5.12 0.0000 400 0.0000 400 0.0000 14.56 1.5020 400 1.5044 400 1.5033 9.59 0.0001 400 0.0000 400 0.0000 113 5.04 0.0000 400 0.0008 400 0.0032 4.85 0.0005 400 0.0013 400 0.00 5.23 3.4971 400 3.4955 400 3.4977 19.68 0.9739 400 0.9212 400 0.9158 4.99 0.0000 400 0.00 400 0.00 5.23 0.0009 400 0.00 400 0.00 4.82 0.4985 400 0.4980 400 0.4981 23.40 0.4754 400 0.4219 400 0.4179 19.68 0.0000 400 0.00 400 0.00 23.40 0.4961 400 0.0108 400 0.0096 14.56 0.0001 400 0.0004 400 0.00 4.82 0.0002 400 0.0020 400 0.00 5.00 0.0000 400 0.00 400 0.0013 23.40 0.0003 400 0.0004 400 0.0003 5.00 0.0000 400 0.00 400 0.00 5.06 0.0000 400 0.0001 400 0.00 5.07 0.0000 400 0.0005 400 0.00 5.05 1.5042 400 1.2000 400 1.9894 5.22 3.8239 400 3.3935 400 3.4140 4.89 0.0000 400 0.0001 400 0.00 9.59 2.2709 400 1.8107 400 1.8074 5.07 0.0000 400 0.0003 400 0.00 5.22 0.0000 400 0.00 400 0.0001 5 0.0000 400 0.0002 400 0.4460 4.92 0.0003 400 0.00 400 0.0003 114 5 0.9469 400 0.9171 400 0.4474 5.07 0.0000 400 0.00 400 0.00 5.09 0.0000 400 0.00 400 0.00 5.71 5.8281 400 5.8833 400 5.9033 5.08 2.4473 400 2.4169 400 2.3909 115 جدول40- هزينه سفر هاي بدست آمده از سه الگوريتمFW، FW-OFK-INFINITECAP ، FW-OFK- CAPA CITATED براي شبکه سوفالز دو مبدايي FW-OFK - CAPACITATED FW-OFK - INFINITECAP FW 0.0600 0.060 0 0.0600 0.1766 0.176 0.176 0.0601 0.060 1 0.0601 0.2972 0.301 0.301 0.0400 0.0400 0.0400 0.0828 0.0827 0.0828 0.0448 0.0448 0.0448 0.0400 0.0400 0.0400 0.0234 0.0235 0.0235 0.0815 0.0801 0.0801 0.0200 0.0200 0.0200 0.0459 0.0597 0.0597 0.0785 0.0765 0.0764 0.0500 0.0500 0.0500 0.0402 0.0414 0.0414 0.1047 0.1167 0.1167 0.0300 0.0300 0.030 0.0200 0.0200 0.020 0.0200 0.0200 0.020 0.0302 0.0301 0.0301 0.1000 0.1000 0.1000 0.0517 0.0517 0.0517 111 0.0500 0.0500 0.0500 0.1000 0.1000 0.1000 0.0307 0.030 9 0.0309 0.0300 0.0300 0.0300 0.0500 0.0500 0.0500 0.0600 0.0600 0.0600 0.0497 0.0493 0.0493 0.0800 0.0800 0.0800 0.0600 0.0600 0.0600 0.0511 0.050 7 0.0507 0.0600 0.0600 0.0600 0.0434 0.0451 0.0451 0.0400 0.0400 0.0400 0.1190 0.1180 0.1181 0.0303 0.030 3 0.030 3 0.0300 0.0300 0.0300 0.0930 0.0936 0.0934 0.0400 0.0400 0.0400 0.0503 0.0506 0.0506 0.0400 0.0400 0.0400 0.0600 0.0600 0.0600 0.0500 0.0500 0.0500 0.0300 0.0300 0.0300 0.0300 0.0300 0.0300 0.0500 0.0500 0.0500 111 0.0400 0.0400 0.0400 0.0206 0.020 6 0.020 6 0.0300 0.0300 0.0300 0.0800 0.0800 0.0800 0.0200 0.0200 0.0200 0.0200 0.0200 0.0200 0.0200 0.0200 0.0200 0.0300 0.0300 0.0300 0.0400 0.0400 0.0400 0.0300 0.0300 0.0300 0.0200 0.0200 0.0200 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0600 0.0600 0.0600 0.0500 0.0500 0.0500 0.0607 0.060 2 0.060 2 0.0209 0.020 5 0.020 5 0.0300 0.0300 0.0300 0.0300 0.0300 0.0300 0.0500 0.0500 0.0500 0.0200 0.0200 0.0200 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 0.0400 111 0.0200 0.0200 0.0200 0.0400 0.0400 0.0400 0.0391 0.0395 0.0396 0.0200 0.0200 0.020 1 119 جدول41-مشخصات كمان هاي شبکه سوفالز تک مبدايي ظرفيت زمان سفر آزاد كمان 25.90 0.06 1 36.84 0.04 2 25.90 0.06 3 7.60 0.05 4 23.40 0.04 5 20.91 0.04 6 23.40 0.04 7 17.11 0.04 8 17.78 0.02 9 6.51 0.06 10 17.78 0.02 11 4.95 0.04 12 11.81 0.05 13 4.96 0.05 14 4.95 0.04 15 5.15 0.02 16 7.84 0.03 17 23.40 0.02 18 7.84 0.02 19 4.90 0.03 20 121 5.05 0.1 21 5.04 0.05 22 10 0.05 23 5.05 0.1 24 13.91 0.03 25 13.91 0.03 26 10 0.05 27 13.51 0.06 28 5.19 0.04 29 4.99 0.08 30 4.91 0.06 31 10 0.05 32 4.91 0.06 33 5.49 0.04 34 23.40 0.04 35 5.92 0.06 36 25.90 0.03 37 25.90 0.03 38 6.00 0.04 39 4.88 0.04 40 5.12 0.05 41 4.92 0.04 42 121 13.51 0.06 43 5.12 0.05 44 14.56 0.03 45 9.59 0.03 46 5.04 0.05 47 4.85 0.04 48 5.23 0.02 49 19.68 0.03 50 4.99 0.08 51 5.23 0.02 52 4.82 0.02 53 23.40 0.02 54 19.68 0.03 55 23.40 0.04 56 14.56 0.03 57 4.82 0.02 58 5.00 0.04 59 23.40 0.04 60 5.00 0.04 61 5.06 0.06 62 5.07 0.05 63 5.06 0.06 64 122 5.22 0.02 65 4.89 0.03 66 9.59 0.03 67 5.07 0.05 68 5.22 0.02 69 5 0.04 70 4.92 0.04 71 5 0.04 72 5.07 0.02 73 5.09 0.04 74 4.88 0.03 75 5.08 0.02 76 123 جدول42- عرضه و تقاضا در مبدا-مقصدهاي شبکه سوفالز تک مبدايي 1 مبدا/مقصد 0.5 2 0.5 3 2.5 4 1.0 5 1.5 6 2.5 7 4.0 8 2.5 9 6.5 10 2.5 11 1.0 12 2.5 13 1.5 14 2.5 15 2.5 16 2.0 17 0.5 18 1.5 19 1.5 20 0.5 21 2.0 22 1.5 23 0.5 24 124 جدول43- مشخصات كمان هاي شبکه سوفالز دو مبدايي ظرفيت زمان سفر آزاد كمان 25.90 0.06 1 51.99 0.04 2 25.90 0.06 3 11.04 0.05 4 23.40 0.04 5 28.80 0.04 6 23.40 0.04 7 17.11 0.04 8 19.03 0.02 9 7.76 0.06 10 17.78 0.02 11 4.95 0.04 12 16.06 0.05 13 4.96 0.05 14 4.95 0.04 15 7.75 0.02 16 7.84 0.03 17 23.40 0.02 18 4.89 0.02 19 7.84 0.03 20 125 5.05 0.1 21 5.04 0.05 22 10 0.05 23 5.05 0.1 24 13.91 0.03 25 13.91 0.03 26 10 0.05 27 13.51 0.06 28 6.49 0.04 29 4.99 0.08 30 4.91 0.06 31 10 0.05 32 4.91 0.06 33 4.91 0.04 34 23.40 0.04 35 8.64 0.06 36 25.90 0.03 37 25.90 0.03 38 8.55 0.04 39 4.88 0.04 40 5.12 0.05 41 4.92 0.04 42 121 13.51 0.06 43 5.12 0.05 44 14.56 0.03 45 9.59 0.03 46 5.04 0.05 47 4.85 0.04 48 5.23 0.02 49 19.68 0.03 50 4.99 0.08 51 5.23 0.02 52 4.82 0.02 53 23.40 0.02 54 19.68 0.03 55 23.40 0.04 56 14.56 0.03 57 4.82 0.02 58 5.00 0.04 59 23.40 0.04 60 5.00 0.04 61 5.06 0.06 62 5.07 0.05 63 5.06 0.06 64 121 5.22 0.02 65 4.89 0.03 66 9.59 0.03 67 5.07 0.05 68 5.22 0.02 69 5 0.04 70 4.92 0.04 71 5 0.04 72 5.07 0.02 73 5.09 0.04 74 4.88 0.03 75 5.08 0.02 76 121 جدول44- عرضه و تقاضا در مبدا اول شبکه سوفالز دو مبدايي 1 مبدا/مقصد 0.5 2 0.5 3 2.5 4 1.0 5 1.5 6 2.5 7 4.0 8 2.5 9 6.5 10 2.5 11 1.0 12 2.5 13 1.5 14 2.5 15 2.5 16 2.0 17 0.5 18 1.5 19 1.5 20 0.5 21 2.0 22 1.5 23 0.5 24 129 جدول45- عرضه و تقاضا در مبدا دوم شبکه سوفالز دو مبدايي 2 مبدا/مقصد 0.5 1 0.5 3 1.0 4 0.5 5 2.0 6 1.0 7 2.0 8 1.0 9 3.0 10 1.0 11 0.5 12 1.5 13 0.5 14 0.5 15 2.0 16 1.0 17 0.0 18 0.5 19 0.5 20 0.0 21 0.5 22 0.0 23 0.0 24