A recent trend in the layout design of unit-load warehouses is the application of layouts without conventional parallel pick aisles and straight middle aisles. Two examples for such designs are flying-V and fishbone designs for single- and dual-command operations. In this study, it is shown that the multi-item order picking problem can be solved in polynomial time for both fishbone and flying-V layouts. These two designs are compared with the traditional parallel-aisle design under the case of multi-item pick lists. Simple heuristics are proposed for fishbone layouts that are inspired by those put forward for parallel-aisle warehouses and it is experimentally shown that a modification of the aisle-by-aisle heuristic produces good results compared with other modified S-shape and largest gap heuristics when items have uniform demand. Computational experiments are performed in order to compare the performances of fishbone and traditional layouts under optimal routing and it is shown that a fishbone design can obtain improvements of around 20% over parallel-aisle design in single-command operations but can perform as high as around 30% worse than an equivalent parallel-aisle layout as the size of the pick list increases. The sensitivity of the results to varying demand skewness levels when volume-based storage is applied is tested and it is shown that unlike the single- and dual-command cases, a fishbone design performs better compared to a traditional design under highly skewed demand as opposed to uniform demand.