تحقیق در مورد روش گرادیان

بخشی از مقاله

روش گراديان

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

در اين مقاله ما يك مدل بر پايه گراديان كه قابل اعمال در شبكه هاي در بعد بزرگ است ارائه مي كنيم . از نظر زياضي مدل به شكل يك مسئله حداقل سازي محدب در جائيكه توسط دنبال كردن جهت نزولي ترين شيب ما مي توانيم تضمين كنيم كه ماتريس OD اصلي بيش از حد لازم تغيير پيدا نكرده است ، فرموله شده است .

ما نمايش مي دهيم كه چگونه اين تنظيم مدل درخواستي مي تواند بدون احتياج به گسترش هيچگونه نرم افزار جديد اجرا شود . بلكه تنها توسط استفاده از اقلام موجود از يك بسته برنامه ريزي حمل و نقل قابل اجرا خواهد بود . از آنجائيكه يك قلم از مراحل تنظيم اساساً در دو انتخاب تعادلي در شبكه م.ورد نظر وجود دارند ، اين روش حتي در شبكه ها و ماتريس ها در مقياس بزرگ قابل اعمال است . تا به اينجا ، مدلها بطور موفقي در چندين پروژه ملي و شهري در سوئيس ، سوئد و فنلاند با استفاده از شبكه هايي تا حد 522 منطقه ترافيكي و 12460 سفر اعمال شده است . برخي از نتايج اين مطالعه نشان داده خواهد شد .
كلمات كليدي : برآورد ماتريس O-D ، انتخاب تعادلي ، روش گراديان .

مقدمه :
تقريباً در تمامي كاربردهاي برنامه ريزي حمل و نقل ، اطلاعات ورودي كه بدست
مي آيد نشان از همه چيز مشكل تر و گران تر است . ماتريس درخواست مبدا - مقصد است . از آنجائيكه اطلاعات درخواستي بطور مستقيم قابل مشاهده نيست ، بايد توسط تحقيقات دقيق و گران قيمت جمع آوري شود كه درگير با مصاحبه هاي در منزل و در جاده ها يا روشهاي پيچيده علامت گذاري يا نشانه گذاري است . برعكس حج سفرهاي مشاهده شده به آساني و با دقت قابل قبولي توسط شمارش در نقاط خاصي از سفر يا دستي يا اتوماتيك با استفاده از دستگاههاي شمارنده مكانيكي يا القايي قابل بدست آمدن است . بنابراين تعجب آور نيست كه مقدار چشم گيري از تحقيقات در جهت بررسي احتمال برآورد يا بهبود يك ماتريس درخواست مبدا - مقصد با
حجم هاي مشاهده شده روي سفرهايي در شبكه مورد نظر انجام مي شود .
تعداد زيادي از مدلها در گذشته پيشنهاد شده است . Vanvilet - (1980) willumsen , vanzuylen و (1981)willumsen - (1982)Nguyen - Vanzuylen و Branston (1982) - (1987)spiess . اين مدلها در حاليكه خيلي از لحاظ تئوريكي جالب هستند ، تاكنون از لحاظ عملي ارتباط كمي داشته اند . اين ناشي از زمان زيادي است كه صرف محاسبات مي شود و كاربرد در مسائل در بعد كوچك است . آنچه كه ما خيلي خوب مي دانيم اين است كه هيچكدام از اين روشها بطور موفق به شبكه هاي در ابعاد وسيع و بزرگ با صدها منطقه ترافيكي و هزاران سفر شبكه اي اعمال نشده است . اكثر اين روشهاي سنتي به شكل مسائل اپتيمم سازي كه در آنها تابع هدف هماهنگ با برخي توابع فاصله بين يك ماتريس درخواست اوليه و درخواست نتيجه شده g قابل فرموله شدن هستند . سپس مسائل محدود كننده در جهت نزديك كردن حجم هاي انتخاب شده به حجم هاي مشاهده شده در نقاط شمارش استفاده مي شوند . (توجه داشته باشيد كه برخي فرمولاسيون ها VanZuylen و (1982)Branston مسائل محدود كننده در آنها دخيل مي شوند و بنابراين بعنوان اصطلاحات اضافي در توابع هدف ظاهر مي شوند . )
در بخشهاي زير ما يك مدل جديد كه مناسب براي كاربردهاي در مقياس بزرگ است را تشريح مي كنيم . ما نشان مي دهيم كه چگونه اين مدل بدون احتياج به گسترش هيچگونه برنامه جديدي قابل اجرا است ، اما به جاي آن با استفاده از نسخه استاندارد از بسته برنامه ريزي حمل و نقل EMME/2 استفاده مي شود . در نهايت ما نتايج برخي كاربردهاي در مقياس شهري و ملي را كه در آنها مدل جديد ما اخيراً استفاده شده را خلاصه مي كنيم .

روش گراديان :
در اين مقاله يك نوع جديد از مدلها پيشنهاد شده است . همچنين بعنوان يك مسئله اپتيمم سازي فرموله شده است . اما در اينجا تابع هدف براي اينكه حداقل سازي شود آنرا در فاصله بين حجمهي مشاهده شده و انتخاب شده در نظر گرفته ايم . آسان ترين تابع از اين نوع جذر جمع اختلاف ها ، كه به مسئله حداقل سازي هدايتمان مي كند مي باشد .
(1)
(2)
در جائيكه تابع assign(g) براي نشان دادن حجمهاي نتيجه شده از يك انتخاب از ناتريس درخواست g است . البته مدل خاص استفاده شده بايستي هماهنگ با يك مسئله اپتيمم سازي باشد تا فرمول «1» مهدب (Conver x) باشد . به خاطر اين مقاله ما بايد فرض كنيم كه اصطلاح «انتخاب» همان انتخاب تعادل است . در جائي كه يك سري از توبع هزينه سفر غير كاهش يابنده در تمامي سفرهاي شبكه محدب بودن مدل راتضمين نمايد . اين نوع از مسائل انتخاب تعادلي بطور گسترده اي مورد مطالعه قرار گرفته است و بطور بهره وري قابل حل هستند يا با تقريب خيلي پشت سرهم و يا با روش pARTAN كه روش جديدي است .

از آنجائيكه مسئله برآورد ماتريس همانطوريكه در شماره 10 فرمولارائه شده است خيلي زير حد واقعي بدست مي آيد . معمولاً تعداد محدودي حدهاي اپتيمم وجود دارد بعنوان مثال ماتريسهاي درخواست امكان پذير كه تمامي آنها حجمهاي مشاهده شده را به مساوات منعكس مي كنند . البته در برنامه ريزي هاي واقعي از ماتريس نتيجه شده انتظار داريم هر چقدر ممكن است به ماتريس اوليه نزديك باشد ، آنجائيكه شامل اطلاعات ساختاري مهمي در حركات مبدا - مقصد است . بنابراين تنها پيدا كردن يك راه حل براي مسئله«1» به وضوح كافي نيست .

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

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

در آسانترين مورد وقتي كه گراديان را مستقيماً نسبت به متغيرهاي g اعمال مي كنيم روش گراديان به شكل زير قابل فرموله شدن است :
(3)
در جائيكه بايد به قدر كافي كوچك اختيار شود تا تضمين كند مسير دنبال شده توسط بطور چشمگيري به مسير اصلي گراديان نزديك است . توجه داشته باشيد كه ما انديس i را براي نشان دادن يك جفت مبدا - مقصد (O-D) استفاده مي كنيم و اينكه سري تمام جفت O-D هاي فعال I است .
بهرحال اگرگراديان بر پايه متغيرهاي g همانطوريكه در فرمول (3) آمده است باشد اين نشانگر اين مسئله است كه تغييرات در ماتريس درخواست از راه مطلق اندازه گيري مي شود . بعنوان مثال تعداد مسافرت ها گذشته از تغيير مرتبط با اين معنا خواهد بود كه همان ماتريس اوليه است . بخصوص اين نشان خواهد داد كه جفت هاي O-D با توسط تنظيم هم به خوبي تحت تاثير قرار مي گيرد . براي بدست آوردن يك روش واقع گرايانه تر ، گراديان بايد بر پايه تغيير نسبي درخواست كه مي توان آنرا به شكل زير نوشت باشد :

(4)
توجه داشته باشيد وقتي گراديان نسبي استفاده مي شود الگوريتم در قابل ضرب مي شود . بنابراين يك تغيير در درخواست متناسب بادرخواست در ماتريس اوليه است و بخصوص صفرها توسط فرآيند حفظ مي شوند .

قبل از اينكه توجهمان را بر برآورد گراديان معطوف مي داريم ، اجازه دهيد اول به تجزيه و تحليل حجم سفرها در مسير در حال جريان نگاه مي كنيم . اجازه دهيد سري مسيرهاي استفاده شده براي هر جفت را با i و و نشان دهيم . حجم سفرها قابل بيان شدن به شكل زير خواهد بود :
(5) و
در جائيكه :
(6)
با استفاده از احتمالات مسير به جاي جريان مسير داريم :
(7) و ،
تساوي (5) ، قابل دوباره نويسي به شكل زير است :
(8) ،
حالا ما مي توانيم به جلو برويم و گراديان را محاسبه كنيم . با گرفتن مشتق از فرمول (1) بدست مي آوريم :
(9) ،
با فرض اينكه احتمالات مسير بطور محلي ثابت هستند ما از فرمول (8) بدست
مي آوريم :
(10) و و
كه در فرمول (9) جايگزين شده و مي دهد :
(11) ،
براي اجراي روش گراديان (4) ما همچنين نياز به ايجاد مقاديري براي طولهاي مرحله اي خواهيم داشت . با انتخاب مقادير بسيار كوچك براي طول مرحله اين فرصت را خواهيم داشت كه مسير گراديان دقيق تري داشته باشيم ، اما داراي اين ضعف خواهيم بود كه مراحل بيشتري مورد نياز خواهد بود . از طرف ديگر وقتي كه مقادير بيش از اندازه بزرگ براي طول مرحله انتخاب مي كنيم ، تابع هدف در واقع
مي تواند افزايش يابد و هماهنگي الگوريتم از دست مي رود . بنابراين طول مرحله بهينه در درخواست داده شده g توسط حل كردن يك مسئله جانبي يك بعدي قابل پيدا شدن است .
(12)
(13) for all with ،
از آنجائيكه تابع سفر Z در اصطلاح حجم سفرها بيان مي شود ، ما نياز داريم بدانيم چگونه اينها در طول جهت گراديان تغيير مي كنند . اين كار توسط اعمال قانون زنجيره ها بر فرمول زير قابل انجام است :
(14)
حل كردن مسئله حداقل سازي (12) قابل انجام توسط پيدا كردن صفر در مشتق است. با اعمال مجدد قانون زنجيره ها مشتق را به شكل زير بدست مي آوريم :
(15)
اين ما را به طرف طول مرحله اپتيمم هدايت مي كند :
(16)
براي اينكه دقيق باشد بايد چك شده و به تدريج به فرمول B متصل شود .
با تساويهاي 11 ، 15 و 16 ما تمامي نتايج لازم براي حل مسئله ماتريس(1) با استفاده از روش گراديان نسبي را خواهيم داشت .