A Multi-start Tabu Search Based Algorithm for Solving the Warehousing Problem with Conflict

摘要

In this paper, we propose a new global warehousing problem supporting advance conflicts: the Warehousing Problem with Conflict (WPC). A set of items are to be loaded into a number of warehouses. We assume a fixed capacity for all warehouses and a predefined weight for each item. The main goal of the WPC is to minimize the overall used number of warehouses under the incompatibility constraint of some pairs of items. We model this optimization problem as a Bin Packing Problem with Conflict (BPPC). As the complexity of the BPPC is NP-Hard, a Multi-start Tabu Search (MTS) is proposed as a solution approach. The empirical validation is done using a developed Decision Support System (DSS) and a comparison to a state-of-the-art approach is performed. The experimental results show that the MTS produces considerably better results than the various existing approaches to the detriment of the gap values.