Using GIS for Optimisation in Transportation Planning

by Günter Kiechle

The use of Geographic Information Systems (GIS) for preparing input data for optimisation algorithms improves the practical applicability of such algorithms in the field of transportation planning. This promising combination of technologies is the subject of a collaboration between the University of Vienna and Salzburg Research.

Vehicle Routing Problems (VRPs) are a widely investigated class of problems in combinatorial optimisation, and include many transportation tasks (eg parcel services). In general, a VRP consists of a set of customers that must be served via a fleet of vehicles, each of which leaves from and returns to a central depot. The type of VRP determines whether customers have goods delivered to them, are transported from one location to another, or are served in some other way.

Using GIS for Real-World Input Data
In research, most solution techniques for this class of problem are designed and tested by means of synthetic problem structures. However, the tackling of real-world VRPs requires a thoroughly elaborated data basis in order to provide reasonable outcomes. If this is not the case, even the best solution techniques are of no use for practical applications.

Essential input data for real-world VRPs is gathered by using Geographic Information Systems (GIS). Whereas most researchers use Euclidean distances between customers and depots for their optimisation algorithms, a GIS can provide real distance information derived from a digital road network.

Experiences in former projects showed that using distance data of limited quality in optimisation algorithms leads to results of even more limited quality. In the worst case, a valid solution for a given input dataset might actually be unfeasible in reality.

To get distance information of sufficient quality, the most detailed street network commercially available for the considered region should be used. Unfortunately static distance information from a digital road network does not correlate directly with real travel times because of dynamic influences like traffic jams, road works and weather conditions. Travel times also depend on parameters such as driving style and vehicle type, which are particularly hard to quantify.

Empirical Evaluation of Travel Times
In a former project, the quality of calculated driving times was evaluated by comparing them with actual driving times for 91 trips within a range of 20 to 250 kilometres in eastern Austria. The average, maximum, minimum and standard deviation of actual minus calculacted driving times in minutes recorded by tachographs is given in Table 1.

This analysis comprised trips to more than forty locations carried out by more than twenty drivers on several days and at all times of day. All the vehicles were of the same type and were able to exceed the allowed speed limit on all the roads used. These results enable us to specify safety margins that are suitable to counteract these observed variations in driving time. The results of this evaluation were used to define reasonable buffer values for optimisation procedures in order to achieve highly robust solutions for use in practical scenarios.

Integration of GIS and Optimisation
In general, optimisation algorithms are implemented in a highly separated software component and used via a well-defined interface. GIS are not only needed for input data processing but in some cases also for enclosing the user interface of a decision support system that guides decision makers by allowing them to schedule vehicles visually. In the following example, GIS plays an integrating role by handling user interactions as a graphical user interface on the one hand and managing communication between all other required software components on the other. A typical example of system architecture is depicted in Figure 1.

Figure 1: Component diagram.

The system works as follows: after retrieving customer coordinates and other relevant data from the CRM-Application, the Front-End uses the Network Toolbox to obtain a distance matrix containing travel times for all possible customer pairs. The Front-End forwards all information to the Optimisation Module, which applies the optimisation algorithm. Resulting tours are returned to the Front-End and given a geographical representation using the Network Toolbox. Finally, a complete list of travel plans including customers, street paths and visiting order for the requested period of time may be generated and presented to the application user.

Implementing the Optimisation Algorithm
Vehicle Routing Problems belong to the group of NP-complete programs that are known to be hard to solve. In general, the computation time for solving a VRP increases exponentially with the overall number of customers. Even execution times for heuristics and metaheuristics suffer from this effect. For optimisation problems of a certain size only the development and implementation of highly parallel algorithms may achieve reasonable execution times.
Optimisation algorithms are usually implemented in Fortran or C due to the high-performance compilers that are available for these languages. Next to efficiency, additional criteria such as programming convenience, adoption of technology and availability of tools could also justify the use of C++ as a programming language.

Real World VRP Example
The use of GIS for optimisation in transportation planning described above was applied in a project dealing with the development of a decision support system for transportation of blood donations in Austria. The underlying optimisation problem originates from the blood collection process of the Austrian Red Ccross blood program, where processing requirements state that all blood must be processed in one centrally located blood bank within four hours of donation. This restriction causes a significant amount of vehicle movement, which could be reduced with problem-tailored optimisation algorithms by more than 25%, as measured in total driving time. Figure 2 depicts the user interface of the transportation-planning tool developed in this project.

Figure 2: User interface of a decision support system for transportation planning.

Please contact:
Günter Kiechle
Salzburg Research Forschungsgesellschaft, Austria
Tel: +43 662 2288 421
E-mail: guenter.kiechleimgsalzburgresearch.at