Frank Schweitzer, Werner Ebeling, Helge Rose, Olaf Weiss:

Optimization of Road Networks Using Evolutionary Strategies

in:

Evolutionary Computation 5/4 (1998) 419-438

Abstract:

A road network usually has to fulfill two requirements: (i) it should as far as possible provide direct connections between nodes, to avoid large detours, (ii) the costs for road construction and maintainance, which are assumed proportional to the total length of the roads, should be low. The optimal solution is a compromise between these contradicting demands, which in our model can be weighted by a parameter. The road optimization problem belongs to the class of frustrated optimization problems. In this paper, evolutionary strategies, such as the Boltzmann and Darwin strategy, are applied to find different optimized solutions (graphs of varying density) for the road network in dependence on the degree of frustration. We show, that the optimization process occurs on two different time scales. In the asymptotic limit, a fixed relation between the mean connection distance (detour) and the total length (costs) of the network exists, which defines a range of possible compromises. Further, we investigate the density of states, which describes the number of solutions with a certain fitness value in the stationary regime. We find that the network problem belongs to a class of optimization problems, where more effort in optimization certainly yields better solutions. An analytical approximation for the relation between effort and improvement is derived.

Keywords:

network, evolutionary strategy, frustrated problem, compromise

Back to Front Page