Genetic algorithm for the automatic drawing of octalinear maps of public transportation systems
DOI:
https://doi.org/10.14295/transportes.v22i1.696Keywords:
schematic map, public transportation, genetic algorithm, automated cartography, graph drawing, metro map.Abstract
The octalinear map, also known as subway map, is an informative tool for a public transportation system. Now-adays, the production of those maps is handmade and it is rapidly outdated. Consequently it becomes a costly task espe-cially for bus lines that are more complex and have a fast modification dynamic. As a solution to the problem of automatic drawing those diagrams, it was developed a technique that uses graph algorithms and genetic algorithms. Data from Bra-silia public transportation system was adopted to apply the technique. Results obtained have good quality and were al-most instantly. Genetic algorithm was proved to be an adequate solution.Downloads
References
Avelar, S. e M. Müller (2000) Generating topologically cor-rect schematic maps. In Proc. 9th Int. Symp. on Spatial Da-ta Handling (SDH’00).
Anand, S., S. Avelar, J. M. Ware e M. Jackson (2007)
Au-tomated schematic map production using simulated anneal-ing and gradient descent approaches. Geographical Infor-mation Systems Research - GISRUK'07.
Avelar, S (2002) Schematic maps on demand: Design, modeling and visualization. Thesis (PhD), Institute of Tech-nology Zurich.
Battista, G. D., P. Eads, R. Tamassia e I. Tollis (1999) Graph Drawing: algorithms for the visualization of graphs. Allan Apt, New Jersey, Estados Unidos.
Douglas, D. e T. Peucker (1973) Algorithms for the reduc-tion of the number of points required to represent a digital-ized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, v. 10, n. 2, p.
–122. DOI: 10.3138/FM57-6770-U75U-7727.
Galvão, M. (2010) Esquematizações infográficas automáti-cas para transporte público: usando algoritmos genéticos. Trabalho de Graduação – Ciência da Computação, Univer-sidade de Brasília.
Garland, K. (1994) Mr Beck´s Underground Map. Capital Transport Publishing.
Hong, S. H., D. Merrick e H. Nascimento (2005) The metro map layout problem. In: Proc. Graph Drawing 2004, Spring-er-Verlag.
Melanie, M. (1999) An Introduction to Genetic Algorithms. MIT Press, Cambridge, England
Neyer, G. (1999) Line simplification with restricted orienta-tions. 6th Int. Workshop on Algorithms and Data Structures
(WADS’99), Lecture Notes in Computer Science, v. 1663, p. 13–24, Vancouver, BC. Springer-Verlag.
Nöllenburg, M. (2005) Automated drawings of metro maps. Dissertation (Master’s degree), Fakultät für Informatik, Uni-versität Karlsruhe
Nöllenburg, M. e A. Wolff (2006) A mixed-integer program for drawing high-quality metro maps. In Proc. 13th Interna-tional Symposium on Graph Drawing. Springer-Verlag.
Stott. J., P. Rodgers, J. C. Martinez-Ovando e S. G. Walker (2011) Automatic Metro Map Layout Using Multicriteria Op-timization. Transactions on Visualization and Computer Graphics v. 16, n. 1, p. 101–114. DOI: 10.1109/TVCG.2010.24.
Wolff, A. (2007) Drawing subway maps: A survey. Universi-tät Karlsruhe.
Wolff, A. e M. Nöllenburg (2011) Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE Transactions on Visualization and Computer Graphics, v. 17, n. 5, p. 626–641. DOI: 10.1109/TVCG.2010.81.
Downloads
Published
How to Cite
Issue
Section
License
Authors who submit papers for publication by TRANSPORTES agree to the following terms:
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
