Modelo matemático para o planejamento da circulação de trens em ferrovias de linha singela

Authors

  • Edson Pimentel Pereira Universidade Federal do Espírito Santo
  • Rodrigo Alvarenga Rosa UFES-Universidade Federal do Espírito Santo
  • Pedro Pelacani Berger Universidade Federal do Espírito Santo
  • João Teixeira Carvalho VLI S/A
  • Glaydston Mattos Ribeiro Universidade Federal do Rio de Janeiro - UFRJ

DOI:

https://doi.org/10.14295/transportes.v25i1.903

Keywords:

Train Timetabling Problem, Railroad operation, Railroad transport.

Abstract

In the last years the export of agricultural and mineral commodities has increased in Brazil and this has led to an increase in rail demand to railroad transport. Then, it is important that mathematical models shall be proposed for the planning of trains´ movement with the objective to increase the amount of circulating trains. Thus, this paper presents a mathematical model based on the Job Shop model to solve the Train Timetabling Problem on a single track railroad. The proposed model allows the trains to have an earlier or delayed departure time in order to reduce the stopped time at a crossing yard. The model was solved using CPLEX 12.6 and tested were done with real data of Ferrovia Centro Atlântica (FCA). The model results were compared with the results of the current planning of FCA and in all tested scenarios the model obtained a reduction of the trains travel time.

Downloads

Download data is not yet available.

Author Biographies

Edson Pimentel Pereira, Universidade Federal do Espírito Santo

Mestre em Egnharia Civil pela UFES (2015). Possui graduação em Engenharia Elétrica pela Universidade Federal do Espírito Santo (2003) e Pós-Graduação em Engenharia de Segurança do Trabalho pela UCL(2006). Atualmente é Professor Efetivo do IFES - Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo - Campus Cariacica.

Rodrigo Alvarenga Rosa, UFES-Universidade Federal do Espírito Santo

Pós-Doutor no Programa de Engenharia de Transportes (PET) na COPPE/UFRJ. Bolsista de Produtividade da Fundação de Amparo à Pesquisa do Espírito Santo (FAPES) recebendo a bolsa Pesquisador Capixaba (2013-2016). Doutor em Engenharia Elétrica pela Universidade Federal do Espírito Santo (UFES), Planejamento Portuário utilizando Inteligência Artificial Distribuída (2006) Professor adjunto no Depart. Eng. Produção da UFES.

Pedro Pelacani Berger, Universidade Federal do Espírito Santo

Graduação em Estatística pela Universidade Federal do Espírito Santo e Mestrado em Engenharia Civil

João Teixeira Carvalho, VLI S/A

Engenheiro Ferroviário da VLI S.A., Engenheiro de Produção e Pós-graduado em Engenharia Ferroviária PUC-BH

Glaydston Mattos Ribeiro, Universidade Federal do Rio de Janeiro - UFRJ

Doutorado em Computação Aplicada pelo Instituto Nacional de Pesquisas Espaciais (2007) e Pós-Doutorado pela HEC-Montréal/Universidade de Montréal (2011). É professor do Programa de Pós-Graduação em Engenharia de Transportes da COPPE/UFRJ e também atua no Programa de Pós-Graduação em Energia do CEUNES/UFES. 

References

BORNDÖRFER, R.; Grötschel, M.; Lukac, S.; Mitusch, M.;Schlechte, T.; Schultz, S.; Tanner, A. An auctioning approach to railway slot allocation. Technical Report 05–45, Konrad-Zuse-Zentrumfür Information stechnik Berlin, 2005.

BORNDÖRFER, R.; Schlechte, T. Models for railway track allocation. Technical Report 07–02, Konrad-Zuse-Zentrumfür Informations technik Berlin, 2007a.

BORNDÖRFER, R.; Schlechte, T. Solving railway track allocation problems. Technical Report 07–20, Konrad-Zuse-Zentrumfür Information stechnik Berlin, 2007b.

BRÄNNLUND, U.; Lindberg, P. O.; Nõu, A.; Nilsson, J. E. Railway timetabling using lagrangian relaxation. Transportation Science 32(4):358–369, 1998. DOI: 10.1287/trsc.32.4.358

CACCHIANI, V.; Caprara, A.; Toth, P. A column generation approach to train timetabling on a corridor. 4OR 6:125–142, 2008. DOI:10.1007/s10288-007-0037-5

CACCHIANI, V.; Caprara, A.; Toth, P. Scheduling extra freight trains on railway networks. Transportation Research Part B 44(2):215–231, 2010. DOI: 10.1016/j.trb.2009.07.007

CACCHIANI, V.; Toth, P. Nominal and robust train timetabling problems. European Journal of Operational Research, Vol.219(3):727–737, 2012. DOI: 10.1016/j.ejor.2011.11.003

CACCHIANI, V.; Galli, L.; Toth, P. A tutorial on non-periodic train timetabling and platforming problems. EURO Journal on Transportation and Logistics. Springer-Verlag Berlin Heidelberg, 2014. DOI: 10.1007/s13676-014-0046-4

PEREIRA, E.P.; ROSA, R.A.; BERGER, P.P.; CARVALHO, J.T.; RIBEIRO, G.M. 20 TRANSPORTES v. 25, n. 1 (2017), p. 12-20

CAI, X..; Goh, C. J. A fast heuristic for the train scheduling problem. Computers & Operations Research 21 (5): 499–510, 1994.

CAI, X.; Goh, C. J.; Mees, A. I. Greedy heuristics for rapid scheduling of trains on a single track. IIE Transactions 30:481–493,1998.

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

CAPRARA, A.; Monaci, M.; Toth, P.; Guida, P.L. A Lagrangian heuristic alogorithm for a real-world train timetabling problem. Discrete Applied Mathematics 154:738–753, 2006. doi:10.1016/j.dam.2005.05.026

CAREY, M. A model and strategy for train pathing with choice of lines, platforms, and routes. Transportation Research Part B (5):333–353, 1994.

CAREY, M.; Lockwood, D. A model, algorithms and strategy for train pathing. The Journal of the Operational Research Society 4(8):988–1005, 1995.

CNT (CONFEDERAÇÃO NACIONAL DO TRANSPORTE). Pesquisa CNT de Ferrovias 2011. Brasília: CNT, 2011.

CNT (CONFEDERAÇÃO NACIONAL DO TRANSPORTE). Transporte e Economia – O Sistema Ferroviário Brasileiro. Brasília: CNT, 2013.

CORDEAU, J. F. ; Toth, P. ; Vigo, D. A survey of optimization models for train routing and scheduling. Transportation Science Vol. 32(4):380–404, 1998. doi.org/10.1287/trsc.32.4.380

DALL’ORTO, L. C.; Crainic, T. G.; Leal, J. E.; Powell, W. B. The single-node dynamic service scheduling and dispatching problem. European Journal of Operational Research, vol. 170(1), p. 1–23, 2006. DOI: 10.1016/j.ejor.2004.06.016

FABRIS, S.; Longo, G. ; Medeossi, G. ; Pesenti, R. Automatic generation of railway timetables based on a mesoscopic infrastructure model. Journal of Rail Transport Planning and Management 4:2–13, 2014. DOI: 10.1016/j.jrtpm.2014.04.001

GEIPOT (Empresa Brasileira de Planejamento de Transportes) Anuário Estatístico dos Transportes, 2001.

HARROD, S. S. A tutorial on fundamental model structures for railway timetable optimization. Surveys in Operations Research and Management Science, vol. 17 p. 85–96, 2012. doi:10.1016/j.sorms.2012.08.002

HARROD, S. S. A Method for Robust Strategic Railway Dispatch Applied to a Single Track Line. Transportation Journal, vol. 52(1) p.26–50, 2013. DOI: 10.1353/tnp.2013.0002

HAY, W. Railroad Engineering. 2nd ed. New York: Wiley-Interscience, 1982.

HIGGINS, A.; Kozan, E.; Ferreira, L. Optimal scheduling of trains on a single line track. Transportation Research Part B 30(2):147161, 1996.

HIGGINS, A.; Kozan, E.; Ferreira, L. Heuristic techniques for single line train scheduling. Journal of Heuristics 3:43–62, 1997.

JOVANOVI´C, D.; Harker, P. T. Tactical scheduling of rail operations: the scan I system. Transportation Science 25(1):46–64, 1991.

KRAAY, D.; Harker, P. T.; Chen, B. Optimal pacing of trains in freight railroads: model formulation and solution. Operations Research 39 (1):82–99, 1991.

LEAL, J. E.; Soares, A. C.; Nunes, L. S. N. Uma abordagem heurística para o problema de programação de trens em linhas singelas. In: XVIII ANPET - Congresso de Pesquisa e Ensino em Transportes – Florianópolis,2004.

LIU, S. Q.; Kozan, E. Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model. Transportation Science Vol. 45(2):175–198, 2011. DOI: 10.1287/trsc.1100.0332

LUSBY, R. M.; Larsen, J. Ehrgott, M.; Ryan, D. Railway track allocation: models and methods. OR Spectrum; vol. 33, p. 843-883, 2011. DOI: 10.1007/s00291-009-0189-0

OLIVEIRA, E.; Smith, B. M. A Job shop scheduling model for the single track-railway timetabling problem. Technical Report 21, University of Leeds, 2000.

PINEDO, M. L. Planning and Scheduling in Manufacturing and Services. 2nd ed. Springer Series Operation Research: New York, USA, 2009.

REIMANN, M., Leal, J. E. Single line train scheduling with ACO. In Proceeding EvoCOP'13 Proceedings of the 13th European conference on Evolutionary Computation in Combinatorial Optimization. p. 226-237 Springer-Verlag Berlin, Heidelberg 2013. DOI: 10.1007/978-3-64237198-1

SAHIN, I. Railway traffic control and train scheduling based on inter-train conflict management. Transportation Research Part B33:511–534, 1999.

SAUDER, R.; Westerman, W. M. Computer aided train dispatching: decision support through optimization. Interfaces 6:24–37, 1983. DOI: 10.1287/inte.13.6.24

SZPIGEl, B. Optimal train scheduling on a single line railway. Operation Research: 72:344–351.1973.

SZPIGEL, B. Sequenciamento de Trens. Dissertação de Mestrado. Pontifícia Universidade Católica do Rio de Janeiro: Rio de Janeiro, 1972.

TÖRNQUIST, J., 2006. Computer-based decision support for railway traffic scheduling and dispatching: a review of models and algorithms. 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, (Dagstuhl, Germany). Dagstuhl Research Online Publication Server, 2006. DOI: 10.4230/OASIcs.ATMOS.2005.659

TÖRNQUIST, J.; Persson, J. A. N-tracked railway traffic rescheduling during disturbances. Transportation Research Part B 41(3):342

, 2007. DOI:10.1016/j.trb.2006.06.001

TÖRNQUIST, J. N Design of an effective algorithm for fast response to the re-scheduling of railway traffic during disturbances. Transportation Research Part

Downloads

Published

2017-03-01

How to Cite

Pereira, E. P., Rosa, R. A., Berger, P. P., Carvalho, J. T., & Ribeiro, G. M. (2017). Modelo matemático para o planejamento da circulação de trens em ferrovias de linha singela. TRANSPORTES, 25(1), 12–20. https://doi.org/10.14295/transportes.v25i1.903

Issue

Vol. 25 No. 1 (2017)

Section

Artigos

License

Authors who submit papers for publication by TRANSPORTES agree to the following terms:

  1. Authors retain copyright and grant TRANSPORTES the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  2. Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of this journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in TRANSPORTES.

  3. Authors are allowed and encouraged to post their work online (e.g., in institutional repositories or on their website) after publication of the article. Authors are encouraged to use links to TRANSPORTES (e.g., DOIs or direct links) when posting the article online, as TRANSPORTES is freely available to all readers.

  4. Authors have secured all necessary clearances and written permissions to published the work and grant copyright under the terms of this agreement. Furthermore, the authors assume full responsibility for any copyright infringements related to the article, exonerating ANPET and TRANSPORTES of any responsibility regarding copyright infringement.

  5. Authors assume full responsibility for the contents of the article submitted for review, including all necessary clearances for divulgation of data and results, exonerating ANPET and TRANSPORTES of any responsibility regarding to this aspect.