Printer Friendly Format

Page 1 of 2
| Next |

Network flow model using temporal GIS


Rajiv Gupta
Civil Engineering Group
Birla Institue of Technology and Science
Pilani, Rajasthan
rajiv@bits-pilani.ac.in

Introduction
Transportation applications of Geographic Information System (GIS) have become increasingly popular in recent years and are referred to by the acronym GIS-T. Many conceptual developments are important in aiding the rise to prominence of GIS-T. These developments included work in operations research and programming, which led to new algorithms for shortest path analysis, routing procedures, solving the ‘transportation problem’ of linear programming, and the dynamic segmentation of links within the GIS-T.

Three types of Network flow models (NFM) are commonly solved using GIS-T packages: the assignment problem which seeks an optimal matching, on a one-to-one basis, of demand and supply points within the network; transportation problem which seeks to satisfy a set of demand points from a set of supply points, but in which one supply point can service many demand points or alternatively one demand point can receive from many supply points; and the minimum-cost flow problem (Waters, Chapter 59). Location-allocation models (Church and Sorensen 1996; Densham 1996) seek to determine optimal locations of facilities as well as optimal allocations of ‘customers’ to these facilities. Stand-alone computer programmes for location-allocation have been widely available (Rushton et al 1973; Dresner 1995). Frequently, the algorithms became embedded first in the stand-alone packages and then in the fully developed GIS and GIS-T packages. The development of standalone packages for carrying out specific operations such as shortest path analysis and location-allocation modeling contributed to the development of GIS-T (Waters 1999). However, in all the transportation problems, time plays an important role in decision-making and should always be given due importance. This led to advent of another dimension ‘time’ in the GIS, which is getting more attention now than ever (Agouris 2000; Peuquet 1999; Roddick 2001). Relationships among once static GIS elements may become clear once examined within a temporal framework. Representations used historically within GIS assume a world that exists only in the present. Information contained within a spatial database may be added to or modified over time, but a sense of change or dynamics through time is not maintained. This limitation of current GIS capabilities has been receiving substantial attention recently (Longley et al. 1999). Hence, GIS should be able to represent geographical phenomena in both space and time. The construction of temporal GIS databases is one of the ongoing challenges in the transportation sector (Beard & Palancioglu 2000; John 2001).



Problem definition
The present work concentrates on the NFM. There are multiple supply and demand points whose location and number can vary with time. To meet the demand by the supply, there are multiple paths available at any time. The objectives of the model are (i) to obtain the optimum number and therefore the locations of supply points for varying demand with time, and (ii) to obtain the optimum cost path.

Methodology
As it is well known that GIS is a combination of spatial databases and non-spatial databases, here the spreadsheet and Data Base Management System (DBMS) combination has been used. Spreadsheet, as it works like a grid-sheet, is used to prepare the map in 2-dimensional. DBMS facilitates platform for preparing a databases that can be always referred to the map drawn over the spreadsheet using some interface language. The cells are programmable over the spreadsheet, using the interface language Visual Basic (VB) and they are interrelated to the data in the database and specific tasks are performed. This work interfaces three modules (Fig. 1): (i) MS Excel(Sandler et al 1997), (ii) IDRISI (IDRISI Source Code, 1986-1999), and (iii) Excel -VB-Access (Curtis & Amundsen 1999).

The steps are as follows

• Map all available supply and demand points under consideration over the spreadsheet (MS Excel).
• Import the area map/ image to GIS package (IDRISI).
• Store the required spatial and non-spatial information in the database (MS Access).
• Use inbuilt VB environment of the worksheet to write macros to perform the task. Similarly VB SQL (Sequential Query Language) is used to write the queries.

Here the task is implemented in following manner:
The allotment is being done on the basis of travel distance from the supply point to demand point. The travel distance is formulated on the basis of following formula:

For i^th demand point: T_ij =(D_i +b_i d1_i)/ (1000*exp(t_i)    .....(1) where T_ij = total travel distance from j^th supply point to the i^th demand point; D_ij = road distance of j^th supply point to the i^th demand point; d_i = internal distance factor; b_i = difficulty factor; t_i = traffic factor on the basis of hour.

Table 1. Allotment of the sections for the students from different hostels

Section no	Class room no	Hostels							Filled seats	Available Seats	Strength
		Vyas	Shankar	Gandhi	Krishna	Ram	Budh	Meera	Filled seats	Available Seats	Strength
1	3203	0	0	0	0	0	50	4	54	96	150
2	3160	0	0	0	0	0	0	150	150	0	150
3	3156	0	0	0	99	15	0	6	120	0	120
4	2217	41	0	29	0	0	0	0	70	0	70
5	3252	0	0	0	0	50	0	0	50	0	50
6	2221	0	0	45	0	0	0	0	45	0	45
7	3215	0	0	0	0	0	0	0	0	180	180
8	1101	21	72	0	0	0	0	0	93	57	150
9	2204	24	0	26	0	0	0	0	50	0	50

Table 2: Prioritisation list from a Hostel (Ram) for a Course (General Biology)

Section No.	Effective distance	Priority	Class room no.	Time from	Time to
1	0.0933	5	3203	10 AM	11 AM
2	0.0878	4	3160	11 AM	12 Noon
3	0.0818	2	3156	12 Noon	1 PM
4	0.1112	7	2217	2 PM	3 PM
5	0.0772	1	3252	3 PM	4 PM
6	0.0870	3	2221	4 PM	5 PM
7	0.1111	6	3215	10 AM	11 AM
8	0.3090	9	1101	11 AM	12 Noon
9	0.1200	8	2204	12 Noon	1 PM

Page 1 of 2
| Next |