Shortest route relaxation (SRR) of the Set Covering Problem (S C P ) is away of relaxing the problem to nd quick lower boundson the value of the objective function. A number of useful cost allocation strategies for the SRR are introduced which are applied to a number of test problems and computational results are presented.