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

1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

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[.
1268732040127Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

ورودي هاي مورد نياز براي مسئله برنامه ريزي خطوط مسافري شامل ايستگاه ها، ارتباط ريلي ايستگاه ها و تقاضاي سفر بين هر زوج مبدا و مقصد است. بنابراين تقاضا به صورت يک ماتريس تعريف مي شود. اگر شبکه ريلي با G(V,E) نمايش داده شود ، V بيان کننده ايستگاه ها و E بيان کننده مسيرهاي بين دو ايستگاه متوالي مفروض يا همان کمان هاي شبکه است. مجموعه V از n ايستگاه يا گره تشکيل شده است. ماتريس تقاضاي ورودي يک ماتريس n×n است. در اين مدل، تقاضا در مسير رفت با تقاضا در مسير برگشت، يکسان در نظر گرفته مي شود و برابر با حداکثر تقاضاي رفت يا برگشت فرض مي شود. علت اين مسئله، استفاده چرخشي3 از ناوگان است. بدين معنا که تعداد تکرار در مسير

3 Cyclic
1268732040127Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

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. روش حل پيشنهادي مبتني بر الگوريتم ايجاد ستون
1268732040127Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

همانطور که بيان شد، روش حل ارائه شده در اين مقاله مبتني بر الگوريتم ايجاد ستون است. اين الگوريتم يک روش حل دقيق براي دستيابي به جواب بهينه مسائل برنامه ريزي خطي است، که به نام الگوريتم تجزيه نيز شناخته شده است. به کارگيري اين روش براي حل مسائل بزرگ است که توسط نرم افزار هاي بهينه سازي در زمان قابل قبول امکان حلشان وجود ندارد. مقالات متعددي تا کنون در زمينه الگوريتم ايجاد ستون و حل مسائل گوناگون به کمک اين الگوريتم ارائه شده است که مي توان به
1268732040127Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:41 IRST on Saturday November 4th 2017

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 ورودي مسئله از زير مسئله ها و



قیمت: تومان


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