DESIGN AND IMPLEMENTATION OF A TRANSPORT SYSTEM USING SEARCH ALGORITHM

By

Author

Presented To

Department of Computer Science

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