In this article, we deal with the Order Batching Problem (OBP) considering traversal, return, and midpoint routing policies. We consider the Set Partitioning Problem formulation of the OBP and develop a specially tailored column generation–based algorithm for this problem. We suggest acceleration techniques such as a column pool strategy and a relaxation of the column generation subproblem. Also, a specially devised upper-bounding procedure and a lower-bounding method based on column generation that is strengthened by adding subset-row inequalities are employed. According to the computational results, the proposed solution approach manages to solve OBP instances with up to 100 orders to optimality.