International O.R.: Forestry logistics in Sweden

Swedish forest industry agrees on common distance calculation based on advanced O.R. methodology.

By Patrik Flisberg and Mikael Rönnqvist

forestry in Sweden

Road attributes such as length, width and surface play a key role in determining “best” routes – and transportation fees – for logging trucks in Sweden.

In developed countries, many car drivers use a GPS tool to find the best route between a starting point and an ending point. Typically, such tools have an option of selecting the shortest distance, fastest route or a combination of both. For most people this is enough. However, for heavy truck drivers working in the forestry industry, such tools may suggest routes that are ill-suited for trucks … or the GPS tool may be unable to find any route at all.

In Sweden, about two-thirds of the roads are private, and the percentage is much higher in forested areas, which creates GPS problems starting with the lack of publically available data for privately owned forest roads. Another concern for the forestry industry is that roads suggested by the GPS tool, based on shortest distance for example, may be unsuitable for heavy trucks, leading to high fuel consumption, long driving hours or even dangerous driving on narrow roads with no space to pass trucks traveling in the opposite direction.

Trucking transportation rates in Sweden are based on the loaded distance driven, which means that truck drivers and forest companies must agree on the “best” distance and route between a forest harvesting area and a mill or terminal.

In the mid-1990s, Swedish forest companies agreed to develop a road database that included detailed information of all privately owned roads. Each company collected this information and inserted it in a common Swedish road database, which includes information about all state and municipality roads. The information collected includes a description of road attributes including, among other features, length, speed limits, road classification, width and surface. This work is now completed, and the task today is to continuously update the database with new information.

The new road database solves the first of the issues raised above. What about finding a route and distance that can be agreed upon by both parties? This involves establishing “weights” (in this context, relative influence or importance of measurable characteristics) for different attributes describing the road network. Such a project was established in 2007 by SDC, an organization owned by all Swedish forest companies that is responsible for managing the information flow in all forest transportations.

Early in the project it was assumed that such weights could be set manually. However, since the total number of weights reached 56, it soon became obvious that such an approach would fail. Instead, an approach based on inverse optimization was successfully applied. This involves establishing a set of routes, called “key routes,” agreed to by all parties. These are then used as the optimal solution of an inverse minimum-cost model where the main decision variables are the weights, and the objective is to maximize the number of key routes generated as solutions from minimum-cost route problems with the found weights.

The solution, i.e., values of the weights, is then used in a Web-based tool for truck drivers and forest companies as a basis for both invoicing and direct route proposal. The Web-based tool uses a Dijkstra-based algorithm to establish the minimum-cost route with the proposed weights. This article focuses on the forestry transport problem, a Web-based solution, users, systems, its O.R. challenges and some key results and experiences. A more detailed description of the model, method and analysis can be found in Flisberg, et al. (2012).

Forest transportation in Sweden

The forest industry is an important export industry for many countries (D’Amours, et al., 2008). Transportation itself accounts for about 25 percent of the overall procurement cost of forestry products in Sweden (where the transportation cost by logging trucks totaled about $800 million in 2011). The volume harvested was 73 million cubic meters transported by 1.7 million truckloads. Each of these truckloads had an average transportation distance of 98 kilometers, and each truckload required an invoice as the basis for the payment transaction.

Since the payment is based on transport agreements, which in turn are expressed as a function of the loaded distance (concave piece-wise linear function), the correct and agreed distance needed to be determined. Traditionally, distances have been agreed to by both parties in a manual fashion. However, this approach has a number of drawbacks, starting with the difficulty in formally agreeing on the distances between harvest areas and mills. In 2011, the number of harvest areas was 122,000 and the number of mills was 1,000. This corresponds to a huge number of distances, even if the number of mills for each harvest area is limited. The geographical distribution of harvest areas and mills is shown in Figure 1. Note that some mills are outside Sweden.

forestry in Sweden

Figure 1: Geographical distribution of the harvest areas (green dots) and mills (red dots) in Sweden in 2011.

The situation is further complicated by the fact that the parties have opposite objectives. If you ask a forest company manager what route the driver should take, he or she would aim for the shortest distance (as this has a minimum cost), but if you ask the truck driver, he or she would prefer a longer route since this would result in higher pay. Besides the money issue, drivers list a number of reasons in favor of a longer route, including a preference for special forest roads built for heavy forest transports and avoiding:

  • roads with low speed limits, i.e., they prefer a longer route with higher speed limits if there are time savings;
  • roads of low quality as this increases maintenance costs and fuel consumption;
  • driving in towns where there may be many stop signals, which increase both route time and fuel consumption;
  • certain private roads that require a fee to use them; and
  • roads with low width as the possibility for two trucks to pass each other goes down. In such cases the trucks must meet at designated passing locations.

Transport agreements may also provide a bonus if the truck driver operates in a “difficult area” with many low quality roads or difficult terrain. Such a bonus is an agreement on top of an underlying base tariff. Although the parties try to establish “good” distances, it may differ between different forest companies and truck companies. Figure 2 provides an example of 853 invoiced truckloads for one specific transport distance, i.e., the same start and end point. In this case, 51 different invoiced distances varied between 57 and 243 kilometers. The average invoiced distance is 149 kilometers, but the correct and agreed distance today is 134 kilometers. This example, together with many others, has led to a desire to standardize the distance computation so that all companies use the same basis. This would lead to simplified procedures, saved negotiation time and a more equitable system.

forestry in Sweden

Figure 2: Illustration of 853 invoiced truckloads between the same pair of nodes with 51 different invoiced distances.

Swedish road database

The Swedish National Road Database (NVDB) was developed through collaboration between the Swedish National Road Administration, the Central Office of the National Land Survey, the Swedish Association of Local Authorities and the forest industry. The database contains digital information about all Swedish roads: the state road network, the municipal road and street network and private road networks. All roads, totally approximately 560,000 kilometers, are described geometrically, topologically and with detailed information about each road segment. The database provides special routes for driving heavy loads inside some cities and the “last mile” to some mills, along with restrictions on maximum weights on bridges. These details are handled as an add-on to NVDB, creating the Forestry National Road database (SNVDB). During the past decade, Swedish forest companies have made large investments in order to collect all the necessary data.

SDC [9] is owned by the forestry industry in Sweden in the form of an economic association/industry consortium. SDC provides and refines information between forest and industry through industry common IT- solutions. More than two million forest transports take place in Sweden every year (including movements between mills and/or terminals). Each transport includes information about volume, assortment, starting point in the forest, ending point at industries, contractual distance, time stamps, carrier, wood owner, etc. SDC is also responsible for maintaining the SNVDB. One key logistic service SDC provides is to compute a distance between loading and unloading points. This is handled through a Web-based support tool where the member forest companies can compute the distances for invoicing and also get a route provided on a screen-map.

To use the SNVDB it is first necessary to convert the basic data from the database into a network of nodes and arcs. Currently, this network consists of about 2.20 million nodes and 4.43 million arcs. A node represents a crossing or a point where a feature of the road changes. For example, if the speed limit changes from 70 km/h to 50 km/h, a node is introduced. Each arc has a set of features and attributes. Each arc has a given length and one value for each feature. For example, only one value exists for the road feature “speed limit” even if there are many possible speed limits. This means that an arc always has a unique set of attribute values. In the proposed approach, nine road features are used. Within each feature there is a set of attributes. The total number of attributes (with an unique weight used in the distance computation) is 56. Table 1 provides a summary of the features and attributes used so far in the system.

forestry in Sweden

Table 1. Summary of road features and attributes used in the project.

An O.R. approach

It is easy to compute the shortest path, the fastest route or any path that has a given weight setting. To find the distance between two pairs of nodes in a network, it is possible to solve a minimum-cost path problem using, for example, a Dijkstra algorithm. An illustration of three weight settings – shortest, fastest or a combination (50-50) – is illustrated in Figure 3 where a part of the SNVDB network is given.

forestry in Sweden

Figure 3: Illustration of three potential routes: shortest (black), fastest (red) or 50-50 of each (green)) between a pair of nodes in the SNVDB network north of the cities Stockholm and Uppsala.

The “Krönt Vägval” project (in English, calibrated route finder) was initiated in 2007 by SDC and the Forest Research Institute of Sweden. Originally, it was believed that the process to identify weights for the attributes would be straightforward and that near optimal weights would be easily found. However, it soon became clear that the manual process was very slow and that the quality of the weights was hard to evaluate. In 2008, the SDC and Forest Research Institute of Sweden decided to use a new quantitative approach based on operations research (O.R.) to establish the weights.

The organizations held long discussions about weight settings including using the Analytic Hierarchical Process (Saaty, 1990). However, the impact of different attributes was very hard to evaluate against each other. It was clear that both truck drivers and forest companies could fairly easy compromise on specific examples of “best” routes. It was hence decided to use an inverse optimization approach. Given a (combinatorial) optimization problem and a feasible solution to it, the corresponding inverse optimization problem is to find a minimal adjustment of the cost function such that the given solution becomes optimum. In this case, the problem is a weighted minimum-cost path problem and the adjustment of the cost function (i.e., arc costs) is done through the weights of the attributes.

In this approach, the authors’ research team first collected detailed information on so-called key routes that were agreed to between the parties. These key routes are critical for the approach and form the solution of the inverse minimum-cost path problem. The route information was collected from many companies; today, 1,285 such key routes are equally spread over Sweden. It requires a lot of work to collect the key-route information and keep the network updated. Ideally, the research team would like to be able to recreate all the key routes as the solution of individual minimum-cost path computations. However, it is not possible to create every combination of objective coefficients due to the limited set of weights.

The optimization model is an inverse minimum-cost path problem that is formulated in a mixed integer programming model. The main variables are the weights of the attributes. There are many alternatives of an objective function. After tests and discussions, the research team agreed to first maximize the number of key routes provided as a solution to the minimum-cost path problem, and second to minimize the deviation in distance between key routes not re-constructed and the best minimum-cost path. Since many paths may exist between any pair of nodes corresponding to each key route, the research team used 0/1 variables to identify the best minimum-cost route generated.

The constraints in the optimization model are used to identify the best minimum-cost route (whether or not it is a key route or not) and to set some practical limits on the weights. For example, the weights of the same road feature should be in the same order as the quality, i.e., a higher road quality should have lower weight than a lower road quality.

As a solution method the research team used a heuristic. In each iteration the team used the previously best weights to generate the corresponding minimum-cost routes. The minimum-cost routes that have not already been generated are added to the model, and the MIP model is resolved giving a new set of weights. This is repeated until no more routes are added. The average time to solve one minimum-cost route in the network is only 0.1 second. To solve the overall MIP model, the system considers 3,900 routes generated in 12 iterations. The last MIP model solved had 5,100 binary variables, 55 continuous variables and 5,300 constraints. The total solution time is about three hours. More details of the model and solution method can be found in Flisberg, et al. (2012).

Results and use

Since 2008, the research team has established and put in operation a number of weight settings in the SDC online system. The number of road features and attributes has increased during the project as results have been studied by a project board, evaluators in forest companies and by transporters. In addition, a number of mechanisms to control the route selection have been included. One example is passing routes to avoid traffic in cities and another is approach routes to industries. For the “last mile.” If an industry is situated in a town, a local requirement is often to follow a particular (approach) route.

During 2009-2010, the research team tested and evaluated a prototype at six companies located in different parts of Sweden. Each of the six companies selected a smaller district in which to test the system in practice. The result of the prototype testing was successful, and several companies decided to implement the system for all of their operations. The research team also compared reported distances to SDC during a 10-month period in 2008, which covered all invoiced routes (more than 1.2 million).

In the last weight setting, the Web system can exactly re-construct 81.7 percent of the key routes (1,050 out of 1,285). In cases where the key route is not re-constructed exactly, a large proportion is the same as the minimum cost route. On average, 93.9 percent of the length of the minimum cost route has exactly the same routing as the key routes. More importantly, the average distance for the minimum cost routes have an average distance corresponding to 99.9 percent of the average key-route distance. This means that there are some shorter and some longer routes, but on average the distances are almost the same.

Figure 4 provides graphical results using the weights. The length of each key route is normalized to 1, and the corresponding shortest path length is plotted as a proportion of each key route. All comparisons are sorted in increasing order. It is clear that the distances generated by the shortest path are of very bad quality. On average, they are about 7.4 percent shorter than the distance that was agreed. If the shortest path would be used, as it is in many planning systems with a given payment function, it would result in lost revenues for the transporters. With the proposed weight setting, the minimum-cost paths are of much better quality.

forestry in Sweden

Figure 4: Results of using either shortest path setting or the proposed weight setting on the 1,285 key routes normalized to length 1.

The support tool for route generation at SDC is a Web-based map system that makes it possible to view distances and actual routes, so it can be used as the basis for invoicing (distances) and operational routing. Along with the members of SDC, today more than 100 forest companies and transporters use the system. About 25 percent of all transports in Sweden use the system in batch mode to automatically generate direct invoicing.

Skogsåkarna organizes the transport for about 250 trucks, which makes it the largest transport organization in Sweden. Skogsåkarna has built a support tool [8] based on SDC’s route-generation component so any truck driver (not only their own members) can find distances and routes for their own route planning.

Correct distances are critical for tactical and operational planning. The distances computed are used in many forest-based decision support systems [see e.g., Andersson, et al. (2008), Flisberg, et al. (2009) and Frisk, et al. (2010)]. Figure 5 shows all flows of forest products on individual roads in Sweden during one year. This is possible to construct as the behavior of route selection can be estimated with high accuracy. From such maps it is possible to decide on road investments to improve transport efficiency or safety and to make detailed emission computations.

forestry in Sweden

Figure 5: All flows of forest products (logs and biomass) in Sweden during 2010. The volume illustrated corresponds to 70 million cubic meters and 6,173 million ton*km.

Further challenges

The Web-based tool described in this article is a work in progress. For example, the SDC revises the system on a continuous basis to correct bad information regarding certain roads and routes, and it is still possible to improve the quality of the weights.

Two additional features that could improve the quality of weights are “road curvature” and “vertical work.” If a road has many bends, the driving speed will be lower than if the road is straight. Hence, drivers tend to resist using roads with lots of bends. A key question is whether or not it is possible to collect the data needed to measure the bends. One approach to the problem is to assign each road segment (link in the network) a point sequence with horizontal and vertical coordinates, which exists today. With this geographical information as a basis, it is possible to establish a curvature value.

Truck drivers also want to avoid driving on roads with many hills as that results in increased fuel consumption. However, the vertical coordinates are currently not of the same quality as the horizontal ones. A process is now under way to make high-quality aerial surveys. When this survey is completed, it will be possible to compute the vertical work accurately as well.

Today, all invoiced transport costs in Sweden are based on distances. This may be unfair since two routes with different distances may be regarded as equally good (same minimum cost). However, the two routes are not compensated with the same payment.

An interesting idea for future development is to base the transport payment on road resistance instead of distance. Using this approach, the agreement would be based on the cost from the weight setting. This would be rational but requires a better understanding and acceptance of the weights by both truck drivers and planners. Also, it makes it possible to remove many special agreements for driving in “difficult” areas.

Patrik Flisberg (pafli@mweb.co.za) is a researcher at the Forestry Research Institute of Sweden (Uppsala, Sweden). Mikael Rönnqvist (mikael.ronnqvist@gmc.ulaval.ca) is a professor in industrial engineering at Université Laval (Québec, Canada). The authors acknowledge the contributions by Jan Selander, Anette Eliasson and Ulrica Zetterkvist at SDC for valuable discussions and input data for the case studies. Staff at the software company Triona and the Forestry Research Institute of Sweden have also made important contributions to the project over the years.

The authors dedicate this article to the late Bertil Lidén of the Forestry Research Institute of Sweden who worked intensively on this project and routing development in Sweden when he tragically died with his wife in a car accident in September 2012.

References

  1. G. Andersson, P. Flisberg, B. Liden and M. Rönnqvist, Ruttopt, 2008, “A decision support system for routing of logging trucks,” Canadian Journal of Forest Research, Vol. 38, p. 1784-1796.
  2. D. Carlsson and M. Rönnqvist, 2007, “Backhauling in forest transportation – models, methods and practical usage,” Canadian Journal of Forest Research, Vol. 37, p. 2,612-2,623.
  3. S. D’Amours, M. Rönnqvist and A. Weintraub, 2008, “Using Operational Research for supply chain planning in the forest product industry,” INFOR, Vol. 46, No. 4, p. 47-64.
  4. P. Flisberg, B. Lidén, M. Rönnqvist and J. Selander, 2012, “Route selection for best distances in road databases based on drivers’ and customers’ preferences,” Canadian Journal of Forest Research, Vol 42, No 6, p. 1,126-1,140.
  5. P. Flisberg, B. Liden and M. Rönnqvist, 2009, “A hybrid method based on linear programming and tabu search for routing of logging trucks,” Computers & Operations Research, Vol. 36, p. 1,122-1,144.
  6. M. Frisk, M. Göthe-Lundgren, K. Jörnsten and M. Rönnqvist, 2010, “Cost allocation in collaborative forest transportation,” European Journal of Operational Research, Vol. 205, p. 448-458.
  7. M. Rönnqvist, 2012, “OR challenges and experiences from solving industrial applications,” International Transactions of Operations Research, Vol 19, No. 1-2, p. 227-251.
  8. http://www.skogsakarna.se/smartonline/avstand/avstand.asp (in Swedish only)
  9. SDC: http://www.sdc.se/default.asp?id=1232&ptid= (Information in English)
  10. T. L. Saaty, 1990, “The Analytic Hierarchy Process: Planning, priority setting, resource allocation,” 2nd ed., R WS Publications, Pittsburgh.