بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
قيمت گذاري شبکه با استفاده از مسائل برنامه ريزي دوسطحي و حل آن با استفاده از الگوريتم بهينه سازي گروه ذرات
چکيده
استراتژي قيمت گذاري شبکه از نمونه سياست هايي است که بر کاهش تقاضا استوار هستند. با توجه به اينکه در سياست هاي قيمت - گذاري روي شبکه ، عوارض بر پايه ميزان و نوع بهره مندي استفادهکنندگان از آنها دريافت ميگردد، اعمال قيمت گذاري بر شبکه به عنوان راهکاري مناسب براي کنترل شلوغي شبکه مورد توجه قرار گرفته است و به عنوان يکي از موثرترين روش هاي کنترل و مديريت تقاضـا مطرح است .
در اين مقاله يکي از مدلهاي قيمت گذاري که مدلي دوسطحي با توابع هدف دوخطي است بيان ميگـردد. در سـطح بـالاي مـدل متوليان شبکه قرار دارند که هدف آنها ماکزيمم کردن درآمد حاصل از عوارض اخذ شده است در حالي که در سـطح پـايين آن کـاربران شبکه قرار دارند و در جستجوي کوتاهترين مسير براي سفر خود هستند. به دليل NP-hard بودن ساختار مسئله ، حل آن درحالت کلي با استفاده از روشهاي دقيق امکانپذير نيست و بايد از الگوريتم هاي ابتکاري و فراابتکاري براي حل استفاده کرد. ما بـه عنـوان روشـي براي حل مسئله ، الگوريتم بهينه سازي گروه ذرات بهبود يافته براي مسائل دوسطحي را به کار گرفتـه و کـارايي مـدل را بـا ارائـه مثـالي عددي نشان ميدهيم .
کلمات کليدي
قيمت گذاري شبکه ، مسائل دوسطحي، الگوريتم هاي فراابتکاري، الگوريتم بهينه سازي گروه ذرات
١- مقدمه
اقتصاددانان دريافته اند هنگامي که يـک منبـع ضـروري و کميـاب، رايگان يا زير قيمت عرضه شود، آنگاه تقاضا براي چنـين منبعـي از عرضه پيشي ميگيرد و در نتيجه کمبود پيش ميآيد. اين پديده به راحتي در بخش حمل و نقل رخ ميدهد. هنگامي که تقاضا يا تعداد وسايل نقليه اي که از يک مسير خاص استفاده ميکننـد از ظرفيـت آن بيشتر ميشود، آنگاه تراکم بوجود ميآيد [١].
به علت اثرات منفي تراکم ترافيـک ، بسـياري از پژوهشـگران حـوزه اقتصاد، و مهندسان حمل ونقل ، براي مواجهه با اين مشکل ، استفاده از استراتژي قيمت گذاري معابر را پيشنهاد ميکنند. آنهـا معتقدنـد که ، چون جادهها يک منبع با ارزش و ناياب هستند، بايد با مکـانيزم قيمت گذاري سهميه بندي شوند و کاربران جادهها بـراي اسـتفاده از شبکه حمل ونقل هزينـه پرداخـت کننـد. از سـوي ديگـر، تحميـل عوارض براي تردد در برخي خيابانهاي خاص، کاربران را بـه تغييـر مسير از قبل برنامه ريزي شده خود سوق خواهـد داد و بـا ايـن کـار باعث ميشود ترافيک به طور يکساني در شبکه توزيع شود و زمـان سفر کل شبکه نيز کاهش پيدا کند [١].
استراتژي قيمت گذاري خيابانها از نمونه سياست هايي است که بر کاهش تقاضا استوار هستند. بـا توجـه بـه اينکـه در سياسـت هـاي قيمت گذاري روي شبکه ، عوارض بر پايه ميزان و نـوع بهـره منـدي استفادهکنندگان از آنها دريافت ميگردد، اعمـال قيمـت گـذاري بـر شبکه به عنوان راهکاري مناسب براي کنترل شـلوغي شـبکه مـورد توجه قرار گرفته است و به عنوان يکي از موثرترين روش هاي کنترل و مديريت تقاضا مطرح است .
ايده دريافت عوارض خيابانها از جمله موضوعات مهم در مطالعـات انجام گرفته حوزه حمل ونقـل ، در دهـه هـاي مختلـف بـوده اسـت
.
پيگو(١٩٢٠) تئوري دريافت عـوارض از دارنـدگان وسـايل نقليـه را براي اولين بار در کتاب خود که "اقتصاد رفاهي" نام داشت ، مطـرح کرد. والترز (١٩٦١) در ادامه تحقيقات پيگو، در مطالعات خـود کـه با اندازهگيري هزينه هاي شخصـي و اجتمـاعي ترافيـک بزرگـراههـا مرتبط بود، براي اولين بار توضيحي جامع از قيمت گـذاري ترافيـک ارائه داد. در سالهاي بعد محققان ديگري همچون ويکري (١٩٦٣) با انتشار مقاله اي در مورد قيمت گـذاري خيابـانهـا در حمـل و نقـل شهري و برون شـهري، بکمـن (١٩٦٥) بـا مطالعـه عـوارض بهينـه بزرگراهها، پل ها و تونل هـا و ويکـري (١٩٦٩) تئـوريهـاي ديگـري درباره ترافيک ارائه دادهاند. اين پژوهشها پايه و اساس قيمت گذاري ترافيک در زمان حاضر هستند [٢].
مباني و اصول قيمت گذاري خيابانها بر اصل اساسي اقتصـادي کنـد آن قيمت گذاري هزينه هاي حاشيه اي استوار است که بيـان مـي دسته از کاربران جادهها که از خيابانهاي شلوغ استفاده ميکنند بـه منظور بيشينه کردن مازاد منافع عمومي بايد عوارضي برابـر اخـتلاف بين هزينه حاشيه اي اجتماعي و هزينـه حاشـيه اي فـردي بپردازنـد.
براي خيابانهاي شلوغ اين هزينه شامل ارزش زمان از دست رفتـه اي است که از طرف يک کاربر بر کاربران ديگر تحميل ميشود همچنين ميتواند شامل هزينه هاي اجتماعي ديگري چون آلودگي هواي ناشـي از آلايندههاي منتشر شده از وسايل نقليه ، سروصدا و افـزايش خطـر تصادف باشد. به اين طرح قيمت گذاري، قيمت گذاري به روش اولـين -بهترين گفته ميشود. در اين روش تقريباً براي تمام يالهاي شبکه ، عوارضي در نظر گرفته ميشود [٣].
در دنياي واقعي، پيادهسازي اولين طرح قيمت گـذاري خيابـانهـا بـه دليل مقاومت هاي عمومي و سياسي و همچنين هزينه هاي بالايي که صرف تجهيزات جمع آوري عوارض در کل شبکه ميشود، نادر است .
اين دلايل و مسـائل ديگـر از ايـن دسـت انگيـزهاي بـراي تحقيقـات پيرامون قيمت گذاري به روش دومين - بهترين بوده اسـت کـه در آن تنها براي برخي از يالهاي شبکه عوارض تعيين مـيشـود. شـهرهاي بسياري چون سنگاپور و اسلو قيمت گذاري به روش دومين - بهتـرين را براي مديريت تقاضا در منطقه کمربندي از شهر به کار گرفته اند.
به دليل ساختار دوسطحي مسئله تعيين عوارض خيابـانهـا، برنامـه - ريزي دوسطحي روش مناسبي براي فرمولبندي ايـن مسـئله اسـت و اکثر مدلهاي ارائه شده در اين زمينه مدلهايي دوسـطحي هسـتند.
به طور کلي مسائل دوسطحي در دسته مسائل Np-hard قرار مـي- گيرند به همين جهت الگوريتم معين جامعي که بتوان براي حل آنهـا بکار برد در دست نيست . اکثر مسائلي که به صورت مسائل دوسطحي فرموله ميشوند، بخصوص مسائل با ابعاد بزرگ، از روشهاي ابتکـاري و فراابتکاري براي حل بهره ميبرند.
در اين مقاله مدل دوسطحي ارائه شده توسط لبه [٤] مـورد بررسـي قرار خواهد گرفت . از آنجا که در پژوهش هاي صورت گرفتـه بـر پايـه اين مدل، بيشتر بر جنبـه هـاي پـژوهش در عمليـاتي و مـدلسـازي رياضي اين مدل تأکيد شده است ، لذا تحقيق در زمينه روشهاي حل و قابليت پياده سازي واقعي اين مدل قابل توجه خواهد بود. همچنين همه کارهاي صورت گرفته قيمت گذاري شبکه هاي حمـل و نقـل در ايران در حوزه مهندسي عمران و حمل ونقل بوده و پرداختن به ايـن نوع از مسائل از ديدگاه مهندسين صنايع ميتواند راهگشـاي زمينـه - هاي نوين پژوهشي براي اين رشته باشـد. در ايـن مقالـه روش PSO
دوسطحي براي حل مدل به کار گرفته ميشود و نتايج به دست آمـده از اين الگوريتم با نتايج ارائه شده در مقاله مرجع براي حل يک مثال عددي مقايسه ميشود.
در بخش هاي بعد مدل عنوان شـده بيـان مـيشـود و مثـالهـايي از حالات خاص و کلي مسئله به همراه روش حل آنها آورده خواهد شد.
٢- فرمولبندي مسئله
مسئله تعيين عوارض براي يالهاي شبکه هاي حمل و نقل کـاربردي از مسئله کلي تعيين عوارض براي فعاليت ها ( اعم از کالا و خدمات ) است که براي اولين بار در سال ١٩٩٨ توسـط پروفسـور لبـه فرمولـه شده است . مدل ارائه شده مدلي دوسـطحي دوخطـي(هـر سـطح بـا درنظر گرفتن متغيرهاي خود به تنهايي خطـي و بـا در نظـر گـرفتن متغيرهــاي هــر دو ســطح غيرخطــي اســت ) اســت کــه تعــدادي از متغيرهاي آن به صورت عدد صحيح تعريف ميشـوند [٤]. در سـطح بالاي مدل دوسطحي ارائه شده توسـط ايشـان متوليـان شـبکه قـرار دارند که به تنظيم عوارض بر مجموعه اي از يالهاي شبکه ميپردازند و کـاربران شـبکه در سـطح پـايين قـرار دارنـد کـه در جســتجوي کوتاهترين مسير بين مبداء و مقصد خود هستند. تابع هدف در سطح بالا ماکزيمم کردن درآمد حاصل از مجموعه عوارض اخذ شده است و در سطح پايين مينيمم کردن هزينه سفر بر يالهاي شبکه ميباشـد.
فمردملوله دوشسدطحاسيت ار.ائه شده به صورت يک مسئله مختلط عـدد صـحيح براي بيان مدل يک شبکه حمل و نقل را به صورت گرافي با چند زوج مبداء – مقصد در نظر ميگيريم . فرض کنيم (N,A)G= نشـان- دهنده گراف شبکه حمل و نقل باشد که N مجموعه گرههاي شـبکه ، و A مجموعه يالهاي شبکه است که به دو زيرمجموعه A1 و A2 کـه بته ستريتم ب ميمشجومدوعبره اييالههراييالداراAيaعـوواهرضيالو بـAدεوaنبه عـتورارتيض هزسيـنتـند- هاي ثابت ca و da (شامل مصرف سوخت ، زمان سفر، ...) وجود دارد و همچنين براي هر aεA1 عوارض Ta تعريف مـيشـود. K را مجموعـه گروههايي از کاربران شبکه که بين هر زوج مبـداء- مقصـد مشـخص سفر ميکنند يا براي سادهتر شدن مسئله به صورت مجموعه مبداء – مقصدها در نظر مـيگيـريم و هـر زوج مبـداء- مقصـد را بـه صـورت ((d)k,o)k() نمايش ميدهيم . براي هـر زوج مبـداء- مقصـد k بـردار تقاضا bk را به صورت زير تعريف ميکنيم (فرض ميکنيم تقاضا ثابت است ):
که nk تعداد کاربران هر زوج مبداء- مقصـد را نشـان مـيدهـد. همچنين xak و yak به ترتيب تعداد کاربراني که از طريق يـالهـاي aεA1 و aεA2 سفر ميکنند تعريف ميشوند.
در اين مدل با فرض ناديده گرفتن تراکم ترافيـک در حـالي کـه فرض ميشود تقاضاي سفر در هر يک از يالهاي شبکه ثابـت اسـت ، براي هر مقدار عوارض Ta داده شده براي يال a که توسط تصـميم - مگبيدرناءبدا –عامهرقبيرصدعايرالاي بن سمهئيشوتصل يکان يرعاکوناندکوبتاابهـيرييسن يرماانسيخهرـاايبيکميــيه هنـشـزوجه حمل و نقل ميتواند به صورت يک مسئله دوسطحي بـا محـدوديت - هاي خطي زير فرموله شود، که توابع هدف هر دو سطح بـا توجـه بـه متغيرهاي هر دو سطح غيرخطي هستند.
که +i و -i به صورت زير تعريف ميشوند:
با توجه به اينکه ساختار جواب مسئله سطح پايين به اين صورت است که از هر مسير بين هر زوج مبداء- مقصد يا جرياني عبور نمي - کند و يا همه تقاضاي جريان عبور ميکند لبه و همکاران مسئله را به صورت مسئله مختلط عدد صحيح زير تغيير داده اند.
حال اگر مسئله غيرخطي سطح پايين را با شرايط بهينگي KKT
آن جايگزين کنيم مسئله يک سطحي زير حاصل ميشود:
تنها روابط غيرخطي موجود در مسـئله ، تـابع هـدف سـطح بـالا معادله (٩) و شرط برابري تابع هدف سطح پايين با تابع دوگان خـود است که با تعريف T k T xkو جايگزيني آن در اين معادلات، بـه
توابعي خطي تبديل شدهاند.
راچ و همکاران با متنـاظرکردن مسـئله بـه مسـئله Sat-٣ ثابـت کردند که اين مسئله Np-hard است [٥]. با اين حال برخي حـالات خاص مسئله در زمان چند جمله اي قابل حـل هسـتند. در ادامـه دو مورد از اين حالات خاص را بيان کرده و براي هر کـدام مثـالي ارائـه ميدهيم .
٢-١- حالتي است که فقط يک يال داراي عوارض است .
لبه [٤] روشي را براي بدست آوردن عوارض بهينه در اين حالـت ارائه داده است که به شرح زير است . فرض کنيم يـال a داراي عـوارض اسـت . (λk)T را بـه عنـوان هزينه کوتاهترين مسير بين هر زوج k تعريف ميکنـيم و قـرار مـي-دهيم :
که πk اختلاف هزينه کوتاهترين مسير براي زوج k اسـت در حـالتي که Ta مقادير ٠ و ∞ را ميگيرد. حال πk ها را بـه صـورت نزولـي مرتب کنيم .
قرار ميدهيم :
آنگاه مقدار بهينه عوارض يال به صورت مستقيم از رابطه
به دست ميآيد. اگر πk براي همه زوج مبداء – مقصدها کمتـر از حد پايين عوارض la باشد به ازاء هرمقدار Tala سـود صـفر خواهد بود. مثالي از اين مورد را در نظر ميگيريم .
مثال٣-١: شکل (١) را با دو زوج مبداء – مقصد در نظر بگيريـد. اعداد نشان داده شده روي هريال هزينه هاي ثابـت آن يـال هسـتند. اولين زوج داراي دو کاربر است که از گره ١ به گره ٢ سفر ميکننـد. با استفاده از روش ارائه شده در بالا نتايج زير به دست ميآيد.
