Automated generation of context-aware schematic maps: design, modeling and interaction

University of Porto Doctoral Thesis Automated Generation of Context-Aware Schematic Maps: Design, Modeling and Interaction Author: Jo˜ao Mourinho Supervisor: Prof. Teresa Galv˜ ao Co-Supervisor: Prof. Jo˜ao Falc˜ ao e Cunha A thesis submitted in fulfilment of the requirements for the degree of Doctor of Philosophy in the Department of Engineering and Industrial Management FACULTY OF ENGINEERING OF THE UNIVERSITY OF PORTO July 2015 Declaration of Authorship I, Jo˜ao Mourinho, declare that this thesis titled, ’Automated Generation of Context- Aware Schematic Maps: Design, Modeling and Interaction’ and the work presented in it are my own. I confirm that: This work was done wholly or mainly while in candidature for a research degree at this University. Where any part of this thesis has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated. Where I have consulted the published work of others, this is always clearly attributed. Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this thesis is entirely my own work. I have acknowledged all main sources of help. Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself. Signed: Date: i UNIVERSITY OF PORTO Abstract Faculty of Engineering of the University of Porto Department of Engineering and Industrial Management Doctor of Philosophy Automated Generation of Context-Aware Schematic Maps: Design, Modeling and Interaction by Jo˜ao Mourinho Spider Maps are schematic maps with enhanced features which make use of the conceptual spider maps design principles. They share a set of characteristics with traditional schematic maps, but they include innovative features such as a spider architecture which makes them an enhanced vehicle for spatial context communication for public transport networks. This thesis presents a comprehensive state of the art analysis regarding the cartographic evolution through time, the automated generation schematic maps and contextual aspects of map use. It also defines the concept of Spider Map, its design properties and presents a proof of concept regarding their advantages in comparison with traditional diagrammatic maps, both in what concerns to learning enhancement by reducing extraneous cognitive loading and to support user actions in a transportation network. These evidences were supported by a usability test conducted with real users. As most of the production of schematic maps is currently done manually or by assisted methods, being both approaches resource (time and money) expensive, this thesis proposes an approach which includes an innovative algorithm based on the tabu search metaheuristic to effectively generate them. A set of tests were conducted with real world maps, with the results showing excelling results in what concerns to execution speed, quality of solutions and the ability to support geographical constraints (such as rivers, lakes, mountains, etc). It is also shown show that the automated generation of spider maps can improve Location Based Services and interaction in Public Transportation systems. Universidade do Porto Resumo Faculdade de Engenharia da Universidade do Porto Departamento de Engenharia e Gest˜ao Industrial Tese de Doutoramento Gera¸c˜ao Autom´atica de Mapas Esquem´aticos Sens´ıveis ao Contexto: Desenho, Modela¸c˜ao e Intera¸c˜ao por Jo˜ao Mourinho Os Mapas-Aranha de transporte s˜ao mapas esquem´aticos com caracter´ısticas melhoradas que utilizam os princ´ıpios de desenho dos mapas-aranha conceptuais. Apesar de partilharem um conjunto de caracter´ısticas com os mapas esquem´aticos tradicionais, incluem tamb´em particularidades inovadoras como a arquitectura em aranha. Os Spider Maps s˜ao um meio melhorado para a comunica¸c˜ao de contexto espacial em redes de transporte p´ublico. Esta tese apresenta uma an´alise completa do estado da arte no que toca `a evolu¸c˜ao cartogr´afica atrav´es do tempo, da gera¸c˜ao autom´atica de mapas esquem´aticos e dos aspectos contextuais do uso dos mapas. Define tamb´em o conceito de Mapa-Aranha, as suas propriedades de desenho e apresenta uma prova de conceito no que toca `as suas vantagens em compara¸c˜ao com os mapas diagram´aticos tradicionais, tanto no que diz respeito `as melhorias de aprendizagem pela redu¸c˜ao da carga cognitiva como no apoio `as a¸c˜oes do utilizador numa rede de transportes. Esta prova ´e apoiada por um teste de usabilidade com utilizadores reais. Como a maior parte da produ¸c˜ao de mapas esquem´aticos ´e atualmente feita manualmente ou de forma semi-autom´atica, acarretando custos em termos de dinheiro e tempo, ´e tamb´em proposta uma abordagem inovadora para a sua gera¸c˜ao de forma eficaz e eficiente que inclui um algoritmo baseado na meta-heur´ıstica pesquisa tabu. Esta abordagem foi testada atrav´es de um conjunto de mapas reais com bons resultados no que toca ao tempo de execu¸c˜ao, qualidade das solu¸c˜oes e capacidade de suportar os acidentes geogr´aficos (tais como rios, lagos, montanhas, etc). Esta tese mostra tamb´em que a gera¸c˜ao autom´atica de mapas esquem´aticos pode tamb´em melhorar os Servi¸cos Baseados na Localiza¸c˜ao e a interac¸c˜ao em sistemas de transporte p´ublico. Acknowledgements Special thanks to my advisor Professor Teresa Galv˜ao and to my co-advisor Professor Jo˜ao Falc˜ao e Cunha for their great inspiration, support, help and true friendship along this project. I want to thank all the support and sympathy i had from all the Department of Engineering and Industrial Management people, in particular from Professor Jos´e Fernando Oliveira and Professor Jos´e Sarsfield Cabral. To my office colleagues and friends who walked along with me, a big thanks. They were always friendly, supportive and exemplar in all aspects of our daily work. I would also like to thank the people of OPT1and FWT2for their collaboration and to INEGI3for funding this research project. 1OPT is an company based in Porto which develops IT infrastructures for Transportation Services. http://www.opt.pt 2FWT is a company based in London which produces maps for transportation networks. http://www.fwt.co.uk 3INEGI is a research institute based in Porto iv Contents Declaration of Authorship i Abstract ii Resumo iii Acknowledgements iv Contents v List of Figures viii List of Tables xiv Abbreviations xvi 1 Thesis Overview 1 1.1 Motivation and Problem Definition ...................... 1 1.2 Research Questions ............................... 3 1.3 Objectives .................................... 3 1.4 Methodology .................................. 4 1.4.1 Automated Design of Context-aware Schematic maps ....... 4 1.4.2 Definition and Interaction of Spider Maps .............. 6 1.5 Thesis Outline ................................. 7 2 Literature Revision 8 2.1 Maps and Cartography ............................. 8 2.1.1 Map Definition ............................. 8 2.1.2 Maps as Communication Vehicles Through Times ......... 9 2.1.3 Map Taxonomy ............................. 20 2.1.4 Transportation Maps .......................... 20 2.2 Schematic Maps ................................ 25 2.3 Automated Generation of Schematic Maps .................. 30 2.4 Context Awareness and Cognitive Psychology ................ 39 v Contents vi 2.4.1 Map Creation as a Communication Process ............. 39 2.4.2 Concept Maps as Precursors of Schematic Maps .......... 43 2.4.3 Context Enhancement Techniques .................. 45 2.5 Location Based Services ............................ 51 2.5.1 Quality of Information in Mobile Services .............. 53 3 Spider Maps 55 3.1 Concept and Definition ............................ 55 3.2 Design Guidelines ................................ 58 3.3 Proof of Concept ................................ 60 3.3.1 Test Design ............................... 60 3.3.2 Phase 1 - Assessing Conceptual Maps ................ 62 3.3.3 Phase 2 - Assessing Bus Network Maps ............... 63 3.3.4 Results ................................. 65 3.3.4.1 Phase 1 - Conceptual Maps Test .............. 65 3.3.4.2 Transportation Network Maps Test ............ 69 3.3.5 Test Conclusions ............................ 73 3.4 Spider Maps as Location Based Services and Public Transportation Improvement .................................... 74 3.5 Conclusions ................................... 75 4 Problem Modeling 76 4.1 Problem Description .............................. 76 4.2 Spider Map Modeling ............................. 77 4.2.1 Semantically Rich Data Structure .................. 79 4.2.2 Simple Graph Data Structure ..................... 80 4.3 Data Structures ................................. 82 4.4 Modeling the Multicriteria Optimization Problem .............. 85 4.4.1 Decision Variables ........................... 85 4.4.2 The Objective Function ........................ 85 4.4.3 Constraints ............................... 92 4.4.3.1 Hard Constraints ...................... 92 4.4.3.2 Hybrid Constraints - Topological Relation Preservation . 94 4.4.3.3 Geographical Constraints .................. 97 4.5 The Tabu Search Algorithm .......................... 99 4.6 Conclusions ...................................101 5 The Proposed Approach 102 5.1 Initialization and Alignment to Grid .....................103 5.1.1 The SmartFit Algorithm ........................104 5.1.2 The HPPO Algorithm .........................106 5.2 Tabu Search Optimization Metaheuristic ...................114 5.2.1 Getting the Best Move .........................117 5.2.2 Spatial Distribution Analysis .....................119 5.3 Post Processing and Spider Map Output ...................120 5.3.1 Inserting Inflection Points .......................123 5.3.2 Dealing with Geographic Restrictions ................124 Contents vii 6 Testing in Real World 126 6.1 The GenX Framework .............................126 6.2 Tests and Results ................................127 6.2.1 Test Environment and Description ..................128 6.2.2 Parametrization ............................130 6.2.3 Results and Analysis ..........................133 6.2.3.1 Test 1 - Execution time ...................133 6.2.3.2 Test 2 - Quality versus Iterations Number .........134 6.2.3.3 Test 3 - Maximum Vertex Displacement Parameter Influence ............................136 6.2.3.4 Test 4 - Candidate Move Generation Ratio Parameter . . 138 6.2.3.5 Test 5 - Soft Constraint Isolated Effect of Parameters in Map Visual Presentation ..................139 6.2.3.6 Test 6 - Hard versus Soft Topological Relation Enforcement143 6.2.3.7 Test 7 - A* Pathfinding Overhead .............145 6.2.3.8 Test 8 - Spatial Distribution Smart/Blind Algorithm Evaluation .............................146 6.3 Real World Use .................................147 7 Conclusions 151 7.1 Summary ....................................151 7.2 Limitations of this Work ............................152 7.3 Main Contributions of this Thesis .......................153 7.3.1 Spider Map Concept ..........................153 7.3.2 Automated Spider Map Generation ..................154 7.3.3 Value to Society ............................154 7.4 New Insights for Future Research .......................155 A Map 1 - Avenida da Rep´ublica 157 B Map 2 - Castelo do Queijo 162 C Map 3 - P´olo Universit´ario 165 D Map 4 - Rotunda da Boavista 168 E Map 5 - S. Jo˜ao 171 F Map 6 - Paranhos 174 G Algorithm Execution Graphs for Test 2 177 Bibliography 182 List of Figures 1.1 A Spider Map in Lisbon showing the bus network available from Marques de Pombal .................................... 2 1.2 Boehm’s spiral model of the software process (c) IEEE 1988 [1] ...... 5 1.3 Incremental Delivery Software Development Model [2] ........... 6 2.1 Imago Mundi [3] (5th century B.C.), the oldest known map ........ 11 2.2 Hecatheus of Miletus world map (modern reconstruction) [4] (4th century B.C. ....................................... 11 2.3 The Shield of Achilles Map [5], modern recreation of the shield described at Homer’s Iliad (13th century B.C.) ..................... 11 2.4 Ptolemy World Map [6] (2th century A.D. .................. 11 2.5 The Peutinger Map (first sheet), showing roman routes [7] (From the 13th century A.D., believed to be a copy from a much older original). . . . . . 12 2.6 The Tabula Rogeriana [8] (12th century A.D.) ................ 12 2.7 The Da Ming Hum Yu Tu map [9] (14th century A.D.) ........... 12 2.8 De Virga World Map [10] (early 15th century A.D.) ............. 13 2.9 Bianco World Map [11] (early 15th century A.D.) .............. 13 2.10 Genoese World Map [12] (late 15th century A.D.) .............. 13 2.11 Fra Mauro World Map [13] (late 15th century A.D.) ............ 13 2.12 Diogo Ribeiro World Map [14] (16th century A.D.) ............. 14 2.13 Joseph DesBarres Atlantic Neptune Map [15] (18th century A.D.) ..... 15 2.14 Pigot and Co.’s New Map Of England and Wales With Part Of Scotland (detail of London) [16] (19th century A.D.) ................. 17 2.15 Michelin Road Map (detail of Auxerre) [17] (20th century A.D.) ...... 18 2.16 Smartwatches with GPS Personal Navigation [18] .............. 18 2.17 Google Maps - Palo Alto area [19] ...................... 19 2.18 India Topographic Map [20] .......................... 21 2.19 Thematic map, showing the number of Walmart stores per state in the United States in 2009 [21] ........................... 22 2.20 Mixed Cartographic-Thematic map, showing both the geography of France and the dates and places of the Tour de France of 2011 [22] ........ 23 2.21 Map Taxonomy according to its function ................... 24 2.22 Map Taxonomy according to its visual presentation ............. 24 2.23 London Underground Map, from the beginning of the twentieth century. Source: http://www.chadsayshello.com .................... 25 2.24 Most common generalization techniques [23] (adapted) ........... 26 2.25 Route Map: Cheam Bus Route Map [24] ................... 27 2.26 London Underground Diagram by Harry Beck [25] ............. 28 viii List of Tables xv 6.4 Results of Test 3. MVD = MaxVertexDisplacement, ET = Execution time, ET Var = Execution Time Variation in comparison with the same map with MVD=20, SC = Score, SC Var = Score Variation in comparison in comparison with the same map with MVD=20. .............137 6.5 Results of Test 4 - CMGRatio = Candidate Move Generation Ratio Value, ET = Execution time, ET Var = Execution Time Variation in comparison with the same map with CMGRatio=10, SC = Score, SC Var = Score Variation in comparison in comparison with the same map with CMGRatio=10. .................................139 6.6 Results of Test 6. ET - Execution Time, ET Var - Execution Time Variation, SC Var - Score Variation ........................144 6.7 Results of Test 7 ................................145 6.8 Results of test 8 (ID = Map ID) .......................146 Abbreviations CPU Central Processing Unit FWT London Based Company that produces the London Bus Maps GIS Geographic Information System GPS Global Positioning System GRASP Greedy Random Adaptive Search Procedures GUI Graphics User Interface HPPO Heuristic Point Placement Optimization ICA International Cartographic Association IPC Inter-Process Communication KPI Key Performance Indicator LBS Location Based Services MIP Mixed Integer Programming OPT Optimiza¸c˜ao e Planeamento de Transportes PT Public Transportation SGDS Simple Graph Data Structure SRDS Semantically Rich Data Structure SVG Scalable Vector Graphics TCP Transmission Control Protocol UDP User Datagram Protocol UML Unified Modeling Language VLSI Very Large Scale Integration XML Extensible Markup Language xvi To my parents for their unconditional love, to my sister and my two little nephews for their joy, to my shining angel Isabel, and to God, to whom i owe everything. xvii Chapter 1 Thesis Overview 1.1 Motivation and Problem Definition Public transportation systems are fundamental to support efficient mobility and cities’ livability. With the increasing complexity of public transportation networks, the existence of clear and easy-to-read transportation maps helps users to learn and understand the underlying network thus increasing ridership in public transports. The main questions when one looks at a transportation map are “Where am I?” and “From here, where can I go to?”. Improving passenger information does not mean to increase the amount of information provided to user. Instead, by eliminating superfluous information and entropy, it is possible to increase map learnability. A good transportation map will provide to the user the correct space context to make the map easier to understand and thus speed up trip planning. Schematic maps, due to their apparent simplicity, have been used to depict transportation networks on public transportation systems. They are diagrammatic representations based on highly generalized lines, usually not following precise geographic accuracies. They use a non-linear scale that emphasizes some details while omits or removes relevance from others. A good example of a schematic map is the one produced by Harry Beck for London Underground in 1933 [25]. A particular type of schematic map called Spider Map is particularly well suited to improve user learning due to its inherent context improving features. Spider maps are suited to depict bus or underground transportation networks in a city or region. Instead of representing the entire network, spider maps represent a particular area of specific context, but they are still able to provide the user with the complete transport network overview. The diagrammatic representation has a central area, named Hub, from which all the schematic routes leave. This central area may depict a geographic representation of a borough, a tourist area or a transport interface. The Hub adds context to the 1 Chapter 1. Introduction 2 information provided to the user, as it provides details about the area where the user currently is, such as streets names, bus stops locations or relevant touristic places (see figure 1.1). Figure 1.1: A Spider Map in Lisbon showing the bus network available from Marques de Pombal Several cities around the world offer schematic maps to the citizens, mainly for metro networks or bus networks. Teams of cartographers and designers produce these schematic maps by hand. This manual work involves high costs, especially when the transportation network suffers frequent changes. In 2009, MBTA (Boston, USA) launched a 2-year project for replacing the existing schematic map with a total cost of $500,000 for labor and production [45]. The production of schematic maps is, therefore, an expensive and time consuming task. As a consequence, schematic maps cannot be effectively used for powering Location-Based Services (LBS) where near real time agile schematic map production is needed, nor the contextual advantages of spider maps can be fully extracted. Consequently, there is the need to develop methods to automatically generate spider maps in an effective and efficient way. In this research work we propose an approach to automatically generate Spider Maps through a comprehensive information system that includes an innovative algorithm based on the tabu search meta-heuristic that can produce ready-to-publish quality spider maps in soft real time. The automated production of spider maps opens a new world of context Chapter 1. Introduction 3 dependent applications and drastically reduces production and maintenance time and costs. To our best knowledge, the automatic generation of transportation spider maps has not been addressed in literature, and all the research made on the topic of the generation of schematic maps fails to model the multidisciplinary nature of the problem in some aspect. With this research we also intend to define spider maps, their properties and to demonstrate that they are more effective than traditional schematic maps in the communication of public transports information, user learning and interaction, testing them with real users and real world maps. If generated automatically, spider maps can be an effective tool in powering LBS, increase information quality available to users and increase Public Transportation (PT) ridership. 1.2 Research Questions The research questions that guide this thesis are the the following: •Q1 What are the significant features that define the spider map, concerning its mathematical properties and visual presentation? •Q2 Can we prove that Spider Maps are better than traditional Schematic Maps concerning to user experience in wayfinding? •Q3 How to effectively generate Spider Maps through an information system addressing the issues of the current state of the art? 1.3 Objectives This research work has the following objectives: •Describe the state of the art in what concerns to the problem of the design, modeling and interaction of schematic maps. •Define and systematize the set of features that comprise effective context-aware schematic maps (spider maps). •Test the validity of the spider map concept and its advantages regarding traditional schematic maps both conceptually and in practical use in public transportation networks. Chapter 1. Introduction 4 •Build a theoretical framework that supports the assumption that spider maps improve LBS and PT ridership •Develop an effective and efficient system of computer algorithms capable of generating good context-aware schematic maps in soft real time, by mapping into the algorithm knowledge from different areas. •Develop a software framework that could support and power the algorithms in the task of automatically generate context-aware schematic maps •Evaluate the performance and quality of the algorithms that were developed. •Impact real world public transportation, both socially and economically, bringing advantages both to transportation company ecosystem and end users. 1.4 Methodology In order to be successful, this investigation followed a mixed approach, as literature revision showed us that the design, modeling and interaction of context-aware schematic maps generated by automatic means is not complete and there are many voids in what concerns to its state of the art. The knowledge, therefore, needs to be obtained not only by a objective/quantitative approach (mathematics, computing algorithms) but also by a qualitative vision, as it deals with subjective concepts (like human perception, user satisfaction, information quality) which are inherently subjective and contextdependent. In addition, this is a complex multidisciplinary problem that involved a great deal of research and information integration from different (but often intersecting) areas of knowledge such as computer science and software engineering, mathematics and operations research, artificial intelligence, cognitive psychology, linguistics, services, human-computer interaction, arts and cartography. 1.4.1 Automated Design of Context-aware Schematic maps In what concerns to the problem of the automated generation of context-aware schematic maps, it was important to understand the nature of the problem, why the problem is important and how this research could contribute to improve the actual state of the art. In order to achieve that, a comprehensive literature and state of the art analysis was carried out along with a critical analysis of the advantages and disadvantages of several researches on the field. The strong points and shortcomings of each approach to this problem were summarized. This study can be classified as exploratory and descriptive, as the investigation questions found helped to shape our investigation. The solution of this Chapter 1. Introduction 5 problem, more than purely academic or theoretical, needs to have a strong connection to real world (and have social and economic consequences). Therefore, the close cooperation with real world business experts in the transportation field such as OPT and FWT was crucial to mold the course of the research as real world presents some challenges that are not usually found in purely conceptual problems. The implementation of the information system that could generate context-aware schematic maps in an automatic way was not a sequence of activities with some backtracking from one activity to another. It was based on a spiral model instead[46], as depicted in figure 1.2, for the development of the main algorithms, mixed with an incremental delivery model (figure 1.3) when small improvements were produced for each of the main algorithms. Figure 1.2: Boehm’s spiral model of the software process (c) IEEE 1988 [1] This mixed development model allowed us to combine the advantages of both models: for the main algorithms, each spiral cycle allowed us to elaborate objectives such as performance and functionality. Alternative ways of achieving these objectives and the constraints imposed on each of them are then enumerated. Each alternative is assessed against each objective and the advantages and risks of each option were identified. The identified risks were then addressed through the literature revision or, if no literature Chapter 1. Introduction 6 on the issue existed, creative ways of tackling the problem were developed, followed by more detailed analysis, prototyping and simulation. Having done this, the development of the software was carried one (algorithm coding, unit tests, integration, integration tests. Figure 1.3: Incremental Delivery Software Development Model [2] When an algorithm was developed through the spiral model, before proceeding to the next spiral cycle, it entered in an incremental delivery model: making small improvements and delivering them till the improvement potential of the algorithm was exhausted. After that, the algorithm proceeded to the next spiral model cycle. The computer software framework supporting the algorithm system for the development of context-aware schematic maps was specified through a complete descriptive method, as the framework properties and architecture needed to be described (software engineering requirement elicitation). The properties of the framework and the generated maps needed to be tested through a pure experimental plan, where several schematic maps (intentionally varying in its properties and characteristics) were tested. 1.4.2 Definition and Interaction of Spider Maps As the concept of Spider Maps for as a context-aware type of schematic map for depicting transportation networks was non-existing in the literature, the first task was to systematize their features and elaborate their definition. To prove the validity of this definition and all the advantages concerning traditional schematic maps, a user test based on the best quality versus cost examples of usability testing found in the literature was conducted, through a field experiment. This assured the external validity of the results. The satisfaction level of the users was measured through a brief written interview, with a couple of open questions, in order to gather valuable feedback from the users. The interview was semi-structured as there was a simple predefined question structure but there was space given to users if they wanted to disclose further details about their user experience. Learning times and other relevant indicators were measured through the observation method and the use of measuring instruments. Then, the information Chapter 1. Introduction 7 was put together with the interview results. The intention was not to get an absolute measurement of user friendliness, but a relative comparison measure between traditional schematic maps and spider maps and classify their comparative quality. 1.5 Thesis Outline The research in this thesis investigates and contributes to the design, modeling and interaction challenges of context-aware schematic maps applied to transportation networks. The thesis is organized in seven chapters, with chapter 1 being the introduction. In Chapter 2the foundations on where our research work was developed are described. The state of the art regarding the evolution of maps and the characteristics of schematic maps and the spatial communication exercise in which they take part are exposed. The evolution of the research on the automated generation of schematic maps is also presented, with a relative evaluation of each approach in what concerns to its advantages and shortfalls. Then, important previous work about cognitive psychology, human interaction and context aspects in maps is detailed. A description of the Location Based Services and their characteristics is also presented. In Chapter 3the context-aware enhanced schematic map, called Spider Map, is defined. Its formal definition, characteristics and particular advantages in what concerns to traditional schematic maps are presented. In this chapter it also made proof of its concept, through the description of a user testing process regarding the use of spider maps versus traditional schematic maps. The chapter ends by highlighting the theoretical bases on how spider maps can enhance Location Based Services. Chapter 4thoroughly presents the modeling of the problem of the automated generation of Spider Maps, starting with the description of the problem. The Spider Map data structures and multicriteria optimization modeling are portrayed. The approach to automatically generate spider maps is proposed in Chapter 5, regarding its architecture and algorithms. The tests conducted on real map instances with the algorithms developed based on our approach are presented in Chapter 6, together with the description of the GenX software framework developed along this research work. The tests are described and their results are presented and analyzed. Finally, the conclusions and contributions of this thesis are highlighted and the insights for future research are presented in chapter 7. Chapter 2. Literature Revision 14 Figure 2.12: Diogo Ribeiro World Map [14] (16th century A.D.) about, and graphic representation of, the world at various scales. One of those cognitive transformations was the recognition, by groups of people, that what today we call a map could record and structure human experience about space. Whether this was intuitive or conscious, a graphic language of maps was being developed. Other cognitive transformation derives from the former one: maps have become graphical designed artifacts with distinctive geometrical structures and arrays of signs recognizable to the intended viewers. We can think of the syntax, semantics and pragmatics here, if we are describing the use of maps as a communication process. With the evolution of maps, a set of common geometric elements appeared: all maps share a number of common elements, as the frame, which bounds the area of the map. This was an innovation of the Renaissance era, as it was not present in the Peutinger Map (figure 2.5, where the area of the map was limited by the format of the scroll on which it was drawn. A second geometric element was the nonexistent notion of uniform scaled image, as in many of those maps some areas were given significantly different weight and map space, according to the map function and political or religious importance. Other geometric feature was the centering of maps: a point of higher importance was chosen to be the center of the map. This reflects the same sort of manipulation of the geometry of the map to fit a specific perception of the world. Another very important geometric feature which is fundamental to influence the cognition of space is map projection and orientation, as a transformation from real coordinates to map coordinates had to be performed. More than a mirror of society, maps are a reciprocal part of cultural growth and influence the pattern of its development. Chapter 2. Literature Revision 15 Cartographic activity has increased with the transition from the Renaissance to the Enlightenment era, as the exploration of the globe was being executed at high speed and geographical findings were being rationalized and analyzed together with other types of knowledge. Mercator, Ortelius, Cassini and many others improved the cartographic science on that time frame, and thus maps begun to reflect that integration in the work of newly created scientific institutions to bolster cartographic works. Government and administrative institutions increasingly relied on maps in order to manage and control their territories, although this remained very much an unstructured process until the beginning of the nineteenth century. Expanded map consumption resulted from increasing economic stability and growth after the seventeenth century. This in turned spurred increased literacy, allowing the middling sort to engage in cultural and political criticism within the “public sphere”. An increased widespread print and visual culture produced maps that adhered to a common aesthetic of layout and design [53]. An example is the Atlantic Neptune atlas by Joseph DesBarres, an important collection of maps of North America made for the British Admiralty depicted in figure 2.13. Figure 2.13: Joseph DesBarres Atlantic Neptune Map [15] (18th century A.D.) At the late 18th century, the industrial revolution brought a wide set of scientific, economic and social changes which pushed new developments, namely in the transportation field. [54] The geographical world had already been discovered but the transportation systems (railways, roads, airways, underground systems, high-speed trains) have been Chapter 2. Literature Revision 16 growing till today, and they are expected to continue to grow. Large urban areas appeared and needed complex transportation systems, combining different transportation types. The need of highly efficient, easily understandable (and thus, practical) transportation maps pushed the evolution of the traditional maps, and new forms of cartographic representation have emerged. The importance of route maps on modern society has been increasing. At the nineteenth century, railway and route maps started to be more common. One example is the 1841 Pigot and Co.’s New Map Of England and Wales With Part Of Scotland, which depicted mail roads, turnpike roads, cross Roads, rail roads, rivers and navigable canals (figure 2.14). With the massification of the automobile in the twentieth century and increasingly dense transportation networks, transportation maps (such as road maps) became widespread. An example is the Michelin Road map collection [17]. The second half of the twentieth century has seen the rise of computing technology, and computers became an important base of all human activity. The first Geographic Information Systems (GIS) was developed in the 1960 decade in Canada by Tomlinson [55] and their use become generalized in many activities such as public service planning (including public transportation networks) and military applications. The GIS conceptualized by Tomlinson was a digital analogy of the physical multilayer geographic maps previously used. Modern GIS technologies use digital information merged and filtered from several sources (aerial or satellite imaging, digitization of geographic points, etc) to present a true integrated information system. Other important development was the Global Positioning System (GPS) which helped to add the variable “time” into GIS and turning them in Real Time GIS [56]. The development of personal computing, portable and wearable devices, together with the onset of real time GIS and GPS democratized the access to GIS. New types of navigation and wayfinding appeared, such as the personal navigation systems with usercentered perspective [57] [58], as seen in figure 2.16. Parallel to these developments was the use of the World Wide Web as communication platform. For many years, it has been the medium to acquire and disseminate geospatial data. This resulted in new mapping techniques as well as new possibilities for uses not seen before with traditional printed maps and most on-screen maps. A true revolution was caused in 2005 by the introduction of the programmes Google Earth and Google Maps [48]. Everyone with internet access could display satellite data and maps for free on a level of detail that was not heard of before (figure 2.17) From the early Babylonian maps to the current map applications, it is possible to see that mapping provided a vehicle not only for space presentation but also for the implicit and explicit transmission of ideas. Maps are part of the communicative process intended to Chapter 2. Literature Revision 17 Figure 2.14: Pigot and Co.’s New Map Of England and Wales With Part Of Scotland (detail of London) [16] (19th century A.D.) Chapter 2. Literature Revision 18 Figure 2.15: Michelin Road Map (detail of Auxerre) [17] (20th century A.D.) Figure 2.16: Smartwatches with GPS Personal Navigation [18] Chapter 2. Literature Revision 19 Figure 2.17: Google Maps - Palo Alto area [19] communicate space information: the producer of maps (i.e. the sender) communicates to the receiver the message (map). The making of maps was only possible through the use of symbols and abstraction (which serve as a language), as maps are mainly intended to communicate space information. They use a language, a conceptualization of the reality. However, “(...) we must accept, although our general position is founded in semiology, that precise scientific analogies to the structure of language may be impossible to sustain.” [52]. Being so, as with every translation from a real domain to a conceptual domain we accept that inevitably there is loss of information. A similarity is the conversion of an analog signal to a digital signal: the analog signal is continuous and contains the “truth” about the signal, while the digital signal is a discretization of the continuous signal, and therefore it is a simplification. The fidelity level of the digital signal is related to its sampling frequency and resolution. The same happens in cartography: if we increase the fidelity level of a map, we need more information resolution. In practice this means magnified scales (the more magnified, the closer to reality till reach the 1:1 scale) and less schematization. Of course this implies, for example, a larger piece of paper as a map basis (or a larger screen, if we talk about digital visualization). As its dimensions increase beyond the reasonable, the advantages of the map start to fade. Therefore, the schematization and simplification of detail is an inherent and necessary part of cartography. In some special cases, the geometric accuracy in the map will be less important than functional relationships between mapped features. To serve this purpose, mapmakers sometimes distort map’s geography to show relations that are more meaningful to the map users [23]. Thus the degree of information loss (distortion Chapter 2. Literature Revision 20 or dissimilarity with reality) is related to the trade-off between connection to the reality and practical use of the map. 2.1.3 Map Taxonomy Although there is not an explicit agreement regarding the taxonomy of maps, they can be divided into two main classes with non intersecting characteristics: topographic and thematic[59]. While topographic maps communicate the general image of the surface of an area (figure 2.18), thematic maps represent the distribution of one or several particular phenomena (figure 2.19) or represent the relations between phenomena (for example, conceptual maps for learning purposes). Topographic maps feature some degree of distortion of area [60], and distortions reveal information about the places that would otherwise be difficult to observe [50]. From the two main categories we can create a new one that mixes characteristics from the first ones in differing degrees. Nowadays, most of commonly used maps mix topography with thematic approach to improve readability and include clues to tailor geographic features to special purposes (figure 2.20). In the mixed category it is possible to include climate maps, economic maps, political maps, and transportation maps. Transportation maps, in turn, are a generic definition for maps which serve the purpose of communication transport network information, and encompass the route maps, metro maps, railway maps, transit maps, schematic maps. Figure 2.21 summarizes this categorization. Maps can be also classified regarding its visual presentation. Diagrammatic maps are simplified maps, they are intended to form a general idea of the phenomenon or event shown in graphic form on the map and to emphasize its fundamental characteristics. Schematic maps increase simplification to a higher degree, using highly generalized lines that conform to a specific and finite orientation schema. Spider maps are a special type of schematic map that appeared recently and follows visual architecture resembling the layout of a spider (figure 2.22). 2.1.4 Transportation Maps In this thesis we pay attention to transportation maps. They depict paths between location points and are nowadays one of the most common form of graphic communication. One famous map is the London Tube Map (figure 2.23) that has seen many developments and updates since the nineteenth century. Map producers use a wide array of generalization techniques to improve the clarity of the map and to emphasize important information that needs to be communicated[61]. Chapter 2. Literature Revision 21 Figure 2.18: India Topographic Map [20] Although creating a simple sketch depicting a simple route for personal use may be a simple task, when we talk about transportation maps, the underlying design is quite complex. Map makers use a variety of cartographic generalization techniques to improve the clarity of the map and to emphasize the most important information [62]. The most common generalization techniques are presented in the following list[23], and illustrated in figure 2.24. •Simplification - Selectively reducing the number of points required to represent an object •Smoothing - Reducing angularity of angles between lines •Aggregation - Grouping Points locations and representing them as aerial objects •Amalgamation - Grouping of individual areal features into a larger element Chapter 2. Literature Revision 22 Figure 2.19: Thematic map, showing the number of Walmart stores per state in the United States in 2009 [21] •Collapse - Replacing and objects physical details with a symbol representing the object •Merging - Grouping of line features •Refinement - Selecting specific portions of an object to represent the entire object •Exaggeration - To amplify a specific portion of an object •Enhancement - To elevate the message imparted by the object •Displacement - Separating objects Generalization of transportation maps causes them to be “diagrammatic” maps, by their inherent sparseness and imperfection, but those factors facilitate learning of the map by the user, by being more straightforward and not overwhelming user imagination with the completeness of the concrete visual world or with details shown in non-diagrammatic maps [60] (figure 2.25). Metro maps depict routes as as compromised spatial and logical transformation, where only relevant data is presented to users. Generalization techniques, therefore, are essential to simplify the complexity of the route system for presentation. Being so, metro maps often present qualitative spatial concepts adapted to Chapter 2. Literature Revision 23 Figure 2.20: Mixed Cartographic-Thematic map, showing both the geography of France and the dates and places of the Tour de France of 2011 [22] common characteristics of mental knowledge representation [63]. This means that in what concerns to transportation maps, it is more important for users to capture the basic structure of the network than to show accurately physical locations on the map. Cognitive psychology research shows that an effective route map must clearly communicate all the turning points on the route[64], and that precisely depicting the exact length, angle, and shape of each transportation line is much less important[65], although when traveling at earth’s surface, the use of important clues is proved to improve user learning [66] [67]. 2.2 Schematic Maps The need of highly efficient, easily understandable (and thus, practical) transportation maps pushed the evolution of the traditional maps, and new forms of cartographic Chapter 2. Literature Revision 30 Avelar also includes a set of other aesthetic features, but they are not considered to be included in the commonly accepted definition of schematic map, such as the line coloring and shape scheme, line corner aesthetics and styles as they are not specific and exclusive characteristics of schematic maps. 2.3 Automated Generation of Schematic Maps Nowadays, schematic maps are widely used in transportation networks, and they keep most of the design principles introduced by Harry Beck. Nevertheless, not much has been written about them. Some authors [60] defend that the production of schematic maps can be be manual, assisted and automatic. The manual design of schematic maps involves a spiral iterative labor-intensive process where sketches are produced entirely by hand in the search of the most pleasing solution, and incremental steps toward that direction are taken from sketch to sketch. The assisted method is the currently most used method since the advent of computers and computer assisted design software. In this method, the geographical coordinates transportation network points are digitized (through GPS or other assisted measurement tools), the geographical features are used as the background of the map, and re-placement of the visual elements such as lines and stops is done with manual input from the user. Although this method is faster than the pure manual production, it requires as much visual evaluation and iteration from the map producer. The automatic method is based on the automation of the whole process of the production of schematic maps, by implementing strategies to automate each of the phases of the schematization process (figure 2.27. Automating the process has been, and continues to be, the subject of much research [76][77][78], nevertheless those approaches have yet to support real world complexity and interaction. Nowadays, most of the maps are still made by teams of expert designers, with a mix of manual and assisted methods[79]. The roots for the automated generation of schematic maps can be traced to the development of computer graphic geometry. In 1973, Douglas and Peucker published a scientific article proposing an algorithm for the reduction of the points needed to represent a line[27]. This paper also predicted what would be one of the major components of schematization algorithms by stating “line reduction will form a major part of automated generalization”. Line generalization involves simplifying the line such that the overall form of the line is maintained as much as possible. The Douglas and Peucker heuristic is used as a basis for many schematization algorithms. This heuristic recursively subdivides the original line at the node which is furthest from a line between the two end-points until all nodes are within a certain error criterion (fig. 2.28). Chapter 2. Literature Revision 31 Figure 2.28: Example of the Douglas and Peucker Algorightm [26] [27] Douglas and Peucker algorithm runs in O(nlog n) time, although it may not find the optimal solution (keeping the overall form of the line). By this time, map schematization was focusing on relaxations of the network structure while keeping topological accuracy. Routes and junctions were symbolized abstractly [80]. Elroi [81] enhanced the process by proposing a three step algorithm: 1. Simplify lines to their most elementary shapes 2. Re-orient lines to conform to a predefined regular grid, to obtain a 0, 45 and 90 degree schema 3. Apply differential scaling to allow congested areas to be magnified while sparse areas are condensed With this research work, Elroi laid the theoretical foundations of the schematization process, despite not providing any real world examples. He pioneered the idea of embedding the map layout on a regular grid[82]. At that time, Weibel and Brassel published a conceptual framework for automated map generalization [83]. In what concerns to the magnification of crowded areas through differential scaling, Sarkar and Brown [28] developed a method based on the idea of a very wide angle lens that magnifies nearby objects while shrinking distant objects, called fisheye as a valuable tool for seeing both Chapter 2. Literature Revision 32 Figure 2.29: Fisheye Algorithm Example [28] local detail and global context simultaneously. In fact, this may be considered a focus- and-context technique for graphs that serves the schematization purpose of emphasizing important map details while de-emphasizing unimportant details. This research systematized a formal model for differential scaling concepts only using one map view, thus combining the advantages of having different views (one for the focus, and one for the context) into the same view, while not having any of the disadvantages of having two different views. Basically, generating a fisheye view involves magnifying the vertices of greater interest and correspondingly demagnifying the vertices of lower interest. The position of all vertices and bend points must also be recomputed in order to allocate more space for the magnified area so that the entire map does not overflow the map frame or boundary. Figure 2.29 shows an example of this algorithm, on a graph that represents the major cities in the United States with the edges representing paths between neighboring cities. The fisheye algorithm was generated with focus on a particular city (St. Louis) It is possible to observe how this area is magnified, while the others are demagnified. Differential scaling is widely used in the design of visually unbalanced schematic maps which have crowded areas and uncrowded areas as it allows better visual balance of the map elements. Differential scaling can also be used to manage the emphasis of some map aspects through scale. It introduces geometric distortion on the map, and this distortion on the map produces visual changes that may be useful to enhance map readability (at the cost of precise geographic accuracies). The topic of geometric distortion of schematic network maps was later revisited by Jenny [29], in an analysis made to the London tube map through a software called MapAnalyst. He analyzed the differential distortion that occurred in the London tube map in comparison with the real geography of London (figure 2.30). He developed the idea of using distortion grids or displacement vectors during the design process, as seen in the figure 2.31. The displacement vectors could be used to systematize the adequate scaling of the map, and to allow further interaction possibilities for map makers in assisted and automatic schematic map production. Chapter 2. Literature Revision 33 Figure 2.30: The current London Underground diagram with an overlaid distortion grid and displacement circles. The circles’ areas are proportional to the distances to the correct locations [29]. Figure 2.31: Displacement vectors. Arrows point at the correct geographic location of each station [29] Chapter 2. Literature Revision 34 Line simplification was again researched by Latecki and Lak¨amper[30] [84] through the vertex deletion on polygons to simplify their shapes. Through discrete curve evolution strategies, their algorithm achieves the following goals: •It leads to a simplification of shape complexity •It does not introduce any blurring (i.e. shape rounding) •There is no dislocation of relevant features •It is stable with respect to noisy deformations •It allows to find line segments in noisy images This algorithm keeps the same planar position of a set of predefined points. Figure 2.32, shows how this algorithm reduces a graph to its elementary shape by keeping the position of the squared/circular points (predefined points). Figure 2.32: Example of the Discrete Curve Evolution Technique of Latecki and Lak¨amper[30] The Discrete Curve Evolution approach was later improved by Barkowsky [63] having this research as a basis. Nevertheless this approach does not take in consideration the distance between stations, nor restricts possible edge directions. In addition, it does not provide a mean to magnify crowded areas to improve readability nor considers station labeling occlusion possibility. Therefore this algorithm is more suitable for simplifying road maps than for schematizing public transport maps. Neyer [85] also studied a line simplification problem where each simplified line segment must be parallel to one of a set of given orientations. This algorithm forces the segments of a polygonal chain Pto be in compliance with a finite set of orientations O. The objective is to find another polygonal chain which is a C-oriented approximation of P, Chapter 2. Literature Revision 35 i.e. the distance between Pand Qin the Fr´echet metric1[86] needs to be within a certain threshold value. Neyer gives a dynamic programming algorithm to compute C- oriented line simplifications in O(kn2logn) time, where Nis the number of vertices on P, kthe number of segments of Q and the number of orientations |C|is constant. In what concerns to practical schematization of transportation maps, Cwould contain the usual orientations (0, 45 or 90 degree). The problem with this algorithm is that only considers one path in the transportation map at a time, so there is no interaction between the lines within the whole graph. This may introduce undesired features (segment intersection, change in network topology, vertex disconnection, etc) [87]. Generalization techniques were improved by Agrawala and Stolte [61] merging some knowledge from cognitive psychology. They consider that an effective route map must clearly communicate all the turning points on the route and that precisely depicting the exact length, angle, and shape of each road is much less important. While those considerations also hold true for generic schematic maps, their generalization methods do not take in account several specific schematic map problems such as unbalanced maps with non uniform density and they have only applied those generalization methods to one route (line) at once, so they do not take in account generalization of complex transportation maps and interaction between lines. Avelar and M¨uller [88] developed an algorithm to enhance the aesthetic criteria of a transportation network by moving the vertices of the line segments while preserving topological relations. The method of preservation of map topology was made through three conditions: •No absence of line crossings that were present in the input map •No line crossings that were not present in the input map •Cyclic order of outgoing connections around any node agrees with the ordering of connections in the input map Although this algorithm was successfully applied to the road map of Zurich, not all line segments could be drawn octilinearly because vertex positions are influenced by several potentially conflicting terms. Other considerations such as labeling were not included in this research. Further research carried by Avelar [60] identified and summarized two key factors for producing what she calls good schematic maps: a set of Aesthetic Criteria, a conceptual model for a database containing geographical and topological information about the map, capable to address user queries. She proposes an iterative schematization algorithm which handles the conflicting objectives by establishing a compromise between 1The Fr´echet metric is a measure of similarity between curves that takes into account the location and ordering of the points along the curves. Chapter 2. Literature Revision 36 them at each iteration, and stated a set of constraints related to length, angle, and shape of edges to evaluate the quality of solution. This research, however, falls short of integrating cognitive psychology and computer science research knowledge into the algorithm, centering much of the research into the so called “aesthetic factors”. Also, it uses a constant scale factor which may force shorter lines to shrink to a point. Her algorithm also relies heavily on user parametrization. Data about computational efficiency are also not given. Another algorithm for schematizing road maps is presented by Cabello and Kreveld [89]. The algorithm draws the edges of the input network as octilinear paths with two or three links while preserving the input embedding. The user can restrict the links to 0, 45 and 90 degrees and vertex positions keep their original position. The algorithm runs in O( n log n) time as long as input edges are drawn monotonously. It also determines if a schematized map can be produced. However if it cannot, the algorithm fails and no map is generated, which is a disadvantage. Other drawback is that vertices (stops) keep their original positions[89]. In real-world transportation maps, moving stops is crucial, as not doing it leads to many unnecessary bends in the layout and crowded downtown areas remain confusing. Although efficient, this algorithm does not generate effective schematic maps. This research work was later completed [90] with a combinatorial approach to the problem of aligning points. Given a set of points, the task is to align as many points as possible horizontally, vertically or diagonally, where each point can be placed somewhere in its own, given region (for example a circle, rectangle or Voronoi cell around each point). The points represent the vertices of an underlying graph and alignments are only considered for adjacent vertices. The goal is to place vertices such that as many edges as possible are drawn as straight, octilinear line segments while roughly preserving their positions. After modifying the vertex positions, the remaining non-octilinear edges could for example be simplified with the previous method of Cabello and Kreveld [89]. Although being an improvement, this method still has the problem that after being placed, the vertices remain at the same position. This is a big limitation as as the algorithm progresses, much improved results could be obtained if there was the possibility of displace the vertices to avoid local minima. N¨ollenburg [87] formulated the problem as a Mixed Integer Programming (MIP) problem. Given a planar graph Gof maximum degree 8 with its embedding and vertex locations and a set Lof paths or cycles in G(e.g. transportation network lines) such that each edge of Gbelongs to at least one element of L, draw Gand Lnicely. He first defines the concept of “niceness” a map by listing a number of hard and soft constraints. This method optimizes a weighted sum of costs corresponding to the soft constraints, while enforcing the compliance with the hard constraints. This approached was tested with real world city maps, and the results were compared with the actual maps used in Chapter 2. Literature Revision 37 those cities. This algorithm proved that high quality solutions can be found, but the time to find them is a serious concern, although good intermediate solutions could be found easily. Introducing labeling constraints produced a big MIP search space making the processing time a big concern. In addition to this, this algorithm may fail to produce a solution if there is none. These factors prove that this algorithm is not suitable for soft real time and/or dynamic environments where response time and finding a solution are fundamental (such as location based services). The MIP approach was latter revisited [91] [92], with this latter research improving some details. Nevertheless, the maps tested were generated within a 10-12 hours timeframe, which is still an enormous processing time. The authors confirm that their method is unable to produce good labeled maps instantaneously. Other approaches to the problem of generating schematic maps involved the use of multicriteria optimization techniques. Stott et al [93] used a hill climbing algorithm to improve the starting layout of a map. The algorithm starts, therefore, with an initial layout placed on a regular grid. At each iteration, the algorithm measures the map by calculating a number of criteria. These criteria are weighted and summed together: stations are moved if the sum of the weighted criteria is reduced (thus minimizing the objective function value). An iteration of the method consists of attempting to move each station in the map. Some advantages of this method in regarding to MIP were the faster processing time and the fact that a solution is always obtained, even if is very suboptimal. Despite this advantages, the initial version of the algorithm had some problems such as typical local minimum management problems (for example, overlong edges would not be moved as this would need moving several vertices at the same time), the relative position of stations was not kept and occlusion problems could occur with labeling. Therefore new refined versions of this algorithm were developed [26] [94]. These refined versions solved the disadvantages by being capable of moving sets of stations at once if it advantageous. The set of criteria and labeling was also improved. Despite these improvements, this algorithm had some downfalls: parametrization is not automated, so the user has to set up the criteria weightings, computational efficiency was not the focus of the algorithm, and some of the criteria use quadratic complexity which can cause problems. The placement on an initial grid is too simple, which can avoid denser area stops to be successfully placed as no contention management strategies were employed, and this can jeopardize all the algorithm. Uniform grid scaling is also employed, and this factor can cause lower quality map production. Octilinearity is also not guaranteed. Generalization by vertex displacement has been investigated using a number of metaheuristic techniques, including simulated annealing [95], genetic algorithms [96] and tabu search [97]. The application of of memetic algorithms to automated schematization was researched by Swan et al [98]. This algorithm was also based on a set of seven constraints: Chapter 2. Literature Revision 38 •Topological: the original network and derived schematic map should be topologically consistent; •Orientation: if possible, network edges should lie in a horizontal, vertical or diagonal direction; •Length: if possible, all network edges should have length greater than or equal to some minimum length (to ensure clarity); •Clearance: if possible, the distance between disjoint features should be greater than or equal to some minimum distance (to ensure clarity); •Angle: if possible, the angle between a pair of connected edges should be greater than or equal to some minimum angle (to ensure clarity). •Rotation: an edge’s orientation should remain as close to its starting orientation as possible •Displacement: vertices should remain as close to their starting positions as possible A prototype algorithm was built and a mockup result was presented, but no details were given in what concerns to performance and no analysis on the result quality was made, so little is known about this algorithm, its results and implementation. This set of constraints, however, was the base to other research works on the automated generation of schematic maps. A simple simulated annealing algorithm for producing schematic maps for mobile applications was implemented [78] but it had the typical limitations: the annealing schedule had to be set manually and finding an appropriate set of parameter values can be time-consuming. No tests were performed with real data and few data was provided regarding the ability of the algorithm to escape local minima. Dong [99] also designed a schematization algorithm based on those constraints, but he admitted that in a schematic map design of a complicated transport network, more map design aspects should be taken into account, such as overlap of a number of road segments, and false and true intersection points in the road network, such as having an intersection but not having any stations. The algorithm has not been tested with real world data and complexity, no details were given on performance, nor an analysis was made on the results other than the visual presentation of the map. A recent research work was performed in order to automatically produce destination maps. Although destination maps may not be schematic maps in their traditional definition, some aspects are also important on what concerns to the design of schematic maps. This research [100] merged some cognitive psychology knowledge into aspects Chapter 2. Literature Revision 39 such as hierarchical navigation (emphasize the more important transportation routes and remove the non-important ones to avoid information overloading, for example). Although the objectives of this research were not to produce traditional schematic maps in their strict definition, but more enhanced “navigation sketches”, easy to learn and use by people when traveling across a transportation network, this work proved that cognitive psychology considerations play a fundamental role if we want to automatically generate effective schematic (or other type of) maps for navigation purposes. Figures 2.33 and 2.33 provide a summary of these approaches through time. 2.4 Context Awareness and Cognitive Psychology 2.4.1 Map Creation as a Communication Process In a communication process exercise, beyond the essential speech terms (sender, receiver and message), there are other elements that are necessarily present. These elements, called linguistic elements (as they depend on the language used in the speech) are the syntax, semantics and pragmatics [101]. Syntax is synonymous with “grammar” and it is related to the orthography and phonology, while semantics is the study of the meanings of linguistic expressions (as opposed to their sound, spelling, etc.) [102]. Semantics has four inner concepts [103]: •Reference or extension: the object or set of objects to which an expression applies •Truth and falsity •Intension: what determines the extension of an expression; often regarded as a function from possible worlds to extensions) •What a competent user of an expression must know (although this is a very important concept, there is no term that unambiguously expresses it) Pragmatics has to do with context-dependent features of language and also includes things people can do with words or sentences that go beyond the literal meaning of the expressions involved. These three linguistic elements have a powerful influence over the message configuration and also in the particular understanding of the reality by the sender of the message. More important, the same happens for the understanding of the message by the receiver. Chapter 2. Literature Revision 46 the context (either user, spatial or time context) is the clue for an adequate balance of map features, design and layout. In what concerns to user context, two main enhancement strategies found in the literature: “user-centered design” and “user-adapted interaction”. Porathe conducted an experiment where a user-centered map (a map viewed in the user’s perspective) was compared to other type of maps (paper map, north-up map and head-up) ([57]. The results suggested that for route guidance, user-centered maps are more efficient (faster decision making), less erroneous, and more user-friendly than maps displayed in the traditional exocentric perspective. However, one limitation of the study was that the map display types were not tested for route planning or judging distance. Used-adapted interaction is related to the discovery of the user characteristics and preferences, either automatically or manually through user input. Automatic discovery of user characteristics may be obtained through stereotypical assumptions through user behavior, sensors, or other type of pervasive device that can capture user characteristics [113], serving as a base for user profile inference through meta-operators[114]. User characteristics may then be used to design specific maps tailored to each specific type of user (for example: maps with specific color schemes for colorblind people or school maps for children) which can speed up their spatial learning. User context, by adapting the map to the people (instead of being the other way around) can speed up their learning and improve user experience. Designers and artists also have always tried to discover new forms of improving user experience by directing user attention to the relevant spots in their artworks and consequently managing context accordingly to their intentions. Studies on how to direct user’s attention to specific points on paintings have been conducted [115], and they showed that the following techniques can be used to direct user’s attention: •Ink use: the quantity of ink can be used to draw user’s attention •Blur: the focus of attention shall be always sharp and the picture shall be blurred gradually as we move far from that focus. •Using non-realistic rendering (as it removes detail in unimportant detailed areas) •Selectively reducing detail according to an importance scale •Using luminance bright/dark contrasts to focus user attention •Reducing color detail (using less bits to map color) •Reducing edge number (similar to a sketching process) Chapter 2. Literature Revision 47 •Differential space scaling Those generic techniques have been used for other purposes, including map creation through the study of the aesthetic factors [60]. Another relevant issue is the visual pleasure a graphical representation causes. If a schematic map is not pleasant to the eyes, it is highly probable it will be ignored or rejected by the user. To minimize this probability, the factors that influence a good representation have to be investigated. A study on this topic has been conducted on a set of famous paintings [69]. The results show that users like the paintings that are based in vertical and horizontal contours, instead of the paintings based in oblique lines. The author of the study calls this the “aesthetic oblique effect”, and formulates a possible explanation for it: we like looking at what we are good at seeing. This may well be the reason why the 0, 45 and 90 degree line orientation schema has been used and commonly accepted by the public in schematic maps to depict transportation networks. There are other context enhancement approaches that cognitive psychology and humancomputer interaction show to be effective in improving map reading. Focus+context techniques are fundamental hybrid user/space context enhancement techniques that provide a visual layout that combines a focus area, where the data of most interest is displayed at full size or with full details, and a context area, which is a peripheral zone where elements are displayed at a reduced size or simplified. This way, the most relevant information is presented to the user while not overloading him with all the information the map has. There is a variety of widely used focus+context techniques and we mention here only a few ones: •Fisheye - This technique assigns more display space to a a portion of the map (focus), magnifying and distorting it, while the rest of the map is presented with an increasingly diminishing scale as the map components depart from the focus [116] (figure 2.37). •Hyperbolic Geometry - Similar to the fisheye technique, the essence of this scheme is to lay out the map components in a uniform way on a hyperbolic plane and map this plane onto a circular display region [34] (figure 2.38). •Spiral Representation and Augmented Context - This technique uses a spiral layout divided into sectors to display items, and the higher DOI (degree of interest) objects may be magnified [117] as shown of figure 2.39. •F+C technique for Metro Map - A special technique from Wang et al[35] that can be used for real time interaction with schematic metro maps: the best route Chapter 2. Literature Revision 48 Figure 2.37: Fisheye view applied to central Washington D.C.. The Focus is the White House [33]. Figure 2.38: Change of focus on the Hyperbolic Geometry Focus+Context technique [34]. Chapter 2. Literature Revision 49 Figure 2.39: Spiral Representation and Augmented Context [34]. to the destination, which can be obtained from the arrival time of trains, is highlighted. The stations on the route enjoy larger spaces, whereas the other stations are rendered smaller and closer to fit the whole map into a screen. To simplify the navigation and route planning for visitors, the authors formulate various map characteristics such as octilinear transportation lines and regular station distances into energy terms. Then they compute the optimal layout using a least squares technique. In addition, the names of stations that are on the route of a passenger are labeled according to human preferences, occlusions, and consistencies of label positions using the graph cuts method. [35]. A comparison of this method with the traditional fisheye is depicted in figure 2.40. Figure 2.40: (left) The official metro map of Atlanta city. (middle and right) The focus+context metro maps obtained using the fisheye and the F+C technique for Metro Map from Wang et al [35], respectively. The official map would become too small if it is displayed on a small area. •Semantic Depth of Field - This method is based on the depth of field (DOF) effect used in photography and cinematography, and is therefore both familiar to Chapter 2. Literature Revision 50 users and perceptually effective. Because this method blurs objects based on their relevance rather than their distance, it’s called semantic depth of field (SDOF). [118] Figure 2.41: Semantic Depth of Field: the less relevant area is blurred while the important. It is possible to see that the important area (Matosinhos) looks sharp. Adapted from Bing Maps [36]. Other focus+context techniques appeared recently, associated with the onset of the mobile devices use and interaction, such as the fingerglass technique [37]. This technique lets the user to interactively define a viewport using one hand while the other hand can simultaneously interact with objects in the scene. The contents of this viewport are shown twice on the screen: in a global zoomed-out view stretched out across the entire screen, retaining contextual information, and as a magnified copy on top of the zoomedout view. Figure 2.42: FingerGlass focus+context technique[37]: The user specifies an area of interest with one hand and interacts with the magnified objects with the other hand. During the interaction, a new area of interest can be defined. Releasing all fingers makes the tool vanish. Chapter 2. Literature Revision 51 Techniques like the fingerglass have the potential to highly improve map interaction in mobile devices and modern location-based services. 2.5 Location Based Services Location-Based Services (LBS) are information services accessible with mobile devices through the mobile network which have the ability to make use of the location of the mobile device [119]. This definition is also accepted by the international Open Geospatial Consortium [120]. Some authors state that LBS are an intersection of several technologies as internet, mobile devices and geographic information systems (GIS) [38] [121]. This model is shown at figure 2.43. Figure 2.43: LBS as an intersection of technologies [38] LBS allows the establishment of two way communication and interaction: the user tells the system his actual context, intention and/or preferences (or the system may obtain them in a pervasive way) which can help the provider of such location services to deliver information tailored to the user needs [106]. As it is also possible to observe in figure 2.43, there is a relationship between GIS and LBS. Both handle handle data with geographical reference and spatial analysis functions in order to answer the questions “Where am I?”,“What surrounds me?” and “Where can i go to?”. Nevertheless, their focus is completely different: while LBS targets large non-professional user groups, GIS can be seen as traditional “professional” systems to be used by a restricted group of expert Chapter 2. Literature Revision 52 people. Schematic maps and Spider Maps in particular may be used to improve both GIS and Location-Based Services [54] and therefore their relation is specially important. According to Steiniger [106], LBS have the following components: •Mobile Devices: The apparatus serving as the physical interface for the user to access the service. It can be a smartphone, tablet, mobile embedded systems or toll payment systems (ex: in automobiles). •Communication Network: The communication network that transfers data between the service provider and the user mobile device. •Positioning component: This is the component that determines the position of the user. It can be a Global Positioning System (GPS) unit, or a triangularization technology that makes use of the wireless access points position (or GSM/CDMA antennas) to determine mobile device position, or any hybrid combination of both (as happens with assisted GPS (AGPS)). If this automation component is not present, the user has to specify its position by other mean. •Service and Application Provider: The service provider offers a set of services to user. •Data and Content Provider: Many times, the service and application provider needs to obtain certain information it does not own (such as geographical information, event information, etc) and needs to produce the contextual information that matters to the user. LBS applications need to be aware of a set of details, such as the type of mobile user, the context of the user, the user needs (can be gathered by questioning the user or by pervasive means, automatically), the search and spatial analysis, the user interface, the visualization properties of the device and a wide set of technological questions(how to transmit and store data, technical protocols and details). These details allow the user to effectively use the services. Reichenbacher [122] enumerated five possible mobile actions users usually execute when using LBS: •Locating: This is the most obvious action: user wants to know where he is. •Searching: User may want to search for persons, objects or events •Navigating: User may ask for the way to a location Chapter 2. Literature Revision 53 •Identifying: Involves asking information about a location •Checking: User may look for events near or nearby some location. From this five possible actions it is easy to understand that all of them depend on the context. We can divide the context into three types of context [106], as previously stated: •Spatial Context: Where the user is, •Temporal Context: When it is using the service, •User Context: What is he using the service for. Other authors [105] increase this list with other context types such as navigation history, orientation, purpose of use, social and cultural situation, physical surroundings and system properties. However, those context types can be viewed as subtypes of the three main context types proposed by Steiniger. As it can bee seen, context is a main concept regarding LBS and as its importance is reflected in all the five kinds of mobile user actions, specially the spatial context. 2.5.1 Quality of Information in Mobile Services Although mobile services are gaining popularity in contemporary life, there are some types of mobile services which are not effectively grasping their users. Public transportation services are among these services [123]. A comprehensive research [124] was made on how different dimensions of information quality affect consumers’ satisfaction towards mobile information services and eventually the acceptance of these services. The fact that there are so many features which influence consumers’ perceptions towards mobile services, called for a more precise theoretical framework. One promising way to consider the factors that affect the perceived quality of mobile information service from the consumers’ point of view is the information quality framework of Chae et al.[39]. This framework identifies four dimension of information quality: •Context: Although context was already mentioned previously, it is worth to mention that the definition from Dey [104] is adequate not only LBS but also generic mobile services context: “any information that can be used to characterize the situation of an entity”. Here an entity refers to a person, a place or an object that is considered important to the communication between the user and an application of the mobile service. Chapter 2. Literature Revision 54 •Content: Content quality is the value and utility or usefulness of the information provided by mobile services [125] •Connection: Connection refers to the link between the several components of the mobile service which allows the flow of information. •Interaction: Interaction may be defined as the communication between a site and its users [126]. Mobile services achieve a high interaction quality if they are able to provide easy and efficient ways of interaction [124]. Being so, interaction is closely related to ease of use. According to the framework, those qualities influence directly the user satisfaction. This influence has been proven by several studies [127] [128] [129] [130]. Based on the framework, Koivumaki et al [124] also show that all the four dimensions of quality in information services are positively related to user satisfaction. Another relevant conclusion of those studies is that user satisfaction is positively related to intention to use the service. The studies also state that although content quality is the most important factor, user satisfaction is affected by the set of the four factors, and consequently, the success of a mobile service depends on the form of all quality factors. Figure 2.44 shows the complete model. Figure 2.44: The theoretical model of information quality, source: [39] Chapter 3 Spider Maps Spider Maps are a type of schematic map (fig. 2.22) used in a few cities (London, Lisbon, Porto, etc) to depict public transportation networks. They are inspired by the London metro map, but they use enhanced context features and an improved visual presentation. This section focuses describes Spider Maps and how they reduces information overload, and how their advantages are, in fact, translated to real use through a usability test. 3.1 Concept and Definition Bus spider maps are schematic maps with features that replicate some of the ideas of the conceptual spider maps. An example of a real spider map is depicted on figure 3.1, which illustrates a real spider map in use in London. A Spider Map is composed of two parts: a hub and a schematic map (fig. 3.2). Alongside with the spider map a route finder table is usually also found. The Hub is a detailed rectangular area that depicts the geographic place where the map user is currently at (spatial context). This includes the contour of the surrounding buildings and all labels for the stops where the user can take a public transport to any of the reachable destinations departing from the hub. The hub is surrounded by a frame with points connecting the routes inside the hub with the schematic lines outside the hub (fig 3.3). The schematic map outside the hub frame comprises a set of lines. Each line is formed by a sequence of segments which are characterized by a start and an ending stop. Segments shared by different lines are drawn together (usually side by side) if they follow the same path. Different lines can share stops(nodes) and segments. All the lines have a 0, 45 or 90 degree orientation and do not necessarily follow the geography of the city. Each node 55 Chapter 3. Spider Maps 62 Figure 3.8: Diminishing returns for usability testing, as more and more users are tested [41]. Nielsen suggests to run multiple tests because the real goal of usability engineering is to improve the design and not just to document its weaknesses (this was also our goal in this test). After the first batch of people performed the usability test, it is possible to probe deeper into the usability of the fundamental structure of important issues, which are may not be clear at the first test. [41]. 3.3.2 Phase 1 - Assessing Conceptual Maps After looking at each conceptual map for two minutes (steps 1 and 3), the users drew a paper sketch of the analyzed map. Sketches are a complimentary tool of conventional usability testing techniques, and their cost is a fraction of the cost of other methods[135]. User sketches are quick to create, take only a brief time to analyze and provide reactive as well as reflective feedback. Users were told to replicate the maximum number of concepts and relations they remember and to identify the first concept that captured their attention. The sketches were then analyzed with the objective of testing the following parameters: •Task 1 - Overall memory recall speed: the time the user took to draw a sketch of what he could remember from the concept map. •Task 2 - Overall memory recall correctness: the number of correct concepts presented at the drawn map. •Task 3 - Overall memory recall correctness of concept relations: the number of correct relations presented at the drawn map. Chapter 3. Spider Maps 63 •Task 4 - First looked concept: the first concept where the user looked at, testing the focus property. •Task 5 - Context Learning: we wanted to assess if the context learning was correct and uniform by the users. The concept maps used for testing were related to different topics (to avoid the memorization bias effect from map to map), which have the same degree of familiarity to the users. The number of concepts and relations were the same in both maps. Figure 3.9 and Figure 3.10 depict the concept maps used in the first phase. Figure 3.9: Concept map used in phase 1 of the test Figure 3.10: Spider concept Map used in phase 1 of the test 3.3.3 Phase 2 - Assessing Bus Network Maps In phase 2, users tested real transportation network maps, which are in use in the city of Lisbon. The first one was a traditional diagrammatic map and the second one was a Chapter 3. Spider Maps 64 spider map of the area where the user was. Both maps are publicly available in some bus shelters in Lisbon. The Lisbon diagrammatic map is presented in figure 3.11. The spider map was produced with our GenX framework and algorithms, with minor manual aesthetic work and is depicted in figure 1.1. The questions regarding location of specific places were different in each of them to avoid the memorization bias effect from map to map, which have the same degree of familiarity to the users. The parameters to be tested were concerned to the four main actions users normally perform with geographic services [122] [106]: •Orientation and Localization: This action relates to locating, and answers to questions like “Where am I”,“Where is person/object”? •Navigation: This action relates to navigating through space, such as planning a route, and answers to questions like “How do I get to place X?” •Search: This action relates to searching for people/objects/etc. It answers to questions like “Where is the nearest person/object/etc”. •Identification: This action is related the identification of people or objects and answers questions like “How many objects are here?” The users had 2 minutes to look to the first map (traditional diagrammatic map), then performed the usability tasks (step 7). Then they had two minutes again to look at the second map (the spider map) and they performed the same tasks (step 9). Each usability test was made of the following tasks: •Task 1 Locating - self: We asked the user to locate himself on the map and we counted the elapsed time. •Task 2 Locating - notable point: We asked the user to locate a point of higher importance (such as the city airport) on the map and counted the elapsed time. •Task 3 Navigation: We asked the user how would he/she get to the notable point from his/her current location and measured the time it took to answer correctly. •Task 4 Search: We asked the user to search for a random stop on the map. We measured the response time and registered whether the user gave up (which is an undeniable sign of user frustration). •Task 5 Identification: We asked the user to count the stops in the neighborhood of its current location. Finally, in step 10, the users where invited to answer the same set of open questions, comparing both maps, in order to gather some subjective user feedback. Chapter 3. Spider Maps 65 Figure 3.11: Diagrammatic Map of the Bus Network of Lisbon 3.3.4 Results 3.3.4.1 Phase 1 - Conceptual Maps Test In the first task, we measured the time the user took to draw a sketch of each concept map and it showed that, in average, the spider map has a significant better performance, improving it by 25%, as shown in table 3.2. Table 3.2: Average variation of sketch drawing times for mind maps Normal Map AVG (s) Spider Map Drawing AVG (s) Var % Var 72,63636364 54,54545455 -18,09090909 -25% In the second task, we measured the overall memory recall correctness, by counting the number of correct concepts presented in the user drawn sketches. The results show that, in average, the spider map has a slight better performance, improving by 3%, as shown in table 3.3. In the third task, the objective was to measure the overall concept relation memory recall, by counting the number of correct links presented in the user drawn Chapter 3. Spider Maps 66 sketches. The results show that, in average, the spider map has a better performance, improving by 8%, as shown in table 3.3. Table 3.3: Average number of correct concepts and correct relations present at the drawn sketch Normal Spider Variation concept map concept map Avg. N. of correct concepts (out of 10) 9,56 9,82 3% Avg. N. of correct relations (out of 9) 8,27 8,91 8% In the fourth task, we wanted to identify the first looked concept in each map, the “focus” point of each map. The results show that the common concept map has more “focus” points than the spider map. The user attention spreads over a larger number of points, making it more unpredictable to know where the user will look at. Figure 3.12 shows a comparison between the concepts that firstly attracted user attention in the common concept map (left) and in the spider concept map (right). The semitransparent ball size is proportional to the number of users that looked at that concept. If we compare both concept maps, we can see that the common concept map has four focus points, with the larger point being on the up left side of the map, while the other three focus points are divided around the middle area of the map. We can see that in the spider concept map there is a clear point of focus, which is the central concept. This is consistent with the theory behind the advantages of the spider architecture. At the same time, is seems natural that the center and the left upper corner are the areas that first attract people’s attention in a picture. People (in occidental cultures) start reading documents from top left, so that may explain the small circles in the spider concept map and in the common concept map at that area. Figure 3.12: Comparison of the points that firstly attracted user attention in normal concept map (left) and spider concept map (right). The semitransparent ball size is proportional to the number of users that looked at that point. In the fifth task, we wanted to assess if context learning was correct and uniform. Regarding the normal concept map, users divided themselves on five contexts (that are very close semantically to each other and all could be considered correct). Regarding Chapter 3. Spider Maps 67 the spider map, users divided themselves in just two contexts, very close semantically to each other, even sharing the same word. We can say that the spider concept map leads to a more unified perception of context. Table 4 shows the concepts identified by the users. Table 3.4: Concepts identified by users in normal concept map and in spider concept map Normal Concept Map Context Identification N. Users Electricity 3 Electric circuits 3 Electromagnetism 3 Electric current 1 Physics 1 Spider Concept Map Context Identification N. Users Globalization 6 Globalization and Culture 3 To analyze the feedback from the open answer questionnaire (step 5), we used tag clouds since they provide a quick feedback about the main topics mentioned by the users. The representation is compact, and draws the eye towards the largest, most important items, and three dimensions are represented simultaneously (the words themselves, their relative importance) [136] without having to transcribe every word the users wrote in their multiple line answers. In the answers to the first question, “Which map was easier to learn and why” 10 users (out of 11) chose the spider concept map and one single user chose the common concept map. When asked why, the main words revealed by the tag cloud were “layout”, “keyword”, and “central” (see Figure 3.13). Therefore, we can say that the spider concept map is easier to learn due to its layout and structure. Figure 3.13: Tag Cloud showing the user justification about the easiness of learning of the conceptual spider mind map. Regarding the second question, “which map did you find more intuitive and why”, 9 users (out of 11) have chosen the spider concept map, while 2 users chose the common concept map. Analyzing the tag cloud (Figure 3.14), the highlighted words used to justify the choice are “better”, “layout”, “memorization”, “easy/easier”,“understanding”. This seems to indicate that users think the spider concept map is more intuitive due to its structure, as it allows easier memorization and understanding. Chapter 3. Spider Maps 68 Figure 3.14: Tag Cloud showing the user justification about the intuitiveness of the conceptual spider mind map. Regarding the third question, “What did you like/dislike in the normal concept map” a single user said it was well organized and structured, while the others disliked it due to the bad layout and because it was hard to understand. Figure 3.15 presents the corresponding tag clouds. Figure 3.15: What users liked (at left) and disliked (at right) about the normal mind map To the fourth question, “What did you like/dislike in the spider concept map” users liked it mostly because of the layout, the highlighted main concept, the easiness, the readability and intuitiveness. When asked what they disliked in the spider concept map, users referred the font and the spacing. Therefore, those aspects can be improved in spider maps. Figure 3.16 presents the corresponding tag clouds. When asked the fifth question, “How do you think those maps could be improved”, users identified a main word for it: “differential”. Figure 3.17 shows some of the related concepts: differential styles, lines, colors, sizes, fonts, keyword highlighting, according to the relative importance of the topic. To the sixth question, “Overall, which map did you like the better and why”, all the respondents chose the spider map and the main justifications were the better layout, the central keyword, the easiness of learning and the intuitiveness, as we could see in the respective tag cloud (figure 3.18). Chapter 3. Spider Maps 69 Figure 3.16: What users liked (at left) and disliked (at right) about the spider mind map Figure 3.17: Tag Cloud showing the user topics on how conceptual maps could be improved. Figure 3.18: Tag Cloud showing the user justification about their overall preference on spider mind map. 3.3.4.2 Phase 2 - Transportation Network Maps Test In the first task, we measured the time the users took to locate themselves on the map. Table 3.5 shows that the spider map presents a significant improvement over traditional diagrammatic maps, decreasing the self-location time by 94%. Table 3.5: Average time of self location on maps Diagrammatic Map AVG (s) Spider Map AVG (s) Variation % Variation 24,54545455 1,363636364 -23,18181818 -94% Chapter 3. Spider Maps 70 We believe this is due to the hub focus property, which depicts very clearly the place where the user currently is. Some traditional maps try to overcome this problem by placing a “You are here” tag. In the second task we measured the time the users took to locate a notable point (a point with a higher relevance) on the map, such as an airport, for example. In this task, the spider map showed no advantage or disadvantage compared to the diagrammatic map. Notable points are usually highlighted by different icons, so it is probably due to that reason they can be easily found on either type of map. The third task measured the time the users took to find the bus routes from their current location to the previously identified notable point (navigation task). Table 3.6 shows that the spider map reduces by 84% the average time users took to find their way in the transportation network Table 3.6: Average variation of navigation task on maps Diagrammatic Map AVG (s) Spider Map AVG (s) Variation % Variation 39,27272727 6,272727273 -33 -84% In the fourth task, we measured the time the users took to find the nearest metro station from a random stop of the bus transportation network. This task involved two subtasks: the first one was to search for the mentioned bus stop, and the other one was to search for the nearest metro station. Table 3.7 shows that spider map decreased by 97% the time to complete this of task for those users that completed the task. In fact, eight users (in 11) gave up from the search in the diagrammatic map, seven of them after having spending some time searching for the mentioned bus stop. All users were able to complete the task with the spider map. Besides reducing the searching time, spider maps are able to reduce user frustration. We can see that there is a connection between efficiency and emotions [137]: an efficient design improves user satisfaction. Table 3.7: Average variation of the searching task time on maps Diagrammatic Map AVG (s) Spider Map AVG (s) Variation % Variation 201,9090909 5,363636364 -196,5454545 -97% In the fifth task (identifying) we asked the users to count the stops in the neighborhood of its current location. We measured the time the users spent in counting the stops and the number of counted stops. The results presented in table 3.8 show that spider maps reduce the time counting the neighbor stops by 79%. Table 3.8: Variation of the time spent by the users in counting the stops in the neighborhood Diagrammatic Map AVG (s) Spider Map AVG (s) Variation % Variation 35,63636364 7,545454545 -28,09090909 -79% Chapter 3. Spider Maps 71 The most curious aspect of this task was the concept of “neighborhood”. This concept was deliberately not explained to the users while performing this identification task nor further details were provided on the radius of the neighborhood area. The results show that while in a traditional diagrammatic map, users have different ideas of neighborhood (identifying on average 7 different stops), in a Spider Map the vast majority of users have the same idea of neighborhood (on average, users identified 2 different stops). This happens because in the spider map, the neighborhood is contained in the hub, so it seems to be an intuitive concept for most of the users. As the hub is bounded by a frame, that frame encloses the area of the neighborhood, so there is a standard precise intuitive definition of neighborhood in the spider map. This does not happen in the traditional diagrammatic maps due to their design limitations. In what concerns to the subjective user evaluation, to the first question, “Which map was easier to learn and why”, all the users considered the spider map as easier to learn. When asked why, the main words revealed by the tag cloud (figure 3.19) are: easier, better, clearer, less, detail, organization, location, reading. Therefore, we can say that the spider map is easier to learn because people perceive it as being clearer, better organized, with less detail and easier to read than the diagrammatic map. Figure 3.19: Tag Cloud showing the user justification about the easiness of learning of the Spider Map. The answers to the second question, “Which map did you find more intuitive and why”, showed that ten out of eleven users chose the spider map and one single user chose the diagrammatic map. When looking at the tag cloud (figure 3.20), some words emerge immediately: easier, clearer, learning, faster, context. This seems to indicate that users think the spider map easier to learn, clearer, with a better organization, faster navigation and location. The single user who considered the traditional map more intuitive justified his choice by saying that diagrammatic maps are more similar to the traditional maps and that he could have a more accurate idea of distance. This seems to be the effect of the distortion caused by differential scale function referred in section 2.2. Chapter 4. Problem Modeling 78 •C7: ∀e∈E, e = (v1, Pe, v2,), v1, v2∈V, Pe∈P, |Pe|= [0,∞[ (Each point is formed by an ordered 3-tuple of the initial vertex v1, a set of inflection points Pe and a final vertex v2. The set of breakpoints Pemay be empty but must contain a finite number of elements). •C8: There is a mapping function δ:E→V×V.δ(e) = (v, w)∧(v6=w) (The mapping function returns an ordered pair. There are no loops and therefore a Spider Map is a simple directed graph). •C9: |E|∈ [0,∞[ (The Edge Set must contain an a finite number of elements) •C10: ∀l∈L,lis an ordered sequence of edges e∈E(A line is comprised of an ordered sequence of edges: l= (e1, e2, ..., ek), k =|l|). •C11: |A|= 8 (The number of angles of the edge representation is 8, corresponding to the angles 0, 45, 90, 135, 180, 225, 270 and 315 degrees). •C12: ∀gr∈Gr,gris a sequence of points p∈P, and a sequence of line segments connecting consecutive points, forming a closed polygon. As an illustrative example, we present the spider map in figure 4.1 which corresponds to the following map model: •SpiderMap := (P, V, H, E, L, A, Gr) •P:= {P1, ..., P45} •V:= {V1, ..., V24}(The spider map has 24 Vertices that correspond to line stops on the map), where Vi={Pi, Labeli} •H:= {P38, P39,{P40, P41, P42, P43, P44, P45}} •E:= {E1, ..., E25} •E8:= (V7,{P8}, V9) The edge 8 has V7as start node and V9as end node. It contains also an inflection point P8. Similar definitions apply for the other Edges of the map. •L:= {L1, L2, L3, L4, L5, L6}, where Lk= (Ej), , j ≤ |E|ex: L1 := (E4, E5, E6, E7, E8, E9) •A:= {0,45,90,135,180,225,270,315} •Gr:= {GR1} •GR1:= (P29, P30, P31, P32, P33, P34, P35, P36, P37) Chapter 4. Problem Modeling 79 Figure 4.1: Spider Map Definition example This definition is semantically richer than the definition of a simple Graph G= (V, E), which is not able to capture the semantic complexity of a transportation network spider map. To exploit the advantages of having a semantically rich data structure (SRDS) that is powerful enough to describe a real spider map while having fast computational performance, we decided to implement two data structures: one that is semantically richer, reflecting the real spider map analogies and complexity, and a simple graph data structure (SGDS) which will serve as a working data model for our information system. This way we were able to combine all the advantages while not having any disadvantage. This approach is a considerable improvement over the state of the art approaches to this problem. The conversion between these two structures is achieved through two mapping functions: one can convert from the SRDS to the SGDS, and the other one can convert the other way around. Figure 4.2 shows the initial conversion from the semantically rich data structure (SRDS) to the simple graph data structure (SGDS) and the mappings. 4.2.1 Semantically Rich Data Structure The semantically rich data structure closely follows the real spider map semantics, so the mapping between the reality of a transportation network and our semantically rich spider Chapter 4. Problem Modeling 80 Figure 4.2: UML Diagram depicting the initial data structure conversion from the semantically rich data structure to the simple graph data structure and mappings. data structure is direct. To every feature in a real spider map there is a correspondent piece in that structure, as shown in table 4.1 Table 4.1: Mapping Between Real Spider Maps and our Semantically Rich Data Structure Spider Map Semantically Rich Data Structure Hub H Hub Exit Points P Hub Limits P Stops in Hub P Line L Segment E Segment/Line Bendings P Stop V Geographical Restrictions Gr The other data sets that comprise the semantically rich data model which are not a direct translation of spider map features, such as the number of the angles and the inner relations between vertices and points are automatically derived. 4.2.2 Simple Graph Data Structure A spider map can also be modeled through a graph G= (V, E). Using a simple graph to model a spider map we lose most of the semantic meanings (for example, the notion of lines, geographical constraints, hub, etc), nevertheless we gain simplicity and agility for algorithm processing. Therefore, to avoid the downside and extract the full potential, we do not use this simple graph to directly model the spider map. We use this simple graph data structure as a middleware model which can only be mapped from (and to) the semantically rich data structure. To solve the problem of losing the semantic meanings of the map features, besides the simple graph (which will be processed across the algorithm), we keep a mapping table that stores the semantic meanings of the spider map. This way, when the algorithm finishes processing the simple Graph model, we can convert the simple graph data structure to the semantically rich data structure by Chapter 4. Problem Modeling 81 recovering the semantic mappings stored in that table. This way, the algorithm can be executed over a light data structure but as we keep the semantic mappings, we can solve real world complexity problems. Table 4.2 shows the relation between the semantically rich data structure and the simple graph data structure. Table 4.2: Relations Between the Semantically Rich Data Structure and the Simple Graph Data Structure SRDS SGDS P Vertices V n.a.(stored in semantic mappings table) H Vertices E Edges L n.a. (stored in semantic mappings table) A n.a. (used to process Vertex and Edge positioning) GRn.a. Converted to Polygons (looped graph structure) The mapping table stores the correspondences between the semantically rich and the simple graph structures. This table contains a structure where each vertex is tagged with a unique ID, and contains the information of the line and the segment (edge) it belongs to, and whether it is the start or the end node of the segment. Each Vertex can have several mapping table entries, if it makes part of more than one line. Table 4.3 exemplifies the mappings table for vertices 1 to 10 of the spider map depicted in figure 4.1. Table 4.3: Semantic Mappings Table example for Points 1 to 10 for the spider map depicted in figure 4.1 Mapping # Vertex ID Line ID Segment ID isStartNode 1 1 2 2 True 2 2 2 2 False 3 2 2 1 True 4 3 2 1 False 5 4 1 5 True 6 5 1 5 False 7 5 1 6 True 8 6 1 6 False 9 6 1 7 True 10 7 1 7 False 11 7 1 8 True 12 9 1 8 False 13 9 1 9 True 14 9 3 13 False 15 9 3 14 True 16 10 1 9 False 17 10 3 14 False Chapter 4. Problem Modeling 82 4.3 Data Structures The data structures were designed to directly support the spider map data modeling described in the previous section, as well as their processing. The global view of the data structures organization, and data flow is shown in the UML diagram depicted in figure 4.3. Figure 4.3: UML Diagram depicting the data structures organization and data flow. Our approach to the generation of Spider Maps starts by reading an XML file which describes the transportation network to be transformed in a spider map. It contains the locations of the map features (not schematized) and every semantic information that is inherent to the complexity of a real transportation network. This file (which can be obtained through TCP/UDP1(for example, through a web service negotiation), disk reading or through pipelines2) is read, de-serialized, parsed to their atomic components (such as stops, lines, etc) and then converted and stored into the semantically rich data structure. This structure is then converted into the simple graph data structure which is agile enough to be processed, while the semantic mappings are kept to avoid the loss of semantic information regarding the transportation network. After processed by the algorithms, the simple graph data structure. This structure is combined with the semantic mappings to obtain the resulting processed semantically rich data structure, which can then be stored into an XML file that can be used to output the map in several physical (ex: paper) or virtual supports (computer screens, 3D projections, mobile device screens, etc). The XML file is usually a SVG file due to its system interoperability, scalability and lossless encoding which allows it to be displayed into lots of media types without losing visual fidelity. This XML file can then be directly presented to end users, sent to a network, or further processed by designers or other professionals. The UML Class Diagram depicted in figure 4.4 implements the semantically rich data structure. It is worth to mention the detail of the coordinate system used: we keep 1TCP and UDP are network communication protocols for digital information exchange 2Usually just called “pipes”, the pipelines are connections between two computer processes, such that the standard output from one process becomes the standard input of the other process, allowing the transfer of information between them. Chapter 4. Problem Modeling 83 the real world coordinates (latitude and longitude), but in what concerns to algorithm processing, we use paper coordinates, which are related to the coordinates in the map canvas (either physical or virtual). This class diagram also features some classes (ex. Interface, Area) that are used for tailoring the map to specific purposes such as specific events or themes. The “MapPoints” class map allow us to process the spider map by grouping nearby stops into the so called “mapPoints”, considering each mapPoint as a “dense area of stops”. Figure 4.4: UML Class Diagram that implements the Semantically Rich Data Structure The UML Class Diagram depicted in figure 4.5 implements the simple graph data and the semantic mappings structures. The simple graph data structure is implemented by the Graph, Edge and Vertex classes. The SimplePoint class supports the vertex processing. Chapter 4. Problem Modeling 84 The information about each restriction is stored in the restriction and vertex class. The classes that store the semantic information mappings are the Mapping class (each Graph contains a “MappingSet” property which is a set of “mapping” objects (that are of the type “Mapping” class). Other relevant classes such as the AngleSet and the Settings store information about the derived angles. The VertexMove class is related to the processing of the simple graph throughout the algorithm. Figure 4.5: UML Class Diagram that implements the Simple Graph Data Structure. The conversion from the semantically rich data model to the simple graph data structure is performed through the following actions: •The points where the transportation lines connect to the hub that are stored Chapter 4. Problem Modeling 85 through instances of “HublinePosition” class are converted to instances of “HubLineConnection” classes •The original map “Spider Map” class is converted to the Graph class •The geographic constraints stored through the initial “Restriction” and “Polygon” classes are merged and converted to “Restriction” classes. •The “MapPoint” class objects, initially used for storing the transportation network stops, are converted to instances of the “Vertex” class •The “Line” class used to store line information is converted to the “Edge” class. •The “Simplepoint” class on the simple graph data structure will store points that are inside the hub and other points that may be placed in the edges to achieve better visual quality throughout the map processing 4.4 Modeling the Multicriteria Optimization Problem We modeled the problem of the automatic generation of spider maps as a multicriteria optimization problem. We have a minimization objective function and a set of constraints we need to respect. The generation of a Spider Map involves the inclusion of many - and often conflicting - set of design guidelines. Those design guidelines were modeled through two sets of constraints: soft and hard constraints. The soft constraints measure and influence the visual quality of a spider map and it is desired they are respected as most as possible, while the hard constraints must be respected and enforced in order to generate a spider map: if they are violated, the produced solution is not feasible. 4.4.1 Decision Variables The decision variables of this problem correspond to the spatial coordinates of each vertex v∈Vand point p∈P. Starting with precise geographic coordinates, the goal of the objective function will be to position every vertex and point (and consequently, all of the Spider Map structures that rely on them). 4.4.2 The Objective Function We modeled most of the soft constraints based on an improved version of Stott’s [26] work. We improved his model both on the formulation and on its implementation. The Chapter 4. Problem Modeling 86 goal is to minimize the objective function, which means that if all the soft constraints are perfectly respected, the optimization function would have a value of zero, which would correspond to the “perfect map”. Soft constraints are related to the quality of the spider map, and allow us to evaluate the niceness of the spider maps [87]. It is worth to mention that although not categorized exactly as “soft constraints”, some of these soft constraints have their roots in previous research works [26], [87], [63] and [60]. Soft constraints represent desirable map characteristics, although they are not critical to achieve a spider map, a feasible solution to the problem. At table 4.4 we enlist the set of soft constraints that comprise the optimization function. Table 4.4: Soft Constraints - summary Constraint Description SC1 Adjacent edge angle shall be as wide as possible for each vertex SC2 Homogeneous inter-vertex spacing SC3 All consecutive vertices shall dist a certain distance SC4 Reduce edge crossings to the minimum SC5 Lines should be as straight as possible SC6 Benefit horizontal and vertical edges Constraints SC1 to SC3 use the same modeling as Stott’s work, while SC4 to SC6 are a completely different modeling, much improved through innovative algorithms. All constraints were improved in its implementation to improve execution speed, which is one of the downfalls of Stott’s work[93]. The modeling of each constraint is as follows: •SC1: Adjacent edge angle shall be as wide as possible for each vertex. This makes all the adjacent edge angles uniform (figure 4.6). Regarding this soft constraint we used the following mathematical formula: SC1score =X v∈VX {e1,e3}∈Ev |2π ρ(v)−θ(e1, e3)| where ρ(v) here is the vertex degree, while θ(e1, e3) is the angle between to adjacent edges e1and e3incident to v. •SC2: Homogeneous inter-vertex spacing. All vertices should be at equal distance from their predecessor and successor in a transportation line (figure 4.7). Regarding SC2, we used the following mathematical formula: SC2score =X e∈E ||e| l∗g−1| Chapter 4. Problem Modeling 87 Figure 4.6: SC1 Constraint: the map on the left yields a worse score than the one on the right Where lis the ideal grid length (as user defined parameter) and gis the grid granularity (grid aperture size). The best grid aperture size is automatically calculated by our algorithm, which is a remarkable enhancement regarding to Stott’s work, where user needs to try several grid apertures to see which one fits better to each specific map. •SC3: All consecutive vertices shall dist a certain distance (user definable parameter)(figure 4.7). Regarding SC3, we used the following mathematical formula: SC3score =X v∈V,ρ(v)=2 ||e1|−|e2|| Figure 4.7: An example of the combination of the SC2 and SC3 Constraints. The map on the left presents a non-uniform inter-vertex spacing, while the map on the right presents uniform inter-vertex spacing and a distance of 3 grid units between vertices. Chapter 4. Problem Modeling 94 Figure 4.13: HC3 Constraint: the figure on the left three vertices (V2, V5 and V8) placed at the same grid intersection, occluding each other and violating the HC3 constraint. The figure at the right complies with this constraint. Figure 4.14: HC4 Constraint: the user definable parameter Max Displacement defines the area (left figure) to where the vertex can be displaced from its original placement, through all the algorithm (right figure). 4.4.3.2 Hybrid Constraints - Topological Relation Preservation Not every constraint must be exclusively modeled as a soft constraint in the objective function or as a hard constraint. The example of this is the topological relations preservation. The preservation of topological relations is of fundamental importance [88], and to achieve it the initial relative position of vertices must be kept, i.e. the binary relations “north of” (“No”), “south of” (“So”), “west of” (“Wo”), “east of” (“Eo”) of the geographically correct initial transportation map shall be preserved throughout the generation of the spider map. Although Stott’s work [26] makes a brief mention to the topological relations, it does not provide any model. Chapter 4. Problem Modeling 95 We modeled the topological relations preservation as a hybrid constraint that can either be treated as a “soft” or “hard” constraint. If we enable it as a soft constraint, violations may occur, although this relaxation yields a penalty to the objective function score. The penalty is proportional to the ratio of the topological relations that are violated. This means that treating topological relations as a soft constraint makes them desirable but not obligatory. This is useful in some cases where some degree of topological relation violation is necessary in order to achieve better visual layout, though it can create user disorientation. If the topological relations are treated as a hard constraint, they cannot be violated, although there is some degree of freedom: they can change if they are not reversed in any of the components. This means that if a vertex is “North of” and “West of” another particular vertex at the original map, a solution that would have it placed just “North of” would still be a feasible solution. The same would not happen if the relation is reversed to “South of” and/or “East of”. This example is illustrated at figure 4.15. Figure 4.15: Topological Relations Preservation Constraint example: the map at the right still respects the hard version, considering the hypothetical original map (left) As it is possible to see in tables 4.6 and 4.7 the topological relations that changed (shown in italic at table 4.7 do not invert any of the original topological relations thus complying with the hard topological relation preservation constraint. If there is any inversion of the topological relations, as it is exemplified in figure 4.16, the solution would not considered feasible. It is possible to observe in tables 4.8 and 4.9 the topological relations that changed. The ones shown in bold at table 4.7 invert the original topological relations. The hard constraint version can also be modeled to enforce a strict topological relations preservation by not allowing any change on the topological relations throughout the Chapter 4. Problem Modeling 96 Table 4.6: Topologic Relations of the example map depicted in figure 4.15 (left). Vertices V1 V2 V3 V4 V5 V6 V1 - No No NoWo NoWo NoWo V2 So - No Wo NoWo NoWo V3 So So - SoWo SoWo NoWo V4 SoEo Eo NoEo - NoEo NoEo V5 SoEo SoEo NoEo SoWo - No V6 SoEo SoEo SoEo SoWo So - Table 4.7: Topologic Relations of the example map depicted in figure 4.15 (right). The relations that changed are in italic. Vertices V1 V2 V3 V4 V5 V6 V1 -NoWo No Wo NoWo NoWo V2 SoEo -NoWo SoWo Wo NoWo V3 So SoEo - SoWo SoWo NoWo V4 Eo NoEo NoWo - NoEo NoEo V5 SoEo Eo NoEo SoWo - NoEo V6 SoEo SoEo SoEo SoWo SoWo - Figure 4.16: Topological Relations Preservation Constraint example: the map at the right does not respect the hard version, considering the hypothetical original map (left) Table 4.8: Topologic Relations of the example map depicted in figure 4.16 (left). Vertices V1 V2 V3 V4 V5 V6 V1 - No No NoLo NoLo NoLo V2 So - No Lo NoLo NoLo V3 So So - SoLo SoLo NoLo V4 SoRo Ro NoRo - NoRo NoRo V5 SoRo SoRo NoRo SoLo - No V6 SoRo SoRo SoRo SoLo So - Chapter 4. Problem Modeling 97 Table 4.9: Topologic Relations of the example map depicted in figure 4.16 (right). Italic formatting indicates a topological relation violation without inversion of relation while bold formatting indicates a a topological relation violation with inversion, regarding the map in figure 4.16 (right). Vertices V1 V2 V3 V4 V5 V6 V1 -NoLo NoLo Lo NoLo NoLo V2 SoRo -NoLo SoLo SoLo NoLo V3 SoRo SoRo -SoRo SoRo SoRo V4 Ro NoRo NoLo - NoRo NoRo V5 SoRo NoRo NoLo SoLo - No V6 SoRo SoRo NoLo SoLo So - generation of the spider map (even the ones that do not reverse the original topological relations). 4.4.3.3 Geographical Constraints Respecting Geographical constraints is a complete innovative breakthrough as they do not exist in literature and past research. They allow us to deal with geographical constraints such as rivers, parks, the ocean, or other features that may condition the visual layout of the map. To our best knowledge, it is the first time they are described and modeled into a schematization optimization algorithm. •GC1: The position and geometry of the geographical accident can not be changed throughout the generation of the spider map. As a consequence geographical accident polygons do not need to comply with the octilinearity criteria. This happens because it is not relevant to the transportation network topology that external features such as geographical constraints have their polygonal chain points on the top of grid intersections. In fact, they would occupy available positions for placing vertices, and, depending on the grid aperture, their shape could be severely distorted, making them hard to identify for the user. •GC2: Graph edges or vertices must not occlude any area of the geographical constraint polygons. Geographical constraints shall be respected, as it would be nonsense to place a vertex on a river or ocean (figure 4.17). Sometimes, complying with this constraint may imply disrespecting any of the hard constraints. To avoid this problem, a differential grid aperture size (with finer grid near the geographical constraint polygon, for higher grid resolution) can be introduced. Figure 4.17 (left) shows a river and a vertex and an edge belonging to the transportation network occluding the river. A vertex is even located on the river. This is not plausible Chapter 4. Problem Modeling 98 in real world, and according to the geographical constraint GC2 it would not be a feasible solution. The figure on the right shows a feasible solution where the path between two vertices in opposite sides of the river is drawn by finding a suitable path between the rivers. To achieve this and simultaneously comply with the hard constraints, a higher resolution grid was used to allow the path to cross the river through the available space. The use of different resolution grids (differential grid aperture sizing) is used to overcome limitations on coarser grids whenever needed to comply with CG2. Figure 4.18 shows an example where a differential grid aperture is used. Figure 4.17: GC2 Constraint: An example of the violation of this constraint (left) and an example of compliance of this constraint (right). Figure 4.18: Example of the use of differential grid aperture - magnification of figure 4.17. The magnification of the river cross shows an increased grid aperture to allow river crossing, while keeping the grid embedding. Chapter 4. Problem Modeling 99 4.5 The Tabu Search Algorithm The automatic generation of Spider maps involves the use of efficient optimization algorithms at the optimization phase to produce the best map satisfying all the criteria mentioned in subsection 4.4. Tabu search was chosen as the backbone of our information system as it fits the enunciated model and has the following advantages: •It is considered to be a fast metaheuristic •It has excellent local minimum escaping ability due to the use of the tabu lists •It usually does not start with a random solution, which is quite adequate to our problem •It always generates a solution •It is presents an iterative improvement process which can be stopped at any time •Its structure is well suited for mapping constraints and optimization functions •The tabu search refinements presented in the literature have the potential to be applied to our problem Glover published the original Tabu Search heuristic method more than twenty six years ago [145] [146] and since then several researchers have been applying it to solve operations research problems. Tabu Search has become a popular method in finding good solutions in large combinatorial problems. Even if the obtained solutions are not optimal, they could provide good approaches to the optimal solution. Built around the idea of allowing non improving moves while using memory to avoid cycling back to previously visited solutions whenever a local optimum is found or to pursue intensification/diversification strategies, tabu search has found success in many applications either used as a standalone algorithm or in conjunction with other heuristics [147]. Tabu search relies on two main concepts: adaptive memory and responsive exploration [148]. While adaptative memory is concerned with searching the solution space effectively, responsive exploration is related to intelligent enumeration: a bad strategic choice can yield more information than a good random choice (as other methods such as GRASP, genetic algorithms do, for example). At an abstract high level point of view, Tabu Search starts as an usual local search strategy would, by iterating from one solution to another through a move chosen from the possible neighborhood moves until the defined termination criterion is met. As we take a deeper look into the Tabu Search, the differences become apparent. Chapter 4. Problem Modeling 100 An important first level consideration for Tabu Search is the choice of the move that takes us from one solution to another. A candidate list to restrict the possible moves in the neighborhood is chosen to achieve balancing between the quality of the moves and the effort to find it. If we assume we can guess the quality of each move, we can evaluate and pick intelligent moves that fit our problem. Otherwise we can select randomly, if the neighborhood is random. Another important consideration is the use of memory, either short or long-term based. Short term memory is achieved through the use of a tabu list which stores a list of the recently chose moves, preventing them to be chosen again (tabu moves). Longer term memory is achieved by saving promising solutions or moves. The use of memory means that the neighborhood of a solution is “not a static, but rather a set that can change according to the history of the search” [148]. The memory use can be tailored to specific problems, either its short or long term use. The use of short term memory can also be temporarily bypassed to allow tabu moves that may lead to unvisited solutions that may be attractive in certain situations. This bypass is performed through the aspiration criteria. Aspiration criteria are problem-dependent. Memory in Tabu Search can be also used as a basis for the intensification/diversification balance: it can be used to know the presence or absence of certain elements in good solutions and aspiration criteria can be dynamically changed to reflect that knowledge (intensification). On the other hand, short term memory can be designed such as the neighborhood may include moves that are separated by a certain degree from other solutions visited previously, for example.[149] (diversification). Algorithm 2summarizes the tabu search procedures. Algorithm 2 Tabu Search generic algorithm 1: procedure TabuSearch(a, b) 2: InitialSolution ←solution 3: while TerminationCondition 6=true do 4: CreateCandidateList(solu) 5: ChooseBestCandidate() 6: UpdateSolution() 7: UpdateAspirationCriteria() 8: end while 9: return b 10: end procedure From this generic algorithm it is worth to look with more detail to the ChooseBestCandidate() function, described in algorithm 3. Tabu Search has seen many improvements and refinements to its original specification, many of them concerning with the dynamic change of memory or objective function Chapter 4. Problem Modeling 101 Algorithm 3 Choice of the Best Candidate Move in a generic Tabu Search 1: procedure ChooseBestCandidate(a, b) 2: bestMove ←null 3: while CandidateMoves.Count 6= 0 do 4: if IsTheBestTillNow(move) = true then 5: if IsTabu(move) = false then 6: bestMove ←move 7: else 8: if satisfiesAspirationCriteria(move) = true then 9: bestMove ←move 10: else 11: discard(move) 12: end if 13: end if 14: else 15: discard(move) 16: end if 17: end while 18: return BestMove 19: end procedure definitions on run time to avoid local minima and with the intelligence of the search process. Nevertheless, different real world problems may require different approaches and those refinements are not applicable to every problem. 4.6 Conclusions Throughout this chapter we presented an comprehensive model for the generation of spider maps, including the data structure model, the multicriteria nature of the problem and presented some solutions for improving the state of the art, such as an improved objective model and constraint modeling. The following chapter will explain how this model is implemented in a real information system. Chapter 5 The Proposed Approach This chapter describes the adopted process for the automated generation of Spider Maps. Based on the problem modeling described in the previous chapter, we developed an approach based on three phases: 1. Pre-Processing: to find a first feasible solution, an initial Spider Map 2. Tabu Search Optimization: improve the solution 3. Post-Processing: preparing the best obtained solution to be output This approach is implemented through a a set of algorithms. The input is a XML file containing the description of the transportation network to serve as the base for the generation of the spider map. The XML file is parsed and loaded into a Semantically Rich data Structure (SRDS) that will be converted into a Simple Graph Data Structure (SGDS) and a mappings table. The pre-processing phase is then executed and the graph is aligned to a regular grid to discretize space and achieve an octilinear graph embedding. This step transforms the original map in a way that it becomes compliant with all the hard constraints. Being so, the pre-processing phase transforms the original transportation map into a feasible solution. This solution is then optimized through our tabu search algorithm until the stop conditions are met: the total number of iterations (user defined). The post-processing phase then takes place, by inserting vertices as needed on the graph in order to make it respect the geographic restrictions, and the SGDS, together with the mappings, are ready to be converted to the SRDS to produce the output map, which is an XML and SVG file, that can be published or further manually edited. This process is summarized in figure 5.1 shows this general description of our process of generation of a spider map through an UML activity diagram. 102 Chapter 5. The Proposed Approach 103 Figure 5.1: UML Activity Diagram depicting our process of automatically generating a Spider Map. 5.1 Initialization and Alignment to Grid As shown in the first part of the pseudo-algorithm 4the pre-processing phase starts by loading the XML file to a SRDS. This structure is then converted to a SGDS and mappings. The SGDS is the main data structure that supports all the map processing. The map is then rescaled for the Hub dimension defined by the requester of the spider map. With this transformation the map accommodates the Hub according to the input XML file and translates the vertices coordinates if needed, distorting the graph as needed, as shown in figure 5.2. The rescaling occurs by calculating the new position of the transportation network vertices considering the dimensions and position of the center of the hub. The rescaling has a visual effect of “compression” of the map outside the hub, with the vertices that were near the Hub implantation point at the original transportation map are displaced greater distances than the ones that are near the original map limits. Then, the initial topological relation matrix of the graph (before further processing) is obtained and saved. This matrix will be used to assess, at each iteration in the tabu search optimization phase, the compliance with topological relations. The map is then aligned to a grid in order to discretize space and obtain an octilinear embedding. As the Chapter 5. The Proposed Approach 110 Algorithm 7 Recursive HPPO Function - Part 1 1: procedure recursionHPPO(Graph, Move) 2: ResultMoveList ←Empty 3: if isDestinationGridIntersectionEmpty(Move) then 4: InPlacementVerticesIDs ←empty 5: for all v∈Vdo 6: if v.Placed OR v.Processing OR v.Active then 7: InPlacementVerticesIDs.add(v) 8: end if 9: end for 10: if topologicalRelationCheck(Move, inPlacementVerticesIDs) then 11: ResultMoveList.Add(Move) 12: Return ResultMoveList 13: else 14: ProcessedLocationsMatrix[Move.destination] = true 15: end if 16: end if 17: AlternativeMoveList ←empty 18: AlternativeMoveList.Add(FindAlternativeMoves(Move)) 19: MovesToRemove ←empty 20: for all (doMove in AlternativeMoveList) 21: if !checkForHardConstraints(Move) OR ProcessedLocationsMatrix[Move.destination] then 22: MovesToRemove.Add(Move) 23: end if 24: end for 25: for all move in MovesToRemove do 26: AlternativeMoveList.Remove(move) 27: end for 28: if AlternativeMoveList.Count == 0 then 29: ProcessedLocationsMatrix[Move.destination] == false 30: Return 31: end if 32: for all (Move in AlternativeMoveList) do 33: if !CauseDisplacement(move) then 34: RecursionResultMoves ←RecursionHPPO(Graph, Move) 35: if RecursionResult != null) then 36: return RecursionResultMoves 37: else 38: MovesToRemove.Add(Move) 39: end if 40: end if 41: end for 42: for all move in MovesToRemove do 43: AlternativeMoveList.Remove(move) 44: end for Chapter 5. The Proposed Approach 111 Algorithm 8 Recursive HPPO Function - Part 2 45: for all (doMove in AlternativeMoveList) 46: DisplacementDirection ←empty 47: DisplacementDirection ←CalculateDirectionVector(Move.VertexID, Vertex[Move.destination]) 48: if (NeedsDisplacement(Move.VertexID, Vertex[Move.destination], DisplacementDirection)) then 49: RecursionResultMoves ←RecursionHPPO(Graph, Move) 50: end if 51: if RecursionResult != null) then 52: return RecursionResultMoves 53: end if 54: end for 55: return 56: end procedure The HPPOrecursion starts by checking the destination grid intersection to where the vertex referred in the move shall be placed on. If the grid intersection is free (i.e. it has no other vertex on it), the algorithm checks if this move would violate any topological relations, in what concerns to the vertices that are already placed or in placement by other instances of the recursion HPPO function (this function could be able to distribute threads to different cores in multi-core processors to speed up process). Therefore, we must know the list of placed, being processed or active vertices. Having this list set, we can speed up the topological relations assessment as we will only compare the vertices that are necessary against each other, thus saving time. If there is no violation of topological relations, then, the move can be returned (and it will be executed by the HPPO function). If the move’s destination is a grid intersection which already has a vertex there or there is any violation of topological relations, then, alternative destinations for the move’s vertex are found (within the nearest grid intersections). From those alternative moves we will remove the ones that violate the hard constraints (and thus would not constitute feasible solutions) and those that already have vertices that are definitively placed. An empty list is returned if no alternatives remain. From the remaining alternatives, the algorithm tries first the ones that do not trigger further vertex displacements (corresponding to empty grid intersections), calling recursively the function recursionHPPO. If none of those alternatives is feasible, then the algorithm tries the alternatives that will imply vertex displacements. In this case, the algorithm calculates the displacement vector between the vertex that is originally being moved and the vertex that is at its grid intersection destination. It is important to know this vector to understand in which direction the vertex which is at the destination shall be displaced to allow the original vertex to replace it at its current location. This means we need to know the direction vector of the “domino effect”, to avoid further topological relations violations. After knowing the direction vector, the RecursionHPPO Chapter 5. The Proposed Approach 112 is recursively called to obtain a set of resulting “domino moves” regarding the vertices that need to be displaced, and they will be recursively returned to the HPPO function which will execute them. Each vertex of the map being placed can be in one of the three following situations: •No Grid Intersection Contentions or Topological Relation Violations This is the simplest case to manage: when a vertex needs to be placed on the nearest free grid intersection (figure 5.5 left), and that move does not violate any topological relation, then the vertex can simply be placed there. Figure 5.5: Example of vertex positioning when no contentions nor topological relation violations arise. •Grid Intersection Contentions This happens when a vertex is to be placed on a grid intersection already occupied by another vertex. As figure 5.6 shows, V1 would be placed on the location of V2. The algorithm tries to build a list of alternative moves within a certain range. In this particular case a list of alternative moves {C1, ..., C16}is built. The first alternatives to be tried are the ones that do not cause the displacement of vertices that are already positioned and do not cause topological relation violations. So the alternative destination C11 is chosed as it is the nearest empty location which would not cause a topological relation violation and the vertex V1 is moved there. As no topological relations are violated, there is no need for further vertex displacements. Figure 5.6: Example of vertex positioning when Grid Intersection Contentions arise, but there is the chance to solve the contention without violating topological relations. Chapter 5. The Proposed Approach 113 •Grid Intersection Contentions with topological relation violations This case occurs when a contention arises and all the alternative moves imply recursive vertex displacement due to topological relation violations. This is what we call a “domino effect”, where vertices need to be displaced. In case it causes any topological relation violation, more vertices may need to be displaced, and if contentions arise, more vertices may need to be displaced. It is important to remember at this point that all the initial topological relations are obtained from original transportation of map, before discretization of space. The displacement recursion occurs until all contentions are solved and all vertices are successfully placed without violating topological relations or until there is no possible vertices placement respecting the topological relations. The displacement of the vertices always analyzes the nearest available grid intersections in the first place if they exist, and the grid intersections that despite not being empty, respect the displacement vector, in the second place if they do not exist. Figure 5.7 illustrates this situation. We can see that V5 would be placed at the grid intersection where vertex V2 is placed. Again, a list of alternative moves {Ci, ..., C16}is built. As at this piece of map we have a geographical restriction (a lake), the C2, C3, C4) alternative locations are discarded. From the remaining alternative moves, the ones that do not required apparent vertex displacement (the ones that are on empty grid intersections), are verified to see if they would cause violation of topological constraints. The violation of topological constraint would require a re-placement of some vertices, so, as they all would need re-placement of some vertices (and thus would also cause a“domino effect”), the best option would be to move to the C10 location, where the V2 vertex is. The displacement vector ~ d(given by the direction angle between V5 and V2) is calculated and therefore V2 is displaced according to ~ d, meaning that it would be moved to the next grid intersection that follows the direction of ~ d. This move, however, will cause a violation of the topological relations. Before the move, V2 was “south of” and “right of” V1, and after the move it is just “south of”. Therefore, a movement vector ~ d1 to fix this problem is calculated for the vertex V1, so V1 will be displaced one grid intersection accordingly. In addition to this, V4 also needs to be displaced for the same reason, with a vector ~ d2 being calculated. This vector will cause the vertex V4 to be displaced, and this recursive process ends here as there is no need of further vertex displacements as there are no occlusions and all the topological relations were fixed through the compensation moves executed. If those compensation moves caused further occlusions or topological relation violations, then, new compensation moves would be executed till a feasible solution would be found, otherwise the recursionHPPO function would return empty to the main HPPO function, which by its turn would Chapter 5. The Proposed Approach 114 signal the SmartFit problem that it is not possible to have a feasible solution with this grid resolution. Figure 5.7: Example of vertex positioning when Grid Intersection Contentions and topological relation violations arise, causing the “domino effect”. At the end of this phase, we have automatically determined the best grid aperture size, re-scaled the map to include the hub, aligned the vertices to the grid solving the contentions while respecting topological relations so that the whole graph is prepared for the optimization phase (figure 5.8). The map obtained at the end of the execution of the HPPO is a feasible solution for our problem (the first Spider Map). Chapter 5. The Proposed Approach 115 Figure 5.8: Example of discretization of vertex coordinates, obtained after the initialization and alignment to grid. 5.2 Tabu Search Optimization Metaheuristic After having the first feasible solution which is an initial graph embedding that complies with the definition of spider map, we proceed to executing the tabu search optimization phase (algorithm 9). The initial solution in the Tabu Search procedure is the first Spider Map produced as described in the previous section. We begin by initializing the typical tabu search structures, such as the tabu list which stores the moves considered tabu, the history list of the obtained solutions (that a this point contains only the first obtained spider map), and a structure that computes the objective function score. In the tabu search algorithm applied to our problem, a move consists of a reference to the vertex being moved, the origin and destination grid intersections. Therefore a move defines the movement of a vertex to a location on its neighborhood. Each move has a tenure Chapter 5. The Proposed Approach 116 time that defines the number of iterations it can be kept on the tabu list, meaning that throughout that tenure time the corresponding vertex cannot be moved. We used a tenure time 5. This value has been quoted in the literature [151] [152] [149] as an usual good guess for this type of problem. Algorithm 9 Information system - General Description - Optimization Phase 10: tabuStructure ←initializeTabuStructures() 11: ListOfMovesHistory ←empty; 12: bestGraph ←graph 13: bestGraphScore ←evaluateGraph(graph) 14: iterationsWithoutImprovement ←0 15: while iteration <maxIterations do 16: graph.updateFreqMatrix(); 17: candidateMoves ←generateCandidateMoves(graph); 18: candidateMoves ←checkForHardConstraints(graph) 19: candidateMoves ←evaluate(candidateMoves) 20: candidateMoves.orderBy(score) 21: moveIsTabu ←isTabu(candidateMoves.first) 22: while moveIsTabu do 23: if checkAspirationCriteria(candidateMoves.first) then 24: break() 25: end if 26: if candidateMoves.count == 1 then 27: break() 28: end if 29: candidateMoves.RemoveFirst() 30: moveIsTabu ←isTabu(candidateMoves.first) 31: end while 32: graph ←update(graph, candidateMoves.first) 33: graph.updateTopologicalRelationsMatrix() 34: UpdateTabuStructures() 35: if candidateMoves.first.score <bestGraphScore then 36: bestGraphScore ←candidateMoves.first.score 37: bestGraph ←graph 38: iterationsWithoutImprovement ←0 39: else 40: iterationsWithoutImprovement++ 41: end if 42: if (useSpatialDistributionAnalysisType) then 43: executeSpatialDistributionAnalysis(graph) 44: end if 45: end while The optimization phase is based on the vertex movement [153], [93], [91], [26], [94], [92]. At each iteration, a set of possible moves are generated, the moves that lead to unfeasible solutions are discarded, the remaining ones are evaluated and the best move is executed (if it is not in the tabu list, or even if it is but presents a significant increase of the quality of map). This process repeats as many times as the predefined number Chapter 5. The Proposed Approach 117 of iterations or until a time deadline is met (if we need soft real time map processing), or until a certain quality threshold is obtained.). The algorithm also keeps track of the number of iterations without map score improvement. By the end of the tabu search optimization phase, the best solution found through the optimization phase is retrieved, and the map is ready for post processing. The algorithm starts by updating the frequency matrix (a frequency matrix is a matrix with the dimension of the spider map grid which tells us how and where the vertices are located on the grid and it is important to speed up several calculations throughout the algorithm, such as as the Hard, Soft and Geographical Constraints. Then the set of possible moves is generated for every vertex that is part of the spider map (the candidate move list). The impact of each move is sequentially tested for each of the hard constraints. If it fails to comply with one of them, it will be eliminated from the candidate move list. The remaining candidate moves are evaluated according to the set of soft constraints and then they are sorted according to the quality of the solution they will generate. The best move of the list is chosen and, if it is not a tabu move, it can be applied. Still, if it is a tabu move but satisfies the aspiration criteria, it is also applied. The aspiration criterion here is the evaluation of the improvement of the map over the best map obtained until the moment. If it does not satisfy the aspiration criterion, but there are not any moves left and this is the last move, it is executed to avoid not generating a solution, as a last resource. The optimization phase iterations are repeated until the finishing condition is met. 5.2.1 Getting the Best Move From the initial feasible solution obtained by the HPPO algorithm, a candidate list of possible vertex moves is generated for each vertex of the graph, within a certain range as shown in figure 5.9: for each vertex, several hypothetical moves are generated within a range defined by the user as an algorithm parameter called max displacement (in the depicted case the range is one). For the vertices A, B, C and D, there is a set of possible moves {Aij, Bij, Cij, Dij}∀i, j ∈1,3 that can lead to the displacement of a vertex from its current position to a destination defined by each move. The max displacement parameter sets the grid cell range to where each vertex can be displaced. The higher the value of this parameter, the bigger will be the search space, as shown in figure 5.10. This comes with some advantages (faster map quality increase, better results in few iterations) but also with also with some disadvantages (slower algorithm processing per iteration, premature convergence, decreased ability to escape local minima). Chapter 5. The Proposed Approach 118 Figure 5.9: Generation of candidate moves example. Figure 5.10: The max displacement parameter in the generation of the point candidate list: smaller circles show the generated candidate points if max displacement=1, bigger outer circles show the generated candidate points if max displacement=2 Each move will be tested regarding the satisfaction of the hard constraints. If a move produces an unfeasible solution, it is removed from the candidate list. The moves that pass the hard constraint test correspond to a set of moves that will still produce a feasible solution for the spider map generation problem. The next step is to to choose the best possible move. To do this, each of the possible moves is evaluated using the objective function that encompasses the evaluation of our soft constraints. After obtaining the score for each move, they are listed and ordered from the best to the worst. The algorithm selects the first (best) move and checks if it is a tabu move. If it is, it checks if it satisfies the aspiration criteria that allow it to be selected as the move to be executed at the current tabu search iteration. If if does not, the move is discarded. If the move Chapter 5. The Proposed Approach 119 is not a tabu move, it is selected to be executed at the current tabu search iteration. After having found the best move, it is executed, the graph embedding is updated, the move is added to the tabu list and the next iteration begins. The objective function minimizes the global sum of each of its components, each component being related to an individual soft constraint. Each soft constraint has a relative importance which can be changed through user parameters, according to each type of map. 5.2.2 Spatial Distribution Analysis Throughout the execution of the tabu search in the optimization phase, there is the possibility that it gets stuck in local minima. This may happen when there are several vertices in consecutive grid intersections (vertices clusters), for example. To solve this problem, we introduced a feedback mechanism to our tabu search implementation which allows us to both eliminate clusters of vertexes and to improve map distribution. Instead of a cluster detection and movement algorithm such as Stott’s [26], we developed a spatial density analysis algorithm. As described in pseudoalgorithm 9, it may run at the end of each iteration of the tabu search phase, in order to increase variability in the solution and allow further optimization, allowing to escape local minima. Being so, the Spacial Distribution Analysis algorithm is a significant diversification strategy to this problem. But its advantages go beyond that: it is also a visual map balancing algorithm. Cognitive psychology postulates that it is easier for the human brain to understand regular patterns and balanced presentation of visual information [71] [68][69][87]. Therefore it is desirable that the map produced is visually balanced, without very dense areas with many stops and lines contrasting with sparse areas with almost no lines or stops. This algorithm measures the quality of the spatial distribution of the elements of the map (figure 5.11) as follows: 1. A density matrix with the same dimension of the frequency matrix containing the number of vertices in each cell of the grid. 2. Each cell of the density matrix will store a value which is the number of adjacent cells that also have vertices (fig. 5.12). 3. Calculate the average value of all cells of the matrix (fig. 5.13) 4. Scan every line of the density matrix, calculate the average value, compute the “spike” score (the differences between spikes and the average score value) according to the following formula: Chapter 5. The Proposed Approach 126 Figure 5.16: Intelligent Differential Grid Resolution. Chapter 6 Testing in Real World In this chapter we present the tests conducted on real map instances, together with the description of the test environment and software framework used to perform the tests. The results are discussed and at the end of chapter some maps that are used in real world are shown. 6.1 The GenX Framework The developed algorithms were implemented using C# programming language and were tested through a software framework developed through a collaboration research performed by a team involving collaborators from FEUP 1, OPT 2, STCP 3, FWT 4, INEGI 5. Our information system is already being used to generate spider maps which are already being used in Porto, Lisbon and Santo Tirso cities. The software framework which was developed through a joint effort with OPT in order to support our approach for the generation of spider maps provides the map XML file input. The framework connects to the company proprietary databases, where the transportation network raw information is stored in (the stop locations, the names of the stops, lines and all the meta data and semantic richness that describe a network). It also contains a designer-side GUI which allows user to select the hub zone and the transportation lines the final spider map shall feature. The business logic handles the 1Faculty of Engineering of University of Porto http://www.fe.up.pt 2OPT is an company based in Porto which develops IT infrastructures for Transportation Services. http://www.opt.pt 3STCP is a public transportation company operating in Porto. http://www.stcp.pt 4FWT is a company based in London which produces maps for transportation networks. http://www.fwt.co.uk 5INEGI is a research institute based in Porto 127 Chapter 6. Testing in Real World 128 GUI requests and sends them to the database, returning all the relevant raw data for that map, and building an XML file which is the input of our information system, as shown on figure 6.1 Figure 6.1: UML Layer Diagram providing an overview of the OPT Framework Once our the set of algorithm finishes map processing and outputs the resulting map, the framework gets the resulting file for further automatic adaptation to public use (executing automatic label positioning and visual line arrangement, or further manual processing. 6.2 Tests and Results We began the tests to assess some performance measures, such as Execution Time (raw performance execution time, in seconds), perceived quality versus iterations and execution time. Other assessment we have made was the evaluation of explicit searching versus implicit searching regarding Execution Time and quality. We also tested the isolated effect of each soft constraint to understand how to tune the weights for the soft criteria for some maps. The topological relations hard/soft approaches were also subjected to Chapter 6. Testing in Real World 129 test, as well as the results of the A-Star algorithm and the spatial distribution analysis algorithm. All the maps subjected to test can be found in appendices Ato F, in three versions: raw version (geographically accurate), after the pre-processing phase and after being fully processed by our approach. 6.2.1 Test Environment and Description All the tests performed involved real data with real world complexity, on a laptop computer, with an AMD N830 CPU with 4GB RAM and a typical low grade SATA hard drive using Microsoft Windows 7 64-bit and Microsoft Visual Studio to run the framework and the algorithm. Although it may be much slower, the algorithm was compiled on debug mode for testing and demonstration purposes. As the release mode packs several optimizations in terms of code and hardware architectures, it is expected that the live use of this algorithm can see an increase of up to five times in raw performance, depending on specific hardware optimizations. Nevertheless, hardware environment optimizations or considerations are out of the scope of this research. We used 6 different maps from Porto bus transportation network, whose properties are presented in table 6.1. Each of the six maps considers a variation where geographical constraints are included. The 6 maps are presented in appendices Ato F. The map in figure 6.2 (map 3) was generated with our algorithm, with some minor manual aesthetic work performed such as label inclusion. The algorithm was capable of generating an understandable spider map in soft real time, with no conflict points and respecting the topological relationships between stops. Table 6.1: The maps subjected to test and their features. Map Id Zone Vertices Edges GeoCons XML Size (KB) 1A Av. Republica 36 45 Yes 295 1B Av. Republica 36 45 No 269 2A Castelo do Queijo 47 58 Yes 307 2B Castelo do Queijo 47 58 No 282 3A Polo Universitario 22 20 Yes 149 3B Polo Universitario 22 20 No 124 4A Rotunda da Boavista 104 155 Yes 885 4B Rotunda da Boavista 104 155 No 859 5A S. Joao 114 156 Yes 866 5B S. Joao 114 156 No 841 6A Paranhos 26 25 Yes 165 6B Paranhos 26 25 No 140 We executed a set of 8 tests: Chapter 6. Testing in Real World 130 Figure 6.2: Spider Map of Hospital de Sao Joao area of the city of Porto, generated through our enhanced Tabu Search algorithm •Test 1: Execution Time - Execution time for each map with standard settings6. •Test 2: Quality versus Iterations Number - The graphical evolution of the solution score (quality) over the execution of the algorithm in 10000 iterations. •Test 3: Maximum Vertex Displacement parameter influence on result - Quality versus Execution Time regarding the variation of this parameter. The Maximum Vertex Displacement corresponds to the max displacement parameter which sets the grid cell range to where each vertex can be displaced, as shown in figure 5.10. •Test 4: Candidate Move Generation Ratio parameter influence on result - Quality versus Execution Time regarding the variation of this parameter. The Candidate Move Generation Ratio is a parameter that controls explicit or implicit search in tabu search: a ratio of 100% means that all possible moves are analized by the algorithm. •Test 5: Soft Constraint Isolated Effect of Parameters in map visual presentation - We measure the visual isolated effect of each of the soft constraints that comprise the evaluation function. 6The standard settings may not be the optimal settings. They are the default settings shown at the parametrization window as seen in figure 6.3 Chapter 6. Testing in Real World 131 •Test 6: Hard versus Soft topological relations - The effect of treating topological relation enforcement as a soft or hard constraint in final map visual quality and execution time. •Test 7: A* Pathfinding Overhead - Measurement of overhead time of the A* pathfinding algorithm when finding paths around geographical accidents. •Test 8: Spatial Distribution Smart/Blind Algorithm Evaluation - For every map, test the effect of the Spatial Distribution Algorithm distribution with either by running it automatically when the tabu search solution quality is not improving after a number of iterations (Smart) or by running it periodically along the tabu search (Blind). With these tests we intend to analyze the most important parameters of the algorithm, their influence on the common performance indicators and on visual quality of the maps. Except for the parameter under analysis, all the other parameters are set to their default values. The purpose is to to analyze how the algorithm behaves regarding the variation in each parameter and to extract conclusions that can be applied to generate effective and high quality spider maps. 6.2.2 Parametrization When the GenX framework is launched, a controller window appears. This window allows the parameter values to be set by the user for specific maps and to test the algorithm parameters sensitivity and performance (figure 6.3). This dialog groups the parameters per categories. The algorithm related parameters include: •Grid Granularity is the grid aperture size. This parameter is automated through HPPO, but the user can change its initial guessing value. Default unit type is milimiter. •Hub Clearance Multiplier is a parameter that defines on how big the grid cell range clearance area will be. The clearance area is an area that surrounds the hub which will not contain any vertex. It is used to improve readability. The larger this parameter, the larger will be the empty area surrounding the hub. •Number of Iterations defines the number of iterations of the algorithm •Maximum Vertex Displacement (iteration) defines the range of the move candidate list for each vertex at each iteration, as shown in figure 5.9. Chapter 6. Testing in Real World 132 Figure 6.3: Parametrization Window, showing the standard parameter values. •Maximum Vertex Displacement (total) defines the maximum range of displacement for each vertex regarding its original (geographically accurate) position. •Candidate Move Generator Ratio defines the percentage of the the possible move candidate list elements to be effectively generated at each iteration (the percentage of all possible vertex moves at each iteration that will be analyzed by the tabu search optimization). This affects the balance between implicit vs explicit search. •Generate Inflection Points toggles the generation of inflection points in post processing. •Use A-Star Pathfinding for GeoConstraints switches the A-Star pathfinding in post processing. The Hard Constraints related parameters include: Chapter 6. Testing in Real World 133 •Avoid Forbidden Area guarantees that edges and vertices are not be placed on forbidden areas, like the hub, the outside of the canvas area and the hub clearance area. •Avoid Geographic Constraints guarantees that the vertices are not placed placement of vertices on the areas defined by the geographic accident polygons. •Avoid Hard Conflicts guarantees that the vertices are not placed on top of other vertices. •Enforce Maximum Vertex Displacement (total) ensures that every vertex must be within a certain pre-defined range from its original (geographically accurate) position. The value of this parameter is the range. •Enforce Strict Topological Relations ensures the enforcement of strict topological relations. The parameters related to the soft constraints include the weight of each soft constraint in the optimization function. This parametrization can be used to tailor the execution of the algorithm for specific maps, to assess the effect each soft constraint has in the final result and as a sensitivity analysis, useful for normalization purposes and quality testing. The Spatial Distribution related parameters control the execution of the spatial distribution analysis. The Spatial Distribution Analysis Algorithm can be used in two ways: •Analyze after iteration (Blind) switches the execution of the spatial distribution analysis algorithm periodically after a number of tabu search iterations (defined by the user). To be disabled, it shall be set to -1. •Analyze when stuck (Intelligent) switches execution of the spatial distribution analysis algorithm whenever the tabu search algorithm is not able to improve the current solution for a number of iterations (defined by the user). To be disabled, it shall be set to -1. The topological relations enforcement can be “hard” or “soft”, if we want it to be mandatory or desirable, respectively. For specific maps we may need to consider it part of the optimization function, not being a mandatory feature but a desirable feature. This option adds even more flexibility to the algorithm. Chapter 6. Testing in Real World 134 For normalization purposes, we propose a set of predefined values for the weight of each soft constraint. These values were obtained through intensive testing and after Stott’s research work [26]. Nevertheless, different maps may require different weight relations. 6.2.3 Results and Analysis For each test performed the results were summarized in tabular form, and discussed, extracting conclusions on the data obtained. By default, all the algorithm parameters keep their standard values as shown in figure 6.3, unless stated otherwise. 6.2.3.1 Test 1 - Execution time Table 6.2 shows the result metrics for Test 1, where we wanted to assess the execution time for each map with standard settings. The execution time is measured in seconds. The Geo Var shows the variation of the Execution Time regarding the equivalent map version without geographical restrictions. The Geo Execution Time Delta indicates the decrease in the Execution Time of the maps without geographical restrictions in comparison with the same map with geographic restrictions. Complexity is a measurement of the map XML file size (the larger the file, the more complex the graph is and more amount of information it contains) in relation to map 1A, considered as a reference for comparison purposes (100%). Table 6.2: Results of Test 1 - (ET = Execution Time, Cpx = Complexity) Map ID ET Geo Var Geo ET Delta Cpx Cpx Index 1A 2,56 100% - 295 100% 1B 1,93 75% -25% 269 91% 2A 4,16 100% - 307 104% 2B 3,03 73% -27% 282 96% 3A 1,61 100% - 149 51% 3B 1,15 71% -29% 124 42% 4A 12,91 100% - 885 300% 4B 12,29 95% -5% 859 291% 5A 13,92 100% - 866 294% 5B 12,56 90% -10% 841 285% 6A 1,78 100% - 165 56% 6B 1,31 74% -26% 140 47% Geo Bias Avg -20% As we can see, the algorithm is in average 20% faster (in average) for maps without geographical restrictions, regarding their versions with geographical restrictions. However, this difference shrinks for higher complexity maps. Chapter 6. Testing in Real World 135 Figure 6.4: Relation between the Execution Time and the Geo Variation parameter and the complexity index for each map. Figure 6.4 shows that the Execution Time varies with the map complexity. For example, the complexity of maps 4A,4B,5A and 5B is about almost three times the complexity of map 1, but the Execution Times increase about six times. We observe that map complexity has a strong effect on Execution Time, while the existence of geographical constraints has not such a drastic effect. 6.2.3.2 Test 2 - Quality versus Iterations Number Regarding Test 2, we wanted to assess the graphical evolution of the execution of the algorithm concerning the score solution over 10000 iterations for each map. Figure 6.5 shows an example of the execution of the algorithm for the map 1. For practical purposes, all the execution graphs can be found in appendix G. The figure shows that the first hundred iterations provide a continuous and steady score improvement. After that the improvement rate decreases (although the score continues to improve). After about 1000 iterations the score improvement is quite slower as the algorithm continues to explore the search space. Occasionally, better solutions are found and the score improves. The results also show that solution score variability throughout the algorithm execution decreases as map complexity increases. A possible explanation is that highly complex maps have less score variability as they have more map points, and each move has less impact in global map score. In high complexity maps, increasing variability and diversification would be a good improvement. Another improvement