A SET COVERING APPLICATION IN MINIMUM ROUTE GENERATION

The use of improved storage procedures for route generation for demand actuated systems is necessary for practical implementation of many routing systems. Neighborhood Storage is a method of storing the system information which requires a covering to be generated for a number of sets of points which are generated by the method. The set covering problem is important to the overall practical implementation of the method. The method requires M coverings to be generated for each application. Thus, computational efficiency is of considerable importance in obtaining the required coverings. The problem is defined and formulated as a set covering problem. Solutions are carried out for a number of examples and the results for the optimum covering are reported. An algorithm is then presented for obtaining a suboptimum covering with considerable efficiency in computation and overall data manipulation. The example results are also included. The algorithm presented is applicable to any (V;A,B) modeled in R2.