Microsoft Word - BRAIN_vol_9_issue_2_2018_v4_final2_ok.doc

Using the Genetic Algorithm for the Optimization of Dynamic School Bus
Routing Problem

Özkan Ünsal

Department of Computer Engineering, Süleyman Demirel University, Turkey
Çünür Mahallesi, Isparta 32260, Turkey

Tel.: +90 246 211 10 00
ozkanunsal@gmail.com

Tuncay Yiğit

Department of Computer Engineering, Süleyman Demirel University, Turkey
Çünür Mahallesi, Isparta 32260, Turkey

Tel.: +90 246 211 10 00
tuncayyigit@sdu.edu.tr

Abstract
Vehicle routing problems (VRP) are complicated problems, which can be encountered in a

variety of different fields and are not possible to solve using conventional methods. Thanks to the
technological advancements in areas such as the global positioning system (GPS), geographical
information systems (GIS), mobile communication networks, and traffic sensors, it is now possible
to solve the VRP in a dynamic and real-time manner. In this study, the school bus routing problem
(SBRP), which is a sub-branch of VRPs, was optimized by means of an application developed using
Genetic Algorithms(GA), which is one of the heuristic methods. By using the application developed
based on mobile communication and GPS, the instantaneous locations of stops and the school bus
were determined and the shortest and most convenient route for the vehicle to follow was
dynamically identified. The experimental results obtained at the end of this study showed that the
existing school bus routes can be optimized using GA and therefore the costs associated with the
routing can be reduced.

Keywords: vehicle routing problem, dynamic school bus routing problem, genetic
algorithms, optimization

1. Introduction
Transportation and distribution systems are necessary in every field of daily life and concern

all sectors. The use of these systems brings along considerable expenses to enterprises. The
expenses associated with distribution correspond to 15-20% of the product costs (Rushton,
Croucher & Baker, 2006). The growing population, globalizing economy, and increasing demand
for consumption make the use of transportation and distribution systems even more important and
widespread. This usage density brings along certain problems such as loss of time, traffic jams,
additional expenses, and environmental pollution. Traffic jams, road and weather conditions, and
unplanned route choices can be listed among the reasons for increasingly longer periods spent in
traffic. Longer time-spans allocated to transportation cause significant increases in fuel costs and air
pollution, which also raises health concerns. Traffic is a major source of air pollution in urban areas
of developing countries that leads to high exposure risk of urban dwellers (Oanh, Kongpran, Hang,
Parkpian, Hung, Lee & Bae, 2013). The time loss can be minimized by means of suitable route
selection before starting the journey and the routing plans that can be updated against adverse
situations such as traffic, road, weather, and accidents. Many countries and many enterprises
obtained considerable savings in terms of cost and time via optimization studies on transport and
traffic control systems.

School buses are being used more and more frequently due to current socio-economic
structures, changing family patterns, earlier age limit to start to school, and increasingly longer
distances between school and houses. Route planning is difficult to fully optimize, as the location of
bus stops might continuously change due to the discontinuation of the student on a particular day or

Ö. Ünsal, T. Yiğit - Using the Genetic Algorithm for the Optimization of Dynamic School Bus Routing Problem

address changes. In addition, factors such as multiple routes available between two stops, and
changing drivers working on the same route also contribute to the difficulties arising when the route
planning is desired to be optimized. Thanks to the advancements in today’s information and
communication technologies, vehicle fleets can be managed in real-time. When jointly used,
devices like GIS, GPS, traffic flow sensors and cellular telephones are able to provide real-time
data, such as current vehicle locations, new customer requests, and periodic estimates of road travel
times (Khouadjiaa, Sarasolab, Albab, Jourdana & Talbia, 2012). This brings along the opportunity
to dynamically redefine the vehicle routes, based on changing conditions. These dynamically
defined routes make the saving targets in terms of cost and time in the optimization of VRP even
more efficient.

It was seen that more successful solutions were obtained when heuristic techniques instead
of conventional methods were used for the solution of complicated problems (NP-Hard) such as
VRP. From 1959 onwards, this method and related algorithms have been successfully used for the
solution of problems related to VRP and its sub-types that are applied in many sectors including
collection/distribution, transportation, military, and emergency services. The VRP is an NP-
complete problem, preventing the use of exact algorithms for certain instances of the problem, and
thus requiring the use of heuristic approaches (Hsu, Hsu & Lin, 2014). For the optimization of these
problems, which always attracted scholarly interest, not only classical heuristic methods such as the
classic saving and sweep method, but also meta-heuristics such as tabu search, simulated annealing,
ant colony, and (GA) have been widely used. GA is a searching and optimization technique that was
introduced by John Holland in 1975 on the basis of Darwin’s theory, “only the best survive”. In
particular, classification optimization problems and multi-dimensional optimization problems that
are quite difficult to solve using conventional programming techniques can be easily and rapidly
solved using GA. In the relevant literature, there are numerous studies in which GA is applied to
solve a VRP. In their study conducted to implement GA to solve SBRP, Sghaier, Guedria, and
Mraihi concluded that the number of vehicles in a school bus network can be reduced by bringing
down the transportation costs (Sghaier, Guedria & Mraihi, 2013).

In the current study, the visual software that was developed using C#.NET programming
language and the GA optimization technique to detect the most suitable and shortest route on the
map for school bus services will be discussed. For this software, 10 of the school bus services’
routes in the Ankara Province in Turkey were used as case studies to apply the GA method to solve
the SBRP. The routes that the school buses follow and the GPS locations of the stops were
determined by means of mobile software and were displayed on Google Maps. The present study
aims to improve currently available routes, and to update these routes online using the instantaneous
GPS locations of the students, tracked down by means of mobile software support. The goal is to
avoid the current time, cost, and work-load losses and to reduce air pollution and traffic density by
improving the routes.

2. VRP and SBRP

2.1. VRP and literature review
VRP is widely described as the process where the distribution vehicles deliver goods in a

depot to the clients found in geographically dispersed locations and then return to the depot on the
optimum route. The VRP, first introduced by Dantzig and Ramser in 1959, aims to minimize the
total distance to be covered during the routing of the vehicles in a centrally-located depot (Dantzig
& Ramser, 1959). The routing process is operated by taking the vehicle capacities into
consideration so as to ensure that each client located on the routing plan is visited only once. The
depot, vehicle, and goods concepts mentioned in the general description of VRP can be re-adapted
as school, student and bus stop, based on different sectors that the problem applies to. Figure 1
shows a scheme indicating the VRP solution applied to a distribution system, where the clientele
network is dispersed over three different zones.

BRAIN – Broad Research in Artificial Intelligence and Neuroscience, Volume 9, Issue2 (May, 2018), ISSN 2067-3957

Figure 1. Example of a VRP solution

VRP, which is one of the NP-Hard types of problems, has been studied for more than fifty

years, and a number of solution models and algorithms have been developed thus far. For the
optimization of this complicated problem, which is not possible to solve using conventional
methods, primarily meta-heuristic techniques were preferred for a more efficient and rapid solution.
The heuristic methods reported in the literature in relation to VRP are normally examined in two
groups: classical methods and meta-heuristic methods. The first known classical heuristic method,
applicable to VRP, is the Classic Saving Method developed by Clarke and Wright in 1964. Later,
the Sweep Method and Improved Petal Heuristic methods were introduced by Gillet and Miller
(Gillet & Miller, 1974), and Foster and Ryan (Foster & Ryan, 1976), respectively. Among the meta-
heuristic methods used for the same purpose, one can list tabu search, simulated annealing, ant
colony, and GA. In particular, a number of metaheuristic techniques have been successfully applied
for the solution of VRP and its variants, such as: simulated annealing (Osman, 1993, Samadi-Dana,
Paydar & Jouzdani, 2017), tabu search (Gendreau, Hertz & Laporte, 1994, Taillard, Badeau,
Gendreau, Gendreau & Potvin, 1997), granular tabu search (Toth & Vigo, 2003), GA (Van
Breedam, 1996), guided local search (Kilby, Prosser & Shaw, 1999), variable neighborhood search
(Bräysy, 2003), greedy randomized adaptive search procedure (Resende & Ribeiro, 2003),
differential evolution algorithm (Teoh, Ponnambalam & Kanagaraj, 2015) and ant colony
optimization (Reimann, Doerner & Hartl, 2004, Yigit & Unsal, 2016).

Today, various studies aim to solve a VRP in many sectors including the distribution of
cargo, newspapers, milk, bread, mail and posts, as well as medical and chemical waste collection
systems, and personnel and school busses. All of these examples have their own limitations and
criteria, such as quality of the transported material, and the last stop to reach, as well as the stop
from which the route will begin (for example, in the case of school bus services, the last stop in the
morning and the first stop in the evening is the school), necessity to reach a certain stop before the
others (cargo sent by a client to another). These limitations should be taken into consideration in the
algorithms implemented to create solutions to the problems.

The objective of VRP is to determine a set of conditions such that (Çatay, 2010):
 Each vehicle travels exactly one route.
 Each customer is visited only once by one of the vehicles completely satisfying its demand

and supply.
 The load carried by a vehicle between any pair of adjacent customers on the route must not

exceed its capacity.
 Total distance given by the sum of the arcs belonging to these routes is minimal.
 Vehicle routes starting and ending point must be the central distribution warehouse.

The mathematical description of general VRP was made by Laporte as given below
(Laporte, 1992):

Ö. Ünsal, T. Yiğit - Using the Genetic Algorithm for the Optimization of Dynamic School Bus Routing Problem

Let G = (V, A) be a graph where V = {0 . . . . , n} is a set of vertices representing cities with
the depot located at vertex 0, and A is the set of arcs.

According to this description, the objective function of VRP is as follows:

where Cij is the matrix expressing the distance between each arc (i,j) node, while i≠j. Cij represents
the time, cost or distance parameter that should be minimized in the objective function (Arias-
Rojas, Jiménez & Montoya-Torres, 2012). For a classical VRP, the Euclid equation shown in
equation number 2 is used to calculate the distance between i and j nodes having certain x and y
coordinates

In a classic VRP, d(i,j) is assumed to be the same as d(j, i).
Xij, as shown in equation number 3, stands for a logical variable, whose value varies based on
whether arc(i,j) is found in the optimum solution set.

2.2. Dynamic school bus routing problem(DSBRP)
SBRP, which is a sub-group of VRP, is defined also as a kind of travelling salesman

problem. The SBRP includes determining the shortest route for a school bus to pick up all the
students from the pre-determined stops and to take them to school, and to pick the students up from
school and leave them at the pre-determined stops. The first studies regarding SBRP were carried
out by Newton and Thomas in 1969. In later years, numerous studies were carried out regarding
SBRP. In the studies conducted by Spada et al. in 2005, meta-heuristic methods were applied to
SBRP and a decision-making model was developed (Spada, Bierlaire & Liebling, 2005).
Fügenschuh carried out a study in 2009 on school bus route planning in Germany, and concluded
that fewer school busses would be needed if schools started their daily schedule at different times
(Fügenschuh, 2009). In their study dated 2010, Park and Kim carried out an extensive examination
of different types of SBRP and a wide literature review (Park & Kim, 2010). Martinez and Viegas
carried out a study in 2011 to examine the specific case of the students in Lisbon using school bus
service, and exhibited a two-step approach towards the solution of SBRP. In the first step, they
collected information regarding the geographical locations of the students, and assigned these
locations to different school busses in the most ideal way. In the second step, the most convenient
routes were planned for the identified vehicles (Martínez & Viegas, 2011). In the studies conducted
by Samadi-Dana et al. in 2017, a robust optimisation model for SBRP with uncertainty in times
associated with moving from one bus stop to another is developed and a solution methodology
based on simulated annealing algorithm, is presented for solving the proposed model (Samadi-
Dana, Paydar & Jouzdani, 2017). Although a number of studies focusing on SBRP can be found in
the relevant literature with a variety of purposes, the following issues appear as the most frequent
goals:

 To minimize costs associated with transportation
 To minimize time spent on transportation (Corberán, Fernández, Laguna & Martí, 2002)
 To minimize the total number of vehicles used for transportation
 To identify the stops where the students are taken and dropped off (Thangiah, Bryan,

Anthony & William, 2008)
This problem consists of a number of sub-problems. The problem is solved in five steps

(Park & Kim, 2010).
 Data preparation

BRAIN – Broad Research in Artificial Intelligence and Neuroscience, Volume 9, Issue2 (May, 2018), ISSN 2067-3957

 Selection of stops
 Route development
 Scheduling school bell
 Route planning

In the data preparation step, the addresses of the school and the students as well as the

existing roads between these are determined. In the second step, the student addresses are assigned
to different stops. In the third step, the route is planned for a single school. If the solution is to be
made for more than one school, then the school bells are scheduled for each school, and in the fifth
step the route is planned for all schools.
VRP’s can also be classified into two categories as dynamic and static routing problems. In
the static VRP’s, the stops/locations that the vehicle will visit are pre-specified and do not change
during the distribution/collection process. In dynamic VRP’s, on the other hand, new stops can be
added to the planned route during the process or certain stops can be omitted. In similar dynamic
problems, some or all of the access points are not known in the beginning. These points are
dynamically defined during the route design or planning stages. In the dynamic VRP, using a real-
time communication network between the vehicle and decision-making system, the vehicle routes
can be re-defined during the operation. This type of problems is defined as online or real-time
problems by some scholars (Pillac, Gendreau, Guéret & Medaglia, 2013). Two examples of this can
be certain orders getting cancelled or new orders being taken while a water distribution vehicle is on
its route, or a school bus being informed on its route that certain students will be absent from school
that day. In current conditions, dynamic VRP’s are more frequently needed, and are attributed with
a more specific importance. The first study dealing with dynamic VRP was carried out by Wilson
and Colvin (Pillac, Gendreau, Guéret & Medaglia, 2013). The enhancements in GPS, traffic
sensors, and mobile communication systems caused a further acceleration in studies carried out in
this field. Within the context of this study, DSBRP will be investigated. DSBRP is graphically
explained in Figure 2.

Figure 2. A dynamic school bus routing case

In the previous sections, a number of heuristic methods that are applicable to VRP were

mentioned. In this study, school bus route distances (Cij) were optimized for the VRP objective
function using GA. In the mathematical formulation of the problem, the vehicles represented as the
set V correspond to the school busses, the central distribution depot represented as Vo to the school,
the connections represented as set A to the routes between students’ houses and the school, and
finally the clients to the bus stops.

3. Solving DSBRP with GA
3.1. Genetic algorithms (GAs)
GAs, which are based on the evolutionary approach method in the nature, are a meta-

heuristic technique used in the solution of searching and optimization problems. GAs were

Ö. Ünsal, T. Yiğit - Using the Genetic Algorithm for the Optimization of Dynamic School Bus Routing Problem

recognized as an important technique for optimization after the doctorate dissertation of Goldberg,
where the use of a GA was proposed for the purpose of gas pipeline checks, and then the publication
of the book entitled “Genetic Algorithms in Search, Optimization, and Machine Learning” in 1989
(Goldberg, 1989). GAs are mostly used for the solution of the problems, where a mathematical
model cannot be constructed, the solution domain is too large and there are an extremely high
number of factors affecting the problem. Therefore, they are successfully applied to the solution of
quite complicated problems such as scheduling, assignment, travelling salesman, network design,
logistics, and school service routing.

GAs assess not a single solution, but a multiple number of solutions simultaneously. This
characteristic is called the GA’s parallel search feature. Since GAs that provide the opportunity to
work with a high number of parameters form the solution space through binary coding the variables’
values, they do not require theoretical information regarding the problem. GAs work on a
population composed of different chromosomes corresponding to different eventual solutions to a
given problem (Mohanta, Parhi & Patel, 2011). The costs of GAs associated with problem solving
are lower than that of other heuristic methods, and their flowcharts are simpler. They do not scan the
whole solution space, but only a specific part of it. Through this more effective way of searching,
they reach a solution more rapidly. Another advantage of this method is that they can
simultaneously examine the population composed of different solutions, and therefore they can skip
local best solutions (Goldberg, 1989).

GA Characteristics:

 They aim to access better points through the random points selected from the solution space
by means of operators;

 They use only function values instead of derivative information;
 They use the codes of the variables in the binary system, instead of the variables themselves;
 They use probabilistic rules instead of deterministic ones while producing new solutions

(Goldberg, 1989).
A simple GA follows the solution steps given below:

Determine iteration number and population size
Start with a random initial population

For each iteration
Calculate the conformity value for each individual in the population
Apply selection, crossover and mutation operators
Update population

Show best solution

Due to intrinsic features, GA eliminates the bad individuals, i.e. unsuitable solutions, thanks

to the operators. GA stops searching for a solution either when the selected conformity value is
obtained, or a better solution cannot be produced or the selected number of iterations is performed.

3.2. Implementation of GA to DSBRP
In the previous section, the steps required for DSBRP were listed as data preparation,

selection of stops and route planning. In this section, these steps will be enlightened with more
details and the manner in which school bus routes are formed using GA will be explained.

For the route that is aimed to be planned, N number of bus stops was selected. Therefore, V=
{0,1,…..,N}. The school is denominated as V0 and VN during the evening and morning hours,
respectively. The roads connecting the school and bus stops are shown as set A, and the problem
was defined so that G=(V,A). Distances between the school and bus stops were calculated and Cij
matrix was formed. In this study, the actual distances between different points were calculated using
the GPS (lat, lng) locations of bus stops.

BRAIN – Broad Research in Artificial Intelligence and Neuroscience, Volume 9, Issue2 (May, 2018), ISSN 2067-3957

The distance optimization needed for the formation of the objective function that can be seen
in equation number 1 was done using GA operators and parameters. The flowchart that can be seen
in Figure 3 shows how the school bus routes are formed using GA.

Figure 3. The flow diagram of the SBRP solution by using GA

3.2.1 Data preparation
In this study, the existing school bus routes and the GPS locations (lat, lng) of the related bus

stops and the school were collected using mobile software and recorded in a database.

Ö. Ünsal, T. Yiğit - Using the Genetic Algorithm for the Optimization of Dynamic School Bus Routing Problem

3.2.2 Bus stop selection
In order to ensure a dynamic assessment of the problem, route planning was performed not

for all the students using the school bus, but only for selected bus stops. Moreover, the change of the
initial and final stops in the morning and in the evening was also taken into consideration.

3.2.3 Forming the route with GA
Parameters
The following parameters were used for the solution of the problem: number of iterations,

population size, crossover size, cross-breeding and mutation possibility and whether the school is
the initial or final stop of the route.

Coding
Each chromosome found in the population formed in the GA is structurally an equal-length

coded series. The chromosomes are made of genes. For coding purposes, binary, permutation, and
value coding methods are widely used. In the travelling salesman or other similar VRPs,
permutation coding technique is preferred over the other techniques. Using the permutation coding
technique, each chromosome found in the population is expressed in terms of the numbers of each
stop to be followed in the route, as shown in Figure 4.

Figure 4. Example of a chromosome structure with permutation coding

Creating Initial Population
A solution space compatible with a given population size is formed at the beginning of a GA

procedure. Each chromosome found in the solution space represents a potential solution. The initial
population can be randomly formed, without depending on any rules; however, it can also be formed
applying certain rules established based on the nature of the problem. For SBRP, the initial
population is formed in a random fashion, paying extra attention to the following two limitations:

 The genes (bus stops) in the chromosomes (route) should not repeat themselves; and
 The initial and final stops of the obtained solution should be constant.

In the randomly produced solutions, it is possible that the genes in the chromosomes are
repetitive. However, since in SBRP the school service should call at each bus stop once, the
chromosomes were formed accordingly. In the SBRP, the school is the initial point in the mornings,
while it is the final point in the evenings. This principle was used to fix the initial and final stops
depending on the time of the solution. In the exemplary chromosome given in Figure 4 (route), the
stop represented by a 0 is the school and since this route was formed for the morning hours, 0 is the
last gene.

Fitness function
For each chromosome in the population, a compatibility function depending on the structure

of the problem is calculated. In the solution space, the chromosomes with higher compatibility
functions are more likely to be selected and passed down to the next generation. For this problem,
the compatibility function for each chromosome found in the population was calculated as the total
length of the established route (L), as shown in equation number 4. While calculating this distance,
the Cij matrix was used.

Selection and crossover
After calculating the compatibility functions of the chromosomes in the population, the

crossing over is conducted to produce new individuals. The selection process identifies the families
that should participate in the production of new individuals for the following generation (Goldberg,

BRAIN – Broad Research in Artificial Intelligence and Neuroscience, Volume 9, Issue2 (May, 2018), ISSN 2067-3957

1989). In the GA, roulette wheel, elitism, tournament, and consecutive selection methods can be
used. In the selection mechanism, the individuals passed down from the previous generation
occasionally cannot produce a better individual. In that case, the compatibility of the individuals
might worsen, while producing the exact opposite is what is expected. To avoid this, the elitism
operator is used and it is ensured that the best individual of the previous generation is passed down
to the next generation, even though the current population is diminishing on an overall basis as a
result of the production operators (Goldberg, 1989). In the current study, the consecutive selection
method and elitism selection were preferred. For this aim, after calculating the compatibility
function, the population was ranked according to the population function values (total route length).
In case the crossover possibility is realized, the number of individuals to select will be determined
according to the parameter related to the crossover size. To ensure a high level of variability in the
generation, it is suggested that this possibility is taken as 50% and 95% (Goldberg, 1989). The
crossover process allows the production of a new individual using the genes taken from two
individuals, based on the selected crossover method. In this study, a single point crossover method
was selected. During the crossing over, limitations that were previously mentioned regarding the
formation of a new initial population were taken into consideration. The identified initial or final point
was fixed and kept out of the context of crossing over. An example of crossover can be seen in Figure 5.

Figure 5. Crossover process

Mutation
The individuals obtained at the end of crossing over might not provide the desired level of

variability. In that case, the produced individuals are mutated independently from another individual
in such a way that their own gene sequence will change. The mutation process is performed in the
event that the mutation possibility that is specified in the beginning comes true. The results obtained
from mutation can enhance the outcome or make it worse. It is of utmost importance to specify the
most suitable mutation possibility. This possibility should be high enough to prevent the method
from becoming stuck at a local point, but at the same time, low enough to allow the best results
produced by crossing over and multiplexing. In this study, the mutation possibility was selected as
10%, and the locations of two randomly selected bus stops were changed during the mutation
process. As in the crossing over, also during this process, the limitations regarding producing a new
individual (route) were adapted. Figure 6 shows an example to mutation process.

Ö. Ünsal, T. Yiğit - Using the Genetic Algorithm for the Optimization of Dynamic School Bus Routing Problem

Figure 6. Mutation process

4. Developed software and experimental results
For this study, the school bus routes within the Ankara Province were used as case studies.

The school bus routes were recorded by using the Android application and instantaneous GPS
monitoring method. The home address of each student was taken as a stopping point. At the end of
each route, the distances between the beginning and end points were recorded. After transferring the
obtained route data into the database, the ill-adapted points were eliminated.

By means of the developed application, the existing school bus routes are dynamically
optimized using GA. It was developed both as a mobile and desktop application. Using Android-
based mobile software, the information regarding GPS locations of bus stops and school buses is
transferred to the server on a real-time basis. Using the desktop software, where GAs are run, these
coordinates are shown on a Google map, and the most suitable route is produced and sent to the
school bus via server. This method provides the opportunity to dynamically reflect certain factors
such as a different initial point for the school bus, some students being absent from the school on a
particular day, and eventual changes on the existing roads on the route production process.

Figure 7. Application main form which includes route, bus stops and GA parameters

The application was developed using C#.NET programming language. In order to store the

planned route and points at the route, on the other hand, a SQLite database was used. In this
application, GMap.NET was added to locate the routes on Google Maps. The coordinates, as well as
latitude and longitude values of each point on the route, were recorded in the database. Figure 7
shows the main form, where the routes are produced; bus stops are added to/deleted from the routes,

BRAIN – Broad Research in Artificial Intelligence and Neuroscience, Volume 9, Issue2 (May, 2018), ISSN 2067-3957

the locations of the bus stops belonging to a given route are loaded in the bus stops’ list and on a
map, and the bus stops for which one desires to produce a solution are selected and GA parameters
are defined.

When the main form is loaded for the first time, the route records in the database are
uploaded in the routes list, while the locations of the bus stops found in the active route are
uploaded in the bus stops’ list and on the map together with their names, numbers, and GPS
locations. The area that can be seen on the map is adjusted in such a way that the uploaded stops are
located in the center. In order to add a bus stop to the selected route, the add bus stop option is
clicked, and after the name of the bus stop is typed, the location of the bus stop is clicked twice.
When a bus stop existing in the database is desired to be deleted, on the other hand, the location of
that particular bus stop is clicked on the map, while the delete bus stop option is on. The bus stops
that are desired to be included in the solution should be signed. After making the bus stop selection,
number of iterations, population size, crossover size, and crossover and mutation rates are entered
using the section where the GA parameters are defined. The parameter values for the developed
application are given in Table 1.

Table 1. Application default GA parameters

During the route planning, school is the initial point if the students are going home from

school, whereas it is the final point if they are going to the school from their homes. The application
provides the opportunity to fix not only the school, but also the bus stops as initial or final points.
Since the authors hope to develop a routing solution for more than one school in a future study, both
the initial and final bus stops were given the opportunity to be selected so that the school bus can
complete distribution/collection duties for one school and can go to another school for routing.
When these selections are made, the initial and final genes of the chromosomes produced in the
population were fixed through these selections. When the TSP option is on, on the other hand, the
school bus returning to the initial point after completing the distribution/collection duties is
included in the routing process. The information regarding solutions, route distances and the
number of iterations produced after all the parameters are defined and the relevant selections are
made are listed as shown in Figure 8. Under the solutions list, total crossover, total number of
mutations, and algorithm working times are shown.

Parameter Default Value
Iteration number 1000
Population size 1000
Crossover size 200

Crossover probability 90%
Mutation probability 10%

Ö. Ünsal, T. Yiğit - Using the Genetic Algorithm for the Optimization of Dynamic School Bus Routing Problem

Figure 8. Listing of obtained solutions after running GA on the route

When the solution that is desired to be viewed is double clicked, the connections between
bus stops are drawn in turn, and the route is shown as can be seen in Figure 9.

Figure 9. Step by step drawing of the selected route solution

The GA procedure was carried out using the parameter values that can be seen in Table 1,

for a total of 10 school bus services’ routes identified by means of mobile-based software for a
school located in the Ankara Province. The obtained experimental results are shown in Table 2 and
Figure 10.

The algorithm working duration also includes the formation of a distances’ matrix.

BRAIN – Broad Research in Artificial Intelligence and Neuroscience, Volume 9, Issue2 (May, 2018), ISSN 2067-3957

Table 2. Obtained experimental results
Information of the collected routes Results of GA
No Number of

bus stop
Distance

(km)
Best distance
obtained (km)

Iteration
number

Running time
(sec)

Optimization
rate (%)

1 16 17.85 15.64 321 0.468 12.38
2 17 18.45 15.90 231 0.496 13.82
3 16 17.11 14.45 701 0.424 15.55
4 12 11.16 10.84 26 0.376 2.87
5 7 7.01 6.98 8 0.294 0.42
6 11 14.47 10.43 248 0.370 27.92
7 10 6.73 4.21 18 0.328 37.44
8 12 16.84 11.79 23 1.227 29.98
9 17 17 14.72 606 7.46 13.41
10 13 15 11.69 167 7.35 22.07

The obtained experimental results showed that the distances can be better optimized with an

increasing number of bus stops, and a better solution was obtained for those routes, where the
school was fixed as either an initial or a final point. At the end of the optimization studies carried
out using GA on the routes of a school bus fleet composed of 10 vehicles, whose total daily route
distance is 141.62 km, the total distance to cover was reduced up to 116.65 km, which corresponds
to an improvement of approximately 17.63%. According to these results, the 25491.6 km-distance,
which is normally covered in one school year (180 day) using the existing routes, can be reduced to
20997 km. Therefore, it is estimated that a cost saving of 4494.6 km can be achieved.

Figure 10. Obtained experimental results

Based on the results obtained from the application, it can be concluded that existing route
distances can be successfully optimized using GA. As mentioned also in the previous sections, the
traffic density can be reduced by means of shorter route distances. It will, therefore, be possible also
to reduce the time spent in traffic, as well as the adverse effects of air pollution due to traffic. In
addition to these, the fuel costs can be considerably reduced by means of route optimization studies.

Ö. Ünsal, T. Yiğit - Using the Genetic Algorithm for the Optimization of Dynamic School Bus Routing Problem

5. Conclusions
Transport and distribution systems are needed in every field of the daily life. When these

systems are not managed properly, they can start causing additional costs, environmental pollutions,
and time loss. VRPs are complicated problems with a considerable number of sub-branches that
become increasingly more important, parallel to the technological advancements. With suitable
routing, costs, time, and workload losses and environmental pollution can be significantly reduced.
Thanks to today’s technological means, the routing studies can be carried out dynamically and more
effective solutions can be developed.

In the present study, GA was used for the optimization of DSBRP, which is a sub-branch of
VRP. The developed application was tested on existing school bus routes in the Ankara Province. It
was clearly seen that the application helped achieve successful results in the optimization of school
bus routes. Based on the results obtained for the sample routes, it was concluded that the total
distance to cover can be improved by 17.63%. Thanks to the mobile-support feature of the
application, real-time solutions can be obtained. A future study is planned to initially distribute the
students according to the capacities of school busses, and to carry out the routing process for a
school bus network serving more than one school. In addition, to solve the problem, applying
different artificial intelligence techniques such as particle swarm optimization are considered.

References
Arias-Rojas, J.S., Jiménez, J.F. & Montoya-Torres, J.R. (2012). Solving of school bus routing

problem by ant colony optimization, Revista EIA, 17, 193-208.
Bräysy, O. (2003). A reactive variable neighborhood search for the vehicle routing problem with

time windows, INFORMS Journal on Computing, 15(4), 347–368.
Corberán, A., Fernández, E., Laguna, M. & Martí, R. (2002). Heuristic solutions to the problem of

routing school buses with multiple objectives, Journal of the Operational Research Society,
53(4), 427-435.

Çatay, B. (2010). A new saving-based ant algorithm for the Vehicle Routing Problem with
Simultaneous Pickup and Delivery, Expert Systems with Applications, 37, 6809–6817.

Dantzig, G. B. & Ramser, J.H. (1959). The Truck dispatching problem, Management Science, 6(1),
80-91.

Foster, B.A. & Ryan, D.M. (1976). An Integer programming approach to the vehicle scheduling
problem, Operational Research Quarterly, 27(2), 367-384.

Fügenschuh, A. (2009). Solving a school bus scheduling problem with integer programming,
European Journal of Operational Research, 193(3), 867-884.

Gendreau, M., Hertz, A. & Laporte, G. (1994). A tabu search heuristic for the vehicle routing
problem, Management Science, 40(10), 1276–1290.

Gillet, B. & Miller, L. (1974). A Heuristic algorithm for the vehicle dispatch problem, Operations
Research, 22(2), 340-349.

Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and machine Learning,
Addisson-Wesley, Reading, MA.

Hsu, L., Hsu, C. & Lin, T. (2014). An Intelligent Artificial System: Artificial Immune based Hybrid
Genetic Algorithm for the Vehicle Routing Problem, Applied Mathematics & Information
Sciences, 8(3), 1191-1200.

Khouadjiaa, M.R., Sarasolab, B., Albab, E., Jourdana, L. & Talbia, E.G. (2012). A comparative
study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic
requests, Applied Soft Computing, 12, 1426–1439.

Kilby, P., Prosser, P. & Shaw, P. (1999). Guided local search for the vehicle routing problem, Meta-
heuristics: advances and trends in local search paradigms for optimization, 473–486, Kluwer
Academic, Boston.

Laporte, G. (1992). The Vehicle Routing Problem: An overview of exact and approximate
algorithms, European Journal of Operational Research, 59, 345-358.

BRAIN – Broad Research in Artificial Intelligence and Neuroscience, Volume 9, Issue2 (May, 2018), ISSN 2067-3957

Martínez, L.M. & Viegas, J.M. (2011). Design and deployment of an innovative school bus service
in Lisbon, Procedia - Social and Behavioral Sciences, 20, 120-130.

Mohanta, J.C., Parhi, D.R. & Patel, S.K. (2011). Path planning strategy for autonomous mobile
robot navigation using Petri-GA optimisation, Computers and Electrical Engineering, 37,
1058–1070.

Oanh, N.T.K., Kongpran, J., Hang, N.T., Parkpian, P., Hung, N.T.Q., Lee, S.B. & Bae, G.N. (2013).
Characterization of gaseous pollutants and PM2.5 at fixed roadsides and along vehicle
travelling routes in Bangkok Metropolitan Region, Atmospheric Environment, 77, 674-685.

Osman, I.H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle
routing problem, Annals of Operations Research, 41, 421–451.

Park, J. & Kim, B. (2010). The school bus routing problem: A review, European Journal of
Operational Research, 202, 311–319.

Pillac, V., Gendreau, M., Guéret, C. & Medaglia, A.L. (2013). A review of dynamic vehicle routing
problems, European Journal of Operational Research, 225, 1–11.

Reimann, M., Doerner, K. & Hartl, R.F. (2004). D-ants: savings based ants divide and conquer the
vehicle routing problem, Computers and Operations Research, 31(4), 563-591.

Resende, M.G.C. & Ribeiro, C.C. (2003). Greedy randomized adaptive search procedures,
Handbook of metaheuristics, 219-249, Kluwer Academic, Boston.

Rushton, A., Croucher, P. & Baker P. (2006). Handbook of Logistics and Distribution Management,
3rd Edition, Kogan Page, London.

Samadi-Dana, S., Paydar, M.M. & Jouzdani, J. (2017). A simulated annealing solution method for
robust school bus routing, International Journal of Operational Research, 28(3), 307–326.

Sghaier, B.S., Guedria, B.N. & Mraihi, R. (2013). Solving school bus routing problem with genetic
algorithm, In Advanced Logistics and Transport (ICALT), 2013 International Conference on
IEEE, pp 7-12.

Spada, M., Bierlaire, M. & Liebling, T.M. (2005). Decision-aiding methodology for the school bus
routing and scheduling problem, Transportation Science, 39(4), 477-490.

Taillard, È.D., Badeau, P., Gendreau, M., Gendreau, F. & Potvin, J.Y (1997). A tabu search
heuristic for the vehicle routing problem with soft time windows, Transportation Science, 3(2),
170-186.

Teoh, B.E., Ponnambalam, S.G. & Kanagaraj, G. (2015). Differential evolution algorithm with local
search for capacitated vehicle routing problem, International Journal of Bio-Inspired
Computation, 7(5), 321-342.

Thangiah, S.R., Bryan, W., Anthony, P. & William, M. (2008). School Bus Routing in Rural School
Districts, Computer-aided Systems in Public Transport, 600, 209-232.

Toth, P. & Vigo, D. (2003). The granular tabu search and its application to the vehicle routing
problem, INFORMS Journal on Computing, 15(4), 333–346.

Van Breedam, A. (1996). An analysis of the effect of local improvement operators in genetic
algorithms and simulated annealing for the vehicle routing problem, RUCA Working Paper,
96/14, University of Antwerp, Belgium.

Yigit, T. & Unsal, O. (2016). Using the ant colony algorithm for real-time automatic route of school
buses, International Arab Journal of Information Technology, 13(5), 559-565.

Dr. Özkan ÜNSAL received his BS degree in 2008 and MS degree in 2011
from Gazi University, Turkey in the field of computer education. He received
PhD degree in 2017 from Süleyman Demirel University, Turkey in the field of
computer engineering.
His current research interests include machine learning, artificial intelligence,
optimization, vehicle routing and software technologies.

Ö. Ünsal, T. Yiğit - Using the Genetic Algorithm for the Optimization of Dynamic School Bus Routing Problem

Dr. Tuncay YIĞIT received his BS degree in 1997, MS degree in 2000 and
PhD degree in 2005 from Gazi University in Turkey in the field of electric
education. Between 1998 and 2006, he worked as a Lecturer in the Department
of Computer Education, Gazi University, Turkey. Since 2007, he is working as
a professor in the Department of Computer Engineering, Süleyman Demirel
University, Turkey.
His current research interests include artificial intelligence, optimization,
distance education, software technologies and computer systems.