A Construction Heuristic for the Bin-Packing Problem with Time Windows: A Case Study in Thailand

Abstract

This study aims to improve the efficiency of distribution for food manufacturers, extending previous research that solved the bin-packing problem with time windows (BPPTW) using integer programming (IP) and Microsoft Excel Solver. The drawback of this approach is that it has difficulty solving large problems. In the future, the number of customers is expected to increase, and therefore, we propose a construction heuristic that can solve the BPPTW within a shorter time. The algorithm was designed to allocate customers who had time window constraints first to ensure that only feasible solutions were generated. The program was written in Visual Basic for Applications (VBA) in Excel because it is convenient to use for decision makers. The data were then solved using a heuristic. The results showed that the heuristic can solve real problems with the optimal solution. We showed that, by using these two methods, the annual transportation cost is reduced by 23.23%, or 489,450 baht per year, and the computational time is drastically reduced. Next, we generated larger problems and compared the computational times for the two methods. We showed that the Solver cannot handle a problem involving more than 32 customers, and that it takes more time as the problem size increases. In contrast, the construction heuristic can solve the problem within 1 minute. Hence, it is more attractive to use our heuristic than IP as a decision support tool for a case company’s transportation department.

Keywords

• bin-packing problem with time windows
• construction heuristic
• integer programming
• visual basic for applications