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.

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/productivitites in cases like ambulance calls, fire service calls, armed robbery attack calls, quick calls for stock supplies at business supermarkets/warehourses 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.

1.3  OBJECTIVES OF THE STUDY

The aim of this study is to apply the Dijkstra’s algorithm in finding the shortest path in a road network which can be used for intelligent decision making. The specific objectives include the following:

       i).         To show the user the optimal shortest path to follow from the start location to the destination (i.e. the caller’s address) by using the costs on the edges of the road network sketch (Fig. 3.1) to compute for the optimal shortest path within the decision support system using shortest path algorithms embedded in it.

ii).        To proffer to the user the optimal shortest distance or fastest time it takes to the destination (i.e. callers address) by using the costs on the edges of the road network sketch (Fig. 3.1) to evaluate for the optimal shortest distance or fastest time it takes to the destination within the decision support system using shortest path algorithms embedded in it, which enhances her confidence.

1.4     SIGNIFICANCE OF THE STUDY

The importance of this study is beneficial to the hospital and the entire society in the following ways:

A driver en route embarkation through a traffic congested/bad road network, will be relieved from stress of travelling, costs, losses and other risks, if the driver could access a decision support system that could determine for her the optimal shortest/fastest path or optimal shortest distance or optimal fastest time it would take to her destination. This decision support system illustrated in this study has in-built algorithms (e.g. Dijkstra’s, Bellman-Ford, Backward-recursive) that evaluates the optimal shortest/fastest path, optimal shortest distance, optimal fastest time it would take to the destination by using the costs on the links in the road network sketch (Fig. 3.1) in its evaluations, which guides the driver accordingly en route embarkation through a printed dispatch chart from the decision support system software; to enhance the driver’s confidence and stability whilst on the journey. Again, the decision support system helps in reducing losses (such as saving accident victim lives when a shortest/fastest path to the nearest hospital/medical centre is followed), helps in reducing costs (e.g. vehicle breakdowns via over-heating of the radiators, clutch/break failures etc which often compels the driver to seek for the assistance of road-side mechanics at high costs at traffic congested areas when a shortest/fastest path to the destination is followed) amongst others.

1.5  SCOPE OF THE STUDY

The scope of the study includes an introduction/background of study, shortest path problems, shortest path/path-finding algorithms, dynamic programming methodology/technology, unified modeling language tools (Use case, Flowchart, Class diagram), software architecture (3-tier architecture i.e. the presentation tier, middle tier and database tier) and decision support system (e.g. menus, submenus etc). 

1.6  DEFINITION OF TERMS

There are few basic terms used in the course of the project work which may require our clarification for a better understanding, thence this definition of terms module and may include the following:

i).    DECISION SUPPORT SYSTEM (DSS) is an integration of computer hardware and software that is designed to complement the cognitive processes of humans in their decision making. It can be either fully computerized, human or a combination of both (William, 1985).

ii).   PATHFINDING refers to the plotting by a computer application, of the shortest path/route between two points. It is a field of research that is based heavily on Dijkstra’s algorithm for finding shortest path on a

       weighted graph (http://en.wikipedia.org/wiki/pathfinding).

iii).  DYNAMIC PROGRAMMING is a useful mathematical technique for

       making a sequence of inter-related decisions. In most applications, dynamic programming obtains solutions by working backward from the end of a problem toward the beginning, thus breaking up a large, unwieldy problem into a series of smaller, more tractable problems by forming associated recursive models (Frederick, 2010).

iv).  GRAPH/NETWORK is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices/nodes, and the links that connect some pairs of vertices are called edges/arcs/links. Typically, a graph is depicted in diagrammatic form as a set of dots for vertices, joined by lines or curves for the edges (http://en.wikipedia.org/wiki/Graph).

v).   NODE is a vertex in mathematical graph or a point in network topology at which lines intersect, branch or terminate (http://en.wikipedia.org/wiki/Node).

vi).  ARC or link or edge is an ordered pair of nodes representing possible direction of motion that may occur between nodes or the line that connects a pair of nodes together in a graph (Winston, 2003).

vii). PATH is a sequence of finite/infinite edges which connects a sequence of nodes/vertices (http://en.wikipedia.org/wiki/Path_(graph_theory))

viii).     HISTORIC TRAFFIC MODEL DATA is based on the idea that travel speeds follow a week-long pattern. The expected speeds or data (i.e. historic data) are usually determined by averaging multiple observations of a path over some time span (e.g. such as a year).