XXX -X-XXXX -XXXX -XXXXX.00 20XX IEEE Prediction of Route Choosing Behavior based on [620833]

XXX -X-XXXX -XXXX -X/XX/$XX.00 ©20XX IEEE Prediction of Route Choosing Behavior based on
Genetic Algorithm Approach

Mădălin -Dorin POP
Automation and Applied Informatics
Department
Politehnica University of Timișoara
Timișoara, România
[anonimizat] Octavian PROȘTEAN
Automation and Applied Informatics
Department
Politehnica University of Timișoara
Timișoara , România
[anonimizat] Gabriela PROȘTEAN
Management Department
Politehnica University of Timișoara
Timișoara, România
[anonimizat]
Abstract —AI (Artificial I ntelligence ) became one of the most
used concepts in last years . This concept tries to be the foundation
of standalone systems that can learn by the mselves to adapt to new
situations. This adaptation can come only after the system was
trained how to behave in several often -encountered situations. The
system will be further developed to increasing its evolving capacity
to deal with new situation s relat ed to the learned ones. The
purpose of this paper is to show how a GA (Genetic Algorithm),
part of AI concept, can be used in traffic route choosing prediction.
Our proposed algorithm brings a new approach in fitness function
computing, that has a significant role in individuals’ evaluation.
The obtained results prove that our proposal provid es benefits in
suggesting new alternatives routes for drivers with a high est level
of precision for route prediction volumes.
Keywords —artificial intelligence, fitness function , genetic
algorithm , prediction, route choice .
I. INTRODUCTION
Traffic congestion is one of highest problem that influences
the mobility of people and goods. The impact can be counted in
delays for goods deliveries, decreasing of quality for some
provided services and finally in the increasing of the travel time
between different locations, which affect all participants in
traffic .
In many cities, the ro ads are overloaded every day. To
improve the traffic flow, also in critical mentioned situations, are
developed algorithms having the capacity to adapt to them and
provide solutions to maintain a good traffic flow through the
intersections. A big interest can be seen on AI side. AI provides
mechanisms that allows a real -time optimization for traffic
signals depending on traffic data. Part of this concept are also
GAs, which can be seen as adaptive technique s inspired from
biology concept of genetics.
This paper suggests a GA based system for traffic
monitoring which will provide a prediction for route choosing
behavior. The route choosing will be reduced to a simplest
problem, the lane choosing behavior. If we are able to predict
the lane which will be choo se, we will have also a significant
information of possible destination of the vehicle taking in
account the restrictions for changing the travel direction (e.g.
special lanes for turning right or left). For each vehicle, will be
assigned a chromosome base d on its OD matrix, taking in
account the possible lane changes to reach the desired
destination. A new fitness function computation method is
proposed and each point of split, or merge, lanes will be treated as a mutation of initial chromosome. The scope is to obtain a
precise prediction of route choose behavior, which can be used
as input for traffic planning applications or for traffic signal
control.
To reach our goal, we will start by presenting , in Section II,
related works on GA applications for traf fic monitoring. There
will be explain ed different approaches of GA and how these can
be used in traffic control modeling , especially for traffic signal
control.
Section III, will focused on our approach of GA using for
route choosing behavior. We start with the chromosome
encoding and the m assignment to the vehicles entering in the
road network. The fitness function computation proposed by us
will be detailed and used further in the application of genetic
operators.
The practical usage of our approach an d obtained results will
be discussed in Section IV. There will be made a comparison
between the values obtained for a simulated traffic behavior, for
an intersection from Timisoara (Rom ania) and the results
obtained by using our approach.
In the final part , conclusions will be listed and the new
possible paths for future works.
II. LITERATURE OVERVIEW
Reviewing related works on ITS (Intelligent Transportation
Systems), we can find a lot of solutions for traffic conditions
improvement based on GAs. Some works ar e signal coordinated
control oriented. A binary encoding for green split and pause
rate are used in [1] and genetic operators are applied to obtain
the optimal values for green signal ratio and pause rate. These
can be considered the fundamentals in creati ng new strategies in
signal control and vehicle navigation. OD (Origin -Destination)
volumes represents another parameter that facilitate the
computation of road saturation degree and is used by algorithm
proposed in [1].
Knowing that transportation impli es a lot of parameters and
possible conflicts, it can be modeled like a MOTP (Multi –
objective Transportation Problem). A good solution is provided
in [2] and consisting in an improved algorithm that implements
GA to generate the initial population. The gen erated set is closed
to Pareto optimal solutions that can solve the MOTP. It should
be noticed the proposed structure of chromosomes. Each
chromosome contains a set of sub -chromosomes and the sub –
chromosomes are divided in genes. According to traffic

model ing problem, sub -chromosomes represents the origin
nodes and the genes represents the possible destination nodes.
Recorded traffic data is very important for real -time traffic
lights update. Due to different issues, some of these data can be
missing, which makes difficult the operation of adaptive traffic
lights algorithms, by introducing errors in green intervals
setting. In this case, traffic volumes estimation is useful to
replace the missing data based on data collected from
neighboring road secti ons. To ensure the precision of estimated
values, even if data from many neighboring road sections is
simultaneously missing, a new GA approach is proposed in [3].
This algorithm considers the recorded data from the whole road
network, which makes it usefu l in multiple missing data
simultaneously estimation.
Optimal green intervals can be provided based on traffic
parameters. If the traffic modelling is made using a microscopic
model, an improvement can be brought by including the
pedestrians as parameter in the traffic model. A novelty can be
considered the using a GA which has a fitness function that is
considering the pedestrians flow. This fitness function consists
of two parts: one oriented to green intervals for vehicles and
pedestrians and the other one referring to vehicles and
pedestrian’s queues [4].
GA can be utilized in a lane -by-pass algorithm for route
diversion in smooth traffic flow. The route diversion process
extended version is obtained from GA and can be integrated
with the traffic signa l timing and phases decision system [5].
III. GENETIC ALGORITHM FOR ROUTE CHOOSING BEHAVIOR
GAs are one of ITS solutions used to reduce the traffic
congestion. As we saw in previous section, the interest on these
types of solution is higher and oriented to different things that
are influencing a normal traffic flow on a road network. For road
network with a four -way intersection we can have split points
for lanes. Based on these points, that can be considered decision
points for the driver , the destinatio n is decided. The cars will be
modeled as chromosomes and for each car can be associated all
possible destinations depending on its origin node.
A. Chromosome Encoding and Initialization
Our system design is based on approach proposed in [2], but
tailored to our study direction. Considering the general
intersection configuration from Fig. 1, we assume that for each
origin node
, 0,3iOi , we attach a chromosome. Usually , for a
four-way intersection we attached four chromosomes.
Further, when we talk about nodes, we refer to the available
lanes from the road. As we can see in Fig. 1, for each direction
of moving we can have multiple lanes
l . Based on traffic
demands, an intersection can be configured to have a different
number of lanes depending on moving direction. In the nearby
of intersection we can have some split points, noted as
, 0,3iSi
, which can ensure a proper crossing of intersection
based on wanted route by reducing the queues formed in these
points. The lanes numbering, for a direction of moving, is
starting from the right side of the road and the numbering continues from the same part, for the new lanes introduced by
split points.
Fig. 1. General i ntersection configuration.
Fig. 2 shows the general structure of chromosomes that we
propose in this paper. Those four sub-chromosomes represent
the four possible destinations that can be reached starting from
the node attached to cu rrent chromosome. Further, each sub –
chromosome is divided in 10 genes. Assuming that fo ur genes
we use the binary encoding, the meaning of the genes is
established by their separation in three categories, depending on
node types. The least significant six bits represents the traversal
nodes that are crossed to move from origin node to destinat ion
node . Next t wo bits represent the binary encoding of origin node
and the most significant two bits of a sub -chromosome represent
the destination node.
Fig. 2. Chromosome structure.
The chromosomes initialization will be done by associating
for each sub -chromo some the entire possible path, including
origin and destination nodes, and all traversal nodes that shall be
crossed to reach the destination. Each different path to the same
destination consists in different parents associated to the current
chromosome.
B. Fitness Function for Individuals Evaluation
Fitness function is used to show how some individual fits to
studied problem. More than that, this fitness function can be
utilized to guide the evolution process [3].
For our specific case of route choosing beh avior, the fitness
function can be computed as in relation (1) , for each destination

node . This function is defined as sum of the number of cars that
are joining a destination node
dD.
0 1 2 3
1 1 1 1, 0,3
d d d d dpq mn
D O O O O
i j k lF N N N N d
   
          
(1)
With
, 0,3
idONi
 we noted the number of cars that can be
found after splitting point which started from origin
iOand are
routed to node
dD.
The selection of individuals will be done applying roulette
wheel selection. This procedure consists in assigning a slice of
a circular roulette wheel for each individual. The slice size of an
individual is dependent of the fitness function evaluation value
associated to it [4][6] .
C. Application of Genetic Operators
Crossover operation can be defined as an exchange between
two parents to allow the creation of new two offspring . The
successful creation of feasible offspring depends on chosen
encoding and specific fitness function [3][6]. Our proposed
approach is to use crossover operator at sub -chromosome level
instead of gene level. The proposed algorithm is presented
further. Algorithm 1 starts from two selected parents based on
roulette wheel selection result and a number is random generated
and compared with crossover probability. Is used this
randomization because the traffic route selection can include
factors that cannot be controlled such as road accidents, high
level of traffic congestion, initial route change based on driver
personal plans etc.
Algorithm 1 Crossover operation for sub -chromosomes
1: select two parents
aP and
bP with
 , 0,1 , 2,3ab ,
ab
using roulette wheel selection ;
2: generate a random number
0,1c ;
3: if
cross cp ,
crossp → crossover probability then
4: for
1i to
n, where
n is the number of
sub-chromosomes
5: generate a random number
0,1e ;
6: if
0.5e then
7: exchange the sub -chromosomes from the

thiposition of two parents;
8: end if
9: end for
10: else
11: copy initial parents to the next generation;
12: end if

Mutation operation is described as a process that can change
a random chos en gene from a chromosome , based on the defined
mutation probability [2][3]. As we can see in Algorithm 2, this
operation consists in the change of the selected gene value. The
result o f applying the mutat ion a lgorithm will be a new
offspring. Depending of its genes, the new sub-chromosome can be considered feasible or not. Some new sub -chromosomes
obtained as a mutation result are not part of solution space
attached to th e modeled problem. After the using of this
operator, can be given as soluti on travel paths that are including
inexistent lanes.
Algorithm 2 Mutation operation for sub -chromosomes
1: select one parent
aP with
 0,1 , 2,3 a , using
roulette wheel selection ;
2: generate a random number
0,1 m ;
3: if
m mp ,
mp → mutation probability then
4: for
1i to
n, where
n is the number of
sub-chromosomes
5: generate a random number
 [0, ( )g size n ;
6: if
1 sg , where
[]sg is the
thg gene of
sub-chromosome
s then
7:
0 sg ;
8: else
9:
1 sg ;
10: end if
11: end for
12: end if

IV. EXPERIMENT AND RESULTS
In this section our approach is applied on a real intersection.
The GA operators will be used on the obtained chromosome
and the evolution of travel demands will be analyzed.
A. Overview
Starting from the intersection studied in [7] and [8] and
applying our approach related to intersection configuration, this
will look like in Fig. 3.
Fig. 3. Studied intersection configuration.

We assume that for each origin node we attach a
chromosome . Fig. 4 shows the corresponding chromosome for
the situation where we consider
2O as origin node. Each
column represents the possible destinations from node
2O ,
according to the configuration from previous figure. Based on
lane
2l feature, to give vehicles the opportunity to go ahead or
to turn right, we can see two more parents that have values
attached to this s ub-chromosome.
Fig. 4. Specific chromosome for origin O 2.
B. Individuals Evaluation
The individuals evaluation is performed using pr oposed
fitness function and roulette wheel selection. The scope of this
selection is to determine the chromosomes that will be propagate
to future populati ons. Considering only the vehicle s from origin
node
2O , the selection method is illustrated in Fig. 5. After the
metho d is applied we can determine the best individuals that can
be used in the future . Initial traffic data used for selection is from
[7][8].
For a better understan ding we choose only Parent 1 f rom the
chromosome attached to the ori gin
2O . Each sub -chromosome
has associated the path to a different destination , mapping
between sub -chromosome and its destination is visual done by
colors as it i s illustrated in Fig. 5. After the traffic data was
analyzed using (1 ), for the roulette slices were associated the
correspon ding percents for each destination that can be joined .
We can see that the roulette wheel selection result is the sub –
chrom osome 2, because this has the high est fitness function
value asso ciated , which makes it suitable to be propagate to a
future population.
Fig. 5. Roulette wheel selection for Parent 1 sub-chromosomes for origin O 2 . C. Genetic Operators Applied on t he Studied Intersection
Before we apply the GA operators for the intersection, we
consider, for a better understanding, only two parents for
crossover and one parent for mutation.
Considering that the probability of changing gen es between
the parents is 50%, the offspring obtained after applying
crossover operator s are illustrated in Fig. 6.
Fig. 6. Results after applying c rossover operators.
Mutation operator s applied to a parent leads to changes that
can make an offspring not feasible . In Fig. 7, the genes that have
been undergone mutation operators were marked with red. We
can observe that Offspring 1 is a feasible one, because the
mutation result led to a po ssible path for crossing the intersection
node , from the origin node that is linked to current chromosome.
On the other hand, the Offspring 2 is not feasible because it
cannot be found in solution space of current chromosome. We
can see that the lanes with encoding from traversal nodes
associated genes, does not exists.
Fig. 7. Results after applying mutation operators.
D. Discussion
To see the improvement brought by our proposed method, a
comparison was made between it and a classic estimation
volumes based on prev ious traffic data. The results from Fig. 8
show that the simulation running for 20 0 iteratio ns proves that
the avera ge of destination s volumes obtained are closed to
results obtained by applying o ur method . The results interest
was o n the vehicle s with origin
2O that was studied in current
paper .
Fig. 8. Prediction error of destinations volumes for origi n O2 .

32%
35%
17%
16%Roulette Wheel Selection
D0
D1
D2
D3

0246810
D0 D1 D2 D3NUMBER OF VEHICLESDESTINATION NODEP R E D I C T I O N E R R O R
Classic method Proposed method

V. CONCLUSION AND FUTURE WORK
This paper propose a new method for prediction of route
choosing behavior based on GAs. After reviewing related
literature to see different approaches of GAs utilization for
traffic monitoring and control, we came with a n ew method of
four-way interse ction configuring . The graphical obtained
model us is extendable and is easy to be used for roads w ith
different number of lanes.
Other new thin g brought by is paper is the usage of a new
chromosome structure to model the OD routes. For each origin
is associated a chromosome and this is divided in four sub –
chromosomes that correspon ds to the possible destinations
routes. Different routes to the same destination were modeled as
parents of the s ame chromosome.
Other novelt ies are the fitness function expression that we
propose to be used for individuals evaluation and the modified
crossover and mutation algorithms, adapted to our modeling
which uses sub-chromos omes. The individual s selection for
propagati ng to future populations is done via roulette wheel
selection.
At the final, we applied ou r method to a real intersection and
we saw that th is method facilitate s getting more precise values
than the clas sic estimation based on previous traffic data. The
good level of improvement brought by using th is approach was
obtained by comparing the evolution of route choosing behavior ,
for a large num ber of interations , for both classic and proposed
estima tion method.
REFERENCES
[1] X. Zeng , C. Wu Y. Chen, Q. Xiong and C. Wei , “Research on the model
of traffic signal control and signal coordinated control ”, Smart Innovation,
Systems and Technologies, vol. 62 pp. 64-76, Springer 2017, ISBN 978 –
981-10-3574 -6 [International Symposium on Intelligent Transportation
and Smart City ( ITASC2017), Shanghai: China, 19 -21 May 2017 ].
[2] S. A. Zaki, A. A. A. Mousa, H. M. Gneedi and A. Y. Elmekawy, “Efficient
multiobjective genetic algorithm for solving transportation, assignment
and transsshipment problems”, Applied Mathematics, vol. 3, issue 1 , pp.
92-99, Scientific Research 2012, doi:10.4236/am.2012.31015 .
[3] M. K. Mainali, S. Mabu and K. Hirasawa, “Estimation of missing traffic
volume by genetic algorithm based on t raffic flow balance”, Transactions
of the Society of Instrument and Control Enginners, vol. 10, issue 13, pp.
113-122, SICE 2011.
[4] A. M. Turky, M. S. Ahmad and M. Z. M. Yusoff, “The use of genetic
algorithm for traffic lights and pedestrian crossing contro l”, International
Journal of Computer Science and Network Security, vol. 9, issue 2, pp.
88-96, February 2009.
[5] S. Tahilyani, M. Darbari and P. K. Shukla, “A new genetic algorithm
based lane -by-pass approach for smooth traffic flow on road networks ”,
International Journal of Advanced Research in Artificial Intelligence, vol.
1, issue 3, pp. 32 -36, The Science and Information (SAI) Organization
2012, doi:10.14569/IJARAI.2012.010306 .
[6] M. Mitchell , An Introduction to Genetic Algorithms , Cambridge : MIT
Press , 1996 , pp. 124 -130.
[7] M. D. Pop, “Traffic lights management using optimization tool”,
unpublished [ SIM 2017: 14th International Symposium in Management
Challenges and Innovation in Management and Entrepreneurship ,
Timisoara: Romania , October 2017].
[8] M. D. Pop and O. Proștean , “Bayesian Reasoning for OD Volumes
Estimation in Absorbing Markov Traffic Process Modeling ”,
unpublished.