Non-traditional layouts decrease the average travel distance for unit-load operations compared to traditional warehouse (i.e, straight rows with pick aisles and perpendicular cross aisles that reduce the travel distance between pick locations). Gue and Meller (2009) propose the fishbone layout that decreases average travel distance up to 20%. Ozturkoglu et. al. (2012) relax the assumption of Gue and Meller (2009) so that the pick aisles can take any angle, and achieve up to 22% improvement over traditional layout. Moreover, they prove that these designs are optimal for unit-load operations. However, the optimal warehouse designs for order picking operations are unknown. Here we describe an approach that optimizes layouts with up to 4% improvement over traditional layouts. For small pick list sizes, because of the higher importance of depot location in travel cost, near optimal layouts are creating a vertical cross aisles. As the pick list size increases these cross aisles become horizontal allowing better access between storage locations. We anticipate our approach to be a starting point for more detailed research for warehouse layout optimization. For example, analytical models can be created for the near-optimal layouts we present. Furthermore, layout optimization is a major target for retail industry, and a well-defined encoding and routing approach will be relevant for such optimizations.