Computer Science

Design and Implementation of a Transport System Using Search Algorithm

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, population size, 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 that 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 research this topic “Transport System using Search Algorithms” and finally implement a novel search algorithm that 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 the 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 that 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 pathfinding. The 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 the initial state and applying the successive function to it. Most of the research on search methods has 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 uninformed search methods. On the other hand, incremental search methods promise to find the shortest path for a series of similar path planning problems 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 a 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 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 systems 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 use more memory but will always find the shortest path first. In this search, a queue data structure is 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. The Hill climbing search algorithm is simply a loop that continuously moves in the direction of increasing value, which is uphill. It stops when it reaches a “peak” where no neighbor has a higher value. The hill-climbing comes from the idea that if you trying to find the top of the hill and you go up directly from where ever you are.

1.2 Statement of the Problem

Ample facilities like road infrastructure, appropriate vehicles for the right place, and the right time is a crucial factor in determining the quality of the 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 remains a problem. Hence, there is a need to optimize our transport system. This study aims at using a search algorithm to optimize the transport system in terms of the 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

This research work aims 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 use of algorithms in the field of shortest pathfinding

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 to solve a specific problem.

Search Algorithm: This is an algorithm used for various tasks such as pathfinding.

Depth First Search (DFS): This is an algorithm for traversing or searching a tree or graph data structure that 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 all the neighboring nodes until 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 too 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 traveled or passed.

Destination: The place to which a person or thing travels.



Copyright © 2023 Author(s) retain the copyright of this article.
This article is published under the terms of the Creative Commons Attribution License 4.0