What is the best algorithm to find the optimal path in reducing company's real-estate footprint?
This kind of scheduling problem might fall within the area of operations research.
I would suggest using integer linear programming.  You can formulate this as an instance of ILP, and then solve with an off-the-shelf ILP solver (e.g., Gurobi or CPLEX).
I'll outline a way you could formulate this as an instance of ILP.  We'll let $\ell$ range over locations, $t$ over teams, and $i$ over months (time periods).  Introduce the following zero-or-one variables:

$x_{t,\ell,i}=1$ if team $t$ is at location $\ell$ during month $i$.

$s_{\ell,i}=1$ if you start renting the location $\ell$ at the start of month $i$.

$e_{\ell,i}=1$ if you terminate (end) renting the location $\ell$ at the end of month $i$.

$a_{\ell,i}=1$ if location $\ell$ is available for use during month $i$.

$m_{t,i}=1$ if team $t$ moves at the end of month $i$ to a new location.


Then all of your constraints can be expressed as linear inequalities:

$\sum_{\ell} x_{t,\ell,i}=1$: each time has a home somewhere in each month.

$x_{t,\ell,1}=1$ if $\ell$ is the starting location for team $t$; $x_{t,\ell,24}=1$ if $\ell$ is the ending location for team $t$.

$s_{\ell,1}=1$ if $\ell$ is one of the original 250 locations.  $s_{\ell,1}=0$ if $\ell$ is not one of the original 250 locations.

$a_{\ell,i} = s_{\ell,1} + \dots + s_{\ell,i} - (e_{\ell,1} + \dots + e_{\ell,i-1})$.

$x_{t,\ell,i} - m_{t,i} \le x_{t,\ell,i+1} \le x_{t,\ell,i} + m_{t,i}$.

$\sum_t x_{t,\ell,i} \le a_{\ell,i}$.


Now the cost is a sum of the moving costs (a linear function of the $m$'s), the rent costs (a linear function of the $a$'s), and the early termination fees (a linear function of the $e$'s), so the cost is a linear function of the variables.  Thus, you have an ILP instance, which you can give to an ILP solver and ask it to find the optimal solution -- or the best solution it can find within a set time bound.  You'll have about $350\times 200 \times 24$ variables, i.e., about 1.6M variables, which is large but not necessarily infeasible.