بخشی از مقاله
خلاصه
تاکنون مدلهاي مختلفی براي قیمتگذاري شبکههاي حملونقل پیشنهاد شده است. مدلهاي قیمتگذاري روي کمان، قیمتگذاري روي مسیر و استفاده از کمربند قیمتگذاري از جمله این مدلها هستند. در این پژوهش با توجه به پیشرفت فناوري و امکان ثبت میزان طول پیموده شده توسط خودروها در محدودههاي قیمتگذاري، عوارض دریافتی از آنها براساس یک تابع خطی با مقدارثابت از طول پیموده شده در نظر گرفته میشود.
در حالتی که میزان عوارض به صورت یک تابع خطی از طول طی شده در شبکه باشد، حل مسئله کوتاهترین مسیر ساده است. ولی در صورتی که تابع عوارض غیرخطی باشد، از جمله تابع خطی با مقدار ثابت، حل مسئله کوتاهترین مسیر مشکل میشود. این پژوهش به ارائه یک الگوریتم براي حل مسئله کوتاهترین مسیر با تابع عوارض خطی با مقدار ثابت میپردازد و سپس با استفاده از این الگوریتم در زیر مسئله کوتاه ترین مسیر تخصیص ترافیک، نتایج تخصیص ترافیک یک شبکه بزرگ ارائه میگردد.
.1 مقدمه
براي حل مشکل ازدحام در شبکههاي حملونقل شهري دو رویکرد مورد توجه قرار گرفته است. در رویکرد اول با ساخت معابر و تعریض خطوط شبکه - افزایش عرضه - اقدام به کاهش ازدحام میکنند. اما این رویکرد به علت محدودیت بودجه و فضاي لازم براي ساخت راه همیشه امکانپذیر نیست. افزون بر این، در بلند مدت میتواند منجر به افزایش تقاضاي سفر شده و در نتیجه شلوغی را نمیتوان کاهش داد. رویکرد دوم مدیریت تقاضا است. به این صورت که با ابزارهایی به کنترل و یا اصلاح میزان تردد در شبکه پرداخته میشود. یکی از این ابزارها قیمتگذاري کمانهاي شبکه است.
قیمتگذاري شبکه از این ایده سرچشمه گرفته است که استفادهکنندگان از شبکه، هزینه واقعی براي استفاده از شبکه خصوصا در نقاط مرکزي و پر تردد شهر را پرداخت نمیکنند. از اهداف قیمتگذاري میتوان به کم کردن زمان سفر کل شبکه، کاهش تردد در شبکه و همچنین ایجاد درآمد براي بهبود سیستم حملونقل اشاره کرد.
استفاده از کمربند قیمتگذاري از جمله روشهاي قیمتگذاري کمربند- مبنا3 است. در این روش تعدادي از کمان هاي شبکه به نحوي که یک کمربند بسته را تشکیل دهند انتخاب و از استفادهکنندگانی که قصد ورود به این کمربند را دارند عوارض ثابتی دریافت میشود. استفاده از کمربند قیمتگذاري باعث میشود که کاربرانی که مایل به پرداخت عوارض نیستند از سفر به این منطقه منصرف شوند و یا اینکه وسیله حملونقل خود را تغییر دهند که این کار باعث کاهش ازدحام و تراکم در این مناطق میشود. از مزایاي مهم این روش این است که درك آن براي مردم ساده بوده و دچار سردرگمی نخواهند شد.
از معایب این روش میتوان به این موضوع اشاره کرد که میزان عوارض دریافتی مرتبط با میزان استفاده از ناحیه داخلی کمربند قیمتگذاري نیست، به طور مثال کسی که به محض عبور از کمربند قیمتگذاري اقدام به پارك خودرو خود میکند با کسی که تمام کمانهاي داخل کمربند قیمتگذاري را میپیماید عوارض یکسانی را میپردازند که این امر ناعادلانه است.
در این مقاله سعی میشود با توجه به پیشرفت فناوري و امکان ثبت میزان طول پیموده شده توسط خودروها در نواحی قیمتگذاري، عوارض دریافتی از آنها براساس یک تابع خطی با مقدار ثابت از طول پیموده شده باشد. استفاده از این روش قیمتگذاري باعث پرداخت عادلانهتر عوارض شده و از لحاظ اجتماعی قابل قبولتر است. این نوع قیمتگذاري، جز روشهاي قیمتگذاري ناحیه- مبنا1 است.
هنگامی که عوارض دریافتی از کابران شبکه حملونقل بر اساس یک تابع خطی با مقدار ثابت باشد، حل زیر مسأله کوتاهترین مسیر در الگوریتمهاي تخصیص ترافیک با دشواري همراه است و از الگوریتمهاي رایج کوتاهترین مسیر نمیتوان استفاده کرد. در این مقاله یک الگوریتم براي حل مسأله کوتاهترین مسیر با درنظرگیري تابع عوارض خطی با مقدار ثابت ارائه شده است.. جهت روشن شدن نحوهي عملکرد الگوریتم پیشنهادي ، نتایج اجراي آن براي یک شبکه کوچک ارائه میشود. همچنین به منظور نشان دادن کارایی این الگوریتم، نتایج کاربرد آن در حل مسأله تخصیص ترافیک براي دو شبکه کوچک و بزرگ ارائه میشود.
.2 مروري بر ادبیات
ژانگ و یانگ[1] در سال 2004 به بررسی کمربند قیمتگذاري میپردازد و جانمایی مکان کمربند و سطح عوارض دریافتی را به صورت همزمان مشخص میکنند. در این پژوهش براي پیدا کردن عوارض بهینه از حل یک مدل دوسطحی استفاده میشود که سطح بالاي آن بیشینه کردن تابع رفاه اجتماعی است و سطح پایین آن برقراري تعادل جریان با تقاضاي انعطافپذیر است. دو مسأله تعیین نرخ عوارض و جانمایی مکان کمربند قیمتگذاري روي شبکه به طور همزمان مورد بررسی قرار گرفته است. براي حل این مسأله پیچیده بهینهسازي، از الگوریتم ژنتیک دوتایی و تئوري برش گراف و یک روش جستجوي مشبک2 استفاده شده است.
پارسافرد[2] در سال 1390 براي حل مسأله جانمایی کمربند ترافیکی و مقدار عوارض بهینه که یک مسأله دوسطحی است از روش گرم و سرد شبیهسازي شده3 و روش تقسیم طلایی4 استفاده نموده و مسأله را براي شهر مشهد حل کرده است.
مارویاما و سومالی [3] در سال 2007 به بررسی عملکرد قیمتگذاري ناحیه- مبنا و کمربند- مبنا از نظر مقدار بهبود رفاه اجتماعی و تأثیر برابري اجتماعی پرداختند. منظور از برابري اجتماعی، توزیع یکنواخت و منصفانه منفعت بهدست آمده از دسترسی به سیستم حملونقل بین اقشار مختلف جامعه است. در این پژوهش معیار برابري اجتماعی، ضریب جینی5 در نظر گرفته شده است.
نتایج بهدست آمده نشان میدهد که قیمتگذاري ناحیه-مبنا بهبود بیشتري در رفاه اجتماعی نسبت به استراتژي کمربند-مبنا ایجاد میکند اما نابرابري اجتماعی را نسبت به استراتژي کمربند-مبنا افزایش میدهد. میزان عوارض بهینه در استراتژي ناحیه- مبنا بیش از استرانژي کمربند- مبنا است. همچنین با افزایش اندازه محدوده قیمتگذاري، در استراتژي ناحیه- مبنا میزان رفاه اجتماعی افزایش مییابد.
لافونگپانیچ و یین [4] در سال 2012 اقدام به بیشینهسازي رفاه اجتماعی با قیمتگذاري بر اساس یک تابع قطعهبندي شده خطی در شبکه حملونقل نمودند.آنها براي بدست آوردن ضرایب بهینه تابع عوارض از یک مدل دوسطحی استفاده کردندکه سطح بالاي آن بیشینه کردن تابع رفاه اجتماعی و سطح پایین آن حل مسأله تعادل جریان استفادهکنندگان است.
این پژوهشگران براي حل مسئله تعادل استفادهکننده از روش تجزیه سیمپلیکال استفاده کردند، که یک الگوریتم تکرارشونده است. در این الگوریتم از حل زیرمسأله بهینهسازي اعداد صحیح با محدودیت جانبی جهت یافتن کوتاهترین مسیر با عوارض غیرخطی استفاده میشود. همچنین براي حل مسأله بیشنهسازي رفاه اجتماعی - مسأله سطح بالا - از الگوریتم جستجو هماهنگ7 استفاده کردند. آنها مسأله تعیین پارامترهاي تابع عوارض را براي یک شبکه تصادفی کوچک حل کردند.
بهرامی [5] در پژوهشی جهت یافتن کوتاهترین مسیر مربوط به خودروهاي الکتریکی با ایده گرفتن از الگوریتم بل [6]، که یک الگوریتم براي یافتن کوتاهترین مسیر بدون محدودیت منابع است، دو الگوریتم برچسبگذاري با استفاده از ایده درخت شمارش ارائه نموده است. الگوریتم اول ارائه شده در این پژوهش تنها محدودیت طول مسیر مربوط به خودروهاي الکتریکی را در نظر میگیرد در حالی که الگوریتم دوم علاوه بر در نظرگیري محدودیت طول، امکان شارژ مجدد خودروها را در نظر میگیرد. در این پژوهش همچنین یک مسأله سطح بالا براي مکانیابی ایستگاههاي شارژ معرفی و براي شبکه جادهاي ایران حل شده است.
این مقاله با استفاده از ایده درخت شمارش استفاده شده در الگوریتم بهرامی، به ارائه الگوریتمی براي حل مسأله کوتاهترین مسیر با در نظرگیري تابع عوارض خطی با مقدار ثابت میپردازد.
.3 شرح الگوریتم
الگوریتمهاي کوتاهترین مسیر عمدتا از نوع الگوریتمهاي برچسبگذاري تکرارشونده1 هستند. این الگوریتمها که به دو نوع تصحیح برچسب2 و وضع برچسب3 تقسیم میشوند، یک برچسب هزینه موقتی به گرهها در هر مرحله اختصاص میدهند. الگوریتمهاي برچسبگذاري مختلف در نحوه به روزرسانی برچسبها و میل کردن به جواب بهینه با هم تفاوت دارند.
الگوریتم بل از نوع تصحیح برچسب است که در هر مرحله مجموعهاي از برچسبهاي زمان سفر 0 را نگهداري میکند. برچسب مربوط به گره شبکه، یا داراي مقدار ∞ است که نشان میدهد هنوز هیچ مسیري از مبدأ به گره پیدا نشده است و یا بیانگر زمان سفر مسیر فعلی از مبدأ به گره است. براي هر گره ، همچنین یک برچسب که بیانگر گره قبلی گره در کوتاهترین مسیر است، نگهداري میشود.
زمانی که الگوریتم به پایان میرسد با استفاده از اطلاعات مربوط به گره قبل، میتوان کوتاهترین مسیر از مبدأ به همه گرهها را به دست آورد. در الگوریتمهاي تصحیح برچسب تا زمان رسیدن به شرایط بهینگی زیر، برچسبها به صورت متوالی به روز میشوند. اگر r گره مبدأ با برچسب 0 و زمان سفر کمان , در شبکه باشد، برچسبگذاري تا زمانی ادامه مییابد که شرط زیر برقرار شود
الگوریتمهاي ارائه شده توسط بهرامی [5] بسطی از الگوریتم بل هستند که در آنها برچسب هر گره علاوه بر زمان سفر از مبدا تا گره مربوطه، شامل میزان طول باقیمانده براي ادامه سفر از گره مورد نظر نیز میشود. از آنجا که یک گره شبکه در این روش میتواند داراي چند برچسب باشد، به جاي درخت کوتاهترین مسیر از درخت نگهداري برچسب با نام "درخت شمارش" استفاده میشود.
به عبارت دیگر، به ازاي هر گره شبکه ممکن است چند گره در درخت شمارش با زمان سفرهاي مختلف و طولهاي باقیمانده مختلف وجود داشته باشد. از این درخت براي ساخت درخت کوتاهترین مسیر با محدودیت طول از مبدأ به هر گره دیگر شبکه استفاده میشود.
در این مقاله یک الگوریتم کوتاهترین مسیر براي تابع عوارض خطی بر حسب طول پیموده شده در نواحی قیمتگذاري با مقدار ثابت، براي یک مبدأ به همه مقصدها ارائه میشود. این تابع عوارض ،به صورت رابطه - 2 - است. در این تابع قیمتگذاري، پارامترهاي غیرمنفی تابع عوارض هستند و طول پیموده شده در نواحی قیمتگذاري. است
