view in publisher's site

A genetic algorithm for bi-level linear programming dynamic network design problem

Solving the Bi-level Linear Programming Network Design Problem (BLPNDP), which is typically regarded as a strongly NP-complete problem, with traditional mathematical programming algorithms is computationally intractable. A majority of the research efforts have been focused on tackling this problem using meta-heuristics. However, the evaluation functions in most meta-heuristic approaches involve dynamic traffic simulation when evaluating feasible capacity expansion policies. This commonly used evaluation function becomes a major bottleneck constraining the applicability of meta-heuristics as it is computationally expensive and analytically complicated. To address this issue, we present a modified Genetic Algorithm (GA) to solve the BLPNDP with a novel evaluation function which reduces the number of dynamic traffic simulations needed. The heuristic exploits the underlying linear programming structure of the BLPNDP and employs dual variable approximation techniques to estimate the evaluation function instead of dynamic traffic simulation. Empirical analyses are conducted on three networks of varying sizes to examine the performance of the GA based heuristic. From the experiments conducted, the proposed GA based heuristic outperforms the traditional GA. Also the proposed method of estimating the evaluation function is flexible and can be used within the framework of many meta-heuristic approaches.

یک الگوریتم ژنتیک برای مساله طراحی شبکه پویای برنامه‌ریزی خطی دو سطحی

حل مساله طراحی شبکه برنامه‌نویسی خطی سطح Bi (BLPNDP)، که معمولا به عنوان یک مساله شدیدا NP کامل در نظر گرفته می‌شود، با الگوریتم های برنامه‌نویسی ریاضی سنتی از نظر محاسباتی رام نشدنی است. اکثر تلاش‌های تحقیقاتی بر مقابله با این مشکل با استفاده از روش‌های فرا ابتکاری متمرکز شده‌اند. با این حال، توابع ارزیابی در اکثر رویکردهای فراابتکاری شامل شبیه‌سازی ترافیک پویا در هنگام ارزیابی سیاست‌های توسعه ظرفیت امکان پذیر است. این تابع ارزیابی که به طور معمول مورد استفاده قرار می‌گیرد، به یک تنگنای عمده محدود کننده کاربرد روش‌های فراابتکاری تبدیل می‌شود، زیرا از نظر محاسباتی گران و از نظر تحلیلی پیچیده است. برای پرداختن به این موضوع، ما یک الگوریتم ژنتیک اصلاح‌شده (GA)را برای حل BLPNDP با یک تابع ارزیابی جدید ارائه می‌دهیم که تعداد شبیه‌سازی‌های ترافیک پویا مورد نیاز را کاهش می‌دهد. این روش اکتشافی از ساختار برنامه‌نویسی خطی اساسی BLPNDP بهره می‌برد و از تکنیک‌های تقریب متغیر دوگانه برای تخمین تابع ارزیابی به جای شبیه‌سازی ترافیک پویا استفاده می‌کند. تحلیل‌های تجربی بر روی سه شبکه با اندازه‌های مختلف برای بررسی عملکرد روش اکتشافی مبتنی بر GA انجام می‌شود. از آزمایش‌ها انجام‌شده، روش اکتشافی مبتنی بر GA پیشنهادی بهتر از GA سنتی عمل می‌کند. همچنین روش پیشنهادی تخمین تابع ارزیابی انعطاف‌پذیر است و می‌تواند در چارچوب بسیاری از روش‌های فرا ابتکاری مورد استفاده قرار گیرد.
ترجمه شده با


پر ارجاع‌ترین مقالات مرتبط:

  • مقاله Transportation
  • ترجمه مقاله Transportation
  • مقاله حمل و نقل
  • ترجمه مقاله حمل و نقل
سفارش ترجمه مقاله و کتاب - شروع کنید

با استفاده از افزونه دانلود فایرفاکس چکیده مقالات به صورت خودکار تشخیص داده شده و دکمه دانلود فری‌پیپر در صفحه چکیده نمایش داده می شود.