A GIS-based modelling of vehicles rational routes.

Jakimavicius, Marius ; Macerinskiene, Aida

Abstract. Methods of searching the rational route are dealt with in the presented article, where the main optimality parameters of the route are chosen: the shortest travelling route (1), the fastest travelling route (2) and the alternatively selected route (3), where the optimality criteria are calculated for one-side traffic swath. Based on analysed aspects, GIS tools for transport flow modelling are picked and route search algorithm resulting in evaluation of the road permeability depending on the time of the day designed. Such methodology is based on real adaptability example in one transport area of Vilnius city.

Keywords: geographical information system, traffic modelling, rational route search.

RACIONALIU VAZIAVIMO MARSRUTU MODELIA VIMAS NAUDOJANT GIS M. Jakimavieius, A. Maeerinskiene

Santrauka

Nagrinejami racionalaus kelio paieskos metodai, kai pagrindiniais marsruto optimalumo kriterijais pasirenkami: arciausias vaziavimo marsrutas (1), greiciausias vaziavimo marsrutas (20) ir marsrutas, parinktas pagal alternatyvas (3), kai naudojamas optimalumo kriterijus, apskaiciuotas transporto priemoniu srautui, vienai eismo juostai. Remiantis analizuojamais aspektais parenkamos GIS priemones transporto srautams modeliuoti ir suprojektuojamas marsruto paieskos algoritmas, kurio rezultatai priklausomai nuo paros laiko ivertina gatviu pralaiduma, pagrista naturiniais tyrimais. Sukurta metodika grindziama realiu pritaikymo pavyzdziu pasirinktame Vilniaus miesto transportiniame rajone.

Reiksminiai zodziai: geografine informacine sistema, eismo modeliavimas, racionalaus vaziavimo paieska.

1. Introduction

A drastic rise in travels around the world (from year 1960, an average of 1820 km by car, railway or aircraft, to 4390 km in 1990) [1] substantiate different traffic problems in all capitals and fast developing countries.

Growing Lithuanian economy and quality of the living conditions prompt the population's mobility, the motorisation level and increasingly high transport flow in the countries streets and roads [2, 3].

There are more than 2,448 million vehicles (where over 1,095 million--private cars) in Lithuania this year. The present level of motorisation has reached 384 cars/1000 inhabitants. With this rapidly increasing level and with the existing car fleet growth it is forecast that the overall number of cars will exceed 1,5 million in 2005. The relative motorisation indicators are also increasing. In 1990 the motorisation level (a number of vehicles per 1000 inhabitants) in Lithuania was 215; in 1993 - 245; in 1996 - 285; in 1999 - 332, in 2002 - 426; in 2004 - 476 [4]. This indicator has reached and even measured that of other European countries; for example, there are 466 vehicles per 1000 inhabitants in Germany, 421 in France and 419 in Sweden.

According to the statistical data [4] the development of personal passenger cars transport in Lithuania started in the 1920's. The situation in Lithuania's transport system can be illustrated by the dynamics of vehicle number growth during 1995-2003 (Table 1).

During the last 15 years Lithuania has experienced a sudden increase in motorisation level. The tendency is illustrated in Fig 1.

A sharp bounce in motorisation level invokes a lot of transport problems. Many researches analyse transport system from the point of its sustainability, which influences the economical, social and environmental implications [5-7]. Reorganization of the transport system is one of the possibilities to solve problems in transportation sphere, when the existing transport flows are modelled by arranging the highway detours, capable to unload the main traffic flow [8, 9]. Such solutions, however, necessitate a big amount of investments and strong financial capabilities.

Modelling the trips is another, no less important, part of the research decreasing the travel numbers or numbers of car users in urban transport.

Travel demand management measures can be applied to encourage car users to set car use reduction goals when experiencing impairments in travel options. In forming plans to reduce car-use contingent on such goals, car users consider a range of adaptation alternatives including a more efficient car use, suppressing trips, and switching travel mode [10]. According to the analysis performed by Swedish specialists, travels can be regulated generalising them by travel behaviour, infrastructure and location [11]. Travel dependence on urban structure and target accessibility is discussed in the analysis performed by Dutch National Travel Survey study in 1998 [12].

In order to reduce the idle time of cars on urban streets, the following could be suggested: a rational distribution of transport flows on the urban street network and rational modelling the car driving routes.

The optimal route choice is a problem thoroughly investigated in international literature, with Steenbrink's 1978 description being a benchmark for further studies. Applying modern computer technologies, intellectual transport information systems could be created. Such type IS also covers the task of rational choice of car driving route. Geographical information system (GIS) technology offers extremely significant power in transport modeling [13, 14]. GIS could be also applied to the search for rational car routes when it is necessary to be at a specific spot of the network on a specific time. The system offers to a user a rational route, time of departure and calculated expenses depending on the set parameters. In other papers that analyse the application of GIS technologies in transport task solution, an application of multi-modal networks could be spotted. They are applied when solving route choice tasks within the overall urban transport system (cars, public transport, railway transport, and even pedestrians) [15, 16]. The assessment of transport jams on the street network is necessary when solving the task of the fastest route choice. A search algorithm, the results of which depend on the time set by a system user, has been programmed as the street capacity is different depending on the time of the day [17]. The general public might be the user of IS, which helps to choose a rational driving route. Applying ESRI technologies, a system user is given an application, which has functioned allowing to set the beginning and the end of the trip, and the interim stopping places (if necessary). The IS user is given a map with a marked rational driving route.

2. Analysis: algorithms of tasks of setting rational driving routes and their solutions

Standard Utility Network Analyst allows GIS users to find the shortest path through line segments according to their geometric length. Created data model allows users to assign weights to line (street) segments. It is possible to assign driving time and traffic flow data to street segments. By this reason we can calculate the quickest and the least loaded route. An optimisation criterion depends on user's choice.

2.1. The performance principle of the mechanism of the search for a rational route

The created data model structure and ArcGIS software enable solution of the tasks of setting routes on the street network and calculation of those routes. The software module Utility Network Analyst is used for calculations. This tool has been chosen, as the rational driving route calculation uses the Deijkstra method [11] and weights could be attached to the street line sections. Three-type route setting tasks are being analysed:

* finding the shortest driving route;

* finding the fastest driving route;

* setting the driving routes according to the alternatives by using the calculated flow of transport means on one traffic line.

Calculation of the rational route is used when the amount of the weight (numeric value, for example, section length) given to each street section is minimised in Fig 2.

[FIGURE 2 OMITTED]

After setting the search for the optimal route from point 6 to point 5, the route is chosen, where the sum of section weights is the lowest. There are two alternatives in the given example:

1) The route passing sections s61, s12, s24, s45;

2) The route passing sections s61, s13, s34, s45.

The optimal route will be the one where the sum of section weights is lowest: min [summation] [S.sub.ij].

2.2. Mathematical model of rational route modelling tasks

The group of these tasks belongs to the group of network optimisation, or, to be more specific, to the type of the task of the shortest route optimisation. The essence of the task of the shortest route lays in the fact that a shortest uninterrupted route should be found on the network of streets from the initial to the final point. All the given tasks of rational route modelling have the following features [18]:

* a section of the street corresponds to the edge of the graph, and the junction corresponds to the peak;

* the network of streets consists of m nodes (junctions) on Fig 3 and knowing the weights between nodes [s.sub.ij] we can find rational routes between the initial node i = 1 and the final node i = m;

[FIGURE 3 OMITTED]

* by the weight [s.sub.ij] the distance between the nodes i and j, and the driving time from the node i to the node j, the load of the section between the nodes i and j with the transport flows and other conditions that are of interest might be expressed;

* we accept variables [x.sub.ij], the value of which may be equal to 0 or 1. If the shortest, fastest or the least loaded route passes the nodes (junctions) i and j, then [x.sub.ij] = 1, on the contrary [x.sub.ij] = 0;

* [N.sup.-.sub.i] is the set j of streets coming from i node (junction), and [N.sup.+.sub.i] is the set j of streets coming to i node (junction) (Fig 3).

Then the task of the shortest or the fastest route or the lowest load on the road will be described according to the following mathematical model:

Min f(x) = [m-l.summation over (i=1)] [summation over (j[member of][N.sub.i]][S.sub.ij][X.sub.ij] - goal function when: [summation over [k[member of]N.sup.-.sub.1]] [X.sub.lj] = 1, i = 1, (1)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

[x.sub.ij] [greater than or equal to] 0; i = 1, 2, 3, ..., m; j = 2, 3, ..., m.

Here the goal function means that we perform the minimisation of a certain route, depending on the weight [s.sub.ij]. The weight is a numeral value, which is kept in the field of the created database. It could be used to set the length of the street section, the time of covering a specific section of the street or the load of the specific section of the street with transport flows. If the weight [s.sub.ij] is used for setting the street section length, then the task solution would be the shortest driving route; when the driving speed is set as a specific section, then the solution will the finding the route of the fastest driving; and if the weight [s.sub.ij] is used to set the load of the street section with the transport flows, then the result will be the least loaded driving route.

The equation of restrictions (1) is used to set the balance equation of the first node, which describes the requirement that a certain single direction should be taken from the first node (chosen on the beginning of our route within the network of streets). The Equation (2) sets the condition of balance, so that if a certain section is taken to come to the node, then another section is taken to leave the node.

3. Application and results of the method

3.1. Finding the shortest driving route; its mathematical model and solution

In order to find the shortest driving route between two specific points within the street network, the weights sij, the numeral values of which are equal to the section lengths, should be attributed to the street sections. Let's suppose that we have the network of the following sections (Fig 4).

[FIGURE 4 OMITTED]

The shortest route of driving should be found when the lengths of street sections and the driving directions are known. A mathematical model of this task would be the following:

f(x)min = s12 x [x.sub.12] + s13 x [x.sub.13] + s14 x [x.sub.14] + s25 x [x.sub.25] + s35 x [x.sub.35] + s45 x [x.sub.45] + s26 x [x.sub.26] + s36 x [x.sub.36] + s46 x [x.sub.46] + s57 x [x.sub.57] + s67 x [x.sub.67], (3)

where: [s.sub.ij] - distance of street network section; [x.sub.ij] - route coefficient, possible values (0 or 1).

Limitation of equation:

[x.sub.12] + [x.sub.13] + [x.sub.14] = 1;

- [x.sub.12] + [x.sub.25] + [x.sub.26] = 0;

- [x.sub.13] + [x.sub.35] + [x.sub.36] = 0;

- [x.sub.14] + [x.sub.45] + [x.sub.46] =0;

- [x.sub.25] - [x.sub.35] - [x.sub.46] + [x.sub.57] = 0;

- [x.sub.26] - [x.sub.36] - [x.sub.46] + [x.sub.67] = 0;

[x.sub.ij] [greater than or equal to] 0.

The 7th node does not need restrictions to be put down, as then the equation would have a linear dependence. The following task is being solved by Dejkstra algorithm (Table 2).

The shortest route between points 1 and 7 passes through the nodes (junctions) 1, 3, 5, 7 and its length is 550 m (Fig 5).

[FIGURE 5 OMITTED]

3.2. The task of the fastest driving route; its mathematical model and solution

In order to find the shortest driving route between the two specific points within the street network, the weights sij, the numeral values of which are equal to the section lengths, should be attributed to the street sections. The possible traffic directions along the sections are known. Let's suppose that we have the network of the following sections (Fig 6).

[FIGURE 6 OMITTED]

The fastest driving route should be found when the driving time and the traffic directions on street sections are known. A mathematical model of this task would be the following:

f(x)min = s12 x [x.sub.12] + s13 x [x.sub.13] + s14 x [x.sub.14] + s25 x [x.sub.25] + s35 x [x.sub.35] + + s45 x [x.sub.45] + s26 x [x.sub.26] + s36 x [x.sub.36] + s46 x [x.sub.46] + s57 x [x.sub.57] + s67 x [x.sub.67], (4)

where: [s.sub.ij] - driving time in street network section; [x.sub.ij] - route coefficient, possible values (0 or 1). Limitation of equation:

[x.sub.12] + [x.sub.13] + [x.sub.14] = 1;

- [x.sub.12] + [x.sub.25] + [x.sub.26] = 0;

- [x.sub.13] + [x.sub.35] + [x.sub.36] = 0;

- [x.sub.14] + [x.sub.45] + [x.sub.46] = 0;

- [x.sub.25] - [x.sub.35] - [x.sub.46] + [x.sub.57] = 0;

- [x.sub.26] - [x.sub.36] - [x.sub.46] + [x.sub.67] = 0;

[x.sub.ij] [greater than or equal to] 0.

The 7th node does not need restrictions to be put down, as then the equation would have a linear dependence. The following task is being solved by Dejkstra algorithm (Table 3).

The route that is covered in the fastest way from point to 1 to point 7 passes the nodes (junctions) 1, 4, 6, 7 and the duration of such driving is 50 s (Fig 7).

[FIGURE 7 OMITTED]

3.3. The task of the route the least loaded with transport flows: its mathematical model and solution

In order to find the least loaded driving route between the two specific points within the network of streets, the weights [s.sub.ij], the numeral values of which are equal to the section lengths, should be attributed to the street sections. Let's suppose that we have the network of the following sections (Fig 8).

[FIGURE 8 OMITTED]

The route that is the least loaded with transport flows should be found, when the hourly flow of transport means is known on each street section. The driving direction is also known. A mathematical model of this task would be the following:

f(x)min = s12 x [x.sub.12] + s13 x [x.sub.13] + s14 x [x.sub.14] + s25 x [x.sub.25] + s35 x [x.sub.35] + + s45 x [x.sub.45] + s26 x [x.sub.26] + s36 x [x.sub.36] + s46 x [x.sub.46] + s57 x [x.sub.57] + s67 x [x.sub.67], (5)

where: [s.sub.ij] - traffic flows in street network section; [x.sub.ij] - route coefficient, possible values (0 or 1).

Limitation of equation:

[x.sub.12] + [x.sub.13] + [x.sub.14] = 1;

- [x.sub.12] + [x.sub.25] + [x.sub.26] = 0;

- [x.sub.13] + [x.sub.35] + [x.sub.36] = 0;

- [x.sub.14] + [x.sub.45] + [x.sub.46] = 0;

- [x.sub.25] - [x.sub.35] - [x.sub.46] + [x.sub.57] = 0;

- [x.sub.26] - [x.sub.36] - [x.sub.46] + [x.sub.67] = 0;

[x.sub.ij] [greater than or equal to] 0.

The 7th node does not need restrictions to be put down, as then the equation would have linear dependence.

The following task is being solved using Dejkstra algorithm (Table 4).

The route that is the least loaded with transport flows is between points 1 and 7 and passes the nodes (junctions) 1, 2, 6, 7 and the overall loading of this route is 500 veh/h (Fig 9).

[FIGURE 9 OMITTED]

3.4. Example of optimal route calculation

A developed model was adapted in modelling the Vilnius city transport network. Three possible routes between two chosen points y1 and y2 with the different optimization criteria have been calculated.

A route may be found on which the minimal transport intensity is seen and the weights of the street section are used along the vectorisation direction and counter the vectorisation direction, which characterise an average hourly flow per day or the overall traffic flow irrespective of the number of lines: on the section of one direction traffic or street, the problem of complete prohibition of transport is being solved by applying the maximum values of the flow weight that could be entered the database. For example, if the traffic on a street section is prohibited along the vectorisation direction, then the weight given to the section along the vectorisation direction is 32 000, which is a maximum value that could be entered into the database field the type of which is Short Integer.

Within the urban street network, such numeral value of the weight is sufficient for the route analysis. If the traffic is fully prohibited on the section, then we have to apply maximum weights of street section along the vectorisation direction and counter it. The values of such weights must be 32000; and such values are sufficient for the tool Utility Network Analyst not to include the section, traffic on which is prohibited, into the route of route formation.

The way from point 1 to point 2 was found taking into consideration the minimal load of the street (Fig 10).

[FIGURE 10 OMITTED]

After weights characterising the load are taken away, we get a route which is shortest in geometrical terms and possible driving directions but it is not the one that is the least loaded (Fig 11).

[FIGURE 11 OMITTED]

Created data model allows using a weight for street segment. A weight could be a time period when transport vehicle goes through a street segment. System allows using two weights for one street segment: one along vectorisation direction and the other in opposite direction (Fig 12).

[FIGURE 12 OMITTED]

In Table 5 calculation results between the same two points but different optimisation criteria can be compared.

4. Conclusions

1. A created mechanism of finding the rational driving route can help a user to find a route depending on the optimality criterion chosen by him: the shortest route, the route that is covered in the shortest time and the route that has the lowest load of transport flows.

2. Deijkstra algorithm has been applied in calculations of finding the rational driving route depending on the optimality criterion of the choice of the route, the street sections are given weights, ie attribute fields kept in the database: a street section length, time that is needed to pass the section, and traffic intensity.

3. Traffic prohibition mechanism is installed in the calculation of the rational driving route, under conditions when the street section has a single--direction traffic or traffic on a specific section is prohibited.

4. The developed mechanism of a rational choice of the route and the designed vector database may be published on the general GIS for public usage and attribute information server with the help of ESRI technologies.

5. If the developed database would be supplemented with the real time data, the precision of the route planning would highly increase.

Received 22 Mar 2005; accepted 25 Nov 2005

References

[1.] Schafer, A. The global demand for motorized mobility. Transportation research, 32(6), 1998, p. 455-477.

[2.] Grigonis, V. and Burinskiene, M. Development scenarios for Vilnius public transport. Town Planning and Architecture, 27, Suppl 2003, p. 25-33.

[3.] Burinskiene, M. and Paliulis, G. Consistents of car's parking in Lithuanian towns. Transport, 18(4), 2003, p. 174-181.

[4.] 2004 Transport and Communications (2004 Transportas irrysiai). Vilnius: Statistics Lithuania, 2005. 141 p. (in Lithuanian).

[5.] Black, J. A.; Paez, A. and Suthanaya, P. A. Sustainable Urban Transportation: Performance Indicators and Some Analytical Approaches. Journal of Urban Planning and Development, 128(4), 2002, p. 184-209.

[6.] Camagni, R.; Gibelli, C. and Rigamonti, P. Urban mobility and urban form: the social and environmental costs of different patterns of urban expansion. Ecological economics, 40(2), 2002, p. 199-216.

[7.] Girgonis, V. and Burinskiene, M. Information technologies in energy planning of cities and towns. Journal of Civil Engineering and Management, 8(3), 2002, p. 197-205.

[8.] Anderson, M. A. Evaluation of models to forecast external-external trip percentages. Journal of Urban Planning and Development, 125(3), 1999, p. 110-120.

[9.] Siewczynski, B. Computer visualisation in urban planning of highway surroundings. Journal of Civil Engineering and Management, 10(1), 2004, p. 61-65.

[10.] Loukapoulos, P.; Jakobsson, C.; Garling, T.; Schneider, C. M. and Fujii, S. Car-user responses to travel demand management measures: goal setting and choice of adaptation alternatives. Transportation research: part D, 9 (4), 2004, p. 263-280.

[11.] Eliasson, J. and Mattsson, L. G. A model for integrated analysis of household location and travel choices. Transportation research A, 34, 2000, p. 375-394.

[12.] Schwanen, T.; Dieleman, F. M. and Dijst, M. Travel behavior in Duch monocentric and polycentric urban systems. Journal of Transport Geography, 9(3), 2001, p. 173-186.

[13.] Arampatzis, G.; Kiranoudis, C. T.; Scaloubacas, P. and Assimacopoulos, D. A GIS-based decision support system for planning urban transportation policies. European Journal of Operational Research, 152, 2004, p. 465-475.

[14.] Brown, A. L. A GIS-based environmental modeling system for transportation planners. Computers, Environment and Urban Systems, 26(6), 2002, p. 577-590.

[15.] Mahmassani, H. S. and Liu, Y-H. Dynamics of commuting decision behavior under advanced traveler information systems (ATIS). In: Proc of the International Association Travel Behavior Research (IATBR) 1997 Conference, Austin, Texas, Sept 21-25, 1997, p. 91-107.

[16.] Abdelghany, A. F.; Mahmassani, H. S. and Chiu, Y-C. Spatial micro-assignment of travel demand with activity/ trip chains. Transportation Research Record, 1777, 2001, p. 36-46.

[17.] Geertman, S. C. M. and Ritsema van Eck, J. R. GIS and models of accessibility potential: an application in planning. International Journal of Geographical Information Systems, 9(1), 1995, p. 67-80.

[18.] Kalanta, S. Basics of consiliatory optimisation. Formulation of linear tasks and solution methods (Taikomosios optimizacijos pagrindai. Tiesiniu uzdaviniu formulavimas ir sprendimo metodai). Vilnius: Technika, 2003. 336 p. (in Lithuanian).

Marius Jakimavieius (1), Aida Macerinskiene (2)

Dept of Urban Engineering, Vilnius Gediminas Technical University, Sauletekio al. 11, LT-10223 Vilnius, Lithuania.

E-mail: (1) m.jakimavicius@hnit-baltic.lt (2) aida.macerinskiene@ap.vtu.lt

Marius JAKIMAVICIUS. PhD student of Vilnius Gediminas Technical University, Faculty of Environmental Engineering, Dept of Urban Engineering, LT. Member of Association of Lithuanian Surveyors. Research interests include GIS and GPS systems, GIS based solutions for transport analysis tasks, optimisation of transport system according to urban areas.

Aida MACERINSKIENE. PhD. Lecturer of civil engineering of Vilnius Gediminas Technical University, Faculty of Environmental Engineering, Dept of Urban Engineering, LT. Her research interests include GIS usage in territory planning, the tourism planning in different comprehensive, special, and local-levels.

Table 1. Data on Lithuania motorisation level

Year 1955 1960 1965 1970 1975 1980 1985

Veh/1000 1 5 6 11 35 69 93
inhabitants

Year 1990 1995 2000 2001 2002 2003 2004

Veh/1000 129 190 315 304 316 336 349
inhabitants

Table 2. Solution of the shortest driving route

1) Iteration y1 = 0
2) Iteration y2 = 300
 y3 = 200
 y4 = 250
3) Iteration y5 = min(y2 + s25, y3 + s35, y4 + s45) =
 min(300 + 250, 200 + 300, 250 + 450) =
 500 m
 y6 = min(y2 + s26, y3 + s36, y4 + s46) =
 min(300 + 400, 200 + 350, 250 + 150) =
 400 m
4) Iteration y7 = min(y5 + s57, y6 + s67) = min(500 + 50,
 400+200) = 550 m

Table 3. Solution of the fastest driving route

1) Iteration y1 = 0
2) Iteration y2 = s12 = 30
 y3 = s13 = 20
 y4 = s14 = 25
3) Iteration y5 = min(y2 + s25, y3 + s35, y4 + s45) =
 min(30 + 25, 20 + 30, 25 + 45) = 50 s
 y6 = min(y2 + s26, y3 + s36, y4 + s46) =
 min(30 + 15, 20 + 35, 25 + 15) = 40s;
4) Iteration y7 = min(y5 + s57, y6 + s67) =
 min(50 + 5, 40 + 10) = 50 s

Table 4. Solution of the least loaded driving route

1) Iteration y1 = 0
2) Iteration y2 = 300
 y3 = 200
 y4 = 250
3) Iteration y5 = min(y2 + s25, y3 + s35, y4 + s45) =
 min(300 + 250, 200 + 300, 250 + 450) = 500 m
 y6 = min(y2 + s26, y3 +s36, y4 + s46) =
 min(300 + 100, 200 + 350, 250 + 150) = 400 m
4) Iteration y7 = min(y5 + s57, y6 + s67) = min(500 + 550,
 400 + 100) = 500 veh/h

Table 5. Solution of the least loaded driving route

 Average
Optimization Route Driving traffic flow
Criteria length (m) time (s) (veh/h)

The shortest 1344 188 678
route
The quickest 1965 167 648
route
The least 1387 179 612
loaded route

Fig 1. Dynamics of motorisation level

 Number of motor vehicles Number of cars per
 per 100 inhabitants 1000 inhabitants

1996 285 240
1997 268 226
1998 310 266
1999 323 288
2000 351 324
2001 374 321
2002 426 340
2003 458 365
2004 476 384

Note: Table made from line graph.