KUORMA: A Collection of APS-Algorithms for Forest Industry Wood Transport

by Juha Savola, Hannu Rummukainen and Olli Jokinen

The KUORMA system (English acronym LOAD) is a combination of APS (Advanced Planning and Scheduling) algorithms and the system infrastructure services used in the field of forest industry.

These algorithms enable the forest industry to optimise the transport of wood to sawmills and paper and pulp mills using a nationwide calculation area. The entire operation includes about 250 trucks, about 100 points of delivery and about 10 000 wood batches daily. The KUORMA system is part of a more extensive information system, which incorporates optimisation algorithms for wood harvesting, transport planning and routing.

The KUORMA system was developed in a commercial project headed by TietoEnator as a systems integrator. VTT Information Technology was a sub-contractor responsible for the development of transportation algorithms. The customer was Stora Enso Finland. Stora Enso uses about 17.3 Mm3 of domestic wood annually, corresponding to 288 000 truckloads.

Figure 1: A truck unloading at a paper mill.

Transportation is a remarkable source of cost in the forest industry, especially in Finland where the distances are long and the wood ownership includes private citizens. Not only are wood batches of varying sizes are distributed over some 3 000 000 road segments, but the price for standing timber is relatively high. In order therefore to reduce wood procurement costs for competitiveness reasons, one must concentrate on transportation costs. Stora Enso had a system developed by the coalition in the early 1990s that used greedy algorithms. Its performance and the acceptability of the solutions it provided had reached their limits. Furthermore, improvements in technology had made it possible to use a low-cost Linux workstation cluster with a large amount of essential RAM memory.

The development project started in July 2001, and through October 2002 the system was gradually improved through operational use.

The Techniques Employed
The main components of the KUORMA system are the road network infrastructure, the load cluster model, the load assignment model and the routing model.

The key information for the road network infrastructure is the nationally administrated and updated road material, which covers the whole of Finland and contains about 3 000 000 segments of road, including small, private forest roads. The central attributes are road class, x-y geometry and length. The basic road material is organised as an undirected graph structure. Because the set of current objects with a coordinate varies all the time, the calculation of distances had to be performed uniquely for each data set. Nevertheless, the operative calculation effort can be reduced using so-called supermatrices (size 15 000 - 20 000 squared) based on all the distinct points at any given time. Supermatrices are calculated in a Linux cluster during idle hours. When the actual matrices are calculated utilising supermatrises, the hit ratio can exceed 95 %, depending of course on the time between those two calculations. The calculation time is typically a few minutes using a 2.2GHz dual-processor PC with 2Gb RAM. The basic solution given by the road infrastructure is the fastest or shortest distance between any two objects using three different road weight classes

Load Cluster Model
In the first stage of the KUORMA system, batches of wood in the forest are clustered into loads that fit into trucks. This is done regularly as newly cut stands are entered into the database, and old wood is transported away.

Large batches are easy to divide into truckloads, but due to the large number of private forest owners in Finland, many batches containing several wood types are quite small, and may only be accessible by low-quality, temporary roads. The road quality is modelled by a weight limit, which represents a hard constraint for the order in which the batches of a load can be collected. The primary objective in the optimisation model is the minimisation of total driving time for load collection.

Load Assignment Model
The assignment model calculates the best destinations for all loads to be transported. The destinations are factories, sawmills and railway stations (for final transportation by train to the factories). Assignment is taken as input transportation costs based on distances, the daily wood requirements of the destinations, the availability of loads per day and regional and team goals.

Figure 2: Snapshop from road network of a load cluster model. Before reduction.	Figure 3: Snapshop from road network of a load cluster model. After reduction.

Wood requirements are described as amounts for different kinds of wood and penalty costs for deviation from the desired amount. The calculation period is divided into an operational period (a few days) and a tactical period (some weeks). In the operational period, destinations are assigned for every load. In the tactical period, standing wood marked for cutting is optionally reserved for certain destinations because the loads are not yet to be transported.

The results generated by the model show the destinations for loads, the transportation day within an operative period, and the opening day for every stand marked for cutting in the tactical period.

Load Routing Model
The third stage comprises the routing and scheduling of trucks for the immediate future. At this stage, the load destination can no longer be changed, but the choice of which loads to transport in the operational period is free subject to certain constraints. The primary objective is to minimise the total driving costs. Trucks may operate all over Finland, but they must regularly return to their home areas to exchange drivers, and may also have scheduled days off. The paper mills and sawmills operate on exacting schedules, and must therefore be provided with specific numbers of loads of different types within given time intervals, although deviations are possible with associated penalty costs. There are a number of other constraints and secondary goals, making this the most complicated optimisation model in the KUORMA system.

Future Activities
The transportation branch of the forest industry stands to benefit greatly from optimisation algorithms. Stora Enso anticipates a 5% saving in wood transportation costs compared to the old, greedy-algorithm approach. Our approach can also be applied to other transportation segments.

Further work on the KUORMA system could include evaluating multimodal transports, adaptation of new road material containing z-coordinates (hills) and making use of daily weather data.

Links:
http://www.vtt.fi/tte/projects/fleet_management/kuorma.html
http://www.vtt.fi/tte/projects/fleet_management/dynatrans.html

Please contact:
Juha Savola, Hannu Rummukainen, Olli Jokinen, VTT Information Technology
E-mail: juha.savolavtt.fi