Abstract

Various spatial properties of public school districts may be assessed using location-allocation modelling tools of vector-based geographical information systems. The functionality of these tools and the requirements for a suitable digital map base is discussed initially. Subsequently, the spatial properties of school districts in selected regions of Copenhagen are established based on the actual location and capacity of public schools and the present distribution of pupils. It is shown how the consequences of suggested redistricting projects may be analysed and how 'best solutions' in terms of school locations, capacity and district boundaries may be pointed out. Finally, strategies for the design of transport network models that include traffic safety parameters are discussed.

Keywords

location-allocation, school districts, transport network models, CIS.

Lasse Møller-Jensen, Institute of Geography, University of Copenhagen
Øster Voldgade 10, 1350 København K.

Geografisk Tidsskrift, Danish Journal of Geography 98: 71-80.

This paper deals with various aspects of GIS-based allocation and location modelling which is normally carried out using a set of generic tools suitable for many different types of applications. In this general context the word allocation indicates the process of identifying specific areas, districts or streets surrounding a centre that should interact with that particular centre with respect to the in- or outflow of people or goods, which is generally known as demand. There may be more or less demand than the centre can manage - specified by the supply or capacity of the centre. The word location, on the other hand, indicates the process of identifying optimum locations for new centres given a set of objectives related to f.ex. accessibility. A comprehensive examination of location-allocation concepts as well as fields of application may be found in Ghosh &Rushton( 1987).

Several GIS software packages provide the tools for fast location-allocation modelling as a specific type of network analysis tool based on digital vector maps and databases (Densham, 1996). This implies that the area surrounding a centre is represented as a network of linear features. These linear features identify the location of possible transport routes and indicate how these are connected to each other, and reflect the fact that transportation of resources on the ground normally takes place along certain pre-defined corridors. Each linear feature in the network has an associated impedance value indicating the cost (measured in metres, minutes, petrol or any other relevant unit) of transportation along this line. This impedance value will often be related to specific means of transportation.

Location-allocation modelling is not new; research into the theory was conducted during the 1960's and 1970's (see for example Hagett et.al, 1977) related to the growth of computer science in general. What was missing then was detailed digital maps and broad access to the necessary computing power which meant that few applications of the methods to realistic and complex situations were seen. This has certainly changed - computers on the desks of general users are now powerful enough, and the quantity of digital maps is growing rapidly. The availability of relevant socio-economic data in digital format in many countries has moreover boosted the field of commercial applications of GIS for marketing and business planning purposes in which location-allocation modelling tools also play an important part (Maguire, 1995; Birkin, 1996).

Application to public school districts

The following sections discuss location-allocation modelling in connection with the process of assigning children from their residential location to the nearest school for a selected area of Copenhagen. This kind of spatial analysis provides the means for quantifying the relation between school location and capacity on the one hand and the demand for seats in the surrounding areas on the other hand. The general goal will normally be to maximize accessibility by minimizing the total travel distance for all pupils while at the same time ensuring that no pupil has to travel an excessively great distance to attend school. The allocation algorithm used for this project is implemented by the Allocate function of Arc/Info (ESRI, 1995b). It works by assigning the pupil demand of connected road segments in a least cost path starting closest to the centres and growing outwards. Allocation modelling assigns pupils from the surrounding areas to the nearest schools until either the maximum capacity of a school is exceeded or the boundary of a neighboring school district is reached. The pupil demand of a specific road segment may be divided between schools. It is shown later in this paper how composite objectives may be reflected in the network allocation modelling, including stimulation of desired traffic behaviour: limitation of street crossings, high priority to roads with bicycle paths and paths separated from motor traffic.

Allocation modelling as described above assumes that the location of schools are fixed. These locations may, however, reflect historic conditions and provide unsatisfactory service even with spatially optimal school district boundaries. The process of selecting new locations from a pool of candidate locations given some specific spatial objectives is referred to as location modelling.

Different objectives and therefore different location strategies should be applied for different types of centres such as shopping centres, hospitals or schools. For shopping centres the general goal is normally to find the location that minimizes total travel costs from any demand point to the nearest centre (the P-median problem). This will of course favour densely populated urban areas and some residents of more remote areas may have to travel very far to reach a centre. For many types of public facilities, however, the objective is to provide equitable service to as many people as possible or, in other words, to maximize accessibility while at the same time ensuring that no individual has to travel an excessive distance. This may be accomplished either by replacing the actual travel costs with a power function of costs in the P-median solution or by establishing a constraint on maximum individual travel costs so that all costs of travelling from a demand location to its assigned centre is below a specified value. The effect in both cases is that the facilities are located closer to any remote urban areas of lower population density compared to the P-median solution used for shopping centres. An example showing the identification of an optimum school location given the objective to minimize the total cost of all distances travelled is given below. The mathematical formulation of this objective is :

subject to

t)l(j=,.m)yj = p
(restricts the number of schools top)
2)E(H..n)X,j=l,Vi

(ensres that every demand location / is served)
3)yi>=xij,Vi,V;

(node / can assign toy only if there is an open facility
aty;ifXij = 1 then y^l)

where: i = demand location
j = candidate facility location
n = number of demand location

m= number of candidate facility locations
p = number of facilities to locate
Wj = demand at node /

dy = shortest distance between demand location / and
candidate;

>i = binary variable: 1, if facility is located at site 7, 0,
otherwise

jCjj = binary variable: 1, if demand location / is served by
facility at site j, 0, otherwise

To conclude this paragraph it should be noted that the process of carrying out the modelling tasks described above is normally straightforward and not very time consuming once the necessary digital database is established. The consequences of various changes in pupil location, transport lines, school location or school capacity may thus be

quantified immediately. The results generated by the modelling software include the number of pupils allocated to each school, the mean and maximum travel time and the corresponding school districts which may be superimposed on other GIS layers. In the actual planning situation, a number of other issues will influence the decisions made and the GIS can be used to visualize the location/allocation results in order to identify problem areas as well as to investigate the suitability of different solutions when compared to other types of spatial information. This will enable school planners to make decisions concerning where to increase or decrease school capacity while considering any spatial objectives.

The digital information base

The Road Network

In practice a limiting factor to the exploitation of network location-allocation tools may be the lack of adequate digital maps and geo-coded information or problems with the integration of data from different sources. The network must effectively reflect the cost of moving from one point to another. Delineation of an optimum route and the cost of moving along this route depends of course on the means of transport. For pedestrians the shortest route in terms of physical distance would be preferable; for car-drivers traffic conditions, road conditions etc. would play a role. For the current study a network reflecting walking conditions has been used and the physical distance is therefore considered as the primary factor. In practice, the time required to cross roads, make turns etc. would influence the travel time and suitability of a selected route heavily. Network design with this in mind is discussed in the last part of the paper.

Digital maps of roads in Denmark may be obtained from several sources. Detailed technical maps of larger urban areas must be obtained directly from the urban authorities responsible for map production, while The Danish National Survey and Cadastre provides road maps (road centre line) at the national level. Moreover, several private companies are in the process of establishing and marketing digital maps of transport links for various purposes.

The current analysis is carried out using a digital line map provided by the map publishing company KRAK (KRAK, 1995) which is originally created as a basis for producing analog maps of the Copenhagen area and which

is consequently not produced with network applications in mind (see fig 1). Due to the origin of the map, each line represents the centre line of some road feature that is visible on the surface, while a few transportation links f.ex. roads going into tunnels are not present. This may lead to identification of incorrect best routes' and the network has therefore been edited using the Arc/Info Arcedit software (ESRI, 1995b) to take these situations into account.

The KRAK map was converted into a network model of transportation lines by assigning impedance values to each road segment. The impedance value is in this case equal to the length of the road segment. A road segment is defined as the road between two node points which are points that normally represent road intersections. The transport time required for moving from one road segment to another, e.g. making a left turn, would be recorded as impedance-values for the corresponding node.

Modelling the demand for school seats

Because a GIS provides the means for computer-based spatial analysis, one of the main advantages is the potential for analysing very large and detailed datasets compared to what is possible by manual methods. This implies that a GIS often invites for spatial analysis involving information on the individual person in order to exploit its full potential. In Denmark this will normally present a problem because it is inconsistent with the confidentiality restrictions imposed by the legislation which implies that statistics should be computed on populations aggregated to a level where it is not possible to identify individuals.

The municipality of Copenhagen will of course collect data concerning age and addresses of individuals living within the municipality and make use of this data for various internal planning purposes. In the present context, however, a method is applied which aggregate personal data with a better spatial resolution than what can be achieved from published statistics without going to the individual level; thus maintaining geographical discretion.

What is needed for the location-allocation tasks is informationabout the location of children of a certain age, plus, ideally, information about whether or not each child will attend a public sector school or not. Statistics on age distributionin Copenhagen is published frequently at the level of the administrative statistical unit rode (hereafter termed RUJ. Although a RU normally does not cover a very large area, use of mean figures for complete RUs would be inadequate for the purpose of allocation modelling, giving

unreliable information about the extension of the optimum
school districts and mean travel time for the pupils.

For the current study the Statistical Office of the Copenhagen Municipality has provided data on the age distribution of the population along each road - with the enhancement that roads that run through several RUs are split into two or more segments where they intersect with the RU boundaries. The location of these segments can be found by combining the road network map with a digital RU map. The population figures corresponding to a road segment and, consequently, the demand - in terms of potential pupils - along each road segment is then mapped.

This approach implies that the pupils are assumed to be evenly distributed along the length of a road segment. This is of course very often not the case: if residential housing is only located along a fraction of a road segment or if the type of housing changes from single-family to multi-family housing there will be an uneven distribution of persons, which will affect the statistics reported by the locationallocation

Better accuracy may be achieved if the exact demand locations (i.e. pupil addresses) are represented as nodes in the network model. A prerequisite for such detailed address matching is the rather labourious task of producing an address map in some form and so far this is not available at a national level, but will appear within the next few years. An examination of different methods of modelling population for spatial analysis within a GIS can be found in Martin (1995).

The School Centres

Information about actual school capacity for 1996/97 has been provided by the Copenhagen Municipality's Department for Schools. The location of each school is entered into the network and the corresponding pupil capacity, residing in a relational database, is assigned to each school location.

Examination of school districts in northern Copenhagen

The Municipality of Copenhagen is divided into 15 school districts each containing several schools. The current study is restricted to two school districts: 11, Brønshøj-Husum and 12, Bispebjerg, both located in the northern part of the municipality. Each school has an associated 'primary district'defined by a set of RUs. Children in the primary

district have a right to attend the specific school. It will, however, often be possible to attend a school outside the primary district if it is convenient for some reason and if capacity exists at other schools. Pupils living in primary districts amounts to 69% of all pupils starting in public sector school in Copenhagen in 1996, while pupils living in the district outside the primary district amounts to 20% (Dept. for schools, 1996). Fig 1 shows the location of the 15 schools in school district 11 and 12 and the current delimitation of their associated primary districts.

Three allocation modelling procedures, using the algorithm described above, have been conducted, to examine the results of various restrictions on the choice of school and the capacity of the schools. The first step is to establish the conditions defined by the current school district boundaries concerning travel time. An allocation of pupils within the primary district to each school based on current population data for each road segment - (i.e. the number of children aged 6) - yields the results listed in table 1. This table is sorted by decreasing values of mean pupil travel distance. Note that the use of aggregated data will cause some inaccuracy, especially concerning the maximum pupil distance value, as described above.

The location of pupils that do not want to attend a public sector school in district 11 or 12 is not known when the aggregated data approach is applied. All pupils in a primary district have, therefore, been assigned to the relevant school, in order to compute the travel time statistics. It can be seen, that especially some parts of the Bellahøj school primary district are relatively remote from the location of the school. The table also shows the percentage of pupils in a primary district who attend their primary

school. The rest of the pupils will go to schools outside the
primary district including a relatively high number of
pupils who will attend private schools.

A free choice of school in the two districts will of course affect the spatial properties in terms of pupil travel time and also the necessary school capacity. Fig 2.1 shows the result of an allocation model that does not take any district boundaries into consideration but employs school capacity limitations equal to the capacities of the current schools.

Table 2 - case 1 lists the number of allocated pupils and their mean travel time for each school. 39 pupils are not allocated to a school because the capacity of the neighbouring schools is exhausted before the total demand of the whole area is met. The allocation algorithm used here is not able to adjust for this problem. Table 2 - case 2 reflects a situation where no school capacity limits are imposed and shows the corresponding number of pupils per school. Fig 2.2 shows where the pupils live in this case (under the assumption that they prefer to attend the nearest school).

The last example deals with the hypothetical situation
that a site should be selected for a new school in the area
in order to improve the overall accessibility to schools.

Location-allocation modelling tools may be used to point out the near optimal location - given 11 existing schools and a specific objective which is to minimize the total travel distance for all pupils as described above. Location- Allocation modelling in Arc/Info will presently not take school capacity into account and the capacity of each school must therefore be adjusted subsequently. It has been shown that the best location will be at a node point (Hakimi,1964) and all node points in the area are identified as candidate sites, i.e. possible locations for the new school. Unfortunately, it is necessary to represent the pupil demandlocations differently for location modelling in Arc/ Info due to the requirements of the LocateAllocate commandused than was the case for the allocation modelling described above which was carried out using the more flexible Locate command (ESRI, 1995a). The Locate Allocatecommand requires that pupil demand is associated with node points, rather than road segments. The transformationhas been done by assigning half the demand from one street to each of its end node points. Due to the differences in demand representation it is not possible to compare the mean travel time distances directly.

Fig 3.1, 3.2 and table 3 show the result of the assignment of pupils to existing schools and the selected optimum location of a new school, incidentally very near the location of a former public sector school. The corresponding travel time values and capacity for each school are also reported.

Table 4 summarises the results above. It can be seen, that the mean travel distance for all pupils in the area drops from 641m in the case of fixed boundaries (table 4, A) to 612m in the case of current school locations and size, and all pupils attending the nearest school (table 4, B) and goes down to 574m following the school capacity relaxation (table 4, C). The area surrounded by a dotted line in fig. 2.2 indicates the location of pupils living more than twice the average school travel distance from their nearest school. The mean travel distance will, however, drop to 500m if a new school is opened at the optimum location (table 4, D).

Alternative network models

Minimizing travel distance is only one concern when laying out school districts. Traffic safety for school children is another, and in many cases a longer distance will probably be accepted if a safer route can be found. This may be incorporated in the modelling process by assigning higher impedance values to road segments which are less desirable to use for transportation. Being the focus of a future study, this will not be described in detail here. An example will, however, be given below.

The above described location-allocation examples as-

sume that travel cost may be expressed as distance along centre-of-the-road lines. It is questionable, however, whether this type of network model reflects the real transport lines of pedestrians and cyclists very well. It is likely that a more elaborate network model must be established e.g. similar to the network shown in fig 4. Roads and paths are here represented - not by their centre line - but by two parallel lines that indicate the location of sidewalks and cyclepaths, which are considered the actual transport lines of pedestrians and cyclists. Lines that represent possibilities for street crossing are added to the network at street corners and at other places where zebra crossings or tunnels are present.

Traffic modelling and risk assessment have been the subject of numerous investigations. Two major factors seem relevant in the current context: the risk associated with walking or bicycling along a road, and the risk associated with road crossings. To compute the actual risk values information like average number of cars in 24 hours, average car speed, existence of sidewalk, existence of cycle path, facilities for road crossing, e.g. zebra crossing, tunnels etc may be taken into account. A publication of the Danish Road Directorate (1992) presents the main principles involved in the calculations of risks based on these data. The following road parameters have been added to the network to create the examples below:

YDT: One year average number of cars in 24 hours. The YDT figures are supplied by the Municipality of Copenhagen (1997) for a selection of roads. Data for the rest of the roads are estimated from the known YDT. The fraction of heavy vehicles in the YDT is also part of the risk assessment but will be ignored here.

V: Average car speed

F: Existence of sidewalk: 0.1 = yes, 0.5= no
C: Existence of cycle paths: 0.1 =yes, 0.5= no
RC: Facilities for road crossing, e.g. zebra crossing, tun-

nels etc: o.o=Tunnel, o.2=Zebra crossing & light
etc., I.o=No facilities

The risk (Rl) of moving along a road side is computed by the following formula (adapted from Danish Road Directorate, 1992): Rl = 1 + (0.05 * sqrt(YDT) * (V/50)**3 * (C + F))

The risk of crossing a road (R2) is computed from the
amount of traffic and the average speed by: R2 = 0.1 * sqrt
(YDT) * (V/50)**3 * RC.

The R2 value is subsequently reduced to 20% in the case
of a zebra crossing and to 0 in the case of a tunnel (adapted
from Danish Road Directorate, 1992).

It is, of course, a question of individual preferences how much longer one is prepared to travel in order to minimize risk, and it is, therefore, impossible to suggest one absolute TDest route'. Three examples of best routes that reflect different preferences concerning distance vs. risk are indicated in fig 4.

l. The route depicted by a solid line is the shortest route
between residence and school. The total length is
1600m.

2. The route depicted by a dotted line takes into account

the risk of travelling along the road. The impedance
values of each link has been computed using the
expression: impedance = Rl * length (m) / 100.
This route runs along small roads in residential areas
with little traffic, but has to cross several major roads.
This route is only approx. 6% longer than the shortest
route.

3. The route depicted by broken line shows the result of adding the risk associated with road crossings to the above mentioned risk of movement along the road side. The impedance values of each link is computed using the expression:

impedance = (RI * length (m) / 100 ) + R2

This route is longer because it proposes a detour for the purpose of using a tunnel to cross a major road while at the same time trying to avoid roads with heavy traffic. The route is approx. 60% longer than the shortest route.

Conclusions

The examples above show how a planner may use GIS to solve spatial problems concerning school locations and allocation given different objectives and constraints and thereby produce information that is relevant to the task of providing good service to children attending public school. It is shown how better delimitation of school districts may reduce the average distance to school. It is also shown, how an optimum location for a proposed new school may be computed. In the actual planning situation, a number of other issues will influence the decisions made and the GIS can be used to visualize the location/allocation results in order to identify problem areas as well as to investigate the suitability of different solutions when compared to other types of spatial information.

The vector GIS provides the functionality for solving location/allocation problems, but it also provides the tools for aggregating data, editing spatial features and managing relational databases that makes it possible to establish the necessary data foundation. Once the digital map base has been established, the actual computations can be done in a few minutes, making the tools suitable for scenario and

forecasting purposes. Other means of transportation, e.g. bus, may be incorporated, and more emphasis may be put on the suitability of the transportation links. The current study demonstrates location-allocation modelling in a situation where aggregated data have to be used. It may be possible to obtain a more accurate result in the near future following the establishment of a national database of geocoded

Acknowledgements

I would like to thank Copenhagen Municipality (Statistical Office and Department for Schools), and KRAK's Map Publishing Company for helping to bring about the necessary data.

References

Birkin, Mark (1996): Retail location modelling in GIS. In: Longley, Paul & Michael Batty (ed's): Spatial analysis: Modelling in a GIS environment. Geoinformation International, Cambridge.

Danish Road Directorate (1992): Evaluation of highway investment
projects. Review of appraisal methodology. Economic-
Statistical Department, The Danish Road Directorate.

Densham, Paul J (1996): Visual interactive locational analysis. In: Longley, Paul & Michael Batty (ed's): Spatial analysis: Modelling in a GIS environment. Geoinformation International, Cambridge.

Dept. for schools (1996): Bilag til styrelsesvedtægt, Direktoratet,
Københavns Skolevæsen

ESRI (1995a): Location-Allocation in Arc/Info. Guide. Environmental
Systems Research Institute. Redlands.

ESRI (1995b): Arc/Info on-line documentation. Environmental
Systems Research Institute. Redlands.

Ghosh, A & G. Rushton, eds. (1987): Spatial analysis and location-allocation
models. New.York.

Hagett, P., A. D. Cliff & A. Frey (1977): Locational Models II:
Allocating. London.

Hakimi, S.L (1964): Optimum location of switching centres. In
Operations Research, 12. Here cited from A. Markan (1974).

KRAK (1995): The digital maps are reproduced by permission
(R/950726/1).

Maguire, David (1995): Implementing spatial analysis and GIS applications for business and service planning. In: Longley, Paul & Clarke Graham (ed's): GIS for business and service planning, Geoinformation International, Cambridge.

Markan, Anette (1974): Location-Allocation-Models og deres
anvendelse i lokaliseringsplanlægning. København.

Martin, David (1995): Censuses and the modelling of population
in GIS. In: Longley, Paul & Clarke Graham (ed's): GIS for

business and service planning. Geoinformation International,
Cambridge.

ReVelle, C.S. and Swain, R.W. (1970): Central facilities location.
Geographical Analysis, vol. 2, pp 30-42. Here cited from ESRI
(1995a)

Rushton, Gerard (1987): Selecting the objective function in
location-allocation analysis. In: Ghosh, A & G. Rushton, (eds.):
Spatial analysis and location-allocation models. New York.