International Journal of Industrial Engineering & Production Management (2014)

فول تکست yaghini A 10 208 9 8ae04d7 1

فول تکست yaghini A 10 208 9 8ae04d7 1

ISSN: 2008-4870 January 2014, Volume 24, Number 4
pp. 491-501

http://IJIEPM.iust.ac.ir/

Optimization of Passenger Line Planning in Railway

M. Yaghini*, A. Alimohammadian & M. Karimi

Masoud Yaghini, Assistant Professor, School of Railway Engineering, Iran University of Science and Technology, Tehran, Iran
Alireza Alimohammadian, Master of Science, School of Railway Engineering, Iran University of Science and Technology, Tehran, Iran Mohammad Karimi, Master of Science, School of Railway Engineering, Iran University of Science and Technology, Tehran, Iran

Keywords 1ABSTRACT

فول تکست yaghini A 10 208 9 8ae04d7 1

Railway Transportation Planning,
Passenger Lines Planning, Genetic Meta heuristic Algorithm,
Column Generation Algorithm
The passenger line planning is a process of strategic long-term decision-making problem in the field of railway passenger planning. A line is a direct railway connection between two stations. A line is characterized by the origin and destination stations, the frequency per day, the route between these two stations, and the intermediate stops at passing railway stations. Various mathematical models have been proposed for passenger line planning problem, and different solution methods have been provided so far. Two solution methods based on column generation algorithm and genetic algorithm have been proposed in this article, the first alghorithm is defined in one master problem and two sub problems. Since the solution provided by column generation method is not of the integer number type, a heuristic algoadrithm has been proposed here for converting the results to integer numbers. The objective function for line planning problem in this article is to maximize the number of direct passengers. Direct passengers are the passengers that can travel from their origin station to their destination station without having to change trains. Results on the proposed solution methods, for twirty two test problems, are compared to those of solutions obtained via CPLEX software, one of the well-known solvers for solving both linear and mix integer programming problems using branch and bound algorithm. Results show that the proposed solution methods have high performance and accuracy.
© 2014 IUST Publication, IJIEPM. Vol. 24, No. 4, All Rights Reserved

فول تکست yaghini A 10 208 9 8ae04d7 1

*
Corresponding author. Masoud Yaghini
Email: yaghini@iust.ac.ir
-196087-1394859
بهینه سازی برنامه ریزی خطوط مسافری در راه آهن

مسعود یقینی*، علیرضا علیمحمدیان و محمد کریمی

کلمات کلیدی چکیده:
-137151894

برنامه ریزی حمل و نقل ریلی، برنامه ریزی خطوط مسافری یک تصمیم استراتژیک و بلند مدت در حوزه برنامه ریزی مسافر در راه برنامه ریزی خطوط مسافری ،آهن است. تاکنون مدل های ریاضی و روش های حل گوناگونی برای مسئله برنامه ریزی خطوط ارائه الگوریتم ایجاد ستون ، شده است .در این مقاله یک روش حل بر پایه الگوریتم ایجاد ستون پیشنهاد شده که در آن، مسئله الگوریتم ژنتیک برنامه ریزی خطوط مسافری به صورت یک مسئله اصلی و دو زیر مسئله تعریف شده است. از آنجایی که جواب حاصل از روش ایجاد ستون غیر عدد صحیح است، برای تبدیل جواب های حاصل به مقادیر صحیح یک الگوریتم ابتکاری پیشنهاد شده است. در ادامه یک الگوریتم پیشنهادی جدید برای حل مسئله برنامه ریزی خطوط مسافری، مبتنی بر الگوریتم فراابتکاری ژنتیک ارائه شده است. تابع هدف مسئله برنامه ریزی خطوط مسافری در این مقاله، بیشینه سازی تعداد مسافرین مستقیم است. ارزیابی روشهای حل پیشنهادی با استفاده از بیست مسئله نمونه و مقایسه جواب های بدست آمده از روش پیشنهادی با روش حل مبتنی بر شاخه و حد و نرم افزار بهینه سازی CPLEX انجام شده است. نتایج بدست آمده نشان دهنده کارایی و دقت بالای روشهای حل پیشنهادی است.
-1371561471

1. مقدمه1
مسئله برنامه ریزی خط یا برنامه ریزی مسیر های مسافری یکی از برنامه ریزی های استراتژیک و سطح بالا در برنامه ریزی حمل و نقل مسافر در راه آهن است. در ادبیات موضوع، یک خط، مسیری است بین یک مبدا و مقصد با ایستگاه های توقف مشخص که دارای تعداد تکرار معین حرکت قطار است. حرکت قطارهای مختلف در یک خط دارای مبادی و مقاصد مشخص و زمان های اعزام و ورود متفاوت است. هدف مسئله مورد نظر، انتخاب خطوط بهینه از میان خطوط پیشنهادی است که حداکثر خدمت را برای مشتریان که همان مسافرین هستند، ایجاد کند. خدمت ارائه شده
تاریخ وصول: 3/11/01 تاریخ تصویب: 72/7/01
*نویسنده مسئول مقاله: دکتر مسود یقینی، دانشکده مهندسی راه آهن، دانشگاه علم و صنعت ایران، تهران، ایران .yaghini@iust.ac.ir علیرضا علیمحمدیان، دانشکده مهندسی راه آهن، دانشگاه علم و صنعت ایران،
a_alimohammadian@rail.iust.ac.ir. تهران، ایران
محمد کریمی، دانشکده مهندسی راه آهن، دانشگاه علم و صنعت ایران، تهران،
mohammad_karimi@rail.iust.ac.ir. ایران
به مسافرین را می توان توسط چندین شاخص بیان کرد. یکی از شاخص های مهم، مسافرین مستقیم است. به طور معمول
مسافرین تمایل دارند که مسیر سفر خود از مبدا به مقصد را به صورت مستقیم و بدون نیاز به تعویض قطار طی نمایند. مسافرین مستقیم در برنامه ریزی خط، به مسافرینی گفته می شود که در سفر از مبدا به مقصدشان نیاز به تعویض قطار نداشته باشند ]1[.
ورودی های مورد نیاز برای مسئله برنامه ریزی خطوط مسافری شامل ایستگاه ها، ارتباط ریلی ایستگاه ها و تقاضای سفر بین هر زوج مبدا و مقصد است. بنابراین تقاضا به صورت یک ماتریس تعریف می شود. اگر شبکه ریلی با G(V,E) نمایش داده شود ، V بیان کننده ایستگاه ها و E بیان کننده مسیرهای بین دو ایستگاه متوالی مفروض یا همان کمان های شبکه است. مجموعه V از n ایستگاه یا گره تشکیل شده است. ماتریس تقاضای ورودی یک ماتریس n×n است. در این مدل، تقاضا در مسیر رفت با تقاضا در مسیر برگشت، یکسان در نظر گرفته می شود و برابر با حداکثر تقاضای رفت یا برگشت فرض می شود. علت این مسئله، استفاده چرخشی3 از ناوگان است. بدین معنا که تعداد تکرار در مسیر

3 Cyclic
303
رفت باید با تعداد تکرار در مسیر برگشت یکسان است. مسافریندر مبدا ممکن است مسیرهای مختلفی را برای رسیدن به مقصدداشته باشند، اما در کلیه مدل های برنامه ریزی خطوط مسافری فرض می شود که مسافرین کوتاهترین مسیر ریلی را برای رسیدن به مقصد خود انتخاب می کنند. باید توجه نمود در صورتی که خطوط انتخابی باعث افزایش رضایتمندی مشتریان یا همان مسافرین شود، به طور حتم تقاضای سفر بین هر زوج ایستگاه افزایش خواهد یافت و این مسئله افزایش و تداوم سودآوری سازمان را تامین می کند و از سمت دیگر نیز نیاز به برنامه ریزی مجدد خطوط پس از طی زمانی که تغییرات محسوس در تقاضای سفر رخ دهد را ایجاب می نماید]1[.
شرکت هایی که در حوزه حمل و نقل مسافر فعالیت می کنند با سطوح مختلف برنامه ریزی مواجه هستند که از بین آنها می توان به پیشبینی تقاضا، برنامه ریزی خطوط مسافری، زمانبندی حرکت قطارها، مسئله تخصیص ناوگان و برنامه ریزی خدمه اشاره نمود ]2[.
پیش بینی تقاضا، اولین قدم در برنامه ریزی حمل و نقل ریلی در حوزه حمل مسافر است که یکی از پیش نیاز های برنامه ریزی خطوط مسافری یا تعیین مسیر های مسافری است. در این مرحله تقاضای بین هر زوج ایستگاه برآورد می شود. پیشبینی دقیق تقاضای مسافر مبنای سایر برنامه ریزی ها در حمل و نقل مسافر است. مقالات متعددی به برآورد تقاضای مسافر پرداخته اند که می توان به ]3-4[ اشاره نمود.
مرحله بعدی، برنامه ریزی خطوط مسافری است که در این مرحله خطوط بهینه با تعداد تکرار مشخص، برای هر خط بدست می آید. از مهمترین کارهای انجام شده در زمینه برنامه ریزی خطوط مسافری می توان به مقاله بوسیک و همکارانش در سال 1991 که بر روی بیشینه سازی تعداد مسافرین مستقیم مطالعه کرده است اشاره نمود. وی ظرفیت تمامی قطارها را ثابت و یکسان فرض نموده و روش های مختلفی را برای حل مدل خود بیان می کند]5[.
در سال 1991، کلااسنس و همکارانش یک مدل غیر خطی عدد صحیح برای پیدا کردن خطوط بهینه، جهت کمینه سازی هزینه عملیاتی خطوط ارائه کردند. همچنین برای حل، این مدل را به یک مدل خطی عدد صحیح تبدیل کرده و توسط یک نرم افزار بهینه سازی حل نمودند ]1[. گوسنس و همکارانش در سال 2004 یک مدل برای کمینه سازی هزینه خطوط ارائه کرده و این مدل را توسط یک الگوریتم شاخه و برش حل کردند ]7[. لیندنر بر روی کمینه سازی هزینه های عملیاتی خطوط مطالعه کرده است. وی یک روش شاخه و کران برای حل این مدل ارائه کرده و مدل خود را با مدل زمانبندی حرکت قطارها ادغام میکند ]1[. اسکوبل بر روی کمینه سازی تعداد مسافرینی که برای رسیدن بهمقصد، نیاز به تعویض قطار دارند مطالعه کرده و نشان می دهد، کمینه سازی این مسافرین نسبت به بیشینه سازی مسافرین مستقیم پیچیده تر است و برای پیدا کردن یک حد پایین از آزاد سازی لاگرانژ1 استفاده کرده است ]9[ .
مقالاتی نیز در سال های اخیر با موضوع برنامه ریزی خطوط مسافری در راه آهن ارائه شده است که از بین آنها می توان به موارد ذیل اشاره نمود. شفیعا و همکاران یک مدل عدد صحیح مختلط، با در نظر گرفتن عدم قطعیت در اطلاعات ورودی مسئله برای برنامه ریزی خطوط مسافری ارائه کردند و برای حل آن از یک الگوریتم ابتکاری استفاده نمودند ]10[. یقینی و همکاران با استفاده از تکنیک برنامه ریزی آرمانی، یک مدل چند هدفه را به یک مدل تک هدفه جهت برنامه ریزی حمل و نقل مسافر ارائه نمودند ]11[. همچنین در سال 2012 یقینی و همکارانش یک روش ترکیبی برای حل مسئله برنامه ریزی خطوط مسافری با استفاده از الگوریتم تجزیه و یک روش ابتکاری ارائه نمودند ]12[.
نتایج برنامه ریزی خطوط مسافری، ورودی زمانبندی حرکت قطارها2 است .
نتایج زمانبندی حرکت قطارها، زمان های ورود و اعزام هر قطار به هر ایستگاه است. از این رو این برنامه ریزی از اهمیت ویژه ای در برنامه ریزی حمل و نقل ریلی برخوردار است و تاکنون مقالات متعددی در این زمینه منتشر شده است که می توان به ]13-14-15-11-17[ اشاره نمود. نتایج مسئله زمانبندی حرکت قطارها ورودی مسئله برنامه ریزی وسائل نقلیه است در این مرحله از برنامه ریزی با توجه به زمان های ورود و اعزام قطار ها ،تخصیص ناوگان به هر اعزام قطار صورت می پذیرد. از مقالات ارائه شده در زمینه برنامه ریزی وسائل نقلیه می توان به ]11-19[اشاره نمود. آخرین مرحله، برنامه ریزی خدمه3 است. در این مرحله برنامه کاری خدمه قطارها به نحوی تعیین می شود که با رعایت موازین کاری، حداقل هزینه تخصیص خدمه صورت پذیرد .
برای کسب اطلاعات بیشتر در زمینه برنامه ریزی خدمه از مقالات]20-21-22[ می توان استفاده نمود.
در این مقاله ارائه یک الگوریتم مبتنی بر روش ایجاد ستون4 برای حل مسئله برنامه ربزی خطوط مسافری، با در نظر گرفتن یک مسئله اصلی5 و دو زیر مسئله1 است. روش ایجاد ستون یکی از روشهای دقیق در حل مسائل برنامه ریزی خطی است. از آنجا که جواب های حاصل از الگوریتم ایجاد ستون لزوماً عدد صحیح
Lagrangian relaxation
Train time tabling
43 Crew schedulingColumn generation method
65 Master problemSub problem
نیستند، یک الگوریتم ابتکاری برای تبدیل جوا بهای حاصل ازالگوریتم به جواب های عدد صحیح ارائه شده است. به عنوان یکنوآوری روشی برای حل مسئله برنامه ریزی خطوط مسافری مبتنی بر الگوریتم فراابتکاری ژنتیک1 ارائه شده است.
در ادامه در بخش دوم، مدل ریاضی برنامه ریزی خطوط مسافری که در این مقاله از آن استفاده شده است، بیان می شود. در بخش سوم، الگوریتم پیشنهادی مبتنی بر روش ایجاد ستون برای حل مدل ریاضی بیان شده، ارائه می گردد، در بخش چهارم، الگوریتم پیشنهادی مبتنی بر روش روش فراابتکاری ژنتیک ، ارائه می گردد، ارزیابی روشهای حل پیشنهادی با توجه به مسائل نمونه در بخش پنجم انجام شده و در بخش ششم نتیجه گیری و زمینه های پژوهشی آتی ارائه می گردد.

7. مدل ریاضی برای مسئله برنامه ریزی خطوط مسافری در راه آهن
مدل ریاضی برنامه ریزی خطوط مسافری که در این مقاله از آن استفاده شده، مجموع تعداد مسافرین مستقیم بین کلیه مبادی و مقاصد را بیشینه می سازد. محدودیت های مسئله برنامه ریزی خطوط مسافری شامل محدودیت تقاضا، محدودیت ظرفیت ایجاد شده و محدودیت کل تعداد اعزام قطار روی هر کمان شبکه است
.]5[
شمارنده ها:
e: شمارنده کمان های شبکه eE.
r: شمارنده خطوط rR.
a,b: شمارنده مبدا و مقصد ایستگاه a,bV.
مجموعه ها:
V: مجموعه ایستگاه های موجود.
E: مجموعه کمان های شبکه.
R: مجموعه خطوط پیشنهادی.
پارامترها:

فول تکست yaghini A 10 208 9 8ae04d7 1

,da b: تقاضای سفر از a به b.
u(e): حد بالای تعداد تکرار یا اعزام قطار روی کمان e.
:c ظرفیت ناوگان )نفر.(
متغیرهای تصمیم:
,,yr a b : متغیر مستقیم از تصمیم مبدا ازa بهنوع b عدد توسط صحیحخط ، r.بیانگر تعداد مسافرین

xr : متغیر تصمیم مسئله از نوع عدد صحیح، بیانگر تعداد تکرار خط r.
1 Genetic Meta heuristic algorithm
303
872628172873

Max   yr a b, ,
a b V,  e rr R  ab, )1(
141702148128

 yr a b, ,  da b,
e rr R  a b,  a b V, )2(
141955160296

 yr a b, , c xr
e rr R  a b,   r R e r, )3(
140997193491

 x u er  ( )
e rr R  ab,  e E )4(
xr 0 & Integer, yr a b,, 0 & Integer.    rR a b V,, )5(

تابع هدف) 1(، کل تعداد مسافرین مستقیمی را که توسط کلیه خطوط از مبدا به مقصد شان می رسند، بیشینه می نماید .محدودیت) 2( بیان می کند که کل تعداد مسافرینی که به صورت مستقیم بین هر مبدا و مقصد سفر می نمایند باید، از تقاضای سفر آن مبدا و مقصد کمتر باشد. محدودیت) 3( بیان می کند که در هر خط کل تعداد مسافرین مستقیمی که در یک کمان خاص عبور می کنند باید، از ظرفیت ایجاد شده توسط اعزام قطار در آن خط کمتر باشد. محدودیت) 4( بیان می کند که که تعداد اعزام های کلیه خطوط روی هر کمان باید از حد بالای اعزام روی آن کمان کمتر باشد. این حد بالا با توجه به عواملی نظیر، سیستم علائم و ارتباطات و تعداد ایستگاه های تلاقی در کمان بدست می آید که در این مسئله به عنوان یکی از پارامتر های ورودی فرض می شود. محدودیت) 5( نوع متغیر های تصمیم مسئله را تعریف می کند که هر دو نوع متغیر های تصمیم، از نوع عدد صحیح هستند .

3. روش حل پیشنهادی مبتنی بر الگوریتم ایجاد ستون
همانطور که بیان شد، روش حل ارائه شده در این مقاله مبتنی بر الگوریتم ایجاد ستون است. این الگوریتم یک روش حل دقیق برای دستیابی به جواب بهینه مسائل برنامه ریزی خطی است، که به نام الگوریتم تجزیه نیز شناخته شده است. به کارگیری این روش برای حل مسائل بزرگ است که توسط نرم افزار های بهینه سازی در زمان قابل قبول امکان حلشان وجود ندارد. مقالات متعددی تا کنون در زمینه الگوریتم ایجاد ستون و حل مسائل گوناگون به کمک این الگوریتم ارائه شده است که می توان به
304
]23-24-25-21[ اشاره نمود. در الگورتیم ایجاد ستون، مسئلهاولیه به یک مسئله اصلی و حداقل یک زیر مسئله تقسیم میشود. در هر مرحله از اجرای الگوریتم ایجاد ستون، مقادیر دوگان، خروجی مسئله اصلی و مقادیر جدید متغیرهای تصمیم، خروجی زیر مسئله )ها( است. از این رو فضای حل مسئله به حداقل دو بخش تقسیم می شود. همانطور که بیان شد این روش برای حل مسائل برنامه ریزی خطی است. از این رو هیچ تضمینی برای رسیدن به جواب های عدد صحیح در مسائلی که متغیر های تصمیمش از این دست هستند، وجود ندارد. در این مقاله مسئله برنامه ریزی خط به یک مسئله اصلی و دو زیر مسئله تقسیم می شود و برای تبدیل جواب های بدست آمده به اعداد صحیح، یک الگوریتم ابتکاری ارائه شده است .
در هر مرحله از الگوریتم، مقادیر دوگان از مسئله اصلی به زیر مسئله وارد می شود و در زیر مسئله، مقادیر جدید متغیرها به مسئله اصلی وارد می شود. شرط خاتمه الگوریتم توسط تابع هدف زیر مسئله بررسی می شود. تابع هدف مسئله اولیه همان تابع هدف مسئله اصلی است. همانطور که بیان شد، این روش مسئله را به یک مسئله اصلی و حداقل یک زیر مسئله تبدیل می نماید.
برای حل مسئله برنامه ریزی خطوط مسافری توسط روش ایجاد ستون، محدودیت) 3( را که هر دو متغیر تعداد مسافرین مستقیم و تعداد اعزام خطوط را شامل می شود، در مسئله اصلی قرار داده و دو زیر مسئله، برای برقراری سایر محدودیت ها تعریف شده است. زیر مسئله اول محدودیت) 2( را و زیر مسئله دوم محدودیت) 4( را برقرار می سازد. از این جهت در مسائل با اندازه بزرگ با توجه به یک مسئله اصلی و دو زیر مسئله، فضای حل مسئله به سه بخش تقسیم می شود از این جهت سرعت حل مسئله بالاتر می رود. مسئله اصلی به صورت روابط) 1(- )10( حاصل می شود.
Master problem:

986048156191

Min   (yr a b, , )j )1(
ja b V,
 e r r R  ab,
32090851767

j ((e r r R  a b, yr a b, , )j  (c xr )j)  s0    r R e r, )7(

j j 1 )1(
j j 1 )9(

j  0, j  0, s .0 )10(

در مدل) 1(-)10(، تابع هدف) 1( همان تابع هدف مسئله اولیه است که برای انطباق با روش ایجاد ستون به صورت کمینه سازی تبدیل شده است. متغیر تصمیم مسئله اصلی λ و γ است .
محدودیت) 7( همان محدودیت ظرفیت ایجاد شده توسط اعزام ها روی هر کمان است و بردار متغیر کمبود s این محدودیت را به حالت تساوی تبدیل می کند. محدودیت) 1(، محدودیت تحدب روی جواب های حاصل از زیر مسئله اول است. محدودیت )9(، محدودیت تحدب روی جواب های حاصل از زیر مسئله دوم است. محدودیت) 10( متغیر های تصمیم مسئله را از نوع مثبت تعریف می کند. در مدل) 1(-)10( بردار y وx ورودی مسئله از زیر مسئله ها و به عنوان پارامتر های مدل هستند. بردار مقادیر دوگان برای محدودیت) 7( به صورت w و مقدار متغیر دو گان برای محدودیت) 1( با α و مقدار متغیر دوگان برای محدودیت )9( با β نشان داده می شوند .
زیر مسئله اول که محدودیت) 2( مسئله را برقرار می سازد و در هر مرحله مقادیر متغیرهای تصمیم y را مشخص می سازد به صورت مدل) 11(-)13( تعریف می شود.
Subproblem 1:
Max w A((   ) 1)y  )11(
28583395144

e rr R a b, yr a b, ,  da b,  a b V, )12(
y .0 )13(

تابع هدف) 11(، متغیرهای تصمیم از نوع y و مقادیرشان را برای مسئله اصلی تعیین می نماید. همانطور که بیان شد w بردار مقادیر دوگان محدودیت) 7( و A ضریب متغیر های تصمیم y در محدودیت) 7( است. محدودیت) 12( همان محدودیت تقاضا مسئله اولیه است. محدودیت) 13( متغیر تصمیم زیر مسئله اول را تعریف می کند. در مسئله برنامه ریزی خطوط مسافری ،متغیرهای تصمیم از نوع عدد صحیح است، اما از آنجا که در روش ایجاد ستون، فضای حل زیر مسئله ها باید محدب باشد، از این رو نمی توان متغیرهای تصمیم از نوع y را در زیر مسئله اول عدد صحیح تعریف نمود. با توجه به اینکه این متغیر نشان دهنده تعداد مسافرین مستقیم است و تعداد مسافرین معمولاً یک عدد بزرگ خواهد بود، بنابراین در نظر گرفتن این متغیر به صورت عدد صحیح و یا پیوسته تغییر چندانی در جواب مسئله نخواهد داشت و به سادگی می توان با گرد کردن این مقدار، به یک مقدارعدد صحیح دست یافت.
زیر مسئله دوم که انتخاب و مقدار دهی به متغیرهای تصمیم از نوع x را برعهده دارد به صورت مدل) 14(-)11( تعریف می شود.
Subproblem 2:
Max W A x(  )  )14(
197631109562

e rr R ab, x u er  ( )  e E )15(
)11( 0.x زیر مسئله دوم نیز محدودیتی که تنها شامل متغیر تصمیم x هستند را در برمی گیرد. تابع هدف) 14(، متغیرهای تصمیم از نوع x را برای ورود به پایه انتخاب می کند و مقادیر متناسب را به این متغیر ها تخصیص می دهد. محدودیت) 15( همان محدودیت حد بالای تعداد اعزام روی هر کمان است و محدودیت) 11( متغیر تصمیم را از نوع مثبت تعریف می نماید. جواب حاصل برای این متغیر تصمیم، توسط الگوریتم ایجاد ستون، غیر عدد صحیح است. از آنجا که این متغیر بیان کننده تعداد اعزام هر خط است ،باید به صورت عدد صحیح باشد که توسط الگوریتم ابتکاری به مقادیر صحیح تبدیل می شود. شرط خاتمه الگوریتم ایجاد ستون به صورت) 17( است.

Max W A x(  )   0&
)17( Max ((w A   )1)y  0.

با توجه به) 17(، الگوریتم ایجاد ستون زمانی متوقف می شود که توابع هدف هر دو مسئله همزمان کوچکتر یا مساوی صفر شود .پس از خاتمه الگوریتم ایجاد ستون، مقادیر تعداد اعزام در هر خط برای تبدیل به مقادیر عدد صحیح به الگوریتم ابتکاری پیشنهادی وارد می شود.
همانطور که بیان شد، جواب های حاصل از روش ایجاد ستون ،حتماً عدد صحیح نیستند و جوابهای مورد نیاز مسئله برنامه ریزی خطوط مسافری باید به صورت صحیح باشند. خروجی اصلی مسئله برنامه ریزی خطوط مسافری، تعداد اعزام قطار در هر خط یا مسیر مسافری است. از این رو مقدار غیر صحیح برای این متغیر بی معنا است. برای تبدیل نتایج بدست آمده به صورت عدد
304
صحیح، یک الگوریم ابتکاری ارائه شده است. مراحل الگوریتمابتکاری پیشنهادی به شرح زیر است:

قدم اول: مجموع اعزام ها بر روی هر کمان محاسبه می شود.

در این سایت فقط تکه هایی از این مطلب درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

به سایت مرجع

www.homatez.com

مراجعه نمایید

 

قدم دوم: مجموع اعزام های بدست آمده در قدم اول، به نزدیکترین مقدار صحیح خود گرد می شود.
قدم سوم: میزان اعزام ها بر روی هر کمان را جداگانه گرد کرده و مجموع آن محاسبه می شود .
قدم چهارم: اختلاف حاصل از مجموع گرد شده اعزام ها و گرد شده مجموع اعزام ها محاسبه می شود.
قدم پنجم: با توجه به اختلاف حاصل از مجموع گرد شده اعزام ها و گرد شده مجموع اعزام ها، خطوط با طولانی ترین مسیر ممکنه بر روی شبکه ایجاد می شود.

3. روش حل پیشنهادی مبتنی بر الگوریتم فرا ابتکاری ژنتیک
الگوریتم ژنتیک یکی از کاراترین روش های فرا ابتکاری است .الگوریتم های فراابتکاری، روش هایی برای دستیابی به جواب های نزدیک به بهینه در زمانی قابل قبول برای مسائل با ابعاد بزرگ هستند که روش های دقیق توانایی دستیابی به جواب بهینه را ندارد و یا زمان دستیابی به جواب بهینه با توجه به این روش ها بسیار زیاد است .
در این روش هر جواب به صورت یک رشته کروموزوم تعریف می شود و مراحل کلی یک الگوریتم ژنتیک به صورت زیر است
:]27[
1-ایجاد یک جمعیت1 اولیه )تشکیل یک مجموعه جواب(
2-انتخاب والدین از جمعیت به منظور تشکیل جمعیت جدید
3- عمل لقاح3 )ایجاد یک عضو جدید از دو والد انتخاب شده( و عمل جهش4 و ایجاد فرزندان 4- تشکیل جمعیت جدید
5- تکرار قدم های 2-4 تا رسیدن به شرایط همگرایی

از آنجا که این الگوریتم تنها یک چارچوب کلی برای حل مسئل برنامه ریزی ریاضی است، برای هر مسئله باید الگوریتمی متناسب
1 Population
302
با آن تعریف شود. الگوریتمی که برای مسئله برنامه ریزی خطوطمسافری ارائه شده است، به صورت زیر است.
در مسئله برنامه ریزی خطوط مسافری، هدف انتخاب خطوط بهینه و تعداد اعزام در هر خط برای بیشینه سازی مجموع مسافرین مستقیم است، از این رو انتخاب و مقدار دهی به متغیر های تصمیم از نوع x در مدل) 1( – )5( اهمیت به سزایی دارد. از این رو در الگوریتم پیشنهادی در این بخش، مقداری متغیر تصمیم x که از نوع عدد صحیح است، توسط الگوریتم ژنتیک تعیین می شود و سایر متغیرهای تصمیم مدل توسط یک مدل برنامه ریزی خط آزاد شده محاسبه می شوند .
بدین معنا که به ازا هر جواب برای متغیرهای تصمیمی x یک مدل برنامه ریزی خطی به صورت مدل) 11( – )21( حل میشود و مقدار تابع هدف )مجموع تعداد مسافرین مستقیم( محاسبه می گردد.

776955163778

Max   yr a b, ,
a b V,  e rr R  ab, )11(
128778136180

 yr a b, ,  da b,
e r r R  ab,  a b V, )19(
133989151682

 yr a b, , c xr
e rr R  ab,   r R e r, )20(
y .0 )21(
مدل) 11( – )21( با مدل) 1(- )5( در چند نکته با هم تفاوت دارند:
در مدل) 11(- )21(، x یک پارامتر است که توسط الگوریتم ژنتیک در هر مرحله محاسبه میشود و مقادیر آن با توجه به اینکه از الگوریتم ژنتیک بدست آمده اند، عدد صحیح هستند. این تغییر باعث کاهش در تعداد متغیرهای تصمیم مسئله میشود.
محدودیت) 5( حذف شده است. این محدودیت در الگوریتم ژنتیک برقرار می شود. این تغییر باعث کاهش در تعدا محدودیت ها میشود.
همانطور که دربخش قبل نیز بیان شد به علت ماهیت متغیرهای تصمیم از نوع y، شرط عدد صحیح بودن از روی متغیرهای تصمیم از این نوع حذف شده است. این تغییر باعث آسانتر شدن حل و کاهش زمان حل مدل) 11(- )21( میشود.
همانطور که بیان شد در الگوریتم ژنتیک هر جواب توسط یک رشته کروموزوم نمایش داده می شود. در این مسئله نیز هر جواب برای متغیرهای از نوع x به صورت شکل) 1( بیان می شود. با توجه به شکل) 1( در کروموزوم تعریف شده به تعداد خطوطپشنهادی تعریف شده در صورت مسئله، سلول وجود دارد. مقدار در داخل هر سلول بیانگر تعداد اعزام قطار در هر خط می باشد .به عنوان مثال با توجه به شکل) 1(، خط دوم دارای 10 اعزام است.

10 ……

شکل1. نحوه تعریف جواب به صورت یک رشته کروموزوم

شکل) 2( ، بیانگر الگوریتم ژنتیک مورد استفاده برای حل مسئله برنامه ریزی خطوط مسافری است. با توجه به نحوه تعریف جواب ،یک جمعیت اولیه به تعداد 100 عضو ایجاد می شود. سپس عمل جهش برای روی جمعیت به صورت زیر اجرا می شود .
در یک جواب از جمعیت، سلولی به صورت تصادفی انتخاب شده و به عدد موجود در آن، یک واحد اضافه می شود. احتمال انتخاب یک جواب از جمعیت برای جهش برابر با 1/0 می باشد ،بدین معنی که هر یک از جواب ها )کروموزوم ها( با احتمال 10 درصد جهش بر روی آن ها اجرا می شود.
والدین با احتمال مساوی 3/0 برای عمل لقاح از جمعیت انتخاب می شوند. عمل لقاح به صورت One point )یک نقطه از رشته جواب انتخاب شده و از آن نقطه با جواب دیگر جابه جا می شود(.
صورت می پذیرد و جامعه فرزندان تشکیل می شود.
10 درصد از بهترین جواب های جمعیت والدین برای جمعیت بعدی در نظر گرفته می شود .90 درصد مابقی را نیز از جمعیت فرزندان به صورت تصادفی انتخاب می شود .
از آنجا که جواب های ایجاد شده، ممکن است محدودیت) 5( را نقض نماید، به منظور برقراری این محدودیت، عمل اصلاح جمعیت انجام میشود .
در این عمل با توجه به هر جواب، مجموع تعداد اعزام ها روی هر کمان شبکه محاسبه می شود و برای هر کمان که این محدودیت نقض شده باشد، به طور تصادفی از یکی از سلول های جواب یک واحد کاسته شده و در محاسبات بقیه کمان ها نیز اعمال می شود. این عمل تا زمان رسیدن به جواب شدنی ادامه می یابد و برای کلیه جواب های جمعیت جدید اعمال می شود. جمعیت اصلاح شده یک جمعیت متشکل از 100 جواب شدنی با توجه به محدودیت) 5( است. برای کلیه جواب ها مدل) 11(- )21( حل شده و مقدار تابع هدف هر جواب محاسبه می شود. الگوریتم تا رسیدن به شرایط همگرایی مراحل بیان شده رادر هر مرحله تکرار می کند. شرط همگرایی در این مسئله اجرای 100 تکرار از الگوریتم در نظر گرفته شده است.

4. ارزیابی روشهای حل پیشنهادی الگوریتم پیشنهادی مبتنی بر روش ایجاد ستون در محیط مدل سازی GAMS و موتور حل CPLEX پیاده سازی و حل شده است. الگوریتم مبتنی بر روش ژنتیک نیز با استفاده از زبان برنامه نویسی جاوا پیاده سازی شده است. برای اطمینان از صحت جواب های بدست آمده از این دو روش پیشنهادی، سی و دو مسئله نمونه با اندازه های مختلف مطابق با جدول) 1( طراحی و آزمایش شده است. مسائل حل شده در این جدول با استفاده از الگوریتم شاخه و حد10 در نرم افزار CPLEX و همچنین روشهای حل پیشنهادی حل شده و نتایج و زمان حل توسط هر الگوریتم با یکدیگر مقایسه شده است. در مسائل حل شده تعداد ایستگاه ها 5، 10، 15، 20 ، 25، 30، 35 و 40 لحاظ شده است. خطوط پیشنهادی نیز به دو گونه تعریف شده است. در حالت اول بین کلیه ایستگاه ها خط پیشنهادی تعریف شده است که با علامت )F( نشان داده شده است. در حالت دوم پنجاه درصد تعداد خطوط پیشنهادی در حالت اول، به عنوان خطوط بالقوه تعریف شده است .
304

شکل7. الگوریتم ژنتیک مورد استفاده برای حل مسئله برنامه ریزی خطوط مسافری
این خطوط به گونه ای انتخاب شده اند که امکان جابجایی کلیه مسافرین به صورت مستقیم امکان پذیر باشد، از این رو خطوط بلند بیشتر مد نظر بوده اند. خطوط پیشنهادی در این حالت با علامت) H( نشان داده شده اند. در مورد ظرفیت تعداد اعزام روی هر کمان u(e) نیز دو حالت در نظر گرفته شده است. در حالت اول) T( ظرفیت اعزام ها روی هر کمان، کم لحاظ شده است و در حالت دوم) L( برای آن، مقدار زیادی لحاظ شده است. در جدول) 1(، ستون اول، شماره مسئله، ستون دوم، تعداد ایستگاه ها، ستون سوم، نحوه تعریف خطوط پیشنهادی، ستون، معرف نحوه تعریف ظرفیت اعزام روی هر کمان، ستون پنجم، تعداد متغیرهای تصمیم مسئله، ستون ششم، تعداد محدودیت های مسئله، ستون هفتم، معرف مقدار تابع هدف حاصل از حل توسط نرم افزار بهینه سازی با در نظر گرفتن عدد صحیح بودن متغیر ها، ستون هشتم، زمان حل مسئله توسط نرم افزار بهینه سازی ،ستون نهم، مقدار تابع هدف در صورت حل مسئله توسط الگوریتم پیشنهادی مبتنی بر الگوریتم ایجاد ستون و ستون دهم، زمان حل مسئله توسط این الگوریتم پیشنهادی است. ستون یازدهم ،مقدار تابع هدف با استفاده از الگورتم پیشنهادی مبتنی بر الگوریتم ژنتیک و ستون دوازدهم، زمان حل به وسیله این الگوریتم پیشنهادی است


فول تکست yaghini A 10 208 9 8ae04d7 1
قیمت: تومان