# An Improved Route-Finding Algorithm Using Ubiquitous Ontology-Based Experiences Modeling

Authors: Maryam Barzegar; Abolghasem Sadeghi-Niaraki; Maryam Shakeri; Soo-Mi Choi
Journal: Complexity
 (2019)

---

## Abstract

Every day, people are hired in different organizations and old and retiring employees are eliminated from enterprise systems. Eliminating these individuals from organizations leads to the loss of their spatial experiences. In addition, since new employees lack relevant experience, they need a long time to develop the correct skills for the company and may even cause damage to the organization during this learning process. Therefore, storing the spatial experience of individuals is a critical issue. Due to the intelligence of ubiquitous Geospatial Information System (GIS), any experience from any user can be received and stored. In the future, based on these experiences, an appropriate service to each user may be provided as needed. This paper aims to propose an ontology-based model to store spatial experiences in the field of ubiquitous GIS route finding. For this purpose, first ontology is designed for route finding, and then according to this ontology, an ontology-based route-finding algorithm is developed for ubiquitous GIS. Finally, this algorithm is implemented for Tehran, Iran, and its results are compared with the shortest path algorithm (Dijkstra’s algorithm) in terms of the route length and travel time for peak traffic time. The results show that while the route length obtained from the ontology-based algorithm is more than Dijkstra’s algorithm, the travel time is lower, and on some routes the difference in travel time saved reaches 35 minutes.


---

## Body

## 1. Introduction

Knowledge management is a process that helps organizations to detect, select, organize, and publish important information and skills that are considered as organizational memory and which are not typically organized. This enables organizations to effectively manage learning issues, strategic planning, and dynamic decision making. The causes of the advent of knowledge management can be considered as follows: (1) transformation of the industrial business model; in the past, the assets of an organization were fundamentally tangible and financial assets (production facilities, cars, land, and so on); (2) an extraordinary increase in the amount of information and its electronic storage and increased access to information have generally added value to knowledge; (3) the changes in the age pyramid of populations and the demographic properties that are mentioned in only a few sources; and (4) specializing in activities may also hold the risk of losing organizational and expertise knowledge through the transfer or dismissal of employees. Taxi associations are one of the organizations that need to organize organizational memory. In this organization, taxi drivers acquire skills and knowledge by repeating their daily route many times so that after some years, they become experts and experienced person in their work. Actually, this experience is a kind of knowledge which is gained after many years of effort, and it is called spatial experience because it is based on location. A spatial experience is an everyday experience of the population that is related to locations or people’s activities that are conducted in a location [1]. In other words, spatial experience can be called location-based experience. As finding a route between locations and destinations by taxi drivers is a location-based activity that is conducted by taxi drivers in a city, the experiences of taxi drivers in finding good routes are spatial experiences. On a daily basis, there are many experienced taxi drivers who are removed from taxi associations after they retire. This causes a loss of the spatial experiences of expert drivers without transferring those experiences to the next driver. On the other hand, new taxi drivers need high-cost training and considerable time to gain experience comparable to that of the previous drivers. Due to the aforementioned reasons, it is necessary to use methods that can save this knowledge and reuse it to solve various problems. Semantics plays a significant role in knowledge organization, and it can support the enrichment of measurements and gaining knowledge [2] Ontology is one of the methods that use semantics. Ontology is a collection of terms in a domain, and these terms are linked to visual properties, relationships, and associations. Ontology structures domain knowledge, provides the opportunity of reusing domain knowledge, and makes domain assumptions explicit [3].Several researchers have focused on the storage of experiences and formulation of knowledge. Foguem et al. [4] formulated knowledge in the feedback processes of experience. Their purpose is to transform the information gained from the experience into explicit knowledge. The feedback frame of experience provided in their paper is a general overview of industrial problem-solving methods and includes 5 sections: event, environment, analysis, solution, and learned lessons. To model the experience, case-based reasoning and conceptual graphs have been used. Lasierra et al. [5] used ontology for modeling hospital health catalogs and sharing and acquiring knowledge from hospital personnel’s experiences. The role of organized knowledge in the organized learning process has been studied by Abel [6]. This knowledge is presented using ontology. Ontology is the basis for knowledge maps and web system performance for organized learning. The innovation of the web system provided in his paper is the organization of resources with this knowledge map. A project has been defined that focuses on gathering knowledge and skills in the field of organization and, more specifically, on gathering resources related to this knowledge. The goal of this project is managing this asset through the use of the information technology operating system that supports the organizational memory of its users. It also focuses on how users of an organization apply this system as an organizational learning vector. Garcia-Crespo et al. [7] designed a semantic hotel recommendation expert system and used consumers’ experiences and fuzzy logic techniques to find hotels according to tourist needs.Mourtzis et al. [8], Efthymiou et al. [9], and Mikos et al. [10] also used ontology, the knowledge base, and web software to exchange experiences. Data mining and conceptual graphs were used by Ruiz et al. [11] to reuse industry experiences. Moehrle and Raskob [12] managed nuclear events using data mining of previous experiences. Meng et al. [13] tried to extract effective information from the experience of consumers on the consumer community network of Huawei P10/P10 Plus. They used a network analysis method in which each node represents a topic and the weight of its edges denotes the number of users. Renu and Mocko [14] used data mining to reuse industry experiences. Modoni et al. [15] also used ontology for knowledge reuse in industries. This study has three steps including automatic generation of ontologies from relational database schemas, ontology integration, and addition of rules and execution of queries. Reyes et al. [16] used case-based reasoning and the knowledge base to store and reuse experiences in industry. Kamsu-Foguem and Abanda [17] used the knowledge base to gather experiences and graphic concepts to represent ontology in industry. In another study, Kamsu-Foguem et al. [18] used conceptual graphs and ontology for checking Building Research Establishment Environmental Assessment Methodology (BREEAM) sustainability standard. Othman and Beydoun [19] also used the knowledge base for storing and reusing disaster management knowledge. Xia et al. [20] proposed a new algorithm for analyzing spatiotemporal patterns of taxi trajectories on Apache Hadoop distributed computing platform in order to improve the functionality of Hadoop in handling big datasets associated with massive small files and reducing memory consumption. Geng et al. [21] used OWL-S to promote the geospatial service with spatiotemporal semantics from information to knowledge. OWL-S constitutes three logical parts including service profile (explains the usage and function of the web service), service model (service execution logic), and the service binding rules (rules for invoking the web service). Nowak-Brzezińska [22] proposed a new knowledge base structure and inference algorithm to improve analysis process for rule checking. The inference algorithm is a rule clustering method which merges similar rules based on a similarity value. Maleki et al. [23] proposed ontology as a framework for supporting smart services in product-service system of industries. According to studies on the storage of experiences, different methods including ontology [6, 24], conceptual graph [25], rules [17], and logic [16] have been used for modeling experiences. However, conceptual graphs and rules are primarily used for knowledge representation, and their applications are limited. This stems from the fact that all relations between concepts cannot be presented by conceptual graphs. Moreover, modeling experiences by logical models may lead to some problems including complexity, lack of explicitness, inefficiency in modeling complex phenomena such as human activities, behaviors, and emotions, and updating (changing a logical relation can lead to changing the whole model). However, the relations defined in ontology are explicit and everyone can understand these relations effortlessly. Also, ontological models are easily updatable, and this rule is a fundamental principle in designing these models [26].Several studies also have been done in the field of ontology and route finding. Domain ontology has been built up from a high-level ontology by Camossi et al. [27]. The purpose of this ontology is to identify abnormal routes in the maritime transport industry and for the detection of the transportation of contraband in maritime surveillance. Wannous et al. [28] used ontology to investigate the paths of seals. Path ontology for personalized trips and animal life monitoring was studied by Hu et al. [29]. Baglioni et al. [30] used path ontology to examine the behavior of individuals in a mobile game. In this research, a series of georeferenced points are embedded on the ground. When a person connects to the game server and passes these points by answering some puzzles, a route will be found that can be used to examine individual behaviors during the game. Durak et al. [31] combined path simulation with path ontology to simulate the angle and direction of airplane landing and flight and the flight path. Malgundkar et al. [32] used ontology for urban traffic analysis. Sadeghi-Niaraki et al. [33] used ontology to help SDI services, especially route-finding analysis. An ontology-based route-finding system was developed using a multicriteria decision-making method by Niaraki and Kim [34]. Saeedi et al. [35] proposed an ontology-based conceptual modeling for navigation and tourism systems. The proposed system is a multimedia and spatial database system that can be integrated with various sensors, including digital cameras and Global Positioning System (GPS) in mobile platforms, which generalizes location-based services to context-based services to help context-aware services and available mobile and desktop applications. Effati and Sadeghi-Niaraki [36] used ontology to predict vehicle accidents. Czerniak et al. [37] proposed an owlANT model to store the graphs of possible routes of ants in an ant colony algorithm. In this ontology model, the classes and the relationship of them form apexes and edges of the graph, respectively. Although these studies used ontology for route finding, the definition of the ontology and conceptual vision of each of these papers is different from the present paper, and updating of the created ontology is done less often during the process.Several researchers have used the experiences of taxi drivers in route finding. For example, Li et al. [38] built a hierarchical street network for route finding using taxi GPS data. They considered only GPS data related to peak traffic time. Ji-hua et al. [39] used taxi GPS data to create an experimental street network. In this research, to separate unnecessary GPS data, it is assumed that the taxi speed should not be less than the minimum speed; if the taxi speed was low, it indicates that the taxi is looking for a passenger rather than transporting someone. In addition, a hierarchical approach is used for route finding that firstly examines whether the location and destination entered by the user are in the experimental network or not. If both were in the experimental street network, then only the experimental street network would be used for route finding. If neither of them were in the experimental street network, then the closest point to it (or those) is found in the network and a rectangle larger than the distance between the point and the closest point in the experimental street network is selected from the main street network. For example, if both the location and destination were not in the experimental street network, route finding using Dijkstra’s algorithm is done as follows: the path between the location and the closest point of the experimental street network is found, followed by the path between the closest point of the experimental street network of the location and the closest point of the experimental street network of the destination and finally the path between the closest point of the experimental street network of the destination and destination. In our paper, a part of this hierarchical approach in the proposed method is used. Ziebart et al. [40] proposed a probabilistic approach to predict the next intersection, destination, and route of the driver based on taxi GPS data. This approach was used to help provide the right information and services to users at the right moment in ubiquitous Geospatial Information System (ubiquitous GIS). The behavior of drivers is modeled in this paper, and instead of providing the fastest route to direct the driver, the destination of the driver is anticipated. Yuan et al. [41] also used GPS taxi data to create a time-dependent graph of experimental paths where a node is a segment of the route that has been repeatedly used by taxi drivers. They used an entropy-variance-based clustering method to estimate travel time. In the present paper, the idea of considering the number of times that each segment is passed by drivers for weighting edges of the street network has been used. Chen et al. [42], Chu et al. [43], and Liu et al. [44] identified abnormal routes and the source of these abnormalities using taxi GPS data. Liu et al. [45] used experiences of taxi drivers to study urban structure and user planning. For example, in this research, busy routes are detected, and then the cause of this heavy traffic will be determined (for example, existence of a subway station). Then, it is decided that, for example, more residential accommodation will be created to reduce travel time in this area. Rahmani and Koutsopoulos [46] formed a path graph using taxi GPS data and used this graph to find the shortest path with the minimum cost. Zheng et al. [47] used the GPS data of 60 people within 10 months to infer transport modes of individuals based on supervised learning. This is done to help the cognition of human behavior and to understand the user’s mobility for ubiquitous computing. Due to different studies in this field, and since reducing the processing time of route finding is important, generating a new street network that is simpler than the main street network to speed up route finding is frequently done. However, the separation of traffic-intensive (high-traffic) and low-traffic routes is not considered due to the departure time and the simplification of the taxi street network, and the combination of ontology and the experiences of taxi drivers have not been used. In addition, some of these studies require the full use of Dijkstra’s algorithm that also reduces the speed and precision of route finding in large street networks.This paper aims to model spatial (location-based) experiences using ontology in the field of ubiquitous GIS route finding. Ubiquitous GIS is a combination of GIS and UbiComp and is defined as a set of concepts, methods, and standards that move spatial (and temporal) data and processes into the mainstream of computing and create user-friendly programs and systems. In this regard, the two components of any data and any user of ubiquitous GIS are focused, and each experience from any person in the field of route finding can be modeled in experiences ontology and can be used in route-finding algorithms. The general trend of this paper is that first ontology is designed for route finding. Then, the data needed for this ontology (paths for taxi drivers) are collected using an application. Next, based on the number of times that each segment is passed by drivers, the cost of each segment of the path is determined and an ontology-based route finding algorithm of the drivers’ experiences is proposed. Finally, the proposed method is implemented in a ubiquitous GIS for the city of Tehran and is compared to Dijkstra’s algorithm in terms of travel time and route length. It should be noted that improving route-finding algorithm using ontology-based modeling of driver’ spatial experiences facilitates the timeliness of services, provides the capability to make use of earlier information without reprocessing, and enhances sharing, reusing, and processing domain knowledge [48, 49]. The structure of this paper is as follows. In Section 2, the concepts of ubiquitous GIS and the cause of using ontology for modeling individual’s experiences in ubiquitous GIS are explained. In Section 3, the general method of this paper, drivers’ experiences ontology, weighting method, and the proposed ontology-based route-finding algorithm are introduced. The proposed algorithm is implemented using Tehran’s data in Section 4. In Section 5, the proposed method is compared to Dijkstra’s algorithm in terms of travel time and route length. Finally, general conclusions of the proposed method and its advantages are presented.


## 2. Ubiquitous Computing

With the growth of science and technology, new generations of computing have appeared. Ubiquitous computing, which is a new generation of computing systems, includes a vast range of computers and small sensors embedded in the environment. The goal of ubiquitous computing is, in fact, to diminish the virtual dimension of technology in our lives. In ubiquitous computing, all the limitations are removed for human beings. Figure1 illustrates the elements of ubiquitous computing. In ubiquitous computing, users can access their desired services in any location, at any time, using any device, and without any limitations in the network. At the same time, the huge volume of information and services in today’s world have caused the introduction of some new concepts such as providing intelligent location-based services under any situation, at any time and location, using any device and service, via any network, and for any user. Considering the close relationships between GIS and information technology (IT), geomatics, especially GIS, followed this trend and introduced ubiquitous Geospatial Information Systems. Ubiquitous GIS is based on mobile computing technology environment and provides mobile and distributed geographic information services. It integrates GIS, GPS, and wireless communication [50]. Ubiquitous GIS enhances the provision of spatial data and services to users, even public who have no professional knowledge of GIS, in an easy-to-use way [51, 52].Figure 1
Elements of ubiquitous computing.The major issues with the exact route-finding algorithms are the relatively large time it takes to find the route between two locations and the high volume of data stored in a database. In a ubiquitous environment, the system needs to respond to the user’s requests in a real-time manner; hence, the noted issues are barriers that should be resolved. In this paper, the ontologies are utilized to overcome this issue to enhance knowledge sharing and reusing between different users. In other words, ontologies help the stored knowledge to be used by different users many times. In this case, any user element of the ubiquitous environment is supported. Ontologies provide the capability to make use of earlier information without reprocessing [53]. This facilitates the timeliness of services. In addition, using ontology in route-finding algorithm was to store the knowledge of experienced persons. This makes the systems smart, ubiquitous, and act like an experienced human. Moreover, the data in ontologies are stored in plain text formats such as Web Ontology Language (OWL). Obviously, plain text formats require much lower storage space. Moreover, ontologies are independent from text and implementation and operate on a higher level of abstraction. However, databases are situated at the lower level of abstraction and they are mainly designed to meet the requirements of a particular application or corporation, and when the requirements change, the schema of a database also need to be modified [54, 55]. In our research, since we update the ontology many times, relational databases cannot be used. Relational databases are not appropriate for applications that need to make frequent updates since you need to change the schema for each update. In addition, ontologies do not need to be normalized (such characteristics make for easier the information sharing and merging) [56]. However, relational databases need to be normalized. Besides, ontology languages are more expressive in terms of expressing more semantic concepts than database languages which only include constructs for defining or extracting data [55]. In addition, ontology languages provide a more correct and precise domain conceptualization [57].In this research, any user can access the ontology at any time and in any location to find routes. In addition, due to the intelligence of ubiquitous environment, the experiences from users (any data element of ubiquitous computing) can be received and stored to be utilized for future services.


## 3. Methodology

Figure2 shows the main processes of this research. Based on these processes, the ontology-based route-finding algorithm is proposed which enables to store and retrieve spatial experiences of the taxi drivers.Figure 2
Research methodology.An ontology-based algorithm for storing spatial experiences in ubiquitous GIS space has been presented. Figure3 depicts the workflow of the proposed approach. First, the dataset is collected via an app. This app collects the routes of taxi vehicles, needed for the ontology. The number of times that each segment is passed by drivers is calculated and used to weight the edges of the street network and to build the cost model. Then, taxi paths are converted to the drivers’ experience class in the ontology. Finally, an ontology-based route-finding algorithm is designed, implemented, and evaluated in ubiquitous environment. The work has been described in detail in the following sections.Figure 3
Workflow of the proposed approach.The algorithm makes the route-finding systems smart and ubiquitous intended to act like experienced people. A ubiquitous system is a smart system which acts not only like a person but also like an experienced human. A person who works for some field of interest for many years gets a lot of experience. This person has much knowledge. To transfer the knowledge of the experienced persons to the system, we need this algorithm. The proposed algorithm can receive and store the knowledge of an experienced person and also accumulate the experiences of many experienced persons.


### 3.1. Drivers’ Experience Ontology

In our ontology, the drivers’ experience class includes two subclasses: experimental routes and nonexperimental routes. The experimental route class encompasses the paths which the experienced drivers have driven. These routes are collected via an app and are converted to OWL classes. This class, itself, includes two subclasses: traffic and without-traffic classes. The paths which have been passed at peak traffic times (7–10 AM and 16–20 PM) are categorized under the traffic subclass. The nonexperimental route class encompasses the paths obtained from the route-finding procedure. These should also be converted to OWL classes. In the drivers’ experience ontology, for the sake of simplicity and in order to improve usability, only the names of routes are defined as classes; individuals of each class are not defined in this file. For each route class, a separate OWL file is defined, the name of which is the same as the corresponding route class in the drivers’ experience ontology. The constituent nodes of a route are stored as individuals in the corresponding OWL file using their identification (ID) code as their name. The coordinates of each node are defined as data properties of individuals in the ontology.The created ontology is shown in Figure4. To save space, only a limited number of routes are shown here. This figure depicts the ontology before the route-finding process. After route finding, if a new path has been created and the time entered by the user is within the pick range, it will be stored in the traffic subclass of the nonexperimental route class. Otherwise, it will be stored in the nontraffic subclass. Each class in the lowest level of ontology shows a route, and its name is defined based on its location and destination. For routes which were traversed on nontraffic times, the name of class would be location destination, and for routes related to traffic classes, the name of class would be location_destination_t. If the route was traversed on traffic times and it was retrieved from algorithm’s results, the name of class would be location_destination_n_t. The flowchart of this ontology is shown in Figure 5.Figure 4
Drivers’ experience ontology (to save space, only a limited number of routes are shown here).Figure 5
Flowchart of creating drivers’ experience ontology.


### 3.2. Weighing Method

In this paper, a graph for a street network is constructed. The route finding is performed based on this graph. Each segment of the path is considered as an edge of the graph. The weight of each edge is determined based on the number of times the drivers have passed the corresponding segment. Since this number might be unexpectedly great, its normal form is computed as follows:(1)fnei=fei−fmin+1fmax−fmin+1,where fei is the number of passes of edge, ei, and fmin and fmax are the minimum and maximum number of the whole passes in the graph. For a segment which is not located in experimental routes, fei=0. Therefore, fmin = 0. Generally, the weights of the edges of the street network are computed using the following equation:(2)wei=maxfneLengthe−fneiLengthei,where wei denotes the weight of ith edge of the graph, Lengthei is the length of the edge, and maxfne/Lengthe is the maximum number of passes of an edge divided by the length of that edge. Since edges with smaller weights are preferred in Dijkstra’s algorithm, the values are subtracted from the maximum value to inverse values.The reason for choosing Dijkstra’s algorithm in this research is that in the proposed algorithm, in each execution, if a new path is created by an algorithm, it will be stored in ontology in order to reuse it in future. Therefore, we need to use an algorithm which provides an exact result with one hundred percent reliability because the results will be reused in the future. Among the shortest path algorithms, breadth-first search (BFS) and depth-first search (DFS) can only be used in a weighted graph if the weights are equal. However, in our graph, weights which are the number of traverses by taxis are not equal. Moreover, they are slower than in the Dijkstra algorithm [58]. The Greedy algorithm uses heuristics and A∗ algorithms which are a combination of the Greedy algorithm and the Dijkstra algorithm. Therefore, they provide an approximate result, not an exact result.


### 3.3. Ubiquitous Ontology-Based Route-Finding Algorithm

Figure6 depicts the way our proposed algorithm works. First, the user specifies the location, the destination, and the time. Then, the algorithm determines whether a subclass with the specified location and destination exists in the ontology or not. If the time chosen falls within the range of peak times, the existing paths in the traffic subclass are searched. Otherwise, the paths in the nontraffic subclass are examined. When a path exists, the stored route is displayed to the user and the algorithm terminates, without needing to conduct route finding. However, when there is no corresponding path, the algorithm determines whether the location and destination exist in the experimental street network or not. If both exist in the network, only the experimental network is used to construct the graph and find the route (again, peak time determines the subclass to choose—traffic or nontraffic) and the algorithm terminates. If the location and/or the destination does not exist in the experimental street network, the closest points of the network to them are found. Then, a rectangle with a diameter (R2 = R1 + 2√2 h) greater than the distance between the location (or destination) and the point is extracted from the main road network. The flowchart of the proposed hierarchical algorithm and the extraction of the rectangular region from the road network are shown in Figure 7. To clarify the route-finding procedure, consider a situation where both the location and the destination do not exist in the experimental network. In such a situation, the route finding includes three stages: (1) route finding from the location to its closest point in the experimental network (SS’); (2) route finding from this point to the closest point of the experimental network with respect to the destination (S’D’); and (3) route finding from the closest point of the experimental network (with respect to the destination) to the destination (D’D). After route finding, the resulting route is stored in the drivers’ experience ontology as a separate OWL file. Now, requests with these locations and destinations are responded to in real time without requiring additional route finding.Figure 6
Proposed algorithm flowchart.Figure 7
(a) Hierarchical experimental road network. (b) Extraction of rectangular region from main road network [39].
(a)
(b)


## 3.1. Drivers’ Experience Ontology

In our ontology, the drivers’ experience class includes two subclasses: experimental routes and nonexperimental routes. The experimental route class encompasses the paths which the experienced drivers have driven. These routes are collected via an app and are converted to OWL classes. This class, itself, includes two subclasses: traffic and without-traffic classes. The paths which have been passed at peak traffic times (7–10 AM and 16–20 PM) are categorized under the traffic subclass. The nonexperimental route class encompasses the paths obtained from the route-finding procedure. These should also be converted to OWL classes. In the drivers’ experience ontology, for the sake of simplicity and in order to improve usability, only the names of routes are defined as classes; individuals of each class are not defined in this file. For each route class, a separate OWL file is defined, the name of which is the same as the corresponding route class in the drivers’ experience ontology. The constituent nodes of a route are stored as individuals in the corresponding OWL file using their identification (ID) code as their name. The coordinates of each node are defined as data properties of individuals in the ontology.The created ontology is shown in Figure4. To save space, only a limited number of routes are shown here. This figure depicts the ontology before the route-finding process. After route finding, if a new path has been created and the time entered by the user is within the pick range, it will be stored in the traffic subclass of the nonexperimental route class. Otherwise, it will be stored in the nontraffic subclass. Each class in the lowest level of ontology shows a route, and its name is defined based on its location and destination. For routes which were traversed on nontraffic times, the name of class would be location destination, and for routes related to traffic classes, the name of class would be location_destination_t. If the route was traversed on traffic times and it was retrieved from algorithm’s results, the name of class would be location_destination_n_t. The flowchart of this ontology is shown in Figure 5.Figure 4
Drivers’ experience ontology (to save space, only a limited number of routes are shown here).Figure 5
Flowchart of creating drivers’ experience ontology.


## 3.2. Weighing Method

In this paper, a graph for a street network is constructed. The route finding is performed based on this graph. Each segment of the path is considered as an edge of the graph. The weight of each edge is determined based on the number of times the drivers have passed the corresponding segment. Since this number might be unexpectedly great, its normal form is computed as follows:(1)fnei=fei−fmin+1fmax−fmin+1,where fei is the number of passes of edge, ei, and fmin and fmax are the minimum and maximum number of the whole passes in the graph. For a segment which is not located in experimental routes, fei=0. Therefore, fmin = 0. Generally, the weights of the edges of the street network are computed using the following equation:(2)wei=maxfneLengthe−fneiLengthei,where wei denotes the weight of ith edge of the graph, Lengthei is the length of the edge, and maxfne/Lengthe is the maximum number of passes of an edge divided by the length of that edge. Since edges with smaller weights are preferred in Dijkstra’s algorithm, the values are subtracted from the maximum value to inverse values.The reason for choosing Dijkstra’s algorithm in this research is that in the proposed algorithm, in each execution, if a new path is created by an algorithm, it will be stored in ontology in order to reuse it in future. Therefore, we need to use an algorithm which provides an exact result with one hundred percent reliability because the results will be reused in the future. Among the shortest path algorithms, breadth-first search (BFS) and depth-first search (DFS) can only be used in a weighted graph if the weights are equal. However, in our graph, weights which are the number of traverses by taxis are not equal. Moreover, they are slower than in the Dijkstra algorithm [58]. The Greedy algorithm uses heuristics and A∗ algorithms which are a combination of the Greedy algorithm and the Dijkstra algorithm. Therefore, they provide an approximate result, not an exact result.


## 3.3. Ubiquitous Ontology-Based Route-Finding Algorithm

Figure6 depicts the way our proposed algorithm works. First, the user specifies the location, the destination, and the time. Then, the algorithm determines whether a subclass with the specified location and destination exists in the ontology or not. If the time chosen falls within the range of peak times, the existing paths in the traffic subclass are searched. Otherwise, the paths in the nontraffic subclass are examined. When a path exists, the stored route is displayed to the user and the algorithm terminates, without needing to conduct route finding. However, when there is no corresponding path, the algorithm determines whether the location and destination exist in the experimental street network or not. If both exist in the network, only the experimental network is used to construct the graph and find the route (again, peak time determines the subclass to choose—traffic or nontraffic) and the algorithm terminates. If the location and/or the destination does not exist in the experimental street network, the closest points of the network to them are found. Then, a rectangle with a diameter (R2 = R1 + 2√2 h) greater than the distance between the location (or destination) and the point is extracted from the main road network. The flowchart of the proposed hierarchical algorithm and the extraction of the rectangular region from the road network are shown in Figure 7. To clarify the route-finding procedure, consider a situation where both the location and the destination do not exist in the experimental network. In such a situation, the route finding includes three stages: (1) route finding from the location to its closest point in the experimental network (SS’); (2) route finding from this point to the closest point of the experimental network with respect to the destination (S’D’); and (3) route finding from the closest point of the experimental network (with respect to the destination) to the destination (D’D). After route finding, the resulting route is stored in the drivers’ experience ontology as a separate OWL file. Now, requests with these locations and destinations are responded to in real time without requiring additional route finding.Figure 6
Proposed algorithm flowchart.Figure 7
(a) Hierarchical experimental road network. (b) Extraction of rectangular region from main road network [39].
(a)
(b)


## 4. Implementation

In this paper, an ontology-based route-finding algorithm based on the drivers’ experience in ubiquitous GIS space has been proposed. The steps of implementing the algorithm are shown in Figure8. In order to implement the proposed algorithm, the required data have been collected via an app that stores taxi vehicles’ routes through OpenStreetMap (OSM) maps. These routes and their corresponding pick-up and drop-off stations are located in Tehran, Iran, and are entered into the app by the drivers. Then, they are converted to shapefiles. Preprocessing tasks are performed in the ArcGIS software package, and the results are stored in the Oracle database. Each route is also converted to an OWL file using OWL Application Programming Interface (API) in Java. Using these routes, a drivers’ experience ontology is separately constructed in Protégé software. A sample of a route stored in the app is shown in Figure 9.Figure 8
Steps for implementing the proposed algorithm.Figure 9
A sample of a stored route in the app which collects data.After data preparation, the presented algorithm was implemented. In each run of the app, if a new route has been generated, it will be stored as a class in the drivers’ experience ontology to be used in future requests without need for additional processing. As a result, the routes are stored in a low-volume manner, while data processing reduces with even more runs of the algorithm. Each route class in the ontology occupies about 20–25 percent of its corresponding shapefile. Moreover, in the presented algorithm, two road networks exist—a peak-time road network and a low-traffic road network. During peak times, finding an optimum route becomes important; therefore, the algorithm will utilize Dijkstra’s algorithm and present the optimum path to the user.


## 5. Evaluation

In order to evaluate the proposed method, 10 different location-destination pairs, covering most of Tehran city, were selected. First, the experimental road network was fully constructed (ER). Then, it was constructed only considering the low-traffic experimental routes (ETR). Also, the shortest paths between the location-destinations were obtained using Dijkstra’s algorithm (DR). For all obtained routes, the route lengths were calculated. Using drivers’ reports, the travel times were also calculated. Figure10 illustrates the resulting routes for a location-destination pair (Route 10) using the three methods above.Figure 10
Resulting routes for a location-destination pair (Route 10) using the three methods.


### 5.1. Evaluation Based on the Route Length

Figure11 shows a diagram of the length of the paths for the three methods. The route lengths have been computed by accumulating their constituting segments. Figure 12 depicts the ratio of route lengths obtained from the two proposed methods to that of Dijkstra’s algorithm. Figure 13 compares the mean length of the 10 routes for each method.Figure 11
Comparison of route length for 10 evaluated routes of the three methods.Figure 12
Comparison of route length in 2 modes of the proposed algorithm with Dijkstra’s algorithm.Figure 13
Mean of route length for 3 methods.It is observable from the figures that route lengths in the shortest path algorithm are shorter than that of the other two methods. They have, in contrast, greater values when considering high-traffic routes. The mean length of routes is 11.02 km for Dijkstra’s algorithm, 14.22 km when only considering traffic routes, and 13.4 km when considering all the experimental (traffic and nontraffic) routes. This is due to taxi drivers who generally select the longest, but simultaneously fastest, routes. On the other hand, Dijkstra’s algorithm does not consider travel time.


### 5.2. Evaluation Based on Travel Time

Figure14 shows a diagram of the travel times for the three methods. The travel times have been obtained from different drivers who have driven these routes in peak times and in real conditions. Figure 15 depicts the travel times obtained from the two proposed methods to that of Dijkstra’s algorithm. Figure 16 compares the mean travel times for each method.Figure 14
Comparison of travel time for 10 evaluated routes of 3 methods.Figure 15
Comparison of travel time for the 2 modes of the proposed method with Dijkstra’s algorithm.Figure 16
Mean of travel time for 3 methods.It is observable from the figures that travel times obtained from the hierarchical experimental method when only considering high-traffic conditions are lowest; however, the travel time of the shortest path is the highest. The mean travel time is 80 minutes for Dijkstra’s algorithm, 61 minutes when only considering the high-traffic routes, and 77.5 minutes when considering all of the experimental routes. Although the routes are long when considering high-traffic routes, they are fast due to the selection of low-traffic routes in this case. For example, when going to Tajrish Square from Valiasr Square, Dijkstra’s algorithm suggests driving through Valiasr Street, which corresponds to the shortest, but not fastest, route. However, the proposed ontology-based approach suggests that the driver proceeds mainly along Modarres Highway, which reduces the travel time by 35 minutes in high-traffic conditions.Another approach to evaluate the two proposed methods against Dijkstra’s algorithm is to find the ideal route among them. In order to find the ideal route, one can divide the route length by its travel time. Obviously, when the route lengths for all routes or just two of them are equal, the one which has the shortest travel time should be selected as the optimum path. On the other hand, when the travel times are equal, the one which has the shortest length should be selected as the optimum path. Accordingly, in eight cases (of 10 cases), the ontology-based route finding considering only high-traffic routes (ETR) predominates. In the other two cases, the travel time was roughly equal; however, the route lengths obtained from Dijkstra’s algorithm had lower values. To determine the deviation of each method from the ideal case, which is shown in Figure17, the following formula is used:(3)Fj=travel length  of methodjtravel  time of methodj,j=ETR,ER,Dikjestra,Fe=ideal route fraction,Dj=Fj−FeFe.Figure 17
Comparison of routes from the 3 methods with the ideal route.Therefore, according to the evaluations above, it can be claimed that eliminating the experimental high-traffic routes in high-traffic conditions and utilizing the drivers’ experiences make the algorithm generate the optimum route through low-traffic parts of the network. This minimizes travel time, which is the most important parameter in route finding.


## 5.1. Evaluation Based on the Route Length

Figure11 shows a diagram of the length of the paths for the three methods. The route lengths have been computed by accumulating their constituting segments. Figure 12 depicts the ratio of route lengths obtained from the two proposed methods to that of Dijkstra’s algorithm. Figure 13 compares the mean length of the 10 routes for each method.Figure 11
Comparison of route length for 10 evaluated routes of the three methods.Figure 12
Comparison of route length in 2 modes of the proposed algorithm with Dijkstra’s algorithm.Figure 13
Mean of route length for 3 methods.It is observable from the figures that route lengths in the shortest path algorithm are shorter than that of the other two methods. They have, in contrast, greater values when considering high-traffic routes. The mean length of routes is 11.02 km for Dijkstra’s algorithm, 14.22 km when only considering traffic routes, and 13.4 km when considering all the experimental (traffic and nontraffic) routes. This is due to taxi drivers who generally select the longest, but simultaneously fastest, routes. On the other hand, Dijkstra’s algorithm does not consider travel time.


## 5.2. Evaluation Based on Travel Time

Figure14 shows a diagram of the travel times for the three methods. The travel times have been obtained from different drivers who have driven these routes in peak times and in real conditions. Figure 15 depicts the travel times obtained from the two proposed methods to that of Dijkstra’s algorithm. Figure 16 compares the mean travel times for each method.Figure 14
Comparison of travel time for 10 evaluated routes of 3 methods.Figure 15
Comparison of travel time for the 2 modes of the proposed method with Dijkstra’s algorithm.Figure 16
Mean of travel time for 3 methods.It is observable from the figures that travel times obtained from the hierarchical experimental method when only considering high-traffic conditions are lowest; however, the travel time of the shortest path is the highest. The mean travel time is 80 minutes for Dijkstra’s algorithm, 61 minutes when only considering the high-traffic routes, and 77.5 minutes when considering all of the experimental routes. Although the routes are long when considering high-traffic routes, they are fast due to the selection of low-traffic routes in this case. For example, when going to Tajrish Square from Valiasr Square, Dijkstra’s algorithm suggests driving through Valiasr Street, which corresponds to the shortest, but not fastest, route. However, the proposed ontology-based approach suggests that the driver proceeds mainly along Modarres Highway, which reduces the travel time by 35 minutes in high-traffic conditions.Another approach to evaluate the two proposed methods against Dijkstra’s algorithm is to find the ideal route among them. In order to find the ideal route, one can divide the route length by its travel time. Obviously, when the route lengths for all routes or just two of them are equal, the one which has the shortest travel time should be selected as the optimum path. On the other hand, when the travel times are equal, the one which has the shortest length should be selected as the optimum path. Accordingly, in eight cases (of 10 cases), the ontology-based route finding considering only high-traffic routes (ETR) predominates. In the other two cases, the travel time was roughly equal; however, the route lengths obtained from Dijkstra’s algorithm had lower values. To determine the deviation of each method from the ideal case, which is shown in Figure17, the following formula is used:(3)Fj=travel length  of methodjtravel  time of methodj,j=ETR,ER,Dikjestra,Fe=ideal route fraction,Dj=Fj−FeFe.Figure 17
Comparison of routes from the 3 methods with the ideal route.Therefore, according to the evaluations above, it can be claimed that eliminating the experimental high-traffic routes in high-traffic conditions and utilizing the drivers’ experiences make the algorithm generate the optimum route through low-traffic parts of the network. This minimizes travel time, which is the most important parameter in route finding.


## 6. Conclusions

Different people gain different spatial experiences. As there are no systems to store these experiences, they evaporate over time. The present study provides the ability to store spatial experiences and to make the existing systems in ubiquitous GIS space intelligent. In this paper, an ontology-based route-finding algorithm in ubiquitous GIS space was designed and implemented, using the routes driven by the drivers of Tehran in high- and low-traffic conditions.In the proposed route-finding algorithm based on the drivers’ experiences ontology, the number of times that each segment is passed by drivers is used to assign weights to that segment of the network. First, the user specifies the location, the destination, and the time. Then, the algorithm determines whether a subclass with the specified location and destination exists in the ontology or not. If the time chosen falls during peak times, the existing paths in the traffic subclass are searched through. Otherwise, the paths in the nontraffic subclass are examined. When a path exists, the stored route is displayed to the user and the algorithm terminates, without needing to conduct route finding. However, when there is no corresponding path, the algorithm determines whether the location and destination exist in the experimental road network or not. If both exist in the network, only the experimental is used to construct the graph and find the route (again, peak time determines the subclass to choose—traffic or nontraffic) and the algorithm terminates. If the origin and/or the destination does not exist in the experimental road network, the closest points of the network to them are found. Then, a rectangle with a diameter (R2 = R1 + 2√2 h) greater than the distance between the location (or destination) and the point is extracted from the main road network. The main difference of this algorithm to the previous experimental route-finding algorithms is the use of ontology and the construction of road networks only considering the low-traffic paths when there are high-traffic paths in the network. Since each new path is stored as a separate OWL class, the storage issues in the databases are resolved. In addition, the use of ontology causes the system to update every time the algorithm runs and generates new paths. Utilizing only low-traffic routes in high-traffic conditions allows the system to suggest routes that are faster, ensuring the optimum path based on travel time is achieved. According to our evaluations, the proposed algorithm suggests routes that are longer but simultaneously the fastest. This guarantees the appropriateness of using such an algorithm in route finding. In this research, any user can access the ontology from any location and at any time to conduct route finding. Moreover, being intelligent, the ubiquitous environment can receive and store the experiences (any data element of ubiquitous GIS) of any person to utilize within its services in the future.More innovative applications of spatial experience modeling, such as ambulance, firefighting, and tourism services, can be subjects for further considerations. The process of route finding for this category is also affected by traffic as emergency services can also become stuck in traffic like other drivers because there are no dedicated lines on all roads. Due to the limitation in length of road and a large number of vehicles in the road in traffic times, it is hard for other vehicles to provide a route for traversing of the ambulance and they still need to find a way to avoid traffic. Therefore, the experiences from expert technicians in ambulances or firefighters who have been in real event conditions can be modeled and used in the future. In addition, this study considers only two factors, distance and time, for evaluation. Other criteria including fuel consumption can be considered in future.



---

*Source: 9584397-2019-11-11.xml*