AN OPTIMAL ROUTE DETERMINING METHODOLOGY BASED ON DECISION SUPPORT SYSTEM

H.Vignesh Ramamoorthy; B.Sabarigiri

AN OPTIMAL ROUTE DETERMINING METHODOLOGY BASED ON DECISION SUPPORT SYSTEM

H.Vignesh Ramamoorthy^*1, B.Sabarigiri²

Assistant Professor of Computer Science, Sree Saraswathi Thyagaraja College, Pollachi, Coimbatore, Tamil Nadu, India
Research Scholar of Computer Science, PSG College of Arts and Science, Coimbatore, Tamil Nadu, India

Corresponding Author: H.Vignesh Ramamoorthy, E-mail: hvigneshram@gmail.com

Related article at Pubmed, Scholar Google

Visit for more related articles at Journal of Global Research in Computer Sciences

Abstract

Searching an optimal solution for route finding is one of the major functions in GIS. It also provides a strong decision support for finding the optimal route for specified rural area. Here GIS which is referred as data warehouse in which abundant resource are available. This paper mainly analyses the strategies of the specified area, and identifies the problems in routing. Thus provides the solution for making the feasible path from source to destination with the help of routing graph at given time interval. The aim of this paper is to provide an optimal route map for the transport department.

Keywords

GIS, Data Warehouse, Routing, Optimal.

INTRODUCTION

A Decision Support System (DSS) [1][2] is an interactive software system which supports decision making activities and also used to identify and solve the problems. DSS components are classified into Inputs, user knowledge, expertise, output and decision. Spatial Decision Support System (SDSS) which is associated with DSS. SDSS which is interactive software supports five groups of user for solving the spatial problem such as a noise pollution, transportation, route links etc. This SDSS [3] model which help to identify the most effective decision path for transportation. SDSS is also Known as policy support system and it is a combination of Geographic Information System (GIS) and Decision Support System (DSS) GIS which supports the Geographical data and SDSS which involves both spatial and non-spatial information such as transportation, demographics, agriculture, climate, resource management etc.

Characteristics of SDSS are

i. User interactive

ii. Spatial data management and analysis

iii. Problem solving

iv. Spatial modeling capability

v. Visualization

Section II illustrates about different methods used for achieving optimum route. An analysis of the routing problems using GSTP is made in Section III. Solving the problems by identifying the population factors is given in Section IV. Results and Discussions are done in Section V. Section VI concludes this paper.

METHODOLOGY

This section describes some methods which are used for achieving the optimum route.

Spatial Decision Support System

Decision support systems [1][2] are interactive, computer-based systems that aid users in judgment and choice activities. They provide data storage and retrieval but enhance the traditional information access and retrieval functions with support for model building and model-based reasoning. They support framing, modeling, and problem solving. Typical application areas of DSSs are management and planning in business, health care, the military, and any area in which management will encounter complex decision situations. Decision support systems are typically used for strategic and tactical decisions faced by upper-level management decisions with a reasonably low frequency and high potential consequences in which the time taken for thinking through and modeling the problem pays off generously in the long run.

There are three fundamental components of DSSs

Database management system (DBMS): A DBMS serves as a data bank for the DSS. It stores large quantities of data that are relevant to the class of problems for which the DSS has been designed and provides logical data structures (as opposed to the physical data structures) with which the users interact. A DBMS separates the users from the physical aspects of the database structure and processing. It should also be capable of informing the user of the types of data that are available and how to gain access to them.

Model-base management system (MBMS): The role of MBMS is analogous to that of a DBMS. Its primary function is providing independence between specific models that are used in a DSS from the applications that use them. The purpose of an MBMS is to transform data from the DBMS into information that is useful in decision making. Since many problems that the user of a DSS will cope with may be unstructured, the MBMS should also be capable of assisting the user in model building.

Dialog generation and management system (DGMS): The main product of an interaction with a DSS is insight. As their users are often managers who are not computer-trained, DSSs need to be equipped with intuitive and easy-to-use interfaces. These interfaces aid in model building, but also in interaction with the model, such as gaining insight and recommendations from it. The primary responsibility of a DGMS is to enhance the ability of the system user to utilize and benefit from the DSS. In the remainder of this article, we will use the broader term user interface rather than DGMS. While a variety of DSSs exists, the above three components can be found in many DSS architectures and play a prominent role in their structure. Interaction among them is illustrated in Figure 1. Essentially, the user interacts with the DSS through the DGMS. This communicates with the DBMS and MBMS, which screen the user and the user interface from the physical details of the model base and database implementation[2].

Decision support systems (DSS) [1] are a subset of computer-based information systems (CBIS). The general term 'computer-based information systems' is a constellation of a variety of information systems such as office automation systems, transaction processing systems, management information systems and management support systems. Management support systems consist of DSS, expert systems and executive information systems. In the early 1970s, scholars in the CBIS area began to recognize the important roles information systems play in supporting managers in their semi-structured or unstructured decision-making activities. It was argued that information systems should exist only to support decisions, and that the focus of the information systems development efforts should be shifted away from structured operational control to unstructured critical decisions in organizations [3]. Decisions are irreversible and have far-reaching consequences for the rest of organizational life. The importance of effective decision making [2] can never be overemphasized. Decision making is, in effect, synonymous with management.

Geographical Information Systems

Geographical Information Systems (GIS) [4] are computer-based systems that enable users to collect, store, process, analyze and present spatial data. It provides an electronic representation of information, called spatial data, about the EarthÃ¢ÂÂs natural and man-made features. A GIS [5] references these real-world spatial data elements to a coordinate system. These features can be separated into different layers. A GIS system stores each category of information in a separate "layer" for ease of maintenance, analysis, and visualization. For example, layers can represent terrain characteristics, census data, demographics information, environmental and ecological data, roads, land use, river drainage and flood plains, and rare wildlife habitats. Different applications create and use different layers. A GIS [4] [5] can also store attribute data, which is descriptive information of the map features. This attribute information is placed in a database separate from the graphics data but is linked to them. A GIS allows the examination of both spatial and attribute data at the same time. Also, a GIS lets users search the attribute data and relate it to the spatial data. Therefore, a GIS can combine geographic and other types of data to generate maps and reports, enabling users to collect, manage, and interpret location-based information in a planned and systematic way. In short, a GIS can be defined as a computer system capable of assembling, storing, manipulating, and displaying geographically referenced information. GIS systems are dynamic and permit rapid updating, analysis, and display. They use data from many diverse sources such as satellite imagery, aerial photos, maps, ground surveys, and global positioning systems (GPS).

GIS [4] in essence is an applied science, and it is believed that while the GIS vendor community, hardware and software vendors, provide us with newer, better and faster technological tools, it is in the end, the domain specialists applying the tool that define state-of-the-art. The heartbeat of GIS [5] still lies in the field and district offices, the logging divisions, the engineering offices, and with the small GIS entrepreneurs in offices everywhere who will be applying this technology in their field of work. A geographic information system (GIS) [5] is a computer-based tool for mapping and analyzing spatial data. GIS technology integrates common database operations such as query and statistical analysis with the unique visualization and geographic analysis benefits offered by maps. These abilities distinguish GIS from other information systems and make it valuable to a wide range of public and private enterprises for explaining events, predicting outcomes, and planning strategies. GIS is considered to be one of the most important new technologies, with the potential to revolutionize many aspects of society through increased ability to make decisions and solve problems. Map making and geographic analysis are not new, but a GIS [4] performs these tasks better and faster than do the old manual methods. And, before GIS technology, only a few people had the skills necessary to use geographic information to help with decision making and problem solving.

Transportation Management System

Transportation Management System refers to a category of software that deals with the planning and execution of the external physical movements (transportation) of products across supply chains. Various subcomponents/ features of a typical TMS [6] can be categorized broadly into three categories, namely (Figure 2):

Planning and Optimization

Execution

Visibility and Performance Management

TMS delivers the following benefits. By providing visibility of the consignment through a track-and-trace mechanism to customers and the service provider, a TMS enables better service levels which directly have an impact on key supply chain indicators such as Fill-Rate, Order Fulfillment. By providing a single point to track performance of service providers, it makes it easier for Logistics organizations to manage 3PLs better and to rate their performances. In countries where road transportation is based on managing with significant number of „spot marketÃ¢ÂÂ freight, this system allows capture of information and hence better coordination. A TMS [6] enables load consolidation by providing visibility to all the loads that are emanating from/to a particular location. Since freight rates are usually based on Full Loads or Part Loads, this has a direct impact on profitability for a 3PL and reduced costs for a Logistics Organization.

A transportation management system (TMS) is a subset of supply chain management concerning transportation operations and may be part of an enterprise resource planning system. TMS [6] consist of three key processes such as:

Planning and decision making: TMS will define the most efficient transport schemes according to given parameters, which have a lower or higher importance according to the user policy: transport cost, shorter lead-time, fewer stops possible to ensure quality, flows regrouping coefficient, etc.

Transport follow-up: TMS will allow following any physical or administrative operation regarding transportation: traceability of transport event by event, editing of reception, custom clearance, invoicing and booking documents, sending of transport alerts.

Measurement: TMS have or need to have a logistics key performance indicator (KPI) reporting function for transport.

Various functions of a TMS [6]

i) Planning and optimizing terrestrial transport routes.

(iii) Tracking of real time vehicles

(iv) Service quality control

(v) Vehicle Load and Route optimization

(vi) Transport costs and scheme simulation

(vii) Shipment batching of orders

(viii) Cost control, key performance indicator (KPI) reporting and statistics.

ANALYSIS USING GSTP

Routing problem plays a major role in rural areas for finding an optimal route from source to destination on a roadmap with time limit. Thus GIS & DSS helps in decision making process to overcome the traffic congestion. The optimal solution can be obtained by using the Routing Graph, routing is performed in terms of the graph, finding the shortest route which is equivalent to find a minimum cost sub-tree in the graph. This problem is also known as Graphical Steiner Tree Problem (GSTP). The Steiner minimum tree (SMT) [7] is the shortest network spanning a set of nodes called terminals with the use of additional points named Steiner points. The determination of a Steiner tree is NP-complete and hard even to approximate.

Graphical Steiner Tree Problem

Let G=(V,E) be an undirected graph with a finite set of vertices V and an edge set E. Let C:EÃ¯ÂÂ R* be a cost function assigned to a positive integer to an edge in G. Let S be the subset of V (special vertices). GSTP which mainly used to find the subgraph, GÃ¢ÂÂ=(VÃ¢ÂÂ,EÃ¢ÂÂ) of G such that

(i) VÃ¢ÂÂ contains all the vertices in S,

(ii) GÃ¢ÂÂ is connected

(iii) Σ {(c (e): e ÃÂ EÃ¢ÂÂ} is minimal.

Thus this subgraph must be a tree. VÃ¢ÂÂÃ¯ÂÂ S vertices are known as Steiner vertices. Let us consider a graph of Figure 3, thus the special vertices are numbered as 1,2,3,6,7 are shaded and

GSTP is one of the optimization problem similar to Travelling salesman problem [8] and Knapsack problem [9]. GSTP can be solved in polynomial time and it also reduces the shortest path problem by using the DijkstraÃ¢ÂÂs algorithm [11] [14]. GSTP also used to reduces to find the Minimum Spanning Tree (MST) of G using either the algorithm of Prim[10] or Kruskal[12]. The Steiner problem in graphs can be formulated as an integer linear program or a global concave minimization problem.

Problem Identification in Transport System

The problem constraints mainly involved in finding an optimal solution for transportation to avoid an infeasible solution during search process. Constraints are classified into two types Fixed constraint: Selecting the wide route to decrease the number of turns/rotations.

Dynamic constraints: selecting the route with no traffic congestion.

SOLVING PROBLEMS BY IDENTIFYING THE POPULATION FACTORS

The routing problem can be identified by using the routing graph, for implementing the route map, selecting specific region involved, thus genetic algorithm plays a major role.GA simulates the genetic selection [15]. The application of genetic algorithm into GIS helps to design route map and also helps to identify the shortest path to reach the destination at a given time.

GA involves various strategies such as

(i) A variable length chromosomes (routes) and genes represent an encoding problem for a specified region.

(ii) An initial population of solution is taken as a sample from specified region.

(iii) Fittest route indicates the length of the route and time constraints.

(iv) The selection (reproduction) [13] operator is used to improve the quality of the population by giving the high-quality chromosomes (routes).

(v) Crossover examines the current solutions in-order to find better ones.

Various Parameters can be assigned for routing map are:

(i) Source node.

(ii) Destination node.

(iii) Time taken per distance to reach the destination.

(iv) Number of turns involved.

(v) MRR (rate of main road length to route length) in percentage.

RESULTS AND DISCUSSIONS

Figure 4 which indicates steiner tree with two steiner vertices (4 &5) with six cost.

By using parameters and strategies, population of the specified region can be determined, thus vehicle stoppingÃ¢ÂÂs and shortest path of that region can be analysed.

These factors will help to implement the route map which can be useful for transport department. A sample routing map is shown in Figure 5 and its characteristics table is shown in Table I.

CONCLUSION

This paper is trying to identify the optimal route finding analysis for rural area, thus the data which already exists in GIS (data warehouse) are collected, a route map can be designed for finding the shortest, feasible and optimal path to reach the destination.

References

Sean B. Eom, "Decision Support Systems," International Encyclopedia of Business and Management, 2nd ed., Edited by Malcolm Warner, International Thomson Business Publishing Co., London, England, 2010.
Marek J. Druzdzel and Roger R. Flynn, “Decision Support System”, Encyclopedia of Library and Information Science, 2nd ed., Allen Kent (ed.), New York: Marcel Dekker, Inc., 2012.
Keenan, P. B. (2003) “Spatial Decision Support Systems,” in M. Mora, G. Forgionne, and J. N. D. Gupta (Eds.) Decision Making Support Systems: Achievements and challenges for the New Decade: Idea Group, pp. 28-39.
Arul Prakash, “Geographical Information Systems – An Overview”, International Journal of Engineering and Technology, Vol.2, No.2, April 2010, ISSN: 1793-8236.
Susie Kelly, “Geographical Information Systems” Northwest Center for Sustainable Resources, www.ncsr.org.
Ram Mantravadi, “Transportation Management Systems: An Indian Perspective”, Aqua MCG Leadership Review, www.aquamcg.com.
Samira Noferesti and Hamed Shah-Hosseini, “A Hybrid Algorithm for Solving Steiner Tree Problem”, International Journal of Computer Applications, ISSN:0975 – 8887, Volume 41– No.5, March 2012.
E.L.Lawlyer, J.K.lenstra, A.H.G.RinnoyKan, D.S.Shmoys (2005), “The Travelling salesman problem: A guided tour of combinational optimization”, John Eeiley, New York.
S.Martello and P.Toth (2004), “Knapsack problem: Algorithms and Computer Implementations”. John Wiley, New York.
R.C PRIM (2007), “Shortest Connection Network and some generalization”, Bell system Tech.
E.W.Dijistra (2008), “A note on two problem in connection with graphs Numer math”.
J.B.Krusal (2009), “On the shortest path spanning subtree of a graph and travelling saleman problem”.
Goldberg, D.E., (2009). “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison Welsey Publishing Company.
Golden B., (2010), “Shortest-Path Algorithms – A comparison”, Operations Research, Vol.24, No. 9, pp. 1164-1168.
HollandJ.H., (2005), “Adaptation in Nature and Artificial Systems”, The University of Michigan Press, Reprinted by MIT Press, 2007.