Network flow model using temporal GIS

Network flow model using temporal GIS

SHARE


Rajiv Gupta
Civil Engineering Group
Birla Institue of Technology and Science
Pilani, Rajasthan
[email protected]

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 ith demand point: Tij =(Di +bi d1i)/ (1000*exp(ti)    …..(1)where Tij = total travel distance from jth supply point to the ith demand point; Dij = road distance of jth supply point to the ith demand point; di = internal distance factor; bi = difficulty factor; ti = 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

Case Study
The case study is taken for the educational Institute, ‘Birla Institute of Technology and Science, Pilani’ (BITS). The situation is simulated by allotting the number of students from the different hostels (supply points) to different course sections (demand points) at different time. This objective is to allocate the different course sections to students from different hostels at different time. The same course is taught by different instructors at different time and hence there are number of sections for the same course. The constraints are applied in terms of number of students per section. The BITS campus has eleven boys hostels and one girl hostel. There are three faculty divisions (FD) where the classes are conducted. Each FD has two floors and there are approximately 50 classrooms in three FDs. The allotment is to be done on the basis of travel distance from the hostels to the classrooms. The classroom with lower travel distance has been given the higher priority. Moreover the allotment is not on the basis of students in individual; rather it is done for the total number of students as an input from a particular hostel. The steps are as follows:

  • First of all the image of BITS campus has been scanned and imported to the IDRISI environment. After that the FD map has been prepared over the excel spreadsheet (Fig. 2). Excel worksheet was chosen for this task as it provides the facility of representing a classroom using the range object.
  • Non-spatial data is entered using the MS Access module. The data related to the classrooms, hostels, courses, distances, time, etc. is collected and a database is prepared in normalised form.
  • BITS campus map was digitised in three modes i.e. point, line & polygon: (i) Point type: In this type all the important landmarks are set over the map, (ii) Line type: The roads, connecting the landmarks, of the campus were digitised and vector image was obtained, and (iii) Polygon type: To represent the built environments of the campus. This includes the FD, hostels, temple & lawns. FD map was also digitised in form of ground floor and first floor for classrooms.
  • These vector layers of BITS campus and the FDs were rasterised, so that, they can be linked to the database. For this, the point type, line type or the polygon type vector layer is given as input image for the rasterising function of the IDRISI software. This updates the original raster image by the vector layers.
  • Two databases, one for non-spatial and second for spatial information, were created. In all six non-spatial tables were prepared. These refer to the classrooms in each FD at each floor. So, three FDs and two floors in each FDs result in six tables. These tables consist of the data related to field ‘di (internal distance factor)’ and the field ‘strength (capacity of each classroom)’. Secondly, the table to be prepared is related to the hostels. This consists of fields as ‘no_stud i’(number of students in ith year) and three other fields which keep the information about the distance of the hostel building from each FD. Another table ‘courseinfo’ contains the fields as ‘course_id (unique course number)’, ‘level (students of which year)’. Another table ‘ref-text’ contains the fields as ‘hr_no (which hour of the day, i.e. 1,2,…,9)’, ‘days’ (Monday, Tuesday, etc), ‘room_no’ (the room, where the class is conducted). There are a few tables prepared to contain the data regarding the vector objects created. Tables ‘roads’ (containing information about the roads), ‘class-first’ and ‘class-second’ (data regarding classrooms) and ‘hostel’.
  • Writing macros: This part is the backbone of the project. This refers to programming the range objects, which further represent the Faculty Division (FD) plan over the spreadsheet. The in built Visual Basic environment allows the facility to customize the macros which do the task using Eq. 1 The parameters are used to find out the travel distance. FD distance can be searched from the hostel table. Internal distance factor can be accessed from the classroom tables. Class hour can be accessed from the course section table. VB SQL is used to perform the search operations.

    Hostel name, year, course name is taken as input from the user. After that, the effective distance is calculated and tables are updated. Once the effective distance is calculated, priority with respect to each section is determined. Section with lower travel distance gets the higher priority. After this section allotment is done to the students. Now these rooms are shown over the FD plan on MS Excel spreadsheet (Fig. 3).

Table 1 and 2 show the results of the case studies in terms of allotment of students from the different hostels to different sections for a course at different time.

Conclusion
The model can be applied to real life problems, for example, in a city to allot the time slots at public service centers. However, the criterion for finding out travel distance will be different. It can be in individual or can be specific to a particular zone. On the basis of the information, prioritisation of the facility centres and allotment can be done. The temporal consideration has to be taken keeping the peak traffic hours. The work emphasises the interfacing of GIS with other software packages, which can improve the efficiency of existing GIS packages.

Reference

  • Agouris, P. K., G. B. Mountrakis, A Stefanidis, 2000, Modeling and Detecting Change in an Integrated Spatio-temporal Environment. ISPRS Vol XXXXIII. Amsterdam
  • Beard, K. & H. Palancioglu, 2000, Estimating Positions and Paths of Moving Objects Temporal Representation and Reasoning-TIME 2000 Workshop Proceedings IEEE Press. 155-162.
  • Church R L, & P. Sorensen, 1996, Integrating normative location models into GIS: problems and prospects with the p-median model. In Longley P, Batty M (eds) Spatial analysis: modeling in a GIS environment. Cambridge (U.K.), GeoInformation International 167-83.
  • Curtis, S. & M. Amundsen, 1999, Database Programming With VISUAL Basic 6, First Edition, Techmedia
  • Densham P J, 1996, Visual interactive locational analysis. In Longley P, Batty M (eds) Spatial analysis: modeling in a GIS environment. Cambridge (U.K.), GeoInformation International: 185-205
  • Dresner Z (ed.), 1995, Facility location: A survey of applications and methods, New York, Springer
  • IDRISI Source Code, 1986-1999, Clark Labs, The Idrisi Project, Clark University Graduate School of Geography, USA
  • John Z. Luh, 2001, Case studies for simulation of roadway and traffic operations using corsim, ITE Journal, 71(7): 34-41
  • Longley P, M. Goodchild, D. Maguire, & D.Rhind (eds), 1999, Geographical Information Systems: Management Issues and Applications, John Wiley & Sons, Inc, USA.
  • Peuquet D. J., 1999, Time in GIS and geographical databases. In Longley P, Goodchild M, Maguire D, and Rhind D (eds) Geographical Information Systems: Management Issues and Applications’. John Wiley & Sons, Inc, USA.
  • Roddick, J.F., & M. Spiliopoulou, 2001, A Survey of Temporal Knowledge Discovery Paradigms and Methods, IEEE Transactions on Knowledge and Data Engineering 13.
  • Rushton G., M.F.Goodchild, & L.Ostresh (eds), 1973, Computer programs for location-allocation problems, Monograph No. 6. Iowa, Department of Geography, University of Iowa
  • Sandler, C, T Badgett, & J Weingarten, 1997, Office 97 for windows, BPB Publications, New Delhi.
  • Waters N. M., 1999, Transportation GIS: GIS-T. In Longley P, Goodchild M, Maguire D, and Rhind D (eds) Geographical Information Systems: Management Issues and Applications. John Wiley & Sons, Inc, USA.