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

Articles

License

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

  1. The authors retain the copyright and grant Transportes the right of first publication of the manuscript, without any financial charge, and waive any other remuneration for its publication by ANPET.
  2. Upon publication by Transportes, the manuscript is automatically licensed under the Creative Commons License CC BY 4.0 license. This license permits the work to be shared with proper attribution to the authors and its original publication in this journal.
  3. Authors are authorized to enter into additional separate contracts for the non-exclusive distribution of the version of the manuscript published in this journal (e.g., publishing in an institutional repository or as a book chapter), with recognition of the initial publication in this journal, provided that such a contract does not imply an endorsement of the content of the manuscript or the new medium by ANPET.
  4. Authors are permitted and encouraged to publish and distribute their work online (e.g., in institutional repositories or on their personal websites) after the editorial process is complete. As Transportes provides open access to all published issues, authors are encouraged to use links to the DOI of their article in these cases.
  5. Authors guarantee that they have obtained the necessary authorization from their employers for the transfer of rights under this agreement, if these employers hold any copyright over the manuscript. Additionally, authors assume all responsibility for any copyright infringements by these employers, releasing ANPET and Transportes from any responsibility in this regard.
  6. Authors assume full responsibility for the content of the manuscript, including the necessary and appropriate authorizations for the disclosure of collected data and obtained results, releasing ANPET and Transportes from any responsibility in this regard.