| This paper introduces a novel network planning problem called Multi-stage Edge Server Deployment (M-ESD). The problem calls for a solution that (i) adds fixed edge servers to an existing Multi-access Edge Computing (MEC) network incrementally over multiple stages, e.g., in years, and (ii) optimizes the offloading of tasks to installed servers. More specifically, when upgrading a network, at each stage, the problem involves the following constraints: (i) budget (in \$), (ii) server deployment cost (in \$) and cost depreciation rate (in \%), (iii) number of tasks and their increase rate (in \%), and (iv) server storage capacity. The goal of M-ESD is to ensure the resulting network maximizes the average number of tasks that meet their delay requirement. This paper presents a Mixed Integer Linear Programming (MILP) model and a heuristic approach called M-ESD/H to solve the M-ESD problem. Simulation results on small networks show that M-ESD/H produces results that are within 13.6\% of the optimal MILP solution. Further, it significantly reduces runtime and produces results in less than 0.1 seconds as compared to MILP, which failed to produce results in some networks after running for over 48 hours. For large networks, M-ESD/H is compared against two versions of M-ESD that consider arbitrary budget allocation and/or edge server placement, i.e., M-ESD/A1 and M-ESD/A2. The results show that M-ESD/H outperforms both M-ESD/A1 and M-ESD/A2 across various options with varying numbers of stages, budget allocation, and tasks. |