# Evaluation of Using Genetic Algorithm and ArcGIS for Determining the Optimal-Time Path in the Optimization of Vehicle Routing Applications

Authors: Da’ad Ahmad Albalawneh; Mohamad Afendee Mohamed
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Transportation is regarded as one of the most important issues currently being researched; this issue needs the search for approaches or processes that might lessen many contemporary traffic concerns. Congestion, pollution, and accidents have escalated lately, negatively impacting urban environments, economic development, and citizens’ lifestyles. The rise of illnesses and epidemics throughout the world, such as COVID-19, has created an urgent need to find the best way to save people’s lives. The vehicle routing problem (VRP) is a well-known moniker for improving transportation systems and is regarded as one of the ancient and contemporary difficulties in route planning applications. One of the main tasks of VRP is serving many customers by determining the optimal route from an initial point to a destination on a real-time road map. The best route is not necessarily the shortest-distance route, but, in emergency cases, it is the route that takes the least fitness cost (time) and the fastest way to arrive. This paper aims to provide an adaptive genetic algorithm (GA) to determine the optimal time route, taking into account the factors that influence the vehicle arrival time and cause delays. In addition, the Network Analyst tool in ArcGIS is used to determine the optimal route using real-time map based on the user’s preferences and suggest the best one. Experimental results indicate that the performance of GA is mainly determined by an efficient representation, evaluation of fitness function, and other factors such as population size and selection method.


---

## Body

## 1. Introduction

Transportation problems, which many countries have faced, have been considered vitally significant in the last few decades; these problems necessitate a search for new techniques or alternatives that could determine the shortest time routes between any two locations. The vehicle routing problem (VRP) appeared for the first time in 1959 [1] to reduce the total route cost on continuously updated road maps. Several situations, particularly emergencies, require developing such techniques because the shortest-distance path sometimes is insufficient to save valuable human lives; the shortest-time route is optimum.Two distinct types of VRP have been extensively explored individually, while appearing to be the same or overlapping at times due to mutual interests in network-based optimization models and techniques. First, a dynamic VRP that deals with dynamic road networks is a well-known and extensively studied class. Several dynamic and changeable characteristics, including traffic flow level, unanticipated occurrences, and weather conditions, impact such networks. The second type of VRP is the timetabled or scheduled VRP, which is concerned with public transportation and services involving the conveyance of passengers, such as buses, and operates primarily on regular timetables and trip schedules for public use.This paper proposes a newly developed GA applied on a weighted directed graph representing a real-time road network of the study area, Al-Salt city in Jordan. An integrated ArcGIS Network Analyst tool has been used to visually establish the optimal time route from a source point to the destination and suggest potential routes based on user preferences.GA consists of consecutive procedures that attempt to find the best solutions to problems when it is possible to define the criteria used to evaluate and estimate the best solutions.The proposed GA finds the shortest-time route with fitness function, which calculates the time influenced by different factors. The fitness function uses static and dynamic parameters to calculate each path’s fitness value. The fixed parameters tend to be almost constant through time as follows:(1)
Route distance: the distance is the essential criterion for the shortest path problem; GA uses the road length as weight in the directed graph for obtaining the best route.(2)
Easiness of driving: the safer and more comfortable route is also a driver preference criterion. The proposed GA should find a vehicle route that achieves the driver requests based on this criterion; furthermore, the determined solution should avoid influencing factors like traffic signals.(3)
Streets conditions: these include street type, width, street topology, and street regulations (e.g., allowed velocity limit); the street conditions can be collected using cameras, sensors, car navigation system, and geodatabase of the real-time map. The proposed technique obtains the above parameters from the geodatabase of Al-Salt downtown map.The dynamic factors, such as residential density, are relatively variable throughout time (low, medium, and high density). Travel time reflects the time spent travelling by automobile, such as rush hour in the morning from 6 a.m. to 10 a.m. The residential density in a given region may be calculated using real-time map data and then updated on a regular basis utilizing cameras and sensors, particularly during peak hours.


## 2. Related Work

Several researchers have made a considerable effort to optimize transportation systems by improving and developing various algorithms to solve VRP problems in route planning systems. Figure1 shows the most popular algorithms for determining the optimal route in VRP, and they are classified as follows.Figure 1
Classification of route planning algorithms.


### 2.1. Exact Algorithms

A comparative study has been conducted for different VRP algorithms to evaluate their effectiveness in real-time routing applications and simulate the performance of Dijkstra’s algorithm (DA) among them [2]. Position parameter [3, 4] was added to DA using the global positioning system (GPS). Once GPS retrieves the current position, DA calculates the distance from the source to every node in the graph [5, 6].The researchers in [7] improved the DA; moreover, they have examined the weaknesses of other shortest path algorithms. Dijkstra algorithm was also applied in public transport planning system for Bangkok Metropolitan Area for Buses as in [8], intelligent bus transportation system in Philippines [9], shortest-distance bus routes in Yangon city [10], and parking system in Malaysia [11]. Other research works [12, 13] used breadth-first traversal (BFT) to improve the efficiency of DA in the searching process for the best solution for VRP.


### 2.2. Heuristic Algorithms

A∗ search algorithm has been studied and used to find the point-to-point shortest route using a weighted directed graph [14]. Another research [15] shows that the execution time of DA is lower than the A∗ search algorithm when a large number of nodes are selected. A public transportation system of Yangon’s downtown area applied the A∗ approach in finding the shortest route [16]. The research in [17] has applied the branch-and-bound algorithm on the cost function f(x), while the branch-and-cut algorithm was used in [18, 19] to solve the vehicle assignment problem and the two-echelon vehicle routing problem, respectively.


### 2.3. Metaheuristic Algorithms

GA is an evolutionary technique developed for the first time by Holland et al. in 1975 [20]. GA always begins with an initial population of randomly selected chromosomes; each chromosome represents a potential solution containing a combination of genes [21].GA commonly uses one crossover and one mutation operator to solve the problem and determine a new optimal solution, but researchers in [11] defined one crossover and three mutation operators to find the optimal path. Depending on the experimental results, the algorithm was quick, prosperous, and stable and had a good convergence with high efficiency in determining the shortest emergency route [22]. Variable-length chromosomes with string type are proposed in [23].When compared to other recent metaheuristics, GA offers a wide range of applications, including a vehicle routing problem (VRP) combining time frames [24–30] and a school bus routing issue [31–33]. A route guiding system used GA in a mobile application to determine the quickest driving time for Ankara’s traffic network [34].Several metaheuristic algorithms are also applied to solve VRP problem like Ant Colony Optimization (ACO) as in [35–38], Tabu Search in [39–43], and Particle Swarm Optimization (PSO) in [44]. Figure 1 summarizes the main three approaches, exact, heuristic, and metaheuristic algorithms, applied in VRP using real-time maps.Many studies have demonstrated the effectiveness and importance of GIS in optimizing transportation systems and determining the most fitting routes for vehicles.The ArcGIS Network Analyst tool has recently been used to optimize several route planning applications. The researchers in [45, 46] have used GIS Network Analyst to optimize the solid waste management field. In [47], the authors planned to provide information about tourist attractions in Bandung and create a tourism-specific mass transit route. Based on a network-based spatial analysis of a GIS-based map, the study in [48] uses Dijkstra’s algorithm to identify the shortest-distance route.This study uses an integrated Network Analyst tool with a GA approach for vehicle routing optimization to determine a multiobjective optimal route based on user preferences. Generally, GA works well in problems with a huge solution space, long search times, and complex fitness functions. Furthermore, it performs well and gives better results when the function is discontinuous and noisy or has many local optimums. According to this study, GA becomes more complex when there are a considerable number of nodes in the real-time road network because unlimited-length chromosomes are created.


## 2.1. Exact Algorithms

A comparative study has been conducted for different VRP algorithms to evaluate their effectiveness in real-time routing applications and simulate the performance of Dijkstra’s algorithm (DA) among them [2]. Position parameter [3, 4] was added to DA using the global positioning system (GPS). Once GPS retrieves the current position, DA calculates the distance from the source to every node in the graph [5, 6].The researchers in [7] improved the DA; moreover, they have examined the weaknesses of other shortest path algorithms. Dijkstra algorithm was also applied in public transport planning system for Bangkok Metropolitan Area for Buses as in [8], intelligent bus transportation system in Philippines [9], shortest-distance bus routes in Yangon city [10], and parking system in Malaysia [11]. Other research works [12, 13] used breadth-first traversal (BFT) to improve the efficiency of DA in the searching process for the best solution for VRP.


## 2.2. Heuristic Algorithms

A∗ search algorithm has been studied and used to find the point-to-point shortest route using a weighted directed graph [14]. Another research [15] shows that the execution time of DA is lower than the A∗ search algorithm when a large number of nodes are selected. A public transportation system of Yangon’s downtown area applied the A∗ approach in finding the shortest route [16]. The research in [17] has applied the branch-and-bound algorithm on the cost function f(x), while the branch-and-cut algorithm was used in [18, 19] to solve the vehicle assignment problem and the two-echelon vehicle routing problem, respectively.


## 2.3. Metaheuristic Algorithms

GA is an evolutionary technique developed for the first time by Holland et al. in 1975 [20]. GA always begins with an initial population of randomly selected chromosomes; each chromosome represents a potential solution containing a combination of genes [21].GA commonly uses one crossover and one mutation operator to solve the problem and determine a new optimal solution, but researchers in [11] defined one crossover and three mutation operators to find the optimal path. Depending on the experimental results, the algorithm was quick, prosperous, and stable and had a good convergence with high efficiency in determining the shortest emergency route [22]. Variable-length chromosomes with string type are proposed in [23].When compared to other recent metaheuristics, GA offers a wide range of applications, including a vehicle routing problem (VRP) combining time frames [24–30] and a school bus routing issue [31–33]. A route guiding system used GA in a mobile application to determine the quickest driving time for Ankara’s traffic network [34].Several metaheuristic algorithms are also applied to solve VRP problem like Ant Colony Optimization (ACO) as in [35–38], Tabu Search in [39–43], and Particle Swarm Optimization (PSO) in [44]. Figure 1 summarizes the main three approaches, exact, heuristic, and metaheuristic algorithms, applied in VRP using real-time maps.Many studies have demonstrated the effectiveness and importance of GIS in optimizing transportation systems and determining the most fitting routes for vehicles.The ArcGIS Network Analyst tool has recently been used to optimize several route planning applications. The researchers in [45, 46] have used GIS Network Analyst to optimize the solid waste management field. In [47], the authors planned to provide information about tourist attractions in Bandung and create a tourism-specific mass transit route. Based on a network-based spatial analysis of a GIS-based map, the study in [48] uses Dijkstra’s algorithm to identify the shortest-distance route.This study uses an integrated Network Analyst tool with a GA approach for vehicle routing optimization to determine a multiobjective optimal route based on user preferences. Generally, GA works well in problems with a huge solution space, long search times, and complex fitness functions. Furthermore, it performs well and gives better results when the function is discontinuous and noisy or has many local optimums. According to this study, GA becomes more complex when there are a considerable number of nodes in the real-time road network because unlimited-length chromosomes are created.


## 3. Study Area

Al-Salt city is one of the ancient and densely populated cities in Jordan. The city is located about 30 kilometers northwest of Amman, the capital city of Jordan, between longitude (35° 43′ 30″) east and latitude (32° 02′ 30″) north, at the height of 795 to 1,110 meters above sea level.The study area represents road networks in the downtown of Al-Salt city; the greater municipality of Al-Salt provided the study with real-time maps and the road networks for the study area in cooperation with Al-Balqa’ Applied University, which provided the study with the required equipment and tools used for data collection.The streets in the city of Al-Salt represent 4% of Jordan’s total streets, including secondary and main streets. According to the road classification law at the Ministry of Public Works, Table1 shows the types and lengths of roads in Al-Salt city in 2018 [49].Table 1
Classification for the main types of roads in study area.
Type of roadDistance (km)Percentage (%)Main road216.3128.40By road (secondary)415.6254.66Asphalt (track)128.5116.94Total760.44100The roads were classified according to the width of each road as follows:(i)
Main road: the width of the road is 8 m or more.(ii)
By road: the width of the road is 6 m up to less than 8 m.(iii)
Track road: the width of the road is 3 m up to 6 m.Studying the road networks is one of the critical fields in transportation systems; it combines the spatial relation of the road networks with their characteristics then analyzes them according to space. Figures2 and 3 show satellite images of the study area with the associated digitized road networks.Figure 2
Real-time road networks of study area.Figure 3
Satellite aerial photo of study area.


## 4. Methodology

Photogrammetry refers to the process of measuring and interpreting images in order to extract data needed for geospatial applications, which is often acquired by satellites and airplanes.The key tool in this case study is ArcGIS. It is an ESRI-developed geographic information system (GIS) for dealing with maps and geographical information. It provides a framework for making maps, assembling geographic data, evaluating mapped data, and integrating maps with geospatial databases in a variety of applications [50]. Figure 4 depicts the methods for producing the study map to be combined and used with GA to discover the best-time route.Figure 4
Procedures of georeferencing the study area.


### 4.1. GPS Field Survey to Get the Ground Control Points (GCPs)

The next step is to take the GPS data and postprocess it by importing raw data (the data from the GPS receivers) and exporting the final local grid coordinates and other coordinates. It is composed of the points BAU, reference, az, bs, seha, sew, hassan, hesba, salalem, and fatma. Only two receivers were used to measure the entire network.The local grid coordinates of the points BAU, reference, az, bs, seha, sew, hassan, hesba, salalem, and fatma are derived and known as UTM ZONE 36 North projection and WGS84 Ellipsoid. Figure5 displays the local grid coordinates for the previous selected points.Figure 5
Local grid coordinates of the study area.


### 4.2. Process the GPS Field Data by Leica SKI-Pro Software to Get Values of GCPs

Leica’s SKI-Pro software includes a comprehensive set of programs for GPS surveying with postprocessing capabilities and real-time support. In SKI-Pro, GPS data that belong together can be collected and stored as shown in Figure6.Figure 6
Distribution and adjustment of GCPs.


### 4.3. Process GCPs Using Leica Photogrammetry Suite (LPS) to Construct the Digital Elevation Model (DEM) and Orthophotos

In this study, Leica Photogrammetry Suite (LPS) is applied to find the overlap area between two images, also known as triangulation, by rectifying images to determine orthophoto as well as extracting DTMs and contour maps for use in ArcGIS. Figures7 and 8 display the locations of GCPs and determine their type and usage.Figure 7
Location of GCPS on study map.Figure 8
The type and usage of GCPs.


### 4.4. Using ArcGIS to Construct a Geodatabase and Feature Classes to Represent the Real-World Entities of the Study Area

The process of digitizing GIS data is to convert scanned images or hard copies of geographic data into vector maps by tracing their features. It is one of the ways to ensure that real-world spatial data is accessible. The digitization process involves capturing the underlying map features as coordinates, either as a point, line, or polygon. The task is accomplished by creating layers in ArcCatalog and then adding features to them in ArcMap. Several layers have been created in this stage for the study area in order to use them for retrieving the required spatial data by GA to calculate the optimal time route, as illustrated in Figure9.Figure 9
Digitized layers view concerning the rectified orthophoto.


## 4.1. GPS Field Survey to Get the Ground Control Points (GCPs)

The next step is to take the GPS data and postprocess it by importing raw data (the data from the GPS receivers) and exporting the final local grid coordinates and other coordinates. It is composed of the points BAU, reference, az, bs, seha, sew, hassan, hesba, salalem, and fatma. Only two receivers were used to measure the entire network.The local grid coordinates of the points BAU, reference, az, bs, seha, sew, hassan, hesba, salalem, and fatma are derived and known as UTM ZONE 36 North projection and WGS84 Ellipsoid. Figure5 displays the local grid coordinates for the previous selected points.Figure 5
Local grid coordinates of the study area.


## 4.2. Process the GPS Field Data by Leica SKI-Pro Software to Get Values of GCPs

Leica’s SKI-Pro software includes a comprehensive set of programs for GPS surveying with postprocessing capabilities and real-time support. In SKI-Pro, GPS data that belong together can be collected and stored as shown in Figure6.Figure 6
Distribution and adjustment of GCPs.


## 4.3. Process GCPs Using Leica Photogrammetry Suite (LPS) to Construct the Digital Elevation Model (DEM) and Orthophotos

In this study, Leica Photogrammetry Suite (LPS) is applied to find the overlap area between two images, also known as triangulation, by rectifying images to determine orthophoto as well as extracting DTMs and contour maps for use in ArcGIS. Figures7 and 8 display the locations of GCPs and determine their type and usage.Figure 7
Location of GCPS on study map.Figure 8
The type and usage of GCPs.


## 4.4. Using ArcGIS to Construct a Geodatabase and Feature Classes to Represent the Real-World Entities of the Study Area

The process of digitizing GIS data is to convert scanned images or hard copies of geographic data into vector maps by tracing their features. It is one of the ways to ensure that real-world spatial data is accessible. The digitization process involves capturing the underlying map features as coordinates, either as a point, line, or polygon. The task is accomplished by creating layers in ArcCatalog and then adding features to them in ArcMap. Several layers have been created in this stage for the study area in order to use them for retrieving the required spatial data by GA to calculate the optimal time route, as illustrated in Figure9.Figure 9
Digitized layers view concerning the rectified orthophoto.


## 5. Proposed GA for Route Planning Systems

The most critical and challenging task for developing GA to this problem is how to encode a route in a weighted directed graph into a chromosome. This paper proposes a new GA for solving the shortest-time routing problem and determining the shortest-time route (optimal). Variable-length individuals (chromosomes) have been used; the genes in each chromosome represent nodes included in a path between a selected pair consisting of source (start) and destination (end) positions, and a priority-based encoding procedure is followed, which can probably represent all feasible routes in a graph.


### 5.1. Graph Design

In an implicit way, a road network can be represented as a directed graphG = (V, E), where N is a set of vertices (nodes) and E is a set of edges (arcs). The ID of a node in the graph has given a unique positive integer value from 1,…, N, where N is the number of nodes as in Figure 10.Figure 10
Directed graph for road network.Each chromosome is created to represent a solution for the shortest-time routing problem, and it should not include duplicated nodes. Source and destination nodes are indicated byF and E, respectively, and each link (i, j) has associated with link connection indicator expressed by Iij, which takes a part and plays an important role in chromosome production and encoding via providing connection information; this information describes whether the link from node i to node j is included in the routing path or not.The connection information of the nodes with each other can be determined with an adjacency matrix as follows:(1)Iij=1,ifiandjare connectedadjacent,0,otherwise..An adjacency matrix in Figure11 is used to ensure the connectivity of the randomly selected pair of vertices; the length of the edge is considered as the weight of that edge in the graph. The adjacency matrix illustrates that all the diagonal elements of Iij must equal zero, where the source and destination nodes are the same (S = E). The minimum potential value of the chromosome length is equal to the total number of nodes in the whole graph, because, in some worst cases, the shortest path may contain the total number of nodes. The gene length of a graph with N number of nodes is equal to N or more.Figure 11
Adjacency matrix for road networks.


### 5.2. Chromosome Representation (Encoding)

Chromosome length is variable, but it must not increase beyond the maximum feasible size, which, in the worst case, is the total number of nodes in the network since the chromosome length does not require more than the total number of nodes in order to create a routing path. Figure12 shows the chromosome representation where the genes are selected randomly from source node 1 to destination node 4 based on the topological information database of the network; each chromosome should indicate a feasible route for the proposed GA.Figure 12
Chromosome representation procedure.


### 5.3. Initial Population

The initial population consists of chromosomes (individuals), the lengths of which are variable. The first gene of each chromosome is the first node (S) and the last gene is the target node (E); if the path is between S, a new gene is produced; typically, all the chromosomes in the first generation are produced by this approach.The large population is practically useful, but it requires unnecessary costs in both capacity and time. As expected, choosing a sufficient population size is critical for efficiency demands; for that reason, many researchers used the heuristic approaches for producing the chromosome for the initial population instead of the random method.


### 5.4. Fitness Function

Table2 contains the cost attributes or parameters used in determining the fitness value for each segment of the road path and affects the result obtained.Table 2
Attributes table for road network segments.
Segment IDSegment description (S, E)Distance (m)Allowable velocity limits (km/h)S1(1, 2)50060S2(2, 1)50060S3(1, 3)50060S4(3, 1)60060S5(3, 5)30040S6(5, 3)40040S7(4, 5)20040S8(5, 4)20040S9(2, 4)80040S10(4, 2)80040S11(2, 3)30060Based on these criteria, the fitness cost for the candidate road pathways (chromosomes) from source node 1 to destination node 4 could be computed, and the optimum option with the least driving time would be chosen. Figure13 depicts an actual value for each route in the research area’s road network. Equations (2) to (7) define the fitness function of the GA while taking into account all of the associated parameters as follows:(2)T1ij=∑n=ijdisijVij.Figure 13
Attribute table of streets layer in ArcMap.Fij is the cost value from i to j, where i ≠ j.(3)T1ij=∑n=ij2disijVij−VRijin rush hours,where disij is the length of segment between i and j and Vij represents the allowable velocity limits between i and j.Then,(4)Dy=∑LA×100,(5)T2ij=∑n=ijDyVij,(6)T3ij=T1ij−T2ij,where(7)T4ij=T3ij−NOTL∗0.5minimum,(8)Fij=∑n=ijTij.Tij is the time required to travel between i and j. Dy is the density of the roads network. ∑L is the total length of the network roads. A is the area of the study region (square kilometer). NOTL is the number of traffic light signals. VRij is the estimated vehicle’s speed in rush hours.


### 5.5. Selection and Crossover Procedures

The tournament selection method is the type of selection used for the proposed GA, two individuals are selected, and the more appropriate individual is chosen compared to the fitness of the other chromosomes in the population, but the corresponding individual should not be selected twice as a parent in the population.In 1983, Birndlerproposed a tournament selection technique in which individuals, in pairs, were selected according to their fitness values from a stochastic roulette wheel. Selection of the individuals with the highest fitness values leads to the next generation.The crossover between the two most fitting parents chosen by the selection increases the probability of generating offspring having robust characteristics [51]. The arithmetic crossover is used in this case as follows:(9)Xi=δ.Xi1+1−δ.Xi2,where δε0,1.According to the previous equation, the new offspring generated by the arithmetic crossover are(10)Pi=δ.Xi+1−δYi,qi=δ.Xi+1−δYi.Figure14 shows an illustrative example of the proposed crossover procedure.Figure 14
Crossover procedure.


### 5.6. Mutation Procedure

Mutation procedure leads to a bit of increment in the probability of producing the infeasible chromosomes; it keeps the diversity in the population solutions. Figure15 illustrates a comprehensive description for the proposed mutation procedure in GA.Figure 15
Mutation procedure.


### 5.7. Reorganizing (Repairing) Function

GA is developed based on ideas inspired by evolutionary mechanisms, where successive generations of solutions become more and more efficient until an optimal or nearly optimal set of alternatives are reached.Loops in the shortest-time route routing issue can be produced during the crossover and mutation procedures, resulting in infeasible chromosomes. There are two primary approaches to dealing with infeasible chromosomes. The first is to eliminate them, and the second is to reorganize a chromosome with a repair function. The first is to apply a penalty, and the second is to reorganize a chromosome by removing and deleting the loop; in this work, the rearranging function is utilized to detect and eliminate the loops without incurring any additional capacity or time expenses. Figure16 shows a description of the proposed reorganizing function with an example.Figure 16
Repair procedure.Algorithm 1 displays a pseudocode showing how the algorithm finds the minimum travel time route for the provided graph from start node to the end node.Algorithm 1: Pseudocode for GA implementation.
(1)
►Input: Graph (V, E)(2)
fNode/∗ initial node in the route ∗/(3)
dNode/∗ destination node ∗/(4)
►Output: Ch[]/∗array of Genes represents the optimal time route ∗/(5)
Define: Adj [][]/∗ 0, 1 Check nodes adjacency in the graph ∗/(6)
Ch [0] ← fNode(7)
Pz ← Population size(8)
Cr ← Crossover rate(9)
Mr ← Mutatino rate(10)
for eachi, j where j = PZ(11)
Create_Chromosome (fNode, dNode)(12)
F ← Calculate Fitness Value for each chromosome(13)
End for(14)
Count ← 0(15)
Gen ← 1(16)
While Count ≤ 10 do(17)
Ch1, Ch2 ← RouletteWheel _Selection ()(18)
Ch1∗,Ch2∗ ← Crossover (Ch1, Ch2)(19)
Ch3 ← Mutation (Ch1∗)(20)
Ch4 ← Mutation (Ch2∗)(21)
F1 ← Fitness Value for the first chromosome(22)
F2 ← Fitness Value for the second chromosome(23)
Fm ← Minimum Value of fitness function(24)
If Gen > 1 && Fm (Gen-1) = = Fm (Gen-2)(25)
Count ++(26)
if count > 10(27)
Break(28)
else(29)
count = 0(30)
End If(31)
End while(32)
Gen ++(33)
Go to 17


## 5.1. Graph Design

In an implicit way, a road network can be represented as a directed graphG = (V, E), where N is a set of vertices (nodes) and E is a set of edges (arcs). The ID of a node in the graph has given a unique positive integer value from 1,…, N, where N is the number of nodes as in Figure 10.Figure 10
Directed graph for road network.Each chromosome is created to represent a solution for the shortest-time routing problem, and it should not include duplicated nodes. Source and destination nodes are indicated byF and E, respectively, and each link (i, j) has associated with link connection indicator expressed by Iij, which takes a part and plays an important role in chromosome production and encoding via providing connection information; this information describes whether the link from node i to node j is included in the routing path or not.The connection information of the nodes with each other can be determined with an adjacency matrix as follows:(1)Iij=1,ifiandjare connectedadjacent,0,otherwise..An adjacency matrix in Figure11 is used to ensure the connectivity of the randomly selected pair of vertices; the length of the edge is considered as the weight of that edge in the graph. The adjacency matrix illustrates that all the diagonal elements of Iij must equal zero, where the source and destination nodes are the same (S = E). The minimum potential value of the chromosome length is equal to the total number of nodes in the whole graph, because, in some worst cases, the shortest path may contain the total number of nodes. The gene length of a graph with N number of nodes is equal to N or more.Figure 11
Adjacency matrix for road networks.


## 5.2. Chromosome Representation (Encoding)

Chromosome length is variable, but it must not increase beyond the maximum feasible size, which, in the worst case, is the total number of nodes in the network since the chromosome length does not require more than the total number of nodes in order to create a routing path. Figure12 shows the chromosome representation where the genes are selected randomly from source node 1 to destination node 4 based on the topological information database of the network; each chromosome should indicate a feasible route for the proposed GA.Figure 12
Chromosome representation procedure.


## 5.3. Initial Population

The initial population consists of chromosomes (individuals), the lengths of which are variable. The first gene of each chromosome is the first node (S) and the last gene is the target node (E); if the path is between S, a new gene is produced; typically, all the chromosomes in the first generation are produced by this approach.The large population is practically useful, but it requires unnecessary costs in both capacity and time. As expected, choosing a sufficient population size is critical for efficiency demands; for that reason, many researchers used the heuristic approaches for producing the chromosome for the initial population instead of the random method.


## 5.4. Fitness Function

Table2 contains the cost attributes or parameters used in determining the fitness value for each segment of the road path and affects the result obtained.Table 2
Attributes table for road network segments.
Segment IDSegment description (S, E)Distance (m)Allowable velocity limits (km/h)S1(1, 2)50060S2(2, 1)50060S3(1, 3)50060S4(3, 1)60060S5(3, 5)30040S6(5, 3)40040S7(4, 5)20040S8(5, 4)20040S9(2, 4)80040S10(4, 2)80040S11(2, 3)30060Based on these criteria, the fitness cost for the candidate road pathways (chromosomes) from source node 1 to destination node 4 could be computed, and the optimum option with the least driving time would be chosen. Figure13 depicts an actual value for each route in the research area’s road network. Equations (2) to (7) define the fitness function of the GA while taking into account all of the associated parameters as follows:(2)T1ij=∑n=ijdisijVij.Figure 13
Attribute table of streets layer in ArcMap.Fij is the cost value from i to j, where i ≠ j.(3)T1ij=∑n=ij2disijVij−VRijin rush hours,where disij is the length of segment between i and j and Vij represents the allowable velocity limits between i and j.Then,(4)Dy=∑LA×100,(5)T2ij=∑n=ijDyVij,(6)T3ij=T1ij−T2ij,where(7)T4ij=T3ij−NOTL∗0.5minimum,(8)Fij=∑n=ijTij.Tij is the time required to travel between i and j. Dy is the density of the roads network. ∑L is the total length of the network roads. A is the area of the study region (square kilometer). NOTL is the number of traffic light signals. VRij is the estimated vehicle’s speed in rush hours.


## 5.5. Selection and Crossover Procedures

The tournament selection method is the type of selection used for the proposed GA, two individuals are selected, and the more appropriate individual is chosen compared to the fitness of the other chromosomes in the population, but the corresponding individual should not be selected twice as a parent in the population.In 1983, Birndlerproposed a tournament selection technique in which individuals, in pairs, were selected according to their fitness values from a stochastic roulette wheel. Selection of the individuals with the highest fitness values leads to the next generation.The crossover between the two most fitting parents chosen by the selection increases the probability of generating offspring having robust characteristics [51]. The arithmetic crossover is used in this case as follows:(9)Xi=δ.Xi1+1−δ.Xi2,where δε0,1.According to the previous equation, the new offspring generated by the arithmetic crossover are(10)Pi=δ.Xi+1−δYi,qi=δ.Xi+1−δYi.Figure14 shows an illustrative example of the proposed crossover procedure.Figure 14
Crossover procedure.


## 5.6. Mutation Procedure

Mutation procedure leads to a bit of increment in the probability of producing the infeasible chromosomes; it keeps the diversity in the population solutions. Figure15 illustrates a comprehensive description for the proposed mutation procedure in GA.Figure 15
Mutation procedure.


## 5.7. Reorganizing (Repairing) Function

GA is developed based on ideas inspired by evolutionary mechanisms, where successive generations of solutions become more and more efficient until an optimal or nearly optimal set of alternatives are reached.Loops in the shortest-time route routing issue can be produced during the crossover and mutation procedures, resulting in infeasible chromosomes. There are two primary approaches to dealing with infeasible chromosomes. The first is to eliminate them, and the second is to reorganize a chromosome with a repair function. The first is to apply a penalty, and the second is to reorganize a chromosome by removing and deleting the loop; in this work, the rearranging function is utilized to detect and eliminate the loops without incurring any additional capacity or time expenses. Figure16 shows a description of the proposed reorganizing function with an example.Figure 16
Repair procedure.Algorithm 1 displays a pseudocode showing how the algorithm finds the minimum travel time route for the provided graph from start node to the end node.Algorithm 1: Pseudocode for GA implementation.
(1)
►Input: Graph (V, E)(2)
fNode/∗ initial node in the route ∗/(3)
dNode/∗ destination node ∗/(4)
►Output: Ch[]/∗array of Genes represents the optimal time route ∗/(5)
Define: Adj [][]/∗ 0, 1 Check nodes adjacency in the graph ∗/(6)
Ch [0] ← fNode(7)
Pz ← Population size(8)
Cr ← Crossover rate(9)
Mr ← Mutatino rate(10)
for eachi, j where j = PZ(11)
Create_Chromosome (fNode, dNode)(12)
F ← Calculate Fitness Value for each chromosome(13)
End for(14)
Count ← 0(15)
Gen ← 1(16)
While Count ≤ 10 do(17)
Ch1, Ch2 ← RouletteWheel _Selection ()(18)
Ch1∗,Ch2∗ ← Crossover (Ch1, Ch2)(19)
Ch3 ← Mutation (Ch1∗)(20)
Ch4 ← Mutation (Ch2∗)(21)
F1 ← Fitness Value for the first chromosome(22)
F2 ← Fitness Value for the second chromosome(23)
Fm ← Minimum Value of fitness function(24)
If Gen > 1 && Fm (Gen-1) = = Fm (Gen-2)(25)
Count ++(26)
if count > 10(27)
Break(28)
else(29)
count = 0(30)
End If(31)
End while(32)
Gen ++(33)
Go to 17


## 6. Results and Findings

The road network in this study consists of 226 nodes (junctions) and 280 edges (segments), and each route has several interconnected edges. Determining the size of the initial population is crucial and influential in the effectiveness of the algorithm’s performance. The initial population size tends to increase exponentially with the size of the road network due to an increase in chromosome length.The quality of each chromosome in the population must be calculated accurately using efficient fitness function. Based on a geodatabase of the study area map, a multiobjective fitness function was used in GA to estimate the minimum vehicle arrival time. In this section, the fitness value is calculated for each factor separately in order to illustrate their influence on the estimated time.Table3 shows the calculated fitness value for three chromosomes for the route from node 1 to node 4, considering the allowable velocity limit in measuring the value.Table 3
The calculated fitness value with allowable velocity limit for three chromosomes (routes).
RouteSegment (S, E)Length (m)Vehicle speed40 km/h60 km/h90 km/h120 km/hRoute 1(1, 2)5000.7500.500.3330.250(2, 3)3000.4500.300.2000.150(3, 5)3000.4500.300.2000.150(5, 4)2000.3000.200.1330.100Total (minutes)1.9501.300.8670.650Route 2(1, 2)5000.7500.500.3330.250(2, 4)8001.2000.800.5330.400Total (minutes)1.9501.300.8670.650Route 3(1, 3)5000.7500.500.3330.250(3, 5)3000.4500.300.2000.150(5, 4)2000.3000.200.1330.100Total (minutes)1.5001.000.6670.500Figure17 illustrates the effect of allowable velocity limits on the arrival time from node 1 to node 4 for three separate routes. As a result, the shortest-time route is not necessarily the shortest-distance one. The vehicle speed on the road, which is determined according to street condition (e.g., street type), has a significant effect on the time needed to arrive.Figure 17
The effect of the vehicle speed on the expected arrival time.During peak hours, traffic congestion causes the creation of automobile lines, which decreases the speed of cars and delays their arrival at their destinations. Despite the fact that vehicle deceleration in real-world conditions is not exactly uniform, the delay for a specific vehicle may be estimated using fundamental dynamics equations. Because cars gradually slow down, this assumption should result in a somewhat realistic estimate of the time delay. Figure11 depicts the effect of driving during rush hour on arrival time.Figures18 and 19 illustrate how deceleration of the vehicle during rush hours and the residential density affect the time needed to arrive, which are considered as important parameters in calculating each chromosome’s fitness value in the proposed GA.Figure 18
The effect of the rush hours on the expected arrival time.Figure 19
The effect of residential density of study area on the expected arrival time.In order to emphasize the effectiveness of the genetic algorithm compared to heuristic algorithms such as the A∗algorithm, a comparison was conducted according to the execution time required to determine the optimal solution as shown in Figure 20. Python is used to implement the algorithm, and the GA solver evaluates GA using MATLAB.Figure 20
Execution time for A∗ algorithm and proposed GA.Table4 shows the calculated time for three routes during rush hour, along with the residential density for each segment of the route.Table 4
The calculated fitness value in rush hours for three chromosomes (routes).
RouteSegment description (S, E)Segment length (m)Allowable velocity limitRes. densityTime in rush hours (km/h)406090120Route 1(1, 2)500600.2080.0330.0250.0170.013(2, 3)300600.1250.0200.0150.0100.008(3, 5)300400.1880.0200.0150.0100.008(5, 4)200400.1250.0130.0100.0070.005Total (minutes)0.6460.0870.0650.040.033Route 2(1, 2)500600.2080.0330.0250.0170.013(2, 4)800400.5000.0530.0400.0270.020Total (minutes)0.7080.0870.0650.040.033Route 3(1, 3)500600.2080.0330.0250.0170.013(3, 5)300400.1880.0200.0150.0100.008(5, 4)200400.1250.0130.0100.0070.005Total (minutes)0.5210.0670.0500.030.025The simulation results of GA using GA solver indicate that the proposed GA determines the optimal time route starting from 30 generations and performs effectively over more than 200 generations up to 250, as illustrated in Figures21(a) and 21(b).Figure 21
(a): Estimated time over 80 generations. (b) Estimated optimal time over 250 generations.
(a)(b)Based on various factors that affect the arrival time, the experimental results show multiple routes from the source to the destination. Figures22 and 23 illustrate the shortest-time path obtained with multiobjective calculated time between two locations using GA. The results indicate that GA can be used effectively to design the route planning system that computes the optimal arriving time based on spatial database within dynamic traffic information.Figure 22
The first route from source to destination.Figure 23
The first route from source to destination.The Network Analyst tool can also obtain the optimal route for multiple locations. It can estimate the best route between the source and destination, passing through specific locations, as shown in Figure24.Figure 24
The shortest-time route for multiple locations.Using ArcGIS integrated with GA, the Network Analyst tool can also provide the driver with other services besides obtaining the optimal-time route and selecting a specific route based on the driver’s preferences. Furthermore, the application displays turn-by-turn directions for the preferred route with details that include the estimated distance and time for that route, as shown in Figures25 and 26, respectively.Figure 25
Route directions window.
(a)(b)Figure 26
Estimated time and calculated distance.


## 7. Conclusion

When the problem space includes a huge number of solutions and searching takes a long time, GA might be a useful alternative. To find the optimal route, a modified GA with population initialization, crossover, mutation, and repair functions is used. GA effectively obtained the shortest-time route with variable-length chromosomes based on several criteria (e.g., distance, speed limit, residential density, traffic signals, and rush hour) over 30 generations and remained near the optimum for 200 generations. By comparing the A∗ algorithm with the adaptive GA, it was found that, under increasing node density in spatial road networks, the proposed GA took the least execution time to find the optimal solution. Using ArcGIS to develop the Network Analyst tool helps users determine the shortest-distance route and simultaneously the shortest-time routes based on the user’s impedance. GA will eventually be able to work perfectly with other heuristic algorithms, such as A∗ and Dijkstra’s algorithm, in a wide range of multiobjective optimization techniques in order to maximize its effectiveness in determining the best or near optimum solution.



---

*Source: 7769951-2022-09-27.xml*