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

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

فهرست:

عنوان مطالب 

صفحه 

چکیده

مقدمه

فصل اول: کلیات 

1- 1-  تعریف مساله                                                                                           4        

1- 2-  اهداف                                                                                                   5       

1- 3-  اهمیت موضوع                                                                                         6       

4-  روش تحقیق                                                                                           6        فصل دوم: مروری بر مطالعات انجام شده 

1-  زمانبندی دوره ای (اولیه) قطارها                                                                   9       

2- 1- 1- روش های مبتنی بر مدل سازی ریاضی                                                       10        

2- 1- 2- روش های مبتنی بر حل ابتکاری مدلهای ریاضی                                           11       

2- 1- 2-1- مدل هیگینز                                                                                   13      

2- 1- 2-2- مدل قصیری- مرشد سلوک                                                                 18      

2- 1- 3- روش های شبیه سازی                                                                          22    

2- 1- 4- روش های نوین جستجو                                                                        23     

2- 2-  زمانبندی ثانویه حرکت قطارها ( اصلاح و بهبود زمان بندی اولیه)                         23       

2- 3-  تحلیل و بررسی آماری تحقیقات گذشته                                                        24       فصل سوم: برنامه ریزی شبکه راه آهن 

3 1-  تعاریف و اصطلاحات                                                                               28 

و

3- 2-  بررسی شبکه های راه آهن                                                                       31  

3- 2- 1- برتری حمل ونقل ریلی در مقابل سایر سیستم های حمل ونقل                       32  

2- 2- شبکه راه آهن جمهوری اسلامی ایران                                                      32   فصل چهارم: مدل زمانبندی حرکت قطار ها 

1-روند کلی برنامه ریزی قطار                                                                      37 

4- 2-  نمودار مسافت-زمان                                                                               39 

4- 3-  فرضیات حل مساله                                                                                40 

4- 4-  مدل سازی مساله و نگرش های موجود                                                       42  

4- 4- 1- تابع هدف                                                                                        46 

4- 2- محدودیت های مساله                                                                         46  فصل پنجم: روش های حل مدل زمان بندی حرکت قطارها 

1-  روشهای حل متداول جهت حل مسائل ریاضی                                               57 

5- 2-  برنامه ریزی عدد صحیح و روش های حل آن                                                58 

5- 2- 1-- برناه ریزی صفر و یک                                                                        60   

5- 2- 2- برنامه ریزی صفر و یک مخلوط                                                              62 

5- 3-  حل مساله زمان بندی حرکت قطارها                                                          64 

5- 3- 1-تولید محدودیت جهت کوچک کردن فضای جستجو                                     65   

5- 3- 2-ارایه نامساوی معتبر                                                                             65 

5- 3- 3-ارایه یک روش ابتکاری جهت حد بالا برای تابع هدف                                    68  فصل ششم: نتیجه گیری و پیشنهادات 

       6-1- دستاورد های تحقیق                                                                             71 

6 1-1- زمان بندی مسیر تهران- تبریز در شبکه سراسری راه آهن ایران                      72 

ز

       6-1-2-   بهینه کردن زمان بندی ارایه شده توسط اداره سیر و حرکت                         73 

6- 2- نوآوری تحقیق                                                                                     74 

6- 2-1- ارایه مدلی کاربردی                                                                           74 

6- 2-2-ارایه زمان بندی بهینه مسیر با توجه به زمانها ی شروع و خاتمه معقول حرکت    74       

6- 2-3- کاهش زمان حل مساله                                                                       75      

6- 3- خروجی های تحقیق                                                                             78                            

6- 4- حساسیت مدل به تغیرات حد بالای توقفات ایستگاه ها                                    80 

6- 6- ارزیابی نتایج                                                                                       80  

6- 7- نتیجه گیری و پیشنهادات                                                                       82  پیوست الف: بررسی انواع فاصله زمانی بین دو قطار                                         85  پیوست ب: معرفی نرم افزار Cplex و GAMS                                                 89  1- معرفی نرم افزار Cplex                                                                         89   

1- 1-  حل مدل در Cplex                                                                              90  

2-  مقایسه اجمالی                                                                                   90                             

راهنمای نرم افزار GAMS                                                                          94    

2- 1-  چند نکته مهم برای شروع                                                                      94 

2- 2-  ساختار یک مدل در GAMS                                                                  95  

2- 3-  مجموعه ها                                                                                        97   

2- 4-  داده ها                                                                                             98   

2- 4- 1- ورود داده ها به وسیله لیستها                                                              98   

2- 4- 2- ورود داده ها با جدول                                                                       99                              

2 4- 3- ورود داده ها به صورت تعیین مستقیم                                                   100 

- 4-  ورود داده از سایر برنامه ها                                                                    100 

2- 5-  متغیرها                                                                                           101    

2- 6- معادلات                                                                                          101 

2- 7-  نماد گذاری مجموع و ضرب                                                                  101                             

2- 8-  تعریف معادلات                                                                                 102   

2- 9-  دستور مدل و حل                                                                              103  

2- 10-  دستور نمایش                                                                                 104                            

    ١٠۴                                                            ".LO,.L,.UP,.M" بانک داده  -11 -2

٢ -١١ -١- تعیین حد متغیر ها و مقادیر اولیه                                                     105    

2- 12-  خروجی GAMS                                                                             106  

2- 12- 1-  نسخه برگشتی مدل                                                                      106   

2- 12- 2-  پیغام خطا                                                                                  107 

2- 12- 3-  نگشاته های مرجع                                                                        107  

2- 12- 4-  لیست معادلات                                                                            107  

2- 12- 5-  آمار و اطلاعات مدل                                                                      108 

2- 12- 6-گزارشات وضعیت                                                                           108 

2- 12- 7 - گزارشات حل                                                                              109  پیوست ج: فلوچارت های حل مساله                                                                 110    پیوست د: اطلاعات ورودی و اطلاعات شبکه                                                      114   پیوست ه: خروجی های نرم افزار و گراف                                                            126 

منابع و ماخذ   

منابع فا رسی                                                                                    131      

منابع انگلیسی                                                                                                      132  

چکیده انگلیسی                                                                                            135  

منبع:

پورسید آقایی، محسن  " زمانبندی حرکت قطارها در شبکه یک خطه راه آهن"  پایان نامه دکترا-

  .1377

قیصری،کیوان "توسعه تئوریک مدل بهینه سازی زمانبندی حرکت قطارها با استفاده از ((MODM از نظریه باری ها" پایان نامه دکترا- 1381. 

طاهرپور، شهریار "زمانبندی حرکت قطارهای باری" پایان نامه کارشناسی ارشد- دانشگاه علموصنعت-1373. 

نجفی ، امیر عباس" زمانبندی قطارها و بکارگیری الگوریتم ژنتیک"پایان نامه کارشناسی ارشد-دانشگاه صنعتی شریف - 1377. 

عابدینی ، ایمان " زمانبندی حرکت قطارها با استفاده از یک روش  ابتکاری" پایان نامه کارشناسیارشد -  مؤسسه عالی آموزش و پژوهش-1376. 

عزیزخانی ، علیرضا " زمانبندی حرکت قطارها با استفاده از یک روش ابتکاری مبتنی بر الگوریتمژنتیک" پایان نامه کارشناسی ارشد –  دانشگاه صنعتی شریف -1381.  

خادم ثامنی، ملودی– مرشد سلوک ، فهمیه - انارکی ، سید مهدی و سپاسی، سمیر ا – پروژهکارشناسی همگی از دانشکده راه آهن علم و صنعت. 

8-وحیدی منفرد،امین - آموزش مقدماتی GAMS-دانشگاه صنعتی شریف-دانشکده صنایع 

جزوات و گزارشات سالیانه راه آهن جمهوری اسلامی ایران 

سایت رسمی راه آهن جمهوری اسلامی ایران (www.rai.ir) 

انگلیسی: 

Adenso-Diaz, B., Gonzalez, M.O., Gonzalez-Torre, P., 1999. On-line timetable re-  scheduling in regional train services. Transportation Research Part B 33 (6), 387–398. 12-Ahuja, R.K., Magnanti, T.L., Orlin, J.B., 1993. Network Flows: Theory, Algorithms, and  Applications. Prentice Hall, NJ.

Assad, A., 1980. Models for rail transportation. Transportation Research Part A 14 (3),  205–220.

-41  Bartusch, M., Mohring, R.H., Radermacher, F.J., 1988. Scheduling project networks with  resource constraints and time windows. Annals

-51 Brannlund, U., Lindberg, P.O., Nou, A., Nilsson, J.E., 1998. Railway timetabling using  Lagrangian relaxation. Transportation Science 32(4), 358–369.

-61 Cai, X., Goh, C.J., Mees, A.I., 1998. Greedy heuristics for rapid scheduling of trains on a  single track. IIE Transactions 30 (5), 481–493.

-71 Caprara, A., Fischetti, M., Toth, P., 2002. Modeling and solving the train timetabling  problem. Operations Research 50 (5), 851–861.

-81 Carey, M., 1994a. A model and strategy for train pathing with choice of lines, platforms  and routes. Transportation Research Part B 28988–1005.

-91 Carey, M., 1994b. Extending a train pathing model from one-way to two-way track.

 Transportation Research Part B 28 (5), 395–400.

-02Carey, M., Lockwood, D., 1995. A model, algorithms and strategy for train pathing. Journal  of the Operational Research Society 46 (8),  988-1005.

-12 Chen, B., Harker, P.T., 1990. Two moments estimation of the delay on single-track rail  lines with scheduled tra c. Transportation Science24 (4), 261–275.

22- Cordeau, J.-F., Toth, P., Vigo, D., 1998. A survey of optimization models for train routing  and scheduling. Transportation Science 32 (4), 380–404.

Dorfman, M.J., Medanic, J., 2004. Scheduling trains on a railway network using a discrete  event model of railway tra c. Transportation Research Part B 38 (1), 81–98.

-42De Reyck, B., Herroelen, W., 1998. Branch-and-bound algorithm for the resourceconstrained project scheduling problem with generalized precedence relations. European

 Journal of Operational Research 111 (1), 152–174

-52Greenberg, H.H., 1968. A branch-and-bound solution to the general scheduling problem.

 Operations Research 16 (2), 352–361.

-62 Higgins, A., Kozan, E., 1998. Modeling train delays in urban networks. Transportation  Science 32 (4), 346–357.

-72 Higgins, A., Kozan, E., Ferreira, L., 1996. Optimal scheduling of trains on a single line  track. Transportation Research Part B 30 (2), 147–161.

-82 Jovanovic, D., Harker, P.T., 1991. Tactical scheduling of rail operations: the SCAN I  system. Transportation Science 25 (1), 46–64.

-92 Kraay, D.R., Harker, P.T., 1995. Real-time scheduling of freight railroads. Transportation  Research Part B 29 (3), 213–229.

-03 Kroon, L.G., Peeters, L.W., 2003. A variable trip time model for cyclic railway timetabling.

 Transportation Science 37 (2), 198–212.

-13 Lawler, E.L., Wood, D.E., 1966. Branch and bound methods: A survey. Operations  Research 14 (4), 699–719.

-23 Luh, P.B., Chen, D., Thakur, L.S., 1999. An e ective approach for job-shop scheduling with uncertain processing requirements. IEEE Transactions on Robotics and Automation 15 (2),  .933–823

Newman, A.M., Nozick, L., Yano, C.A., 2002. Optimization in the rail industry. Handbook  of Applied Optimization, 704–718.

-43 Petersen, E.R., Taylor, A.J., 1982. A structured model for rail line simulation and  optimization. Transportation Science 16 (2), 192–206.

-53 Petersen, E.R., Taylor, A.J., Martland, C.D., 1986. An introduction to computer aided train  dispatching. Journal of Advanced Transportation 20, 63–72.

-63 Sabuncuoglu, I., Bayiz, M., 1999. Job shop scheduling with beam search. European Journal  of Operational Research 118 (2), 390–412.

-73 Sahin, I., 1999. Railway tra c control and train scheduling based on inter-train con ict  management. Transportation Research Part B 33(7), 511–534.

-83 Szpigel, B., 1973. Optimal train scheduling on a single track railway. Operations  Research’72. North-Holland, Amsterdam, Netherlands, pp. 343–352.

-93 Zhou, X., Zhong, M., 2005. Bi-criteria train scheduling for high-speed passenger railroad  planning applications. European Journal of Operational Research 167 (3), 752–771.

-04 Zhou, L., Hu, S., Ma, J., Yue, Y., 1998. Network hierarchy parallel algorithm of automatic  train scheduling. In: Proceedings of the

 Conference on Tra c and Transportation Studies, ICTTS, pp. 358–368.

-14 Allen, G.J, Mabrouk K.M, weigel. Utilizing an Expert system for conflict Resolution in a

Train siding selection simulation model . 1996 winter simulation conf. proceeding, Coronado,

 CA-USA.

-24 Araya S.,Abek.,Fukomori k., An optimal Rescheduling for on line Train Traffic Control In  Disturbed Situations. , proceeding of the 22' and IEEE conf on Decisions,1983.

Bud A.E, Nicholson A.E, Scheduling Trains With Genetic Algorithm. International conf.  on Neural Information processing and Intelligent Inf.,v.2,1997.

-44 Chiang T.W, Hau .H.Y, Cycle Detection In Repair –Based Railway scheduling system,  proceeding- IEEE International conf.on Robotic and Automation, v.3,1996.

-54 Fokumori k., et al, Fundamental Algorithm for Train scheduling based on Artificial  Intelligence , system and computers In Japan.v.18.No.1987.

-64 Goh c.j.,Mees A.I.,Optimal control on a Graph With Application to Train scheduling  problems.Mathematical computer Modelling, v.15,No.2,pp.33-42,1991.

-74 Gorman M.F.,An Application of Genetic and Tabu Searches to the Freight Rail road  operating plan problem , Annals of Operations Research, v.78,pp.51-69,1998. 48- Kraft E.r.,A  Branch and Bound Procedure for optimal Train Dispathing ,J.of  Transportation Res.Forum,v.28,pp263,1987.

-94 Martinelli D.R., Teng H.,optimization of Railway operations using Neural Network,  Transportation Res-c,v.4,No.1,pp.33-49,1996.

-05 Mees A.I, Railway scheduiling By Network optimization,. Mathematical computer  Modeling, v.13,No.1,pp.33-42,1991.

-15 Mills R.G.J., Perkins S.E,Pundney P.I., Dynamic Rescheduling of long-haul Trains for Improved Time keeping and energ conservation,.Asi- pacific J. of operation Res.v.8,pp.146 .1991,561

-25 Nediljkovich N.B., Norton N.C, Computrized Train scheduling , Western Australian  convernment Rail ways Report , pp.105-123,1984.

Oyama.T.,Hans-is.,Application of Discrete optimization Techniques to Train scheduling  problem ,. Asia-pasific J. of operational Res .,v.4,pp.158-186,1987.

-45 Scardua L.A.,Silvad M.C,train Dispatching using Expert system, PROCEEDING OF 5'th   IASTED International conf. on Applied Informatics,1997.