A hybrid method to solve railroad passenger scheduling problem

Abstract: Railroad transportation planning is strategically a long term and an important decision making problem especially in the area of travelling passengers. There have been literally various methods to use in order to provide optimum traveling schedule such as direct or indirect methods. Direct solutions involve the implementation of mixed integer programming, which is often hard to solve for real-world applications. The proposed model of this paper uses a column generation method to decompose a large-scale railroad passenger-scheduling problem into some smaller scale problems, which are easier to solve. The primary concern with the resulted problem is that final solutions of the method need to be integer and this is in contrast with convexity assumption of column generation techniques. We propose heuristic method to handle this problem and apply the proposed model for some examples. The preliminary results indicate that the proposed model of this paper could provide optimal solutions for small-scale problems and it can reach some reasonable solutions for larger problems when direct implementation fails to do in reasonable amount of time.

How to cite this paper

 Yaghini, M., Alimohammadian, A & Sharifi, S. (2002). A hybrid method to solve railroad passenger scheduling problem.Management Science Letters , 2(2), 543-548.

Refrences

Barnhart,C. & Laporte, G. (2007). Handbook in OR & MS. Vol. 14, Elsevier B.V.

Bussieck, M. R., Kreuzer, P., & Zimmermann, U. T. (1996). Optimal lines for railway systems. European Journal of Operational Research, 96, 54–63.

Br?nmo, G., Nygreen, B., & Lysgaard, J. (2010). Column generation approaches to ship scheduling with flexible cargo sizes. European Journal of Operational Research, 200(1), 139-150.

Burdett, R. L., & Kozan, E. (2009). Techniques for inserting additional trains into existing timetables. Transportation Research, Methodological, 43(8-9), 821-836.

Claessens, M. T., van Dijk, N. M., & Zwaneveld, P. J. (1998). Cost optimal allocation of passenger lines. European Journal of Operational Research, 110, 474–489.

Chung, J., Moo, S., & Choi, I. (2009). A hybrid genetic algorithm for train sequencing in the Korean railway.
Omega, 37(3), 55-65.

D’Ariano, A., Pacciarelli, D., & Pranzo, M. (2007). A branch and bound algorithm for scheduling trains in a railway network. European Journal of Operational Research, 183(2), 643-657.

Dezs?, B., Jüttner, A., & Kov?cs, J. (2010). Column generation method for an Agent Scheduling Problem. Electronic Notes in Discrete Mathematics, 36, 829-839.

Ghoseiri, K., & Ghannadpour, F. (2010). A hybrid genetic algorithm for multi-depot homogenous locomotive assignment with time windows. Applied Soft Computing, 10(1), 53-65.

Goossens, J. W., Hoesel, S. V., & Kroon, L. (2006). On solving multi-type railway line planning problem. European Journal of Operational Research, 168(2), 403-424.

Goossens, J. H. M., van Hoesel, C. P. M., & Kroon, L. G. (2004). A branch-and-cut approach for solving railway line-planning problems. Transportation Science, 38, 379–393.

Lindner, T. ( 2000). Train schedule optimization in public rail transport. PhD thesis, TU Braunschweig.

Liu, S.Q., & Kozan, E. (2009). Scheduling trains as a blocking parallel-machine job shop scheduling problem. Computers & Operations Research, 36(10), 2840-2852.

Lee, Y., & Chen, C. (2009). A heuristic for the train pathing and timetabling problem. Transportation Research, Methodological, 43(8-9), 837-851.

Mesquita, M., & Paias, A. (2008). Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem. Computers & Operations Research, 35(5) 1562-1575.

Oppen, J., L?kketangen, A., & Desrosiers, J. (2010). Solving a rich vehicle routing and inventory problem using column generation. Computers & Operations Research, 37(7), 1308-1317.

Peeters, M., & Kroon, L. (2008). Circulation of railway rolling stock: a branch-and-price approach.
Computers & Operations Research, 35(2), 538-556.

R?nnberg, E., & Larsson, T. (2010). Column generation in the integral simplex method. European Journal of Operational Research, 129(1), 333-342.

Scholl, S. (2005). Customer-oriented line planning. PhD thesis, University of Kaiserslautern.

Suryani, E., Chou, S., & Chen, C. H. (2010). Air passenger demand forecasting and passenger terminal capacity expansion: A system dynamics framework. Expert Systems with Applications, 37(3), 2324-2339.

Tsai, T. H., Lee, C. K., & Wei, C. H. (2009). Neural network based temporal feature models for short-term railway passenger demand forecasting. Expert Systems with Applications, 36(2), 3728-3736.

Journals

MSL Volumes

Keywords

Authors

Countries

Management Science Letters

A hybrid method to solve railroad passenger scheduling problem Pages 543-548 Download PDF

Add Reviews