DESIGN AND
IMPLEMENTATION OF A TRANSPORT SYSTEM USING SEARCH ALGORITHM
CHAPTER ONE
INTRODUCTION
1.0
Introduction
Transportation is a basic
requirement for every nation, regardless of its industrial capacity,populationsize
or technological development. The Nigerian transport systems, right from
inception, were poorly designed and are unable to scale up to meet greater demand,
a design flaw which causes traffic congestion on roads, overstressed railways,
faltering airfields, and mass-transport blind spots (Igwe, 2010).
Comparative
analysis of three basic search algorithms that can optimize the transport
system is the primary objective of this research work. This explains why we the
researchers have decided to carry out research on this topic “Transport System using Search Algorithms” and
finally implement a novel search algorithm which is most suitable for a transport
system.
In the proposed system, we are going to apply the concept of a novel
search algorithm to optimize transport system. Traditional transport systems have
proved inefficient in that it involves more time and cost.
1.1
Background
of Study
An
algorithm is a set of instructions which describes how to solve a problem.A
search algorithm takes a problem as input and returns the solution in the form
of an action sequence. Once the solution is found, the actions it recommends
can be carried out. As far as search algorithm is concerned, it is a global
problem solving mechanism in Artificial Intelligence (AI). Search algorithms
are used for a multitude of Artificial Intelligence tasks, one of them is path
finding. Artificial Intelligence area of search is very much connected to
problem solving. Artificial Intelligence has investigated search methods that
allow one to solve path planning problems in large domains; having formulated
problems we need to solve them and it is done by searching through the state space.
During this process a search tree is generated by taking initial state and
applying the successive function to it. Most of the researches on search
methods have studied how to solve one-shot path-planning problems. Search is
mostly a repetitive process therefore many Artificial Intelligence systems
replan from scratch and it solves the path planning problem independently. The
problem becomes more severe when changes occur during planning, fortunately,
the changes to the path planning problems are usually small.
Heuristic
search methods promise to find the shortest path for path planning problems
that are faster than uniformed search methods. On the other hand incremental
search methods promise to find shortest path for series of similar path
planning problem faster, which is possible by solving each path planning
problem from scratch.Travel planning is now becoming a vast field and for the
economy of any country, it plays vital role.Artificial intelligence is playing
a major role in this field. Many travel planners using heuristic and uniformed
algorithms are giving better results than the ordinary travel planners. Both
search and graph Artificial Intelligence algorithms are used in travel planning
which makes any travel planner user friendly and time saving.
In
this research work, the main subject has been the search algorithms used in the
travel planning search for better routes, destination and transport system
enabling the customer to build his best travel plan for his desired trip,
however, we will confine ourselves to three basic search algorithms which are
Depth first search algorithm, Breadth first search algorithm and hill climbing
search algorithm.Breadth first search is a general technique of traversing a
graph. It may usemore memory but will always find the shortest path first.In
this search a queue data structureis used and it is level by level traversal.
Depth first search (DFS) is an important type of uniform or blind search. DFS
visits all the vertices in the graph. This type of algorithm always chooses to
go deeper into the graph. Hill climbing search algorithm is simply a loop that
continuously moves in the direction ofincreasing value, which is uphill. It
stops when it reaches a “peak” where no neighbour has ahigher value. The hill
climbing comes from that idea that if you trying to find the top of the hilland
you go up direction from where ever you are.
1.2
Statement
of the Problem
Ample facilities like
road infrastructure, appropriate vehicles for the right place and right time is
a crucial factor in determining the quality of transport system. For a developing country like Nigeria, this
has always been a great challenge and continues to be so. Owing to the civil
wars, lack of proper investment in the transport infrastructure, low quality of
the transport system, unhealthy transport solutions, improper planning and
increasing number of private cars still
remains a problem. Hence, there is need to optimize our transport system. This
study aims at using a search algorithm to optimize the transport system in
terms of shortest path, speed and efficiency. The search algorithm to be used
will be arrived at after comparatively analyzing three basic search algorithms
namely; breadth first, depth first and hill climbing, after which the best will
be chosen for the optimization of our transport system.
1.3
Aim
and Objectives of Study
The
aim of this research work is to analytically compare depth first, breadth first
and hill climbing search algorithms to determine which is faster in a transport
system with the following objectives;
i. To
determine the best search algorithm for a transport system
ii. To
develop a novel hybrid search algorithm for a transportation system
iii. To
implement the novel hybrid search algorithm using a computer system
1.4
Significance
of the Study
This
research work is of great importance in that it seeks to provide innovative
services relating to different modes of transport and enable various users to
be better informed and make safer, more coordinated and smarter use of transport
networks. Other significances it offers are found in the following areas;
i. It
reduces preprocessing efforts on the path of transport planners
ii. It
showcases the usefulness of algorithms in the field of shortest path finding
iii. It
aids journey planning on transportation systems.
1.5
Scope
of the Study
The scope of this research work is to adopt a novel search
algorithm that is most suitable for a transport system in terms of speed and
efficiency taking a case study of Nigeria. Comparative analysis will be carried
out on the selected search algorithms after which the most suitable search
algorithm will be selected and implemented in the transport system.
1.6
Limitations
of the Study
The
limitations of this study are as follows:
i.
This study will cover road
and air transportation
ii.
This study will not include
sea transportation due to limited time and resources.
1.7
Definition
of Terms
Algorithm: An
algorithm can be seen as a self-contained step by step set of operations to be
performed in order to solve a specific problem.
Search Algorithm: This
is an algorithm used for various tasks such as path finding.
Depth First Search
(DFS): This
is an algorithm
for traversing or searching a tree
or graph
data structures which starts at the root
and explores as far as possible along each branch before backtracking.
Breadth First Search (BFS): is
a graph search algorithm that begins at the root node and explores allthe
neighboring nodesuntil it finds the goal.
Hill Climbing:
It is an iterative algorithm that starts with an arbitrary solution to a
problem, then attempts to find a better solution by incrementally
changing a single element of the solution.
Heuristic: This
is a technique designed for solving a problem more quickly when classic methods
are to slow, or for finding an approximate solution when classic methods fail
to find any exact solution.
Problem Solving: It
is the process of working through the details of a problem to reach a solution.
Deterministic: A
deterministic system is a system in which no randomness is involved in the
development of future states of the system.
Non Deterministic: A
non-deterministic system requires some degree of randomness in the development
of future states of the systems.
Route: This
is a course or a way that is travelled or passed.
Destination: The
place to which a person or thing travels.