Abstract
Schematic drawings showing railway tracks and equipment are commonly used to visualize railway operations and to communicate system specifications and construction blueprints. Recent advances in on-line collaboration and modeling tools have raised the expectations for quickly making changes to models, resulting in frequent changes to layouts, text, and/or symbols in schematic drawings. Automating the creation of high-quality schematic views from geographical and topological models can help engineers produce and update drawings efficiently. This paper describes three methods for automatically producing schematic railway drawings with increasing level of quality and control over the result. The final method, implemented in the tool that we present, can use any combination of the following optimization criteria, which have different priorities in different use cases: width and height of the drawing, the diagonal line lengths, and the number of bends. We show how to encode schematic railway drawings as an optimization problem over Boolean and numerical domains, using combinations of unary number encoding, lazy difference constraints, and numerical optimization into an incremental SAT formulation.
We compare resulting drawings from each of the three approaches, applied to models of real-world engineering projects and existing infrastructure. We also show how to add symbols and labels to the track plan, which is important for the usefulness of the final outputs. Since the proposed tool is customizable and efficiently produces high-quality drawings from railML 2.x models, it can be used (as it is or extended) both as an integrated module in an industrial design tool like RailCOMPLETE, or by researchers for visualization purposes.
The first author was partially supported by the project RailCons – AutomatedMethods and Tools for Ensuring Consistency of Railway Designs, with number 248714 funded by the Norwegian Research Council and Railcomplete AS.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Part of the COIN-OR project 2018: https://projects.coin-or.org/Cbc.
- 2.
References
IRS 30100: RailTopoModel - railway infrastructure topological model. The International Union of Railways (UIC) (2016)
Avelar, S.: Schematic maps on demand - design, modeling and visualization. Ph.D. thesis, ETH Zürich (2002)
Barrett, C., Tinelli, C.: Satisfiability modulo theories. In: Clarke, E., Henzinger, T., Veith, H., Bloem, R. (eds.) Handbook of Model Checking, pp. 305–343. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-10575-8_11
Björk, M.: Successful SAT encoding techniques. JSAT 7(4), 189–201 (2011)
Bozzano, M., et al.: An incremental and layered procedure for the satisfiability of linear arithmetic logic. In: Halbwachs, N., Zuck, L.D. (eds.) TACAS 2005. LNCS, vol. 3440, pp. 317–333. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31980-1_21
Brands, A.: Automatic generation of schematic diagrams of the Dutch railway network. M.Sc. thesis, Radboud University (2016)
Cabello, S., de Berg, M., van Kreveld, M.J.: Schematization of networks. Comput. Geom. 30(3), 223–228 (2005)
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. 4, 235–282 (1994)
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River (1999)
Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24605-3_37
Hürlimann, D.: Objektorientierte Modellierung von Infrastrukturelementen und Betriebsvorgängen im Eisenbahnwesen. Ph.D. thesis, ETH Zurich (2002)
Luteberget, B., Claessen, K., Johansen, C.: Design-time railway capacity verification using SAT modulo discrete event simulation. In: FMCAD. IEEE (2018)
Nieuwenhuis, R., Oliveras, A., Tinelli, C.: Solving SAT and SAT modulo theories: from an abstract Davis–Putnam–Logemann–Loveland procedure to DPLL(T). J. ACM 53(6), 937–977 (2006)
Nöllenburg, M., Wolff, A.: Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE Trans. Vis. Comput. Graph. 17(5), 626–641 (2011)
Nöllenburg, M.: Automated drawing of metro maps. Technical report 25, Universität Karlsruhe, Karlsruhe (2005)
Oke, O., Siddiqui, S.: Efficient automated schematic map drawing using multiobjective mixed integer programming. Comput. OR 61, 1–17 (2015)
Ozdal, M.M.: Routing algorithms for high-performance VLSI packaging. Ph.D. thesis (2005)
Papakostas, A., Tollis, I.G.: Algorithms for area-efficient orthogonal drawings. Comput. Geom. 9(1–2), 83–110 (1998)
Bane NOR: Model of the Norwegian rail network (2016). http://www.banenor.no/en/startpage1/Market1/Model-of-the-national-rail-network/
Seyedi-Shandiz, S.: Schematic representation of the geographical railway network used by the Swedish transport administration. M.Sc. thesis, Lund University (2014)
Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987)
van Dijk, T.C., Lipp, F., Markfelder, P., Wolff, A.: Computing storyline visualizations with few block crossings. In: Frati, F., Ma, K.-L. (eds.) GD 2017. LNCS, vol. 10692, pp. 365–378. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-73915-1_29
Wolff, A.: Drawing subway maps: a survey. Inf. Forsc. Entwick. 22(1), 23–44 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Luteberget, B., Claessen, K., Johansen, C. (2019). Automated Drawing of Railway Schematics Using Numerical Optimization in SAT. In: Ahrendt, W., Tapia Tarifa, S. (eds) Integrated Formal Methods. IFM 2019. Lecture Notes in Computer Science(), vol 11918. Springer, Cham. https://doi.org/10.1007/978-3-030-34968-4_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-34968-4_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34967-7
Online ISBN: 978-3-030-34968-4
eBook Packages: Computer ScienceComputer Science (R0)