Sipariş gruplama problemi için karma tam sayılı doğrusal programlama gösterimleri

Order picker's routing operation consists of determining the sequence of the order picking. In this study, we consider the Order Batching Problem (OBP) which is shown to be NP-hard. Given both a list of customer orders and order picker's routing policy, the OBP deals with constructing batches of customer orders such that the total travel length of the pickers is minimized. To the best of our knowledge, there are no MILP formulations suggested for the OBPs with traversal and return routing policies in the literature. Basically, we introduce MILP formulations for the OBP and we also perform computational study to better expose the strength of the proposed MILP formulations. For that purpose, we compare the performance of the MILP formulations with the savings algorithm which is known to be one of the best performing construction heuristics for the OBP. The computational results show the usefulness of the MILP and saving heuristic for the OBP. According to our computational experiments, comparing both methods, savings heuristic yields significantly better results in reasonable CPU times. From the experimental results, we observe that the proposed formulations yield quite good upper bounds. These MILP formulations can also be used as benchmarks for other studies which propose heuristic and meta-heuristics for the OBP. As a further research avenue, developing a branch and bound algorithm exploiting the structure of the problem would be an interesting work. Branch and cut algorithms can be also developed by suggesting valid inequalities based on the proposed MILP formulations. Keywords: Order Batching Problem, Mixed Integer Linear Programming, Warehouse Management