GIS-Based Network Analysis for the Roads Network of the Greater Cairo Area Sayed Ahmed Romani Farid Ibrahim Hesham A. Hefny Computer Sciences Dept, High Institute of Computer Computer Sciences Dept, Institute of Statistical Studies Science and Information - City Institute of Statistical Studies and Research, Cairo of Culture and Science and Research, Cairo University, Giza, Egypt 6 October City, Egypt University, Giza, Egypt se.sayedahmed@gmail.com romanifarid@gmail.com Hehefny@ieee.org Abstract It has been proven to be valid and efficient to solve real-life problems, such as responding and resolving In a crowded city like Grater Cairo Region emergency situations [1]. A geographic information (GCR), Egypt, finding a desired location system is a computerized system that is designed to becomes a difficult task, especially in emergency capture, store, manipulate, analyze, manage, situations. The main criteria of any emergency visualize, and present all types of geographical data response system (ERS) are its readiness to solve associated with geographical locations [2]. GIS can the immediate emergency situation such as fire bring all that data together quickly and enable users emergency response, police station emergency to analyze and visualize information in an efficient response, healthcare emergency response system, way. It has been used in several fields such as etc. The main purpose of this paper is to provide transportation management, emergency services, gas an enhanced network analysis that uses the station mapping, and healthcare planning [2]. The capabilities of Geographic Information System shortest path between two vertices “s” and “t” in a (GIS) to identify the best route from the location network is defined as the directed simple path from of an incident for any healthcare service “s” to “t” with the property that no other such path providers in the Greater Cairo metropolitan area. has a lower weight [8]. Most applications solve the The results obtained in this paper showed that shortest path problem based on the distance as a the best route travel time is much better than the weight. In this paper, we used the time parameter shortest route travel time by 22%. In emergency instead of the distance which calculated the path situations, it is essential to reach the location of between two points that takes minimum time based an incident as fast as possible to rescue people on one or more parameters other than the distance. life. So, based on the obtained results, this paper Examples of these parameters are road width, recommended that the GIS best route algorithm average speed, waiting time, etc. In emergency is better than the shortest route algorithm in situations, the best path is preferred, that it takes the emergency situations especially in a crowded minimum time to reach a destination which helps to city like GCR. save people life. The main objective of this research is to find the best path and representing this valuable 1 Introduction spatial information to end-users in an efficient way using GIS software. Most of shortest path algorithms Geographic Information System (GIS) technology is (Dijkstra’s shortest path algorithm, Euler’s algorithm, one of the hottest research tools in the world recently etc.) are finding the shortest path that has only the and one of the fastest growing high technology of least distance between a source node and a monitoring. destination node. Applying one of these algorithms on GIS software that resolve emergency situations is not suitable for real road network because it Copyright © by the paper’s authors. Copying permitted for private and academic purposes. considers only the length of the path to find the shortest one and does not consider other real-time In: Proceedings of the International Conference on Applied traffic information (i.e. Road width, speed limit, Research in Computer Science and Engineering ICAR'17, surface condition, turn restrictions, etc.) which should Lebanon, 22-06-2017, published at http://ceur-ws.org be defined to identify more realistic routes. The road network of the Greater Cairo region was (OD) cost matrix, network analysis, proximity taken as a case study to apply the proposed enhanced analysis, and buffer analysis. method. In [6], the authors established a GIS based fire emergency response service in Kumasi Metropolis, 2 Related Works Ghana where the Ghana National Fire Service In [2], the authors tried to solve the problem of (GNFS) can identify the optimal route from its finding a specialized hospital and its shortest path to location of any fire incident. The optimal route was reach in Aurangabad city, Maharashtra State, India. modeled based on the travel distance, travel time, the They used the ArcGIS software and Dijkstra’s slope of the roads and the delays in travel times. algorithm that provide the shortest path from one In [7], the authors provided a study that depicted the location to another for finding the nearest location of preliminary results for a decision support tool to the hospitals from user’s location. The calculations of model network congestion routing and provide an the shortest path were based on road distances; traffic alternative route during rush hours in emergency congestion and state of the roads were not cases. The system predicts traffic flow and barriers considered. during rush hours and suggests the alternative route In [3], the authors developed a GIS based application to reach hospitals at the time of emergency. The for healthcare emergency response system services to authors used ArcGIS 9.3 network analyst tool and manage healthcare in the ALMOKATAM Zone in Dijkstra’s algorithm for performing shortest path the south of Cairo, Egypt. The optimal route was analysis. The main objective of this study was to find modeled based on the distance to the closest the best route from the nearest hospital ambulance to healthcare service providers. The system integrated the incident location and from the incident location to data acquisition from databases and plotted the the nearest hospital with alternate routes. location-based features of satellite image through a In [8], the authors proposed an optimized version of web base interface which gives access to all different the shortest path based on the Dijkstra’s Algorithm. tasks by different end users to be a decision maker or In the optimized version, the starting node is changed policy makers in system management. They didn't with the searching process, and uses the stack consider any factor other than the distance. structure to maintain it, in order not to revisit the nodes. This improved the searching efficiency to the In [4], the authors discussed the shortest path analysis shortest path practically. But this system was also based on Dijkstra’s algorithm and implemented an considering only the length of the path and did not emergency response system based on GIS. They also consider other real-time traffic information. integrated GIS, web services, and Asynchronous JavaScript and XML (Ajax) technologies and 3 Methodology provided a web-based application for finding the best routes from specialized response team stations In this research, the flowchart of the proposed locations and incident locations. Their proposed enhanced roads network analysis methodology using GIS software is shown in Figure 1. Six stages of the system provided the optimal route depending on the process have been applied, beginning with collecting distance of route without considering road conditions and preparing the data that will be used in the and traffic congestion. analysis (the study area base map, road network data, In [5], the authors developed a desktop-based healthcare service provider data, and historical traffic emergency response system for emergency readiness data), then Geo-referencing the base map of the study and management through GIS in Delhi, India. The area. Following this is the creation of a Geo-database main objective of this application was to provide that will store the prepared data. Then building both immediate response to any incident or accident. A the network topology and the network dataset. detailed transportation network was maintained and Finally, the network analysis process has been integrated with real-time traffic data provided by applied to the road network of the Greater Cairo Region (GCR). NAVTEQ in India. The near real-time traffic information was used to analyze suitable routes to the 3.1 Data Preparation incident location by avoiding highly congested routes and therefore reducing the response time. Using GIS This phase includes downloading the study area base capabilities, various analyses were performed such as map, preparing the road network data, downloading finding the shortest route using Origin–Destination the healthcare service provider’s data, and preparing The Greater Cairo road network data were the historical traffic data. downloaded using the ArcGIS Online Service as The study area is the Greater Cairo metropolitan area. shown in Figure 3. The data contain an attribute It is extended from 30° 11′ 10″ N and 31° 27′ 50″ E. (Meters) to store the length of each road segment in Greater Cairo is the largest metropolitan area the roads network, an attribute (Direction) to store the in Egypt, and the largest urban area in Africa and the direction of each segment, and two fields world's 16th largest metropolitan area. It consists (TF_Minutes and FT_Minutes) to store the time of Cairo Governorate, parts of Giza Governorate, and required to travel over each road segment in minutes parts of Qaliobia Governorate, with a total population in both directions, and an attribute (Name) to store estimated at 20,500,000; and its area is about the name of each road segment. The healthcare 1,709 km2; as well as its density is 10,400/km2 [9]. service providers’ data were downloaded from the Cairo is the capital of Egypt and it is a vibrant city. It OpenStreetMap. The data contain an attribute (Name) is associated with Ancient Egypt, as the famous Giza to store the name of each healthcare service provider, pyramid complex and the ancient city of and another attribute (Type) to store the type of this Memphis are located in its geographical area. It is healthcare service provider. located near the Nile Delta [10]. The base map of Greater Cairo was downloaded from OpenStreetMap (OSM). OSM can be accessed as an ArcGIS Online Service that provides free read-only access to OpenStreetMap as a base map for GIS work in ESRI products such as ArcGIS Desktop It is shown in Figure 2 Figure 2: Base Map of Greater Cairo (from OSM). Figure 1: Enhanced Network Analysis Process Flow Figure 3: The Greater Cairo Roads Network Diagram The last step in the data preparation phase is the Table 1: Daily Profiles Table Structure preparation of the road network traffic data. Traffic data are given information about how travel speeds on specific road segments change over time. In Field Data Type Notes network analysis, traffic is important because it affects travel times, which in turn affect results. If we Unique identifier don’t account for traffic routing from one location to Object ID Long for each record in another, the expected travel and arrival times could the table. be far from accurate. Another reason to account for traffic is that it gives the routing opportunities that Represent free- SpeedFactor_0000 avoiding the slower, more congested roads, which flow scale factor at to Double saves time. Traffic data can be stored using two different times of SpeedFactor_2300 different models: historical and live traffic. In this the day. paper, traffic data were stored as historical traffic data. The Streets_DailyProfiles join table identifies road The historical traffic data were modeled based on the features, their free-flow travel speeds, and their idea that travel speeds follow a weeklong pattern. related traffic profiles for each day of the week Thus, the travel speeds of a given road segment at a (Table2). certain time of a day of a week are expected to be similar to those of the same road segment at the same Table 2: Streets_DailyProfiles Table Structure time of the same day in another week. The expected speeds are usually determined by averaging multiple observations over some time span, such as a year. Field Data Type Notes Also, the historical traffic data were created according to the ArcGIS Network Analyst Unique identifier for specifications. Object ID Long each record in the 3.2 Geo-processing of Toposheet table. Identifies the feature In this phase, a Geo-referencing process for the EdgeFCID Long class that the street downloaded roads network data is being performed. feature is stored in. The Geo-referencing process allows the registration Identifies the road of the digitized top sheet on the earth’s surface [2]. It EdgeFID Long feature. is considered a very critical stage as it affects the Work together to accuracy of the road network data. identify the direction 3.3 Creation of Geo-database EdgeFrmPos of travel (0 since the And Double The Geo-database is the native data structure used in beginning of the EdgeToPos ArcGIS and is the fundamental data format used for road, 1 for the both editing and management of the data. A Geo- opposite end) database can be personal, file, or enterprise. In this Represents the free- proposed method, a personal Geo-database has been BaseSpeedKPH Double flow speed created using ARCGIS. A personal Geo-database is a Represents the database that can store, query, and manage both Profile_1 Short traffic for Sunday spatial and non-spatial data. It will contain the data of healthcare service providers, road network, and Represents the Profile_2 Short traffic tables. The road network data and the traffic for Monday healthcare service providers’ data were discussed Represents the earlier in the methodology. DailyProfiles and Profile_3 Short traffic for Tuesday Streets_DailyProfiles tables were used to store traffic information. The “DailyProfiles” table is used to Represents the store the speed profiles for each day of the week Profile_4 Short traffic for a (Table1). The times of the day are split into time Wednesday intervals, or time slices (one hour) of equal duration. Represents the Profile_5 Short traffic for Thursday Represents the powerful extension of ArcGIS that provides network- Profile_6 Short based spatial analysis, including route analysis, travel traffic for Friday directions, closest facility analysis, and service area Represents the analysis [2]. It enables users to dynamically model Profile_7 Short traffic for a Saturday realistic roads network factors, such as turn restrictions, speed limits, and traffic conditions at 3.4 Building Network Topology different times of the day. The ArcGIS Network Analyst Extension uses the standard Dijkstra’s To get good analysis and results, it is necessary to algorithm to calculate the least accumulated cost build a topology of the road network to discover between the destination node and every other node in whatever errors in the data and correcting them. This the network. Two types of network analyses were was performed by applying some topology rules such applied; the best route analysis, and the closet as ensuring that there are no dangles in the road facilities analysis. network and the roads do not intersect or overlap with themselves. 3.6.1 Best Route Analysis 3.5 Building Network Dataset The best route analysis generates the best route between two locations based on travel time which After correcting the road network errors, it is ready depends on the traffic conditions available on the for being used in building the network dataset that network at a particular time of a day. The network will be used in the network analysis. To create a analyst extension makes it is easy to set the best rote network dataset that renders traffic data, we need a analysis parameters, such as the travel time that will Geo-database that contains a line feature class, and be used as an impedance factor, the start time of the two traffic data table created earlier. The line traveling which produce different results based on the feature class will represent the road network and day profile selected, the restrictions on the analysis, must be stored in a feature dataset. The traffic tables such as the road directions (unidirectional or will represent the traffic data and its relationship with bidirectional), and the ability to ignore invalid the road network. The network dataset is well suited network locations that may cause the analysis to fail. to model the transportation network. It consists of a set of edges that represent the links over which agents After adjusting the best route analysis settings, we will travel, and a set of junctions that connect edges chose the start location and the end location, and then and facilitate navigation from one edge to another. using the best route solver tool to generate the best The Network analyst extension was used in ArcGIS route between these two locations. Figure 5 shows for Desktop to create the network dataset shown in the best route between a start location (Location 1) Figure 4. and end location (Location 2). Figure 4: Network Dataset Renders Traffic Results Figure 5: The Best Route Result 3.6 Performing Network Analysis The directions window of the previous analysis is shown in Figure 6. The road network analysis has been implemented using ArcGIS Network Analyst Extension. It is a 3.6.2 Closet Facilities Analysis 4 Results and Discussion The closet facilities analysis finds the closest In this paper, we provide analysis and comparison of facilities that can be reached in a specific period from the results of the network analysis using two different an incident location based on travel time and traffic methods. To navigate from one location to another, information available. This helps in emergency either the route with the least length (shortest route) situations to know the closest facilities that can be will be selected, or the route with the least travel time reached from the incident location, which in turns (best route) will be selected depending on the reduces time, effort, resources and saving people life impedance factor you choose to solve for. Figure 9 [3]. The network analysis extension makes it is easy shows the shortest route between a source location to set the analysis parameters for the closet facilities (The Autostrad Road, El-Maadi, Cairo, Egypt) and a analysis, such as the impedance factor in the analysis, destination location (The Ring Road, New El-Marg, the start time, the period to reach the closet facilities, Cairo, Egypt). In this analysis, the road length has the number of facilities to find, and the directions of been chosen as the impedance factor, the start time of travel (from incident to the facility or from the travelling to be 3:00 PM which is the evening rush facility to the incident). Then, by using the network hour traffic on the road network in the Greater Cairo analyst extension solver, the closest facilities to the area. location of an incident can be found as shown in Figure 7. The directions window of the previous The distance of the route obtained from the shortest analysis is shown in Figure 8. route analysis represents the accumulated lengths of the road segments over which agents will travel. In a similar manner, the total time of the route obtained from the shortest route analysis represents the accumulated time in minutes for each route segment over which agents will travel. The shortest route results can be represented graphically as shown in Figure 10. Figure 6: The Best Route Directions Result Figure 8: The Closet Facilities Directions Result Figure 7: The Closet Facilities Analysis Result Figure 9: The Shortest Route Analysis Results Figure 11: The Best Route Analysis Results Figure 11 displays the best route between the same two locations. In this analysis, we have chosen the road’s travel time as the impedance factor, and this analysis was performed at the same time and over the 7 days of the week as the shortest route analysis. The best route results can be represented graphically as shown in Figure 12. We have repeated the two analyses for the same two locations in 7 days from Saturday to Friday, at the same time and calculated the total distance (in KM) and the average travel time (in Minutes) for the two obtained roads as shown in Table 3. Figure 12: The Best Route Analysis at 3:00 PM within the Week Days. Table 3: Times and Lengths of the Best and the Shortest Route Analyses Shortest Route Best Route Day Length Time Length Time Saturday 38.6 82 42.9 80 Sunday 38.6 240 42.9 204 Monday 38.6 330 42.9 206 Tuesday 38.6 164 42.9 144 Wednesday 38.6 197 42.9 156 Figure 10: The Shortest Route Analysis at 3:00 PM Thursday 38.6 315 42.9 300 within the Week Days. Friday 38.6 109 42.5 82 Avg Time 205.29 167.43 To give an evidence for the superiority of the best route on the shortest route, we have performed the previous analysis at different periods for each day in the week on a time slice of 120 minutes starting at 8:00 AM and ending at 12:00 AM for both the shortest route and the best route. We excluded the periods from 1:00 AM to 7:00 AM from the calculations as it will not give us any differences between the shortest route and the best route because in these periods there are no traffic jam on the road network. The average travel time in minutes for each analysis was calculated and recorded as shown in Table 4. Table 4: The Average Travel Times (in minutes) for both the Shortest and the Best Route Analysis Methods for each Time Slice. Shortest Difference Time Best Route Route (%) 8:00 AM 133 120 11 % 10:00 18 % 98 83 AM 12:00 PM 108 81 33 % Figure 13: Average Travel Time Comparison 2:00 PM 193 170 14 % between the Shortest and the Best Route Methods 4:00 PM 184 164 12 % 5 Conclusion and Future Work 6:00 PM 143 126 14 % In this paper, an enhanced GIS-based network 8:00 PM 105 93 13 % analysis was implemented and applied to the Greater 10:00 PM 92 81 14 % Cairo road network. It focuses on finding the best 12:00AM 92 54 70 % route between two locations on the road network and finding the nearest healthcare service providers to an incident location based on the travel time. Also, the The obtained results can be represented graphically proposed method integrates historical traffic data to as shown in Figure 13. The superiority percentage be used in the analysis, which in turn produces more (SP) is a measure for the preference of one alternative accurate results that are suitable for realistic road over another alternative. In our case, it gives an networks. The Dijkstra best routing algorithm built indication for the preference of the best route over the into the ARCGIS software is the best method for the shortest route. The superiority percentage for the best network analysis, especially in the crowded city such route travel time was calculated according to the as Cairo city. This algorithm can preserve the travel following formula: time with 20% to 22%, depending on the travel 𝟗 distances. In the future work, we suggest to use live 𝑺𝑹𝑻𝒊 traffic data when it is available instead of historical 𝑺𝑷 = [(( ) − 𝟏)/𝟗] ∗ 𝟏𝟎𝟎 𝑩𝑹𝑻𝒊 traffic data and consider other factors such as road 𝒊=𝟏 width, road state, road type, and time delay on the Such that: road to get realistic results. Also, we plan to enhance SP = Superiority Percentage the Dijkstra routing algorithm used by the ArcGIS network analysis extension to improve its SRT = Shortest Route Time performance. BRT = Best Route Time References Substituting the values of SRT and BRT from Table [1] Abdel Rahim Elhag Abdel Aziz Elhag, 4 in the previous formula, we get: RanyaFadlallaAbdalla ,Nagla Ali Gism ,Aisha Elhadi SP = 22 % Mohammed ,Salah EddeenKhidirSideeg, “Route Network Analysis in Khartoum City”, Journal of Which means that the best route travel time is much Engineering and Computer Science (JECS), Vol. 17, better than the shortest route travel time by 22%. No. 1, 2016, pp. 50-57. In emergency cases, it is essential to reach the [2] AmrapaliDabhade, Dr. K. V. Kale, Yogesh location of an incident as fast as possible to rescue Gedam, “Network Analysis for Finding Shortest Path people life. So, according to the superiority in Hospital Information System”, IJARCSSE, Vol.5, percentage, the best route is more suitable for being No.7, July 2015, pp. 618-623. used in emergency situations than the shortest route. [3] A. Gubara, A. Amasha, Z. Ahmed and S. El Ghazali, “Decision Support System Network Analysis for Emergency Applications”, Informatics and Systems (INFOS), 2014 9th International Conference on, Cairo, 2014, pp. ORDS-40-ORDS- 44. [4] Ni Kai, Zhang Yao-ting, Ma Yue-peng, “Shortest Path Analysis Based on Dijkstra's Algorithm in Emergency Response System”, TELKOMNIKA Indonesian Journal of Electrical Engineering, Vol.12, No.5, May 2014, pp. 3476-3482. [5] Anshul Bhagat, Nikhil Sharma, “GIS-Based Application for Emergency Preparedness and Management Accelerating Response System through GIS”, 14th Esri India User Conference 2013, December 2013, pp. 1-7. [6] Eric K. Forkuo and Jonathan A. Quaye-Ballard, “GIS Based Fire Emergency Response System”, International Journal of Remote Sensing and GIS, Vol.2, No.1, January 2013, pp. 32-40. [7] SuneetNaithani, Abhishek Choudhry, Sandeep Chauhan, “Decision Support System for Emergency Response”, European Scientific Journal, vol.2, No.3, NOV-DEC, 2013, pp. 680-687. [8] Dechuan Kong, Yunjuan Liang, Xiaoqin Ma, Lijun Zhang, “Improvement and Realization of Dijkstra Algorithm in GIS of Depot”, IEEE, 2011. [9]WikiVisually,Cairo”, http://wikivisually.com/wiki/Greater_Cairo /wiki_ph_id_16. [10]WorldAtlas. " Cairo Photos, Luxor PhotosEgypt", http://www.worldatlas.com/webimage/countrys/afric a/cairoegyptphotos.htm.