DECISION SUPPORT SYSTEM FOR FINDING THE SHORTEST PATH TO A DESTINATION

ABSTRACT

This study is concerned with the design of a Decision Support System for finding the Shortest path to a destination. The objectives of the study is to determine the optimal shortest/fastest path to a given destination or optimal shortest distance/fastest time to a given destination amongst others. The shortest path algorithm used is Dijkstra’s algorithm with finite nodes in the road network for optimum performance. Hence, the system developed in this study, seeks for an optimal solution by decomposing the original problem into several interconnected sub-problems according to hierarchy of decisions as observed in real life i.e. dynamic programming principle. A Shortest path to a destination in a specified road network was illustrated by me, using three different algorithms such as Dijkstra, Bellman-Ford and Backward-recursive algorithms respectively to show their efficiencies/relevance to decision support system for finding the shortest path to a destination within the given road network. The system was designed using object oriented and analysis design (OOAD) methodology and implemented using Netbeans 6.8 IDE on a windows operating system using Java programming language. The study results showed that Dijkstra’s algorithm is more efficient in determination of shortest path on our road networks with finite nodes having non-negative edges.

CHAPTER ONE

1.0     INTRODUCTION

Travelling is part of daily life. The Shortest path (SP) to the given destination therefore becomes inevitable so as to minimize costs, losses in productivity, pollutions, risks etc. Shortest path problem history is difficult to trace back. One can imagine that even in very primitive (even animal societies), finding the shortest paths (for instance, to food, colony) is essential. In the past, when drivers encountered traffic congestions/delays on the road network, they had to queue up and wait until the congestions clears off before continuing in their journeys, but not so today. In recent times, technological advances in operational research and information technology have engineered a new thought to traffic management and control system using several shortest path/path-finding algorithms e.g. Dijkstra, Bellman-Ford, A*, Floyd-Washall, Backward-recursive etc. to evaluating the shortest/fastest path en route embarkation. However, to tackle real life transportation problems today, the problems are reduced to simplified mathematical routing models (i.e. operations research models) embedded in various decision support systems such as Tora, Lingo etc., which can be solved iteratively often times. These decision support systems use dynamic programming principles (that breaks complex tasks into simpler tasks easily solvable). This study illustrates the development of a simple application that runs on dynamic programming principle to show the relevance to decision support system of finding Shortest path to a destination in a road network.

1.1     BACKGROUND OF STUDY

Traffic congestions/bad roads are critical problems experienced daily on our road networks most especially in the urban areas; and thus influences the travel time of vehicles/productivities in cases like ambulance calls, fire service calls, armed robbery attack calls, quick calls for stock supplies at business supermarkets/warehouses etc. The shortest/fastest path to the destination hitherto being inevitable to minimize these costs, losses, risks etc. The shortest path problems uses dynamic programming technology/methodology (i.e. breaking down complex tasks into simpler easy tasks to solve) to finding the shortest path to the destination. There are different types of shortest path problems namely: Shortest path from a node to a node, shortest path from a node to many nodes, shortest path from many nodes to a node and shortest path from many nodes to many nodes in some other few instances. In some applications, the shortest path between two nodes are not necessarily a direct edge but a detour through other traversals. Again, one might require not only the shortest path to a destination but a second and third shortest paths depending on the given occasion/problem.

The major technology used in this study is dynamic programming algorithms (Dijkstra, Bellman-Ford, Backward-recursive) and relational database technology (MySQL). The software developed is a collection of algorithms (a logical step-by-step procedure for solving a mathematical problem in a finite number of steps, often involving repetition of the same basic operations). The algorithms are presented (or rendered visible) to the user, by object oriented programming language (e.g. Java) utilized in the study and also must satisfy the basic properties/characteristics of dynamic programming. The user interface within the application allows interaction between the user and the Decision Support System, which embeds MySQL database instructions required to open the database, establish a connection between the database and the Java language, perform operations such as insert, update, search data etc.

The examples shown in section 3.4 below, illustrates shortest path algorithms (e.g. Dijkstra’s, Bellman etc) which are the solution approaches used in this study.

1.2  STATEMENT OF PROBLEM

Consider a private medical hospital in affiliation to the government and specialized in general medicine. In order to provide fast and efficient patient care services at minimal costs, medical ambulances need to be dispatched promptly to emergent calls from the public.

Today, we have too many health complications including death tolls that result from late arrival of the medical ambulance(s) to callers’ address owing to traffic congestions/delays primarily on the road network.

If the medical hospital will continue to dispatch the medical ambulances same way, they will not only be wasting resources (i.e. time, money etc), which jeopardizes their overall efficiency and earning potentials, but will also enhance undue sufferings/death toll of the public leading to the active customers choosing alternative medical hospitals with better administration and well equipped facilities.

The researcher(s) intend to use Dijkstra’s algorithm to determine the shortest path to the callers’ address. Dijkstra’s algorithm methodology shall be used to evaluate the late arrival of the medical ambulance(s) to the callers’ address and thus provide necessary decision making.

DOWNLOAD PROJECT