Optimal Order Selection Problem: Subproblems Complexity and Integer Programming Based Approaches

Picking orders in a warehouse is a difficult and important problem in logistics. This problem is handled in many different ways generating a large class of problems, one of which is the Optimal Order Selection Problem (OOSP), a problem proven to be in NP-hard. After an analysis of literature, this paper presents additional NP-hardness results, specifically, for subproblems of OOSP. New approaches based on integer programming formulations for OOSP are presented and two algorithms are produced. Computational experiments are performed with the algorithms showing that their performances are competitive when compared with the ones in literature.