The objective of this paper is to develop a scalable binary linear programming model for finding the
optimal aggregation of communes into spatially contiguous administrative territorial units (ATUs)
constrained on certain balancing criteria. The requirement for the ATUs to be contiguous represents
the main computational bottleneck and, therefore, it prevents one from using such models on a large
state level. We propose a novel scalable model that bypasses the contiguity bottleneck by using a
shortest path heuristic. In our approach, the contiguity of an ATU is viewed as the connectedness
between any pair of its communes mediated through its center by means of shortest paths. We ap-
ply the developed model for obtaining optimal administrative territorial consolidation scenarios for
the Republic of Moldova which totally corresponds to legal requirements and achieves a reasonable
compromise between all balancing criteria.