Warehouse management is an important issue in supply chain management. Among all warehouse operations, "order-picking" is the most expensive one and its cost is mainly due to the travelling expenses. In this paper, we study the capacitated warehouse routing problem (CWRP) so as to save the travelling cost, i.e., travelling distance in order-picking. The problem is shown to be strongly NP-hard. However, by noting that the unconstrained routing problem can be tackled by a dynamic programming method, a search heuristic, which is based on the very large-scale neighborhood (VLSN) technique, was designed to solve the capacity-constrained version. We compared the computational results with solutions obtained from branch-and-price method, which are within 1% error bound and identified that our heuristic is efficient in getting high quality solutions of CWRP.