Tabu search optimization of forest road alignments combined with shortest paths and cubic splines

Abstract

This paper describes a program for optimizing forest road alignments using the Dijkstra shortest path method and a cubic spline function.We previously developed a method for optimizing forest road alignments once a series of intersection points (IPs) were selected manually using Tabu Search. The application of the program to a part of Capitol State Forest in Washington State, USA indicated that the program successfully found better alignments than manually selected initial alignments. In order to find initial solutions without manually initialized solutions, the Dijkstra method and a cubic spline function were combined with our optimization program. The Dijkstra method connected some segments between two end points and the spline function generated smooth vertical alignments between two end points based on the horizontal alignments. In order to adapt the new method for forest road design to our existing method, the program converted the spline curves to straight and parabolic sections. The solution using a spline function was 10% poorer than the solution without a spline function, but computing time significantly reduced from 73 hours to 19 hours using the spline function. Furthermore, the program generated smooth vertical alignments automatically. This study reports our initial effort to use the spline function in optimal road design. Additional investigation could improve solution quality using the Dijkstra method and cubic splines.