The order picking problem involves determining the shortest tour for a picker to collect a set of items in a warehouse. Pricing problems of set-partitioning or path-based formulations that address batching and routing decisions in warehouses, rely on extensions of this specific case of the Traveling Salesman Problem (TSP). In particular, a meaningful extension is referred to as the Profitable Order Selection and Routing Problem. In this variant, all items of a selected order must be collected together in the same tour using a limited capacity and a price is gained for collecting an order. We propose a new Integer Programming formulation based on the selection of transitions of the dynamic program for order picking, and additional constraints from the Steiner TSP to ensure the validity of the picking tour. A dedicated branch-and-cut algorithm is proposed to solve the formulation efficiently.

JOBPRP: Joint order batching and picker routing

PORP: Profitable order selection and routing problem