Introduction
As organizations transition back to physical workspaces, the Seating Allocation Problem (SAP) has gained renewed importance. However, traditional SAP models often treat personnel as flat lists, ignoring the complex hierarchical structures of modern corporations. The Hierarchical Seating Allocation Problem (HSAP) addresses this by ensuring that teams with close professional ties—such as sub-groups within a larger department—are seated in physical proximity. Researchers at J.P. Morgan Chase have developed an end-to-end framework to automate this process, moving beyond manual, suboptimal planning to a scalable, wall-aware optimization system.
The Challenge: Context and Realism
The authors identify two major gaps in current seating solutions that prevent them from being useful in practice:
- Organizational Context: Standard models ignore the "org chart." In a corporate setting, it is not enough for a team to be together; that team must also be near its sister teams and its department head to facilitate collaboration.
- Geographic Realism: Most models use Euclidean ("as-the-crow-flies") distance. In a real office, a seat two feet away through a drywall partition might actually require a two-minute walk around a corridor. Ignoring these physical barriers makes optimization results practically useless.
Methodology
The proposed framework solves the HSAP through a two-stage approach combining robotics-inspired pathfinding with recursive integer programming.
Realistic Distance Estimation
To account for walls and obstacles, the framework borrows a technique from robotics: Probabilistic Roadmaps (PRM) using Rapidly-exploring Random Trees (RRT). The system samples random collision-free points on a floor plan and connects them to form a graph. It then utilizes the Floyd-Warshall algorithm to calculate the true shortest walking path between every pair of seats. This ensures the "distance" in the optimization model reflects actual human movement rather than simple linear proximity.
Recursive Allocation (DF-HSA)
Solving a massive organization’s seating in a single calculation is computationally intractable for more than approximately 50 seats. To overcome this, the researchers developed the Depth First Hierarchical Seat Allocation (DF-HSA) algorithm:
- Decomposition: The problem is broken into smaller sub-problems based on the organizational hierarchy.
- Top-Down Assignment: The model first allocates large departments to general zones. It then recursively drills down, assigning sub-teams to specific desks within the parent's allocated area.
- Optimization: Each step employs Mixed-Integer Programming (MIP) to minimize the distance between seats and a "central seat" for each team.
Key Results and Insights
The framework demonstrates that by following the organizational chart, the model naturally creates "neighborhoods" that mirror how people actually work. Key findings include:
- Scalability: While monolithic MIP approaches fail as seat counts increase, recursive decomposition allows the system to scale to large, real-world office buildings.
- Accuracy: By using PRM/RRT instead of Euclidean distance, the model avoids "impossible" allocations where teams are separated by physical barriers like utility shafts or walls.
- Automation: The framework transforms seating from a manual, infrequent task into a continuous, visualizable planning process.
Limitations and Future Work
As this is an extended abstract, the authors have identified several avenues for further research. They intend to test the model on open-source datasets to establish benchmarks against other researchers' work. Additionally, they plan to conduct a deeper study comparing the efficiency of PRM-based distance estimation against existing grid-based pathfinding methods to further refine the computational feasibility for floor plans containing thousands of seats.
Summary updated