*Corresponding Author Email: fogunwolu@unilag.edu.ng; other Emails: asosimi@unilag.edu.ng; jjarbulani@yahoo.com; conyedikam@unilag.edu.ng PRINT ISSN 1119-8362 ELECTRONIC ISSN 2659-1502 J. Appl. Sci. Environ. Manage. Vol. 22 (12) 1941–1946 December 2018 Full-text Available Online at https://www.ajol.info/index.php/jasem http://ww.bioline.org.br/ja Optimal Routing for Automated Emergency Vehicle Response for Incident Intervention in a Traffic Network *OGUNWOLU, L; SOSIMI, A; JAGUN, O; ONYEDIKAM, C Department of Systems Engineering, Faculty of Engineering, University of Lagos, Nigeria *Corresponding Author Email: fogunwolu@unilag.edu.ng; other Emails: asosimi@unilag.edu.ng; jjarbulani@yahoo.com; conyedikam@unilag.edu.ng ABSTRACT: Congestion constitutes a major problem in modern urban traffic networks if not well managed. Its monstrous effects, on occasions, can paralyze a traffic network eating deep into the productive hours of commuters as well as vehicles and persons on essential services. Particularly affected are incidence-intervention vehicles such as emergency vehicles and fire-fighting vehicles. Whatever the cause of the congestion, its effect is counter-productive and an indication of an inefficient traffic network. This work, as presented in this paper, is concerned about the issue of traffic route management for emergency service (emergency vehicle) for which a delay of few minutes may cause tremendous loss of lives and properties. The route management scheme built for this purpose integrates information obtained from the use of Radio Frequency Signals for Traffic Light Preemption at Intersections in a Proteus Simulator environment and the use Arc GIS as a mode of routing the emergency vehicle from base to the incidence location, then to Health Facilities and from thence back to the emergency vehicle base in an optimal routing time. Traffic information are loaded into the Arc GIS environment which predicts the required tri-legged optimal routing and its duration using Dijkstra’s algorithm. Different scenarios of emergency vehicle, incidence and health facility locations were exploited using the scheme and compared with situations without their implementation. The proposed scheme outperforms the trial and error routing of emergency vehicles and can be embedded into traffic advisory system or as stand-alone emergency vehicle management system. DOI: https://dx.doi.org/10.4314/jasem.v22i12.12 Copyright: Copyright © 2018 Ogunwolu et al. This is an open access article distributed under the Creative Commons Attribution License (CCL), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Dates: Received: 19 August 2018; Revised: 26 November 2018; Accepted 12 December 2018 Keywords: GIS, Dijkstra’s algorithm, Facility Location, Emergency-Vehicle, Optimal Routing With the increase of city size, emergency rescue system is playing an important role in the safety of human life and social security. In many instances vehicles and hence users’ transit time within the network are negatively affected because of delays occasioned by traffic lock jams. In particular, in day to day life, an Emergency vehicle or a Fire vehicle may get stuck aggravating the precarious situation of individuals on board for treatment or early intervention at scenes where lives and properties may be saved. There exist various factors affecting the travel times of emergency vehicle (emergency vehicle). The inevitable factors are the traffic condition at different times of the day, random congestions (e.g. due to accidents). Traffic congestion is one of the most fundamental problems in large cities like Lagos. There is a positive connection between the delay of emergency vehicles and ratio of fatal or serious preventable incidences. These untoward losses can be minimized by deploying intelligent decision system and shortest path algorithms to optimize ambulance travel time to and from accidents scene to the nearest hospitals. The work presented here integrates optimal location of emergency vehicle base within predetermined service area, optimal routing based on closest service area of incidence and traffic signal pre- emption in a Proteus Simulator environment, using Arc GIS to route from the emergency vehicle base to the incidence spot to a health facility. Routing of emergency vehicle belongs to the class of dynamic routing in a network for which the principal routing concerns differ and vary over time and space. Concerns of dynamic vehicle routing in traffic network include routing based on the dynamics of goods routed (Goel and Gruhn, 2008; Gribkovskaia et. al., 2008; Hvattum et. al., 2007), services (Beaudry et. al. 2010 and Thomas, 2007), travel times (Tagmouti et. al., 2011; Gholami-Zanjani et. al., 2018 and Tlili et. al., 2017) and vehicle availability (Ghadiri and Banar, 2018 and Aringhieri et. al., 2017). Dynamic routing extrinsically based on service time routing has been sparse in literature (Pillac et. al., 2013) although such timing can be included in the general travel time Optimal Routing for Automated Emergency….. 1942 OGUNWOLU, L; SOSIMI, A; JAGUN, O; ONYEDIKAM, C consideration. Chime et. al. (2013) described the management of traffic congestion around a road intersection based on inputs being received from embedded traffic sensors on the road. The work reported that the system responds intelligently to variable traffic conditions on the road and decisions to improve traffic flow were made. It uses an in-vehicle remote controller that can override the proximate intersection signal timing system’s time distributions in order to give priority to emergency vehicles. Jaiswal et. al. (2013) proposed an idea of Radio-Frequency Identification (RFID) & Infrared (IR) technology to drive intelligent transportation and traffic control systems in relation to emergency vehicle routing. Lim et al. (2001) assumed that electro sensitive traffic lights had better efficiency than fixed preset traffic signal cycles because they were able to extend or shorten the signal cycle when the number of vehicles increases or decreases suddenly, In the work, traffic signal was optimized using fuzzy control. Geospatial information system (GIS) in emergency vehicles routing offers a worthy tool for network analysis visualization and management. The main idea of this paper is to find fastest path for emergency vehicle with minimal disruption of regular traffic flow using the ArcGIS and Proteus software on real life road network and traffic conditions and thus minifying loss of lives and properties in emergency situations. MATERIALS AND METHODS The routing system is composed mainly of 3 sub- systems: (1) Optimal Emergency Vehicle Base Location (2) Optimal Routing for Emergency vehicle (3) Traffic Light Signal Pre-emption Optimal Location of Service Areas and Emergency Vehicle Bases: Eti-Osa Local Government road network in Lagos was used as a test bed for the emergency vehicle routing scheme. The local government is a commercial and recreational hub in Lagos hosting very many health facilities and very good network of roads and a substantial number of signalized intersections. The available map showing the portion of Eti-Osa local Government road network used was properly digitized and imported into ARC GIS environment. For the optimal location of emergency vehicle facilities within the area of study, several service area analyses, closest facility solver analysis and the new location allocation analysis were carried out on the ARC GIS tool box to get the optimal strategic position of emergency vehicle units within the area under study. With ArcGIS Network Analyst, service areas around any location on a network can be found. A network service area is a region that encompasses all accessible streets (that is, streets that are within specified travel time impedance). For instance, the 5-minute service area for a point on a network includes all the health facilities that can be reached within five minutes from that incident point. The Service areas created by Network Analyst also help evaluate accessibility. Concentric service areas show how accessibility varies with impedance. Once service areas are created, one can use them to identify how many people, how much land, or quantities of anything else within the neighborhood or region that can be catered for within that area. It is on this basis that emergency vehicles were optimally positioned on the map of the area of implementation. The primary goal is to contribute to the reduction of response time within the network. Emergency vehicle Routing System: Within ARC GIS Dijkstra's Algorithm, one the most efficient algorithms for solving the shortest-path problem can be implemented. In a network, it is frequently desired to find the shortest path between two nodes. The weights attached to the edges can be used to represent quantities such as distances, costs or times. For the purpose of this work time is used as the impedance because the shortest time for the vehicle to carry out the emergency services is desired. The Dijkstra’s Algorithm: Let �� be the shortest distance from source node 1 to node �, Define ��� (≥ 0) as the length of arc (�, �) Then the algorithm defines the label for an immediately succeeding node j as ��, �� = �� + ��� , ��, ��� ≥ 0 The label for the starting node [0, -], indicating that the node has no predecessor. Step 0: Label the source node as permanent Step i: (a) Compute �� + ��� , �� for each node j that can be reached from node i, provided j is not permanently labeled. If node j is labeled with ��, ��, through another node k and if �� + ��� < �� replace ��, �� with �� + ��� , �� If all nodes have permanent labels, stop. Break ties arbitrarily. Repeat step � until all nodes covered. Traffic Light Signal Pre-Emption System: In the proposed system, when the control centre is alerted of an incident with the incident location coordinates, a message is instantly generated with the information to the most proximate emergency vehicle base to the Optimal Routing for Automated Emergency….. 1943 OGUNWOLU, L; SOSIMI, A; JAGUN, O; ONYEDIKAM, C incident scene. An initial and optimal route is also planned and communicated to the emergency vehicle base from the Control Centre. The emergency vehicle is optimally routed and also communicates with each traffic light signal on its path to avoid delay of any form. The signal to Traffic signal section is transmitted through Radio Frequency (RF) communication. As the emergency vehicle reaches the proximity of a traffic light signal (about 100 metres), the RF transmitter on the vehicle preempts the signal light in favour of the directions of approach and movement of the emergency vehicle (Chime et. al., 2013). Whenever the emergency vehicle reaches near the traffic signal (approximately 100m), the traffic signal is made to be green through RF communication. This aspect of the project is built around the PIC16F877A Microcontroller chip, written and compiled in Micro C Pro and simulated using Proteus 8 Professional software. The model depicts a four-way traffic light intersection model. The traffic light was modeled to have 2 separate circuit boards with a microcontroller (PIC16F876A) each. One board is for transmitter while the other is for the receiver. An RF transmitters and receivers of 315MHz were used in the simulation. The transmitter modules take serial input and transmits these signals through RF. The RF Receiver module receives the modulated RF signal and demodulates it. Fig 1: Emergency vehicle communicating with Traffic Light Signal System Implementation: Emergency Vehicle Unit: Whenever information is sent to the emergency vehicle from a control center, the emergency vehicle is optimally routed using the feature provided by Network Analyst on arc GIS based on Dijkstra’s. Once the emergency vehicle gets to the vicinity of a traffic light signal, depending on the wavelength of the RF transmitter used, the emergency vehicle sends a signal to the traffic light to give way, making all other lanes red except along the approach and route of the emergency vehicle through the intersection. Traffic Light Unit: Once the receiver module on the traffic light received information from an incoming emergency vehicle, it temporarily shuts down the pre- timed response and give tolerance to the emergency vehicle to pass; afterwards normal pre-set operation continues. In this way the emergency vehicle is not delayed at any point. RESULTS AND DISCUSSION In the three-legged routing of the emergency vehicle, three important aspects of the routing procedure were carried out: (1) Closest Facility Analysis, (2) Routes Encountered with a Barrier (3) Integration of Traffic Light Preemption into Routing System. Figure 2 illustrates the three-legged emergency vehicle routing undertaken in this work. Closest Facility Analysis: Finding the closest hospital and the closest emergency vehicle unit to an incident or accident point are all examples of closest facility problems. While finding closest facilities, the number of such facilities and the direction of travel to and from the facility is specified. Once the closest facilities are found, the best route to and from them is displayed within Arc GIS environment and the best of all feasible solutions with the travel costs is obtained. Routes Encountered with a Barrier: A barrier (for example road blockage due to fallen trees or electrical poles or congestion) is placed on the route. Scenario 1 in Fig. 4 depicts a particular road route travelled and it is noticed the time taken to travel from point 1 to point 2 takes 17 minutes without blockage.. Integrating Traffic Light Preemption into Routing System: To further reduce the response time of the emergency vehicle responding to incidents, this paper integrates traffic light preemption into the optimal routing system. Finding the best or fastest route to a location does not necessarily mean it is done at optimal fashion, because there may congestions on that route or bottleneck traffic which are caused by caused inefficient traffic light signal. Therefore, emergency vehicles need right of way whenever they encounter intersection traffic signals. In order to simulate on ArcMap 10.2, traffic light intersections were given a delay 2 minutes when there was no traffic light preemption meaning normal operation of the traffic light and zero minutes when there is traffic light preemption. Optimal Routing for Automated Emergency….. 1944 OGUNWOLU, L; SOSIMI, A; JAGUN, O; ONYEDIKAM, C Fig 2: Illustration of the 3-Legged Emergency Vehicle Routing: Fig 3: Closest Emergency vehicle to an Incident Point Fig 4: Emergency vehicle route without barrier or congestion Scenario 2 in Fig. 5 illustrates the road route travelled faced with a blockage and it is noticed a new route is taken. Instead of the previous time of 17 minutes it now takes 19 minutes to travel from point 1 to point 2. Optimal Routing for Automated Emergency….. 1945 OGUNWOLU, L; SOSIMI, A; JAGUN, O; ONYEDIKAM, C Fig 5: Emergency vehicle route with barrier or congestion Fig 6: Map showing Traffic Light Intersection with Delay Fig 7: Map showing Traffic Light Intersection with Delay Optimal Routing for Automated Emergency….. 1946 OGUNWOLU, L; SOSIMI, A; JAGUN, O; ONYEDIKAM, C Conclusion: The optimal routing for automated emergency vehicle response for incident intervention has been successfully modelled and simulated using the ArcGIS and Proteus software on real life road network and traffic conditions. The method has considerably reduced the response time of emergency vehicle to a great extent, thereby offering better opportunities to save more lives and preventing loss of vital properties. Historical traffic data were used in this simulation. The full potential of this system of routing emergency vehicles can be realized when real life traffic data are integrated into the system. REFERENCES Aringhieri, R; Bruni, ME., Khodaparasti, S; Van Essen, J T. (2017). Emergency medical services and beyond: Addressing new challenges through a wide literature review. Computers & Operations Res. 78, 349-368. Beaudry, A; Laporte, G; Melo, T; Nickel, S (2010). Dynamic transportation of patients in hospitals. OR spectrum, 32(1), 77-107. Chime, C; Bakare, T; Talabi, O (2013). Design And Construction Of A Prototype Prioritized Actuated Road Traffic Control System. University of Lagos, Systems Engineering Students’ Project. Ghadiri Nejad, M; Banar, M (2018). Emergency response time minimization by incorporating ground and aerial transportation. Annals of Optimization Theory and Practice, 1(1), 43-57. Gholami-Zanjani, SM; Pishvaee, MS; Torabi, SA (2018). OR Models for Emergency Medical Service (EMS) Management. In Operations Research Applications in Health Care Management (pp. 395-421). Springer, Cham. Goel, A; Gruhn, V (2008). A general vehicle routing problem. European J. Operational Res. 191(3), 650-660. Gribkovskaia, I; Laporte, G; Shlopak, A (2008). A Tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms. J. Operational Res. Soc. 59(11), 1449-1459. Hvattum, LM; Løkketangen, A; Laporte, G (2007). A branch‐and‐regret heuristic for stochastic and dynamic vehicle routing problems. Networks: An Inter. J. 49(4), 330-340. Jaiswal, S; Agarwal, T; Singh, A (2013). Lakshita: Intelligent traffic control unit. Int. J. Electr. Electron. (ISSN NO.(Online): 27-2626 and Computer Engineering 2, 2, 6-72. Lim, G; Kang, J; Hong, Y (2001). The optimization of traffic signal light using artificial intelligence. In Fuzzy Systems, 2001. The 10th IEEE International Conference on (Vol. 3, pp. 1279- 1282). IEEE. Pillac, V; Gendreau, M; Guéret, C; Medaglia, AL (2013). A review of dynamic vehicle routing problems. European J. Operational Res. 225(1), 1- 11. Tagmouti, M; Gendreau, M; Potvin, JY (2011). A dynamic capacitated arc routing problem with time-dependent service costs. Transportation Research Part C: Emerging Technologies, 19(1), 20-28. Thomas, BW (2007). Waiting strategies for anticipating service requests from known customer locations. Transportation Sci. 41(3), 319-331. Tlili, T; Harzi, M; Krichen, S (2017). Swarm-based approach for solving the ambulance routing problem. Procedia Computer Sci. 112, 350-357.