Partitioning space into polyhedra with a minimum total surface area is a fundamental question in science and mathematics. In 1887, Lord Kelvin conjectured that the optimal partition of space is obtained with a 14-faced space-filling polyhedron, called tetrakaidecahedron. Kelvin's conjecture resisted a century until Weaire and Phelan proposed in 1994 a new structure, made of eight polyhedra, obtained from numerical simulations. Herein, we propose a stochastic method for finding efficient polyhedral structures, maximizing the mean isoperimeter Q, instead of minimizing total area. We show that novel optimal structures emerge with non-equal cell volumes and uncurved facets. A partition made of 24 polyhedra, is found to surpass the previous known structures. Our work suggests that other structures with high isoperimeter values are still to be discovered in the pursuit of optimal space partitions.