NEW ALGORITHMS FOR SOLVING LARGE-SCALE TRANSPORTATION PLANNING PROBLEMS

John SESSIONS, Professor, Woodam CHUNG, Graduate Research Assistant, Department of Forest Engineering, Oregon State University, Corvallis, OR 97331, UNITED STATES OF AMERICA, and Hans R. HEINIMANN, Professor of Forest Engineering, Swiss Federal Institute of Technology, Zurich, SWITZERLAND

Abstract

Many harvest planning problems involve the location of log landings and road locations to carry out harvest activities over time. The goal is to find the combination of road development and harvest equipment placement so as to reach the lowest cost, considering harvesting and transport costs, including investments in infrastructure. Recent demands now include environmental issues and goals. A new heuristic for solving transportation problems is described that builds upon previous algorithms. Two important advantages of the algorithm are that the objective function is flexible and that side constraints involving environmental issues can be incorporated.

Key words: transportation planning, heuristics, network analysis

Introduction

As stated above, many harvest planning problems involve the location of log landings and road locations to carry out harvest activities over time. Traditional solution methods have been by manual trial and error. With the rapid development of mathematical optimization techniques, notably linear and dynamic programming and the availability of computers following the Second World War, interest developed in applying these techniques to improve decision-making in transportation planning. The purpose of this paper is to briefly review exact and approximate methods for solving the fixed and variable cost harvest planning problem and to suggest a new algorithm that builds upon earlier algorithms and uses modern combinatorial optimization techniques.

Because both fixed costs (equipment placement, road construction and reconstruction costs) and variable costs (yarding costs, truck transportation) are considered, the cost minimization problem of identifying the road system, truck routes, and placement of harvesting equipment is a mixed integer linear programming problem. The TRANSHIP model (Kirby et al., 1981) is an example of a mixed integer program developed to solve the fixed charge transportation problem. Because the solution time for mixed integer linear programming problems rises rapidly with problem size, a number of heuristic algorithms (approximate solution methods) have been developed to solve problems involving mixed integer linear programming formulations, often exploiting the special structure of the particular problem.

The harvest planning problem, being network based, has a special structure and falls within a class of operations research problems known as the fixed charge network problem. To solve the fixed charge network problem in North American forestry, several heuristic approaches have been developed. The heuristic approaches often embed some form of variable cost shortest path network algorithm within them. The shortest path algorithm, a variant of dynamic programming, can be solved much more quickly than the equivalent linear program and often provides a useful component of heuristic algorithms. Applications in North American forestry can be divided into two lines: i) those that combine mixed integer linear programming with network programming; and ii) those that combine network programming with other rules.

The Timber Transport Model Algorithm

The Timber Transport Model developed for the United States Department of Agriculture (USDA) Forest Service during the early 1970s (Sullivan, 1974) is an example of combining mixed integer linear programming with network programming. The Timber Transport Model is a route-based algorithm where the decision variable is how much timber volume should be assigned to a route.

The solution algorithm has two phases. In the first phase, candidate routes (paths) were developed by using a k-shortest path network algorithm. The k-shortest paths, considering only variable costs from entry points into the network to candidate exit points, were first determined. In the second phase, a mixed integer linear program was used to optimally select among the candidate routes to determine the combination of routes and volume assignment that minimized the sum of the fixed and variable costs. Because of solution times, the number of candidate routes per entry point into the network was limited, often to fewer than 25 candidate routes. Wong and Kirby (1983) cautioned that although each of the two components of the heuristic developed optimal solutions for each phase, the combination of the two phases might provide solutions far from optimal when combined. On many practical problems, however, good results were reported.

The Prorate Algorithm

The Prorate Algorithm in the MINCOST program developed by Bill Schnelle of the USDA Forest Service (1980) during the same period is an example of a heuristic that embeds the shortest path algorithm with other rules to solve the fixed charge and variable cost problem. The Prorate Algorithm solved a series of variable cost problems by converting the fixed costs into equivalent variable costs by dividing the fixed costs by the volume transported over the arc. The equivalent variable cost technique had been previously applied by Cooper and Drebes (1967) as part of a heuristic solution to solve the fixed charge problem using linear programming.

The algorithm proceeds in a series of stages. In the first stage, the algorithm begins by solving a variable cost shortest path problem by finding the shortest path from each entry point (timber sale node) to the destination node (mill node). The volume that was transported along each arc is then summed. A “new” variable cost is then calculated by dividing the fixed cost of the arc by the total volume transported across it in the previous stage and adding this cost to the variable cost. As the algorithm progresses, the solution stabilizes until the sum of the volume over each are in the current phase does not differ from the last phase and the algorithm terminates.

The shortcomings of the Prorate Algorithm were illustrated by Wong (1981) in a series of examples that showed that the Prorate Algorithm could stall in local minimum. The NETCOST algorithm (Weintraub and Dreyfus, 1985) and the NETWORK algorithm (Sessions, 1985) are similar to the Prorate Algorithm but each uses a series of rules to avoid stalling in a local minimum. The NETWORK algorithm also extended applications to multiple period, multiple product, value maximization or cost minimization through introduction of special arcs.

Modern combinatorial algorithms

The practical importance of combinatorial problems in many industries has continued to stimulate interest in solving large problems. Although there have been advances in solving large mixed integer linear programming programs that can provide optimal solutions, the decrease in solution time still has not been dramatic enough to abandon heuristic approaches. Instead, development of heuristics has intensified along several broad lines: i) stochastic Monte Carlo neighbourhood search heuristics, such as Simulated Annealing (Kirkpatrick et al., 1983), Threshold Acceptance (Dueck and Scheuer, 1990), and the Great Deluge (Dueck, 1993); ii) non-stochastic search techniques, such as TABU search (Glover, 1989); and iii) evolutionary algorithms including genetic algorithms (Holland, 1975).

In forestry, applications of these techniques began in the early 1990s and have been growing rapidly in strategic and tactical forest planning. Applications using Simulated Annealing include Lockwood and Moore (1993), Sessions et al. (2000); using TABU search (Bettinger et al., 1998), Richards and Gunn (2000); and genetic algorithms (Mullen and Butler, 2000). NETWORK 2000 (Chung and Sessions, 2000) includes both Simulated Annealing and Great Deluge options to solve the fixed and variable cost network problem.

New challenges

One major challenge with transportation problems involving many routing options is the introduction of a very large number of feasible routes through a network. With the development of the Geographic Information System, network generation arising with node developments through grid cells can create large networks with many circuits.

Another challenge is the introduction of side constraints, that is, relationships between decision variables, outside of the normal fixed charge, variable cost structure often arising from environmental considerations or requirements.

A “new” approach

A new approach, combining past network heuristic approaches with modern combinatorial heuristic techniques, is suggested here as a way to address both new challenges.

The approach combines the route approach of the Timber Transport Model with use of equivalent variable costs that was the foundation of the Prorate Option of MINCOST, NETCOST, and NETWORK algorithms in a four-step process:

Step 1. Generate k-shortest paths from each origin to the destination. The k-shortest paths can either be based on variable costs only or can include equivalent variable costs. We have had best success in generating “blocks” of k-shortest paths with each block based upon the equivalent variables cost multiplied by a weighting factor. For example, for each origin, develop the k-shortest paths for n blocks of k-shortest paths where the equivalent variable cost of road segment i (EVC_i) is calculated using the following equation:

Step 2. Solve the combinatorial optimization problem of assigning the best route to each origin (sale) to minimize the sum of fixed and variable costs using a heuristic. In this case we are using Simulated Annealing.

Step 3. Using the volumes over each road segment resulting from the assignment in Step 2, recalculate the equivalent variable costs for each road segment.

Step 4. If the number of desired cycles has not been completed, return to Step 1 using the equivalent variable costs calculated from Step 3.

Our initial computational experience is that this process can find the optimal solution for a set of test problems used to compare NETCOST and NETWORK and with some experimentation with weighting factors and block sizes has yielded superior solutions over NETWORK for a large problem.

Example

The input and results from a single period network (see Figure 1) modified from Wong (1981) are shown in Tables 1 and 2. In addition to 13 possible construction projects, a road improvement project for link 4–6 will also be automatically considered as link 4–11 and dummy link 11-6. The minimum total cost found by the NETWORK Algorithm (Sessions, 1985) is US$507 058, while “new” NETWORK Algorithm found 0.16 percent better answer, which is $506 234. Both results are illustrated in Figure 4.

Future Work

Advantages of this heuristic are that its objective function is more flexible than NETWORK, and side constraints can be easily added. Alternative objective functions - such as minimizing total road length, minimizing cost subject to an open road length constraint and including decommissioning costs - can be readily accommodated.

Table 1. Network input for example

Table 2. Harvest input for example (single period)

Figure 1. Best solutions found from two NETWORK algorithms: (a) old NETWORK, (b) new NETWORK Algorithm.

References

Bettinger, P., Sessions, J. & Johnson, K.N. 1998. Ensuring the compatibility of aquatic habitat and commodity production goals in eastern Oregon with a TABU search procedure. Forest Science, 44:96–112.

Chung, W. & Sessions, J. 2000. NETWORK 2000: a program for optimizing large fixed and variable cost transportation systems. In proceedings Eighth systems analysis symposium on forest resource. Kluwer Press.

Cooper, L. & Drebes, C. 1967. An approximate solution method for the fixed charge problem. Nav. Res. Log. Quart,. 14:101–113.

Dueck, G. 1993. New optimization heuristics: the great deluge and record-to-record travel. J. of Computational Physics, 104:86–92.

Dueck, G. & Scheuer, T. 1990. Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. J. of Computational Physics, 90:161–175.

Glover, F. 1989. TABU search - Part I. ORSA Journal of Computing, 1: 190–206.

Holland, J. 1975. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor.

Kirby, M., Wong, P. & Hager, W. 1981. Guide to the Tranship model. USDA Forest Service, Pacific Southwest Forest and Range Exp. Station, Berkeley, CA.

Kirkpatrick, S., Gellat, C. & Vecchi, M. 1983. Optimization by simulated annealing. Science, 220: 671–680.

Lockwood, C. & Moore, T. 1993. Harvest scheduling with spatial constraints: a simulated annealing approach. Can. J. of Forest Research (23):468–478.

Mullen, D. & Butler, R. 2000. The design of a genetic algorithm based spatially constrained timber harvest scheduling model. In proceedings Seventh symposium on systems analysis in forest resources, USDA Forest Service, GTR NC-205, p 57–65.

Richards, E. & Gunn, E. 2000. A model and TABU search method to optimize stand harvest and road construction schedules. Forest Science, 46(2)188–218.

Schnelle, B. 1980. MINCOST users instructions. USDA Forest Service Report, Northern Region, Div. of Engineering, Missoula, MT.

Sessions, J. 1985. A heuristic algorithm for the solution of the fixed and variable cost transportation problems. In Proceedings of the 1985 symposium on systems analysis in forest resources, Society of American Foresters, Georgia Center for Continuing Education, Athens, GA. p. 324–336.

Sessions, J., Johnson, D. Ross, J. & Sherar, B. 2000. The Blodgett Plan: an active management approach to developing mature habitat. J. of Forestry, 98(12)29–33.

Sullivan, E.C. 1974. Network User's Guide. Spec. Rep. Inst. Transport and Traffic Eng. Berkeley, Univ. of California.

Weintraub, A. & Dreyfus, S. 1985. Modifications and extensions of heuristics for solving resource transportation problems. Coop Agreement Final Report, Univ. of Calif., Berkeley. 76 pp.

Wong, P. 1981. An empirical evaluation of the proration option of MINCOST network program. USDA Forest Service Engineering Field Notes. Washington, D.C. 15–22.

Wong, P. & Kirby, M. 1983. An empirical evaluation of the Timber Transport Model, personal communication.