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 & 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.