Zoning constraints impose co-location of the storage addresses assigned to individual items within the same storage area of a warehouse. The cube-per-order index (COI) rule for assigning items to locations cannot guarantee orderpicking cost minimization when zoning constraints are active. A heuristic procedure is presented for using the COI to generate an initial item assignment followed by an improvement step. The improvement step includes a random search phase followed by a simulated annealing step designed to avoid trapping at local minima. The procedure is illustrated in the context of a sample problem with 100 items stored in a facility with 1600 storage addresses distributed among 25 zones. Computational experimentation aimed at developing approximate guidelines for controlling the improvement step are reported.