دانلود مقاله روش گرادیان

در گذشته تعداد زیادی مدلهای مختلف با استفاده از مطالب مشاهده شده در جهت برآورد یا تنظیم ماتریسهای 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 استفاده می شود .

در نهایت ما نتایج برخی کاربردهای در مقیاس شهری و ملی را که در آنها مدل جدید ما اخیراً استفاده شده را خلاصه می کنیم .

روش گرادیان : در این مقاله یک نوع جدید از مدلها پیشنهاد شده است .

همچنین بعنوان یک مسئله اپتیمم سازی فرموله شده است .

اما در اینجا تابع هدف برای اینکه حداقل سازی شود آنرا در فاصله بین حجمهی مشاهده شده و انتخاب شده در نظر گرفته ایم .

آسان ترین تابع از این نوع جذر جمع اختلاف ها ، که به مسئله حداقل سازی هدایتمان می کند می باشد .

(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 توسط حل کردن یک مسئله جانبی یک بعدی قابل پیدا شدن است .

for all with ، از آنجائیکه تابع سفر Z در اصطلاح حجم سفرها بیان می شود ، ما نیاز داریم بدانیم چگونه اینها در طول جهت گرادیان تغییر می کنند .

این کار توسط اعمال قانون زنجیره ها بر فرمول زیر قابل انجام است : حل کردن مسئله حداقل سازی (12) قابل انجام توسط پیدا کردن صفر در مشتق است.

با اعمال مجدد قانون زنجیره ها مشتق را به شکل زیر بدست می آوریم : این ما را به طرف طول مرحله اپتیمم هدایت می کند : (16) برای اینکه دقیق باشد باید چک شده و به تدریج به فرمول B متصل شود .

با تساویهای 11 ، 15 و 16 ما تمامی نتایج لازم برای حل مسئله ماتریس(1) با استفاده از روش گرادیان نسبی را خواهیم داشت .

اجرا : یک مشکل اصلی عملی برای اعمال برآورد ماتریسی مدلها در عمل ناشی از این حقیقت است که اکثر مدلها تنها می توانند در برنامه های خیلی تخصصی کامپیوتری اجرا شوند که بدست آوردن‌ آنها و عملیات با آنها مشکل است .

این در صورتی است که اصلاً این برنامه ها وجود داشته باشند .

در این بخش ما نشان می دهیم که روش گرادیان با استفاده از نسخه استاندارد نرم افزار برنامه ریزی حمل و نقل که بطور گسترده مورد استفاده است یعنی EMME/2 قابل اجرا است .از انتشار نسخه 3.0 از EMME/2 که در اکتبر 1987 منتشر شد .

تا کنون یک مورد از مدل انتخاب تعادل خودرو که شناخته شده بنام انتخاب موارد اضافی است در دسترس قرار گرفته است .

هدف این مورد ایجاد یک چارچوب کاری برای محاسبات مشابه سازی از مسیرهای مختلف وابسته به اطلاعاتی است که ممکن است علاوه بر نتایج انتخاب های معمول مورد احتیاج باشد .

اجازه دهید بطور خلاصه به تعبیرهای ریاضی در این مورد از EMME/2 نگاه کنیم .

(اصطلاحاتی که به آنها تکیه شده ، نشان دهنده اسم گذاری استفاده شده در EMME/2 می باشد .

) برای هر مسیر تولید شده در طول انتخاب تعادل نرمال یک اصطلاح سیر اضافی توسط متحد کردن اصطلاحات سفرهای اضافی از کل مسیر تا نشانگر محاسبه شده است .(که البته می توان با علائم دیگر همچون و ، می نیمم یا ماکزیمم آن را نشان داد ) .

(17) ، ، با چک کردن اصطلاح مسیر در برابر مقطع آستانه ای مسیر خاص ( و ) بدست می آید که آیا مسیر در انتخاب بعدی از درخواست