=Paper=
{{Paper
|id=Vol-2845/Paper_37.pdf
|storemode=property
|title=Intellectual Algorithm Implementation for Megacity Traffic Management
|pdfUrl=https://ceur-ws.org/Vol-2845/Paper_37.pdf
|volume=Vol-2845
|authors=Peter Nikolyuk,Tatiana Neskorodieva,Eugen Fedorov,Esta Chioma
|dblpUrl=https://dblp.org/rec/conf/iti2/NikolyukNFC20
}}
==Intellectual Algorithm Implementation for Megacity Traffic Management==
https://ceur-ws.org/Vol-2845/Paper_37.pdf
Intellectual Algorithm Implementation for Megacity Traffic
Management
Peter Nikolyuka, Tatiana Neskorodievaa, Eugen Fedorovb and Esta Chiomaa
a
Vasyl’ Stus Donetsk National University, 600-richcha str. 21, Vinnytsia, 21021, Ukraine
b
Cherkasy State Technological University, Shevchenka av. 460, Cherkasy, 18006, Ukraine
Abstract
The research aims to create technology to improve the capacity of urban transport networks. An
algorithm for constructing an optimal route for each vehicle in a large city has been developed
with a route correction in real time in accordance with the dynamics of changes in the traffic
situation. Technically, the procedure for regulating vehicle flows is carried out by automating
traffic control at each intersection and road sections between neighboring intersections. This
allows a traffic management center (TMC) to monitor an entire transport network of the megacity
in real time, as well as to accompany each vehicle along the route, which has set its origin-
destination coordinates. An implementation of the intelligent traffic regulation process is based on
the use of graph modeling of the urban transport network and the use of an A-star algorithm to
navigate the optimal route. A computer program written in Java performs the named procedure.
Technically, the process of control and regulation of urban traffic is that the TMC transmits voice
commands to each driver along the route with the destination declared by the driver, as it is in
regular GPS navigation. The peculiarity is that the program analyzes the dynamic traffic situation
throughout the city. As a result, there is a constant update of the travel routes of each vehicle,
taking into account traffic situation at a particular moment in time in accordance with the traffic
situation. The consequence of this process will be the disappearance or a significant reduction in
congestion on urban highways. The final result of the research is the synchronization of traffic
flows and an optimal use of transport arteries throughout the city. In addition, the probability of
traffic will be significantly reduced. It is also significant that each driver in such traffic regulation
scenario will arrive at his destination in the shortest possible time.
Keywords 1
oriented multigraph, GPS navigation, A-star algorithm, optimal route, Java program, intelligent
traffic.
1. Introduction
Traveling a vehicle in a big city anywhere on the globe is a big problem. The name of the problem is
traffic jams on urban transport arteries. Moreover, an urgency of the problem is growing every year due to
a sharp increase in the number of cars on city streets. At the same time, the capacity of urban roads
remains practically unchanged. In this respect it is important to note that modern technologies aimed at
solving urban transport problems are not capable of improving the traffic situation in megacities today.
We are talking about a variety of modern technologies for managing urban traffic, including GPS
navigation, which only states the fact of traffic problems with a delay – post factum.
IT&I-2020 Information Technology and Interactions, December 02-03, 2020, KNU Taras Shevchenko, Kyiv, Ukraine
EMAIL: p.nikolyuk@donnu.edu.ua (P.Nikolyuk); t.neskorodieva@donnu.edu.ua(T.Nescorodieva); fedorovee@ukr.net(E.Fedorov);
chioma.e@donnu.edu.ua (E. Chioma)
ORSID: 0000-0002-0286-297X (P.Nikolyuk ); 0000-0003-2474-7697(T.Nescorodieva); 0000-0003-3841-7373(E.Fedorov ); 0000-0003-1134-
782X(E. Chioma)
©️ 2020 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
400
To solve the problem due to its complexity and the need to consider technological and managerial
factors, a systematic approach is required. In the technological aspect, this work solves the formulated
problem by using a special algorithm in combination with technical means of organizing urban traffic.
The study lays the foundations of an automated intelligent system (AIS) for vehicle traffic regulation in
large city. The task of such AIS is to navigates the optimal routes for each car that participates in city
traffic and interacts with the TMC. In comparison with other means of elimination of congestions the
offered approach allows to prevent their formation. In general, the study is a fundamentally new approach
to solving the problem of organizing the movement of vehicles in large cities.
In the managerial aspect, to implement the technology in the real structure of the municipal economy,
it is proposed to implement a sequence of processes that will reduce organizational risks.
The known solutions to the problem of transport collapse of megacities relate to technical aspects,
while the issues of their implementation remain out of the attention of researchers. This approach limits
the possibilities of commercialization of the research results and significantly reduces the probability of
their use in a practice of municipal government.
Consequently, the urgency of work in solving transport problems of cities is due to:
development of an algorithm for coordinating the movement of vehicles, the implementation of
which prevents the occurrence of critical traffic situations in big cities;
the inclusion of technical and organizational processes in the range of issues under study, which is
due to the use of a systematic approach and the need to reduce the cost of introducing technical;
the lack of significant modernization of the city's transport infrastructure with significant
investment; in the context of directing significant resources of large cities to fight the pandemic, this
factor will help accelerate the implementation of the proposed technical solution;
the possibility of two-vector scaling of work results – both in the direction of increasing the
number of tracked vehicles, and in the direction of decreasing them;
the above indicates that the proposed algorithm for generating optimal routes for a car to the size of
a transport network is promising and, thus, expands the range of cities for the implementation of the
proposed automated traffic management system.
2. Analysis of literature sources and problem statement
An investigation of networks of different nature, in particular neural, allows to make predictions,
including for urban transport networks [1-3]. The use of such networks is relevant due to the possibility of
a certain frequency in urban traffic. This circumstance allows forecasting traffic processes both during the
day and in the longer term.
Special attention is paid to the choice of optimal routes in the urban transport network, as this issue is
key in terms of urban traffic strategy. In particular, the study [4] to solve this problem uses a macroscopic
mathematical model to control the dynamic factors of traffic – speed, intensity and congestion of cars.
Principles of operation of transport networks should be explored in different modes. Particular
attention in this regard should be paid to the overloaded mode, which causes traffic. It is the dynamics of
the transition between different phases of traffic devoted to the study [5].
The authors [6] proposed a real algorithm that allows to navigate routes that are optimal in terms of
trip time. Moreover, there is a constant correction of the route, considering dynamic changes in the city's
transport network. Each intersection is equipped with special sensors that allow carrying out monitoring
of the load of lanes at any given time and respond in a timely manner to such changes. The transport
network is modelled in the form of a weighted non-planar oriented multigraph. The weight of each arc of
such graph corresponds to the load of the simulated lane. Drivers interacting with the TMC could receive
constantly updated data as to their optimal routes. Special computer program that implements the A-star
algorithm performs plotting a route in the graph that simulates the city’s transport network.
The optimization of urban traffic processes is based on a separate city intersection. The intersection
itself is the main cause of congestion on urban transport networks. The main challenge in this sense is to
401
maximize a throughput of this type of facility. Many researchers pay attention to this problem. Let us
dwell on the analysis of the results of work [7] as to connected vehicle technology. The study proposes an
algorithm to optimize the passage through a controlled intersection. The algorithm records the location
and speed of connected and identified unconnected vehicles within an area of interest around each
intersection. As a result of the algorithm, we obtain an optimal sequence of switching phases of the
intersection traffic lights. Consequently, the algorithm gives a minimum delay time of cars at the
intersection. Works [8-13] are also devoted to a similar problem.Let us now formulate the stages of
solving the problem of an optimal mode of urban traffic management. The first step in this regard is to
model the city's transport network using a weighting oriented non-planar multigraph. The fundamental
point is that in such graph each edge is matched with a dynamic value – weight, which changes
synchronously with a dynamics of changes in a congestion of the city's transport arteries. The second
important step is application of A * -algorithm, which is used to plot optimal routes in the graphs
simulating city transport network. This algorithm navigates the time-optimal routes for each car that
ordered such route. The third stage is a software algorithm that implements a navigating of specific
routes, considering all the features of the transport network. Such features include high dynamics and
different levels of congestion of individual lanes on the same section of the road in one direction, as well
as compliance with traffic rules. And, finally, the fourth fundamental point is the technical organization of
registration of the vehicle flows by using special sensors built into the roadbed at each intersection. Data
from these sensors enter to TMC, where such information is analysed and presented as input values of the
computer program, which implements A *- algorithms.
As a result of the implementation of the named steps, there will be a complete synchronization of
traffic flows, which will lead to a fundamentally new quality and, consequently, to a disappearance of
congestion (or sharp reduction) in the transport network. This will allow each driver to arrive to their
destination in a shortest possible time. Thus, urban traffic is transformed into a fundamentally new state.
3. The goals of the research
The aim of the study is to create the basic elements of technology that will stabilize city traffic and
transfer it to a qualitatively new state. The frequency of congestion will be minimized, and each vehicle
will arrive at its destination in the shortest possible time.
To achieve the stated goal, the following tasks were set:
to create a model of urban transport network in a form of the weighted non-planar multigraph with
dynamically loaded edges (arcs);
to automate each intersection, which involves the installation in the roadway of special sensors that
detect cars leaving the lanes or, conversely, entering theirs;
to navigate optimal routes to each vehicle participating in city traffic;
implement the transfer of sensor data to TMC;
to implement the work of the software algorithm in real time, which will allow timely monitoring
of changes in urban traffic – this fact fundamentally distinguishes the procedure proposed in this study
from existing urban transport navigation systems.
4. Features of the research method
So, we will formulate the basic principles of the development:
the city transport network is presented in the form of an weighted oriented non-planar
multigraph;
each arc of the above-mentioned graph simulates a lane that runs between adjacent city
intersections and receives a weight, the value of which corresponds to the load of the vehicle of this
lane in the real road situation;
402
the weights of the arcs of the described multigraph are obtained as a result of the use of special
sensors that detect wheel pairs intersecting these sensors, built into a roadway at each intersection;
the above-mentioned scales are dynamic values that correspond to the dynamics of changes in
real urban traffic, which monitors the congestion of the transport network on each elementary road
segment – on the lane;
the obtained model is used for navigating the optimal routes for all vehicles that have ordered
such services.
5. The optimal city route as a result of the research
Piezo-crystalline sensors [6], which are mounted in a roadbed, capable of generating electrical
impulses caused by a car wheelset. Such devices are installed at every intersection. Their main role is to
register cars that either cross intersections (output sensors) or enter a lane between adjacent intersections.
Through the traffic light control system, electrical signals from each intersection are sent to TMC. The
TMC runs computer programs that use such input data in their work. In fact, this means that the urban
transport network is under a control of the TMC. Fif.1 presents of Toronto network. The transport
network is represented in a form of the graph in Fig. 2. Principle of notation each arc of the multigraph
has been used for the whole multigraph in the computer program [6]. The program will describe later too.
Lane a (single road segment) is closest to the center of dividing strip of the road, lane b is on the right,
lane c is further to the right, etc. alphabetically. Some intersections in Fig.1 and in Fig. 2.
Figure1: District of Toronto (Canada). Circles with digits represent urban crossroads
It have been done for effective work of the computer program [6]. The program is a main object of
given investigation. The A *-algorithm is efficient one that allows to navigate the optimal routes in a
graph between two its pointed vertices. In this case, the criterion of optimality is the travel time of each
vehicle along a route. Fig. 3 presents a conditional scheme of data collection from sensors mounted at two
adjacent intersections [6]. Four cars moving from intersection A to intersection B from different
directions and on different lanes are shown. Analysis of a frequency of sensors’ operation – both input
and output ones – gives possibility to estimate a dynamics of the vehicle on the traffic lanes. This analysis
403
allows to assess the load of cars in individual lane and at any time. The numerical estimate of the traffic
load on the AhBh road section (Fig. 3) consists from the number of pulses generated by road sensors and
its frequency during the burning of a green phase of a traffic light. During the period of burning of green
traffic light phase at the corresponding intersection, the input and output sensors emit a range of values
𝑁𝐴ℎ𝐵ℎ and 𝑛𝐴𝑖ℎ𝐵ℎ . Let 𝑁𝐴ℎ𝐵ℎ is the total number of cars (more precisely a number of car’ wheel pairs)
entering the section of the road that runs from intersection A to intersection B. Suppose we are talking
about cars that are along the horizontal section of the road (in Fig. 3 that are cars 1 and 2). Certainly, these
vehicles could travel in the direction of intersection B during the green light at intersection A. The value
𝑛𝐴𝑖ℎ 𝐵ℎ represents the number of vehicles leaving the lane 𝑖 of a section of the road AhBh in different
directions, allowed by traffic rules, during a burning of a green phase of the traffic light at the intersection
B. Each lane at this intersection, as seen in Fig. 3 is equipped with its own sensor to separate registration
of the groups of the vehicles moving on their own routes. On the section of the road AhBh vehicles could
relocate to select the optimal route, which is calculated using a program that operates on the TMC [8].
Figure 2: Oriented non-planar graph modeling part of Toronto transport network. Each single arc of the
graph is weighted and represents directed lanes (red triangles) on a road in one direction as it is shown
between vertices 55 and 56
It is important that every driver who orders the TMC to navigate an optimal route receive timely
instructions as to his further movement. Technically, a position of the vehicle on a map of a metropolis
can be recorded using GPS positioning instrument technology and a map-matching algorithm [14].
The passage of a vehicle on a city route is a sequence of lanes going from the starting position of the
vehicle to the final one. The principal condition is a fulfillment of the following condition [6]:
𝑓
∑ (𝑁𝐴𝑖ℎ𝐵ℎ ⁄(𝑛𝐴𝑖ℎ𝐵ℎ )) 𝐿𝐴ℎ𝐵ℎ → min. (1)
ℎ=1
In this condition f represents a number of lanes forming a route of each vehicle; 𝑳𝑨𝒉𝑩𝒉 is geometric
length of a road section between adjacent intersections, an index of which is h.
Graph modeling of an urban transport network allows a use of various algorithms developed in graph
theory. In this case, a use of the A * -algorithm is most appropriate in relation to solving the problem –
navigating a route in a graph between two given vertices (on the other hand – between the origin-
destination positions of the route).
This algorithm navigates an optimal route (in our case, this route is time-optimal) and has a slight
algorithmic complexity of type O (N) too, where N is the amount of input data. The action of such
404
algorithm leads to the analysis of the function f (n) = g (n) + h (n), where g (n) is the distance from the
origin position of the vehicle to the intermediate vertex n; h (n) is the heuristic distance taken in a straight
line from an intermediate vertex of the graph to the destination position.
The channel “Vehicle ↔ TMC” works in real time, constantly updating data as to a load of the road
sections between adjacent intersections, taking into accounts the results obtained from the road sensors.
Next, the TMC based on the operation of the program [6] (see also Listing 1 on Appendix) navigates the
optimal traffic for each vehicle. Of course, the mentioned program implements routing only for a group of
vehicles located between intersections 1 and 2, and the routes of which are directed to the destination
position, because the heuristics (function h (n)) are the same for all these cars. But every city is a
stationary object and therefore to compile a program, the main elements of which are given below in
Listing 1, is no problem (the full program code is given in [6]).
Figure 3: It is shown two neighboring intersections, lanes between them, denoted as a, b and c. Pulses
from the input sensors (red stripes) and output sensors (green stripes) are transmitted to the ТMС [6].
The next method of the program navigates the route between b1_2 and b11_10 lanes (in Fig.3 these lanes are
highlighted) on Appendix 2. Method used A-star algorithm looks as follows on Appendix 3.
It is fundamental moment that interaction between each vehicle and TMC occurs both in real time and
in a mode of constant route correction. This function realizes computer programs, which navigate the
optimal (on time) routes for each vehicle. As a result, every vehicle driver receives instructions, such as
those presented below:
Course-1: [b1_2-Broad street, a3_7-Valley street, b7_10-Trump street, a10_9-Kennedy street,
a9_10-Kennedy street, a10_11-Apple street, b11_10-Apple street]
Course-2: [a3_7-Valley street, b7_10-Trump street, a10_9-Kennedy street, a9_10-Kennedy street,
a10_11-Apple street, b11_10-Apple street]
Course-3: [b7_10-Trump street, a10_9-Kennedy street, a9_10-Kennedy street, a10_11-Apple street,
b11_10-Apple street]
Course-4: [a10_9-Kennedy street, a9_10-Kennedy street, a10_11-Apple street, b11_10-Apple street]
Course-5: [a9_10-Kennedy street, a10_11-Apple street, b11_10-Apple street]
Course6: [a10_11-Apple street, b11_10-Apple street]
Course-7: [b11_10-Apple street]
The peculiarity of this result is that the route consists only from selected lanes. In this case, each new
Course starts from the second position of the previous Course. The program constantly updates the route:
405
as soon as the vehicle crosses an input sensor, the program on the TMC calculates the updated route.
Thus, the actual route of our hypothetical vehicle will look like this:
b1_2-Broad street → a3_7-Valley street → b7_10-Trump street → a10_9-Kennedy street →
a9_10-Kennedy street → a10_11-Apple street → b11_10-Apple street.
Presented above result is a fundamental feature of the investigation. It allows to navigate dynamic
routes that track a dynamic of changes in urban traffic. Presented above program is characterized the
spectra of fundamental peculiarities, which consist in constant updating of a route by means of
intercepting the result of the previous calculation. In this regard, it should be noted that each previous
Course is associated with the next one. Another words, the result of the calculation in a next step
intercepts the second position of the previously calculated route (these key positions are highlighted
above).
6. Introduction of the technology
The quality of the technology is assessed at the stage of its implementation, so this stage must be given
due attention. The implementation of the proposed algorithm in a real environment requires a use of
modern management tools – project management methodology, the theory of constraints and considering
the practices of managing a transport infrastructure of cities. Then the effectiveness of the technology can
be considered as a tuple:
𝐸 = {𝑃𝑀𝑝1 , 𝑀𝑃𝐼𝑝2 , 𝑇𝑂𝐶𝑝3 }, (2)
where PMp1 – a set of methods of project management, MPIp2 – a set of practices of transport
infrastructure management, TOCp3 – a set of the methods of the constraints theory.
It is important that the elements of the tuple (2) are interconnected by common resources – performers,
time parameters, funds and tangible assets. To solve a problem of optimal control of an implementation
and operation of TMC, which implements algorithms according to relations (1), it is reasonable to apply
the provisions of the theory of distribution design mechanisms (another name – the theory of economic
mechanisms – TEM). TEM is the theoretical basis of modern microeconomics and allows to combine in a
single model all the processes occurring in a complex transport management system of the metropolis,
namely:
testing the technology of optimization of many vehicle routes in a transport environment of large
scale;
development of a project to implement technology in a real environment of a big city;
project implementation while minimizing resource conflicts and
coordination of the interests of participants in a process, in the spectrum of which are economic
(fuel savings for each vehicle owner), environmental (reduction of CO2 emission), social (timely
arrival of ambulances, rescuers, police), etc. Adherence to consistency will reduce organizational risks.
Note also that the proposed technology is easily consolidated into urban transport infrastructure.
Technically, you only need to connect the terminals of the sensors mounted at intersections to the traffic
light control system.
7. Conclusions
1. Created a real multigraph model that reproduces the transport network of the neighborhood area of
Toronto (Fig. 1). Moreover, all existing lanes are modeled considering the directions of traffic in each of
these lanes. Each edge of the graph receives a weight that changes dynamically according to changes in
traffic.
2. A method of using piezocrystalline sensors mounted in each intersection has been implemented,
which has allowed a registration of traffic flows between all neighboring intersections. This means that
entire transport network of the city (in terms of its vehicle load) is under the control of TMC. This system,
thus, monitors all changes in traffic and calculates the dynamic optimal routes for each vehicle, relevant
to each time moment. This circumstance gives possibility to avoid congestion.
3. The research implemented a software module [6], which navigates the time optimal routes for each
406
vehicle that participates in urban traffic. In this regard, the heuristic A-star algorithm is used – a powerful
computational method of the graph theory. This allows to synchronize the flow of cars. At the same time,
traffic is moving to a qualitatively new level. As a result – congestion disappears completely or the
frequency of their occurrence is significantly reduced.
4. Procedure has been created to use data taken from sensors mounted at each city intersection. The
research assumes the transfer of such data to the TMC by using an existing network that controls an
operation of traffic lights. This allows to organically and without significant costs to implement the
proposed technology.
5. The research proposes a scheme for the transfer of designed routes from TMC to vehicle drivers.
This procedure is used of GPS-navigation technology. However, the technology introduced in the study is
characterized by the fact that it works in real time based on real data. This allows responding in a timely
manner to changes in urban traffic, thus avoiding congestion. In this sense, the initiated traffic control
procedure is fundamentally different from the strategy of modern urban GPS-navigation.
9. References
[1] S. Rahimipour, R. Moeinfar, S. M Hashemi. “Traffic prediction using a self-adjusted evolutionary
neural Network.” Journal of Modern Transportation, Vol. 27, Issue 4, December (2019). 306–316.
DOI: 10.1007/s40534-018-0179-5
[2] A. Emami, M. Sarvi, S.A. Bagloee. “Using Kalman filter algorithm for short-term traffic flow
prediction in a connected vehicle environment.” Journal of Modern Transportation, Vol. 27, July
(2019): 222 –232. DOI: 10.1007/s40534-019-0193-2
[3] A. Pompigna, F. Rupia. “Comparing practice-ready forecast models for weekly and monthly
fluctuations of average daily traffic and enhancing accuracy by weighting methods. ” Journal of
Traffic and Transportation Engineering (English Edition).”, Vol.5, Issue 4, August (2018): 239-253.
DOI: 10.1016/j.jtte.2018.01.002.
[4] H. Majid, C. Lu, H. Karim. “An integrated approach for dynamic traffic routing and ramp metering
using sliding mode control.” Journal of Traffic and Transportation Engineering (English Edition),
Vol. 5, Issue 2, April (2018): 116-128. DOI: 10.1016/j.jtte.2017.08.002.
[5] E. Kidando, R. Moses, T. Sando, E.E. Ozguven. “An application of Bayesian multilevel model to
evaluate variations in stochastic and dynamic transition of traffic conditions.” Journal of Modern
Transportation, Vol. 27, Issue 3, October (2019): 235–249: DOI: 10.1007/s40534-019-00199-2.
[6] A. Pidgurska, P. Nikolyuk “ Intelligent urban traffic.” Central European Researchers Journal, Vol.6,
Issue 1, (2020): 33-61.
[7] X. Liang, S. Ilgin Guler, V. Gayan. “ An equitable traffic signal control scheme at isolated
intersections using Connected Vehicle technology.” Transportation Research Part C, Vol. 110:
January (2020): 81-97 DOI:10.1016/j.trc.2019.11.005.
[8] D.G. Boguto, K.K. Kadomskiy, P.K. Nikolyuk, A.I. Pidgurska. “ Algorithm of intelligent urban
traffic.” Bulletin of V.Karazin Kharkiv National University, Series “Mathematical Modeling.
Information Technology. Automated Control System”, Vol. 42: (2019): 12 – 25.
[9] C. Xu, J. Xu. “ Intelligent terminal based intelligent traffic light system and method”, Patent No.
CN104575066, Filed May 5th, (2015), Issued June 16th , (2015).
[10] C. Xu, J. Xu. “A kind of intelligent transportation road capacity note broadcasting system.” Patent
No. CN104064049B, Filed January 15th, (2016), Issued June 16th, (2016).
[11] A. Shu, X. Xu, L. Xu, B. Zhang, C. Liu, Y. Cai. “ Urban artery traffic dynamic green wave signal
control system and method based on real-time traffic flow data.” Patent No. CN110136454 (A), Filed
June 11th, (2018), Issued July 19th, (2018).
[12] H. Zhang, T. Li, H. Hu, L. Li, Y. Hao, Q. Chen, W. Zhang, P. Chu, C. Jiang, W. Zhou. “Dynamic
prediction intelligent traffic management method for urban road.” Patent No. CN109920250 (A),
Filed June 1th, (2018), Issued July 21th, (2018).
[13] T. Wang, A. Hussain, Y. Cao, G. Sangirov. “An improved channel estimation technique for IEEE
802.11p standard in vehicular communications.” Sensors, Vol. 19, Issue 1, December (2019):
DOI:10.3390/s19010098.
407
[14] M. Hashemi, H. Karimi. “A weight-based map-matching algorithm for vehicle navigation in
complex urban networks.” Journal. of Intelligent Transportation Systems, Vol.20, Issue 6, May
(2016): 573-590 DOI:10.1080/15472450.2016.1166058.
10. Appendix
Appendix 1. Listing 1.
import java.util.*;
public class Astar {
/* the next constructor creates some node of the graph, presented in Fig. 2 */
static Node a1_2 = new Node("a1_2-Liberty avenue", 962);
/*the next method creates interactions between adjacent nodes*/
public static void initGraph() {
Random k = new Random();
int L2_1 = 320;
double ra2_1 = 1 + (double) k.nextInt(5) * L2_1;
double rb2_1 = 1 + (double) k.nextInt(5) * L2_1;
double rc2_1 = 1 + (double) k.nextInt(5) * L2_1;
a1_2.adjacencies = new Edge[]{
new Edge(b2_1, ra2_1),
new Edge(b2_1, rb2_1),
new Edge(c2_1, rc2_1),};
Appendix 2.
public static void main(String[] args) {
initGraph();
AstarSearch(b1_2, b11_10);
List path = printPath(b11_10);
System.out.println("Path: " + path);
while (path.size() > 1) {
Node node = path.get(1);
node.parent = null;
for (Node n : nodes) {
n.parent = null;
initGraph();
AstarSearch(path.get(1), b11_10);
path = printPath(b10_11);
System.out.println("Path: " + path); } }
Appendix 3.
public static void AstarSearch(Node source, Node goal) {
Set explored = new HashSet();
PriorityQueue queue = new PriorityQueue(100, new Comparator() {
//override compare method
public int compare(Node i, Node j) {
if (i.f_scores > j.f_scores) {
return 1;
} else if (i.f_scores < j.f_scores) {
return -1;
} else {
return 0; } } });
408