Selecting an appropriate new store location is a complex multi-criteria decision-making problem because potential locations must be evaluated using multiple criteria with different performance characteristics. This study proposes an integrated distance-based Multi-Criteria Decision-Making framework using RECA Weighting combined with TOPSIS, SPOTIS, and EDAS to determine objective criterion importance and evaluate the stability and robustness of alternative rankings. The dataset consists of eight potential store locations evaluated using six criteria: Rental Cost, Building Area, Accessibility, Consumer Traffic, Parking Availability, and Infrastructure. RECA Weighting is applied to determine objective criterion weights based on performance variation, while TOPSIS, SPOTIS, and EDAS are used to generate preference scores and rankings through different distance-based evaluation mechanisms. The results show that Consumer Traffic obtains the highest criterion weight of 0.1824, while Parking Availability receives the lowest weight of 0.1422. The ranking results identify LS5 as the best-performing alternative, followed by LS3, although several alternatives exhibit different ranking positions across the applied methods. Weight-variation analysis using Spearman rank correlation shows that SPOTIS achieves perfect ranking stability with a correlation of 1.0000, TOPSIS demonstrates very strong stability with a correlation of 0.9286, while EDAS produces a lower correlation of 0.1429, indicating greater ranking variation. These findings demonstrate that SPOTIS provides the highest robustness to criterion weight changes, followed by TOPSIS, whereas EDAS is more sensitive to weight variations due to its average-solution-based evaluation mechanism. Overall, the proposed framework provides a comprehensive approach for objective weighting, ranking stability assessment, sensitivity analysis, and robustness evaluation in new store location selection.