بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
مسیریابی بهینه خطوط مترو با استفاده از شبکه هاي عصبی مصنوعی
چکیده
مسیریابی سیستم هاي حمل و نقل عمومی سریع، تعیین امتدادي براي حرکت وسیله نقلیه عمومی سریع با کارایی بالا و حداقل عوارض در یک شهر است. تلاش هاي اخیر در زمینه طراحی خطوط و مسیریابی سیستم هاي سریعاکثراً در جهت استفاده از روش هاي ابتکاري و فرا ابتکاري سوق یافته است. این روش ها به علت فقدان پیچیدگی ها و سرعت عمل بالاي خود در حل مسائل مختلف مورد توجه محققین قرار دارند. ازجمله الگوریتم هاي جدیدي که درسال هاي اخیر براي افزایش سرعت محاسبات و نیز مدل سازي بکار گرفته شده است، شبکه هاي عصبی می باشد. برتري عمده شبکه هاي عصبی نسبت به محاسبات کلاسیک این است که نتایج مورد نیاز با تلاش کمتر و در زمان کوتاهتري قابل حصول است. بنابراین براي مسائلی که مستلزم محاسبات طولانی هستند، بسیار مفید و مؤثر واقع می گردند. در این مقاله مسیریابی خطوط مترو با استفاده از شبکه هاي عصبی مورد بررسی قرار گرفته است. شبکه عصبی بررسی شده در این تحقیق، شبکه هاپفیلد پیوسته می باشد که براي مسائل بهینه سازي با محدودیت، مورد استفاده قرار می گیرد. در پایان، روش ارائه شده در قالب یک مطالعه موردي ارزیابی شده است.
کلید واژه: مسیریابی، شبکه هاي عصبی مصنوعی، شبکه هاپفیلد، تابع انرژي.
-1 مقدمه
امروزه با توجه به افزایش بسیار زیاد هزینه هاي توسعه شبکه خیابانی براي استفاده وسایل نقلیه شخصی و پیامدهاي منفی وسیع آن، توسعه سیستم هاي حمل و نقل همگانی به عنوان یک راه حل اصولی براي شهرهاي بزرگ محسوب می شود و در بسیاري از شهرهاي با بیش از یک میلیون نفر جمعیت، علاوه بر اتوبوس از سیستم هاي دیگري نیز استفاده می شود. این سیستم ها براي نیل به اهداف متفاوتی از جمله افزایش راحتی و امنیت سفر، کاهش آلودگی هوا و حفظ محیط زیست، کاهش زمان سفر و حل مشکلات ترافیکی ناشی از تردد وسایل نقلیه شخصی ایجاد می شوند.
از میان سیستم هاي حمل و نقل همگانی، مترو به دلیل امتیازات عملکردي اش نسبت به سایر سیستم ها، در شهرهاي بزرگ بیشتر مورد توجه قرار گرفته است. مترو سیستمی است کهکاملاً در مسیرهاي خاص و جدا از سایر وسایل نقلیه و عابرین حرکت می کند و مسیر آنعمدتاً در زیر زمین است. از جمله امتیازات و ویژگی هاي مترو می توان به موارد زیر اشاره کرد:
1. سرعت و شتاب بالاي سیستم
2. ظرفیت بالا نسبت به سایر سیستم هاي حمل و نقل همگانی
3. سرفاصله هاي کوتاه، برنامه زمانی منظم و قابلیت اطمینان سیستم
4. ایمنی و آرامش مسافرین و هزینه سفر نسبی پایین
5. حریم انحصاري و منفک بودن از ترافیک سطحی
6. جدا بودن مسیر و ایستگاه ها از شرایط آب و هوایی
7. امکان اتصال و تغذیه با سیستم اتوبوسرانی
8. حداقل عوارض زیست محیطی
مترو به طور مستقیم و غیر مستقیم سبب اثراتی چون توسعه شهر، تحرك مراکز اقتصادي، تغییر الگوي سفر کاربري زمین و غیره می شود که با برنامه ریزي صحیح و هدف دار می توان این اثرات را در جهت مطلوب سوق داد. بنابراین طراحی صحیح سیستم مترو به خصوص مسیریابی خطوط از اهمیت ویژه اي برخوردار است. تلاش هاي اخیر در زمینه طراحی خطوط و مسیریابی سیستم هاي سریعاکثراً در جهت استفاده از روش هاي ابتکاري و فرا ابتکاري سوق یافته است. عدم نیاز به تحلیل هاي وقت گیر شبکه و رهایی از انجام الگوریتم هاي بهینه سازي مرسوم با محاسبات سرسام آور از فواید این روش هاست .[1]
ازجمله الگوریتم هاي جدیدي که درسال هاي اخیر براي افزایش سرعت محاسبات و نیز مدل سازي بکار گرفته شده است، شبکه هاي عصبی می باشد. برتري عمده شبکه هاي عصبی نسبت به محاسبات کلاسیک این است که نتایج مورد نیاز با تلاش کمتر و در زمان کوتاهتري قابل حصول است. بنابراین براي مسائلی که مستلزم محاسبات طولانی هستند، بسیار مفید و مؤثر واقع می گردند. در این تحقیق مسیریابی خطوط مترو با استفاده از شبکه هاي عصبی انجام شده است.
-2 پیشینه تحقیق
تا کنون چندین روش به منظور طراحی و مسیریابی شبکه خطوط حمل و نقل سریع توسط پژوهشگران مختلف ارائه شده است. یکی از اولین تحقیقات انجام شده در زمینه مسیریابی خطوط حمل و نقل سریع، رساله دکتري دیسزار1 در سال 1970 است. دیسزار مسئله را به صورت یافتن مسیري با کمترین هزینه بین مبدأ و مقصد مطرح نموده و آن را مدل کرد.روش دیسزار با ارائه یک روش جدید توسط کورنت2 و همکارانش در سال 1985 بهبود بخشیده شد .[2] کورنت مسیري را با حداکثر پوشش و حداقل طول مورد مطالعه قرار داد و دو مدل کوتاه ترین مسیر با حداکثر پوشش3 و مدل کوتاه ترین مسیر با حداکثر جمعیت4 را ارائه نمود. هر دو مدل گزینه ها را با توجه به هزینه هاي ساخت و میزان منافع اجتماعی ارزیابی می کنند و به صورت برنامه ریزي عدد صحیح مدل سازي شده اند.
دافورد5 و همکارانش در سال 1996 مکان یابی یک خط حمل و نقل سریع را توسط الگوریتم جستجوي ممنوع6 مورد توجه قرار دادند .[3] تابع هدف در این الگوریتم، ماکزیمم نمودن پوشش جمعیتی مسیر می باشد. برونو7 و همکارانش در سال 1998 مدلی ارائه کرده اند که در آن مد وسیله نقلیه شخصی را رقیب سیستم حمل و نقل سریع همگانی فرض می نمود .[4] در این مطالعه فرض بر آن است که کاربران، سیستم هاي مختلف حمل و نقل را به گونه اي انتخاب می کنند که هزینه هاي آنها کمینه شود.
برونو و همکاران در سال 2002 مطالعه دیگري را انجام داده اند که در آن هدف، بیشینه کردن جمعیت پوشش داده شده توسط مسیر بوده است .[5] لاپورته8 و همکارانش در سال 2005 مفهوم پوشش سفر براي ایستگاه را مطرح نموده و با استفاده از یک روش ابتکاري و محدودیت حداکثر طول امتداد، به حل مسئله مسیریابی پرداخته اند .[6] افندي زاده و هاشمی نیز در سال 1389 مسئله طراحی شبکه مترو را با استفاده از یک روش ابتکاري بر مبناي الگوریتم ژنتیک حل نموده اند .[7]
-3 شبکه هاي عصبی مصنوعی
شبکه هاي عصبی مصنوعی یک سیستم پردازش اطلاعات است که داراي ویژگی هاي مشترکی با شبکه هاي عصبی طبیعی است. شبکه هاي عصبی مصنوعی تعمیم یافته مدل هاي ریاضی تشخیص انسان بر اساس زیست شناسی عصبی هستند و بر پایه فرضیات زیر استوار است :[8]
پردازش اطلاعات در اجزاي ساده اي با تعداد فراوان، به نام نرون ها صورت می گیرد.
· سیگنال ها در بین نرون هاي شبکه از طریق پیوندها یا اتصالات آنها منتقل می شوند.
· هر پیوند، وزن مربوط به خود را دارد که در شبکه هاي عصبی رایج، در سیگنال هاي انتقال یافته از آن پیوند ضرب می شود.
· هر نرون یک تابع فعال سازي1 معمولاً( غیر خطی) را بر روي ورودي هاي خود که جمع وزن
دار سیگنال هاي ورودي است، اعمال می کند تا سیگنال خروجی خود را تولید نماید. با توجه به فرضیات فوق، می توان یک شبکه عصبی مصنوعی را با ویژگی هاي زیر مشخص نمود:
· الگوي پیوندهاي بین نرون هاي مختلف آن شبکه که ساختار یا معماري شبکه نامیده می شود.
· روش تعیین وزن هاي روي پیوندهاي شبکه که آن را الگوریتم آموزش یا یادگیري2 می نامند.
· تابع فعال سازي شبکه که هر نرون روي ورودي هاي خود اعمال می کند.
1-3 شبکه هاي با وزن ثابت
شبکه هاي عصبی می توانند مسائل بهینه سازي با محدودیت را حل کنند. برخی از مسائل بهینه سازي وجود دارند که به علت عدم سازگاري محدودیت ها نمی توان در آنها همه محدودیت ها را به صورت هم زمان ارضا کرد. در این گونه مسائل، روش هاي رایجمعمولاً به مشکل می خورند ولی شبکه هاي عصبی می توانند راه حلتقریباً بهینه را براي آنها پیدا کنند که در اغلب موارد این راه حل ها رضایت بخش هستند .[8]
شبکه هاي مورد استفاده در حل چنین مسائلی، شبکه هاي با وزن ثابت هستند که هنگام طراحی آنها، وزن ها طوري تعیین می شوند که نشانگر محدودیت هاي مسئله باشند و کمیت مورد نظر را کمینه یا بیشینه نمایند. براي حل یک مسئله، شبکه به صورت تکراري و طی دوره هاي مختلف اجرا می شود تا الگوي سیگنال هاي خروجی را که نشانگر راه حل مسئله است، پیدا کند. انواع مختلف شبکه هاي با وزن ثابت عبارتند از:
· ماشین بولتزمن (بدون یادگیري)
· شبکه هاپفیلد پیوسته
· ماشین گاوسی
· ماشین کوشی
-4 شبکه هاپفیلد پیوسته
شبکه هاپفیلد پیوسته شکل تغییر یافته شبکه هاپفیلد گسسته است که در آن توابع خروجی مقدار پیوسته دارند. ساختار متداول شبکه هاپفیلد پیوسته در شکل (1) نشان داده شده است که در آن خروجی هر واحد شبکه، به همه واحدهاي دیگر (به غیر از خودش) به عنوان ورودي با وزن مربوطه وارد می شود .[9]
هر واحد نشانگر یک فرضیه است که در صورت درست بودن فرضیه، واحد فعال است و اگر فرضیه غلط باشد، واحد غیر فعال است. اتصالات بین واحدها در این شبکه دو سویه است. از این رو ماتریس وزن متقارن است، یعنی اتصال از واحد همانند اتصال از واحد (با وزن ) است. در شبکه هاپفیلد پیوسته، فعالیت درونی نرون را با Ui نشان می دهند و سیگنال خروجی آن است. فعالیت درونی نرون کلی x برابر است با :
که در آن ضریب زمان که مقدار آن اختیاري است و در عمل برابر 1 در نظر گرفته می شود و Ix بایاس هر نرون است. سیگنال خروجی با اعمال تابع سیگموید (با دامنه 0 و (1 طبق رابطه (3) به دست می آید.
وزن هاي شبکه ثابت هستند تا هم محدودیت هاي مسئله و هم تابعی که باید بهینه شوند را نشان دهند. راه حل مسئله معادل یافتن کمینه تابع انرژي است، بنابراین سطح فعالیت هر واحد به گونه اي تنظیم می شود که شبکه مقدار کمینه مطلوب را پیدا کند.
1-4 تابع انرژي
شبکه هاپفیلد فاقد یک قاعده یادگیري می باشد. در واقع این شبکه آموزش داده نمی شود، بلکه این شبکه بر مبناي تابع لیاپونوف1 مورد استفاده براي تعیین ماتریس وزن ها طراحی می گردد. تابع انرژي لیاپونوف به صورت زیر است:[10]
آنگاه تا زمانی که باشد، شبکه به یک پیکره بندي ثابت که در آن تابع انرژي فوق کمینه است، همگرا خواهد شد. براي تابع انرژي با تعریف فوق، شبکه در صورتی همگرا خواهد بود که فعالیت هر نرون طبق معادله دیفرانسیل (5) با زمان تغییر کند.
-5 اهداف طراحی خطوط
مسئله طراحی خطوط شبکه حمل و نقل همگانی، به دست آوردن مجموعه اي از خطوط است به نحوي که اهداف مرتبط با استفاده کننده و اپراتور را بهینه نماید. تابع هدف در مسئله طراحی خط صورتی از هزینه هاي کاربر و اپراتور می باشد. هزینه هاي کاربرمعمولاً مربوط به زمان هاي صرف شده در سیستم و هزینه هاي اپراتور نیز مربوط به هزینه هاي ارائه خدمات (هزینه هاي عملیاتی و هزینه هاي تعمیر و نگهداري) است. در طراحی مسیر حمل و نقل همگانی باید سه بعد مسافر، بهره بردار و جامعه بطور همزمان در نظر گرفته شود. این سه بعد از طیف وسیع فعالیت هاي حمل و نقل همگانی ناشی می گردد.
تابع هدف در نظر گرفته شده در مدل پیشنهادي این پژوهش شامل پارامترهاي طول خطوط و زمان سفرهاي تخصیص یافته بر خطوط مترو است. از دیدگاه مسافران کمینه کردن زمان سفر و از نظر بهره برداران کمینه نمودن طول خطوط از مهمترین هدف ها هستند. پوشش تقاضا نیز یکی دیگر از مهمترین اهدافی است که باید به آن توجه نمود. بنابراین در تعیین گره هاي پایانی یا به عبارتی پایانه هاي مترو به این مهم توجه می شود و پایانه ها در کریدورهایی که بیشترین تقاضاي سفر را دارند، انتخاب می گردند. با توجه به موارد ذکر شده تابع هدف در مدل پیشنهادي مطابق رابطه (6) می باشد.
که در آن:
L طول کل خط، T زمان سفر کل، ضرایب همسنگ سازي بعد1، ضرایب اهمیت است. ضرایب همسنگ سازي سازي بعد از روابط (7) و (8) به دست می آید.
-6 مسیریابی با استفاده از شبکه عصبی هاپفیلد
اولین گام در مسیریابی با استفاده از شبکه هاپفیلد، تعیین ساختار شبکه و مشخص نمودن گره ها و کمان هاي آن است. براي n گره از n2 واحد استفاده می شود که این واحدها مشابه آنچه در شکل (2) نشان داده شده است، به صورت یک آرایه مربعی مرتب می شوند.
مسیر صحیح با وجود یک واحد فعال در هر ردیف و در هر ستون نشان داده می شود. وجود دو واحد فعال در یک ردیف نشان می دهد که از گره متناظر دو بار عبور شده است و وجود دو واحد فعال در یک ستون نشان می دهد که مسیر هم زمان از دو گره عبور نموده است.
1-6 تابع انرژي
براي تعیین مسیر بهینه میان دو پایانه با استفاده از شبکه هاي عصبی هاپفیلد، باید تابع انرژي متناسب با تابع هدف و محدودیت هاي مسئله نوشته شود .[9] در ادامه هر یک از عبارت هاي تابع انرژي توضیح داده خواهد شد. در راه حل ارائه شده براي مسیریابی، هر واحد از شبکه دو اندیس دارد، اندیس اول x) یا (y نشان دهنده گره و اندیس دوم i) یا (j نشانگر موقعیت در مسیر است.
-1 چناچه هر گره بتواند فقط به یک گره دیگر مرتبط شود، باید حداکثر یک واحد فعال در هر ردیف وجود داشته باشد یعنی حداکثر یک 1 در هر ردیف. تابع انرژي مطابق با این محدودیت در رابطه (9) نشان داده شده است.
-2 براي اینکه مسیر از یک گره دو بار عبور ننماید، باید در هر ستون حداکثر یک واحد فعال یا به عبارتی یک 1 وجود داشته باشد. این محدودیت در رابطه (10) نشان داده شده است.
