What is the best algorithm to find the optimal path in reducing company's real-estate footprint? I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.
Here is the problem: A company is in the process of reducing its office space and wishes to find the path that will minimize double-rent costs during the transition period.
Constraints:

There are 200 teams in the company (team = indivisible unit). Teams are of different sizes ranging from 10 to 500 individuals.
The start and end locations for each team are given.
There are 250 office locations initially (1 per team), 150 will ultimately be removed and 100 will be added. The 100 remaining locations may see a change in occupant, and there will/can be empty locations at any time period.
The transition period is of 24 time-periods (months), however, teams do not need to move every month, and should move only when new buildings are added.
Teams may move 0, 1, 2 or 3 times during the 24 month time-span
Locations are added at different time periods. Once a building is added, monthly rent starts to be charged.
Locations which are removed have leases ending at different time periods, but leases can be terminated early for a set fee.

Cost function to minimize:
$$C = \sum_{t=0}^{24}\left (M(F_{t},F_{t-1}) + DR\left (F_{t} \right ) +T(F_{t})\right)$$
with:

$M(F_{t},F_{t-1})$ the cost of moving teams from one location to another between 2 subsequent time periods, here moving cost per team is an arbitrary constant.
$DR\left (F_{t} \right )$ the cost of double-rents for the footprint at time t.  If at time t, a team's start and end locations are available, only the rent of the team's start location is counted for computation of double rent.
$T(F_{t})$ the total of early lease termination fees at a time period.  Early lease termination fees depend on each location.

Options explored:
I have started exploring different tracks to answer this problem, namely :

Create a graph with every possible permutation at every time step and then find the shortest path using a tree search algorithm.  However, the large number of teams, locations and time periods define an immense number of permutations hence I am pretty sure I cannot list all possible trajectories.
I am thinking of using a classical Solver-type tool in Python to find optimal path, however, I fear the number of variables may be too large.

My research also led me to potential methods in the fields of Dynamic Programming, Integer Programming, Branch &amp; Bound.
Is there a clear algorithm or manner to address this that comes to mind ?
Edit : I forgot to mention that teams may move 0, 1, 2 or 3 times during the 24 month time-span.
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.