With the recent launching of the 8th Compass navigation satellite, the Compass navigation satellite system has been completed. To augment the performance of this system for navigation on the Chinese mainland, it is necessary to optimize its current regional constellation. This paper analyzes the inadequacies of the current regional constellation and presents a method for optimizing the augmented regional constellation in which a new evolutionary algorithm and a Compass constellation optimization problem model are proposed. Three objective functions (the Weighted geometric dilution of precision (WGDOP), the number of visible satellites and constellation costs) are then introduced. Three optimal solutions were obtained through the optimization process. Based on a comparison of the performance of the three optimal solutions, this paper suggests that one GEO satellite and one IGSO satellite be added to complete the Compass augmented regional constellation.