A SET COVERING APPLICATION IN MINIMUM ROUTE GENERATION
Jiaqi Wang, M.H. Mickle, Ronald G. Hoelzeman · Kybernetes · 1974
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.