International Journal of Industrial Engineering & Production Management (2014)

دانلود تحقیق IUST v24n4p492 en 1

دانلود تحقیق IUST v24n4p492 en 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

1268732040127

دانلود تحقیق IUST v24n4p492 en 1

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

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

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

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

به سایت مرجع

www.homatez.com

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

 

دانلود تحقیق IUST v24n4p492 en 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

*
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

دانلود تحقیق IUST v24n4p492 en 1

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


دانلود تحقیق IUST v24n4p492 en 1
قیمت: تومان