International Journal of Industrial Engineering & Production Management (2014)

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

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

*
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: مجموعه خطوط پيشنهادي.
پارامترها:
,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
صحيح، يک الگوريم ابتکاري ارائه شده است. مراحل الگوريتمابتکاري پيشنهادي به شرح زير است:

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

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(، ستون اول، شماره مسئله، ستون دوم، تعداد ايستگاه ها، ستون سوم، نحوه تعريف خطوط پيشنهادي، ستون، معرف نحوه تعريف ظرفيت اعزام روي هر کمان، ستون پنجم، تعداد متغيرهاي تصميم مسئله، ستون ششم، تعداد محدوديت هاي مسئله، ستون هفتم، معرف مقدار تابع هدف حاصل از حل توسط نرم افزار بهينه سازي با در نظر گرفتن عدد صحيح بودن متغير ها، ستون هشتم، زمان حل مسئله توسط نرم افزار بهينه سازي ،ستون نهم، مقدار تابع هدف در صورت حل مسئله توسط الگوريتم پيشنهادي مبتني بر الگوريتم ايجاد ستون و ستون دهم، زمان حل مسئله توسط اين الگوريتم پيشنهادي است. ستون يازدهم ،مقدار تابع هدف با استفاده از الگورتم پيشنهادي مبتني بر الگوريتم ژنتيک و ستون دوازدهم، زمان حل به وسيله اين الگوريتم پيشنهادي است



قیمت: تومان


دیدگاهتان را بنویسید