کاربرد مسائل برنامهریزی دوسطحی در تعیین عوارض بهینه شبکههای حملونقل

در این مقاله، مسائل برنامه ریزی دوسطحی‡ به عنوان روشی برای مدلسازی مسائلی که دارای ساختار سلسله مراتبی هستند معرفی شده و انواع روشهای حل آنها دستهبندی میشود. همچنین مسئله تعیین عوارض بهینهخیابانها به عنوان کاربردی ازمسائل دوسطحی بیان میگردد. مدل مورد بررسی در این مقاله به صورت یک است که به صورت برنامه ریزی عدد صحیح فرموله شده است . در § مدل دوسطحی با توابع هدف دوخطیسطح بالای مدل متولیان شبکه قرار دارند که هدف آنها ماکزیمم کردن درآمد حاصل از عوارض اخذ شده است در حالی که در سطح پایین آن کاربران شبکه قرار دارند و در جستجوی کوتاهترین مسیر برای سفر خودهستند. با جانشین کردن مسئله سطح پایین با شریط بهینگی کروش – کان – تاکر خود در مدل بیان شده، مسئله به بودن ساختار مسئله، حل آن درحالت کلی با استفاده از NP-hard یک مدل یک سطحی تبدیل میشود. به دلیل روشهای دقیق امکانپذیر نبوده و باید از روشهای ابتکاری** و فراابتکاری†† برای حل استفاده کرد . در این مقاله دو حالت خاص از این مسئله که در زمان چندجملهای قابل حل هستند بررسی و مثالی از هر کدام آورده شده است.

Keywords:

مسائل برنامه ریزی دوسطحی , عوارض بهینه , شرایط کروش- کان- تاکر , روشهای ابتکاری و فراابتکاری