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

Title: A Construction Heuristic for the Bin-Packing Problem with Time Windows: A Case Study in Thailand
Wisute Ongcunaruk, Pornthipa Ongkunaruk

Corresponding email:

Cite this article as:
Ongcunaruk, W., Ongkunaruk, P., 2021. A Construction Heuristic for the Bin-Packing Problem with Time Windows: A Case Study in Thailand. International Journal of Technology. Volume 12(2), pp. 390-400

461
Downloads
 Wisute Ongcunaruk Department of Electrical and Computer Engineering, Faculty of Engineering, King Mongkut’s University of Technology North Bangkok, 1518 Pibulsongkram Road, Bangsue, Bangkok 10800, Thailand Pornthipa Ongkunaruk Department of Agro-Industrial Technology, Faculty of Agro-Industry, Kasesart University, 50 Ngam Wong Wan Rd. Lad Yao, Chatuchak, Bangkok, 10900, Thailand
Email to Corresponding Author

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.

Bin-packing problem with time windows; Construction heuristic; Integer programming; Visual Basic for Applications

Introduction

In Thailand, transportation is one of the major activities contributing to the gross domestic product (GDP). The proportion of the GDP represented by logistics in Thailand in 2018 was 13.4%. Transportation made up the largest proportion, at 54.4%, and inventory and administration costs accounted for 36.6% and 9.0% of the GDP, respectively (NESDB, 2018). There is also an increasing trend toward transportation as a proportion of the GDP as the manufacturing industry grows. Transportation causes CO2 gas emissions to the world. Mubarak and Zainal (2018) studied the framework for a company to calculate CO2 emissions in Indonesia. The framework helped companies to assess CO2 emissions to the environment. Transportation costs increase as fuel costs increase; however, without control over the fuel price, manufacturers can only focus on the reduction of transportation costs based on the planning and routing of transportation management. The precision of the routes and schedules of vehicles are logistics challenges, and transportation modeling is highly significant research (Pamitran et al., 2015). Transportation management is related to many activities, such as demand forecasting (Pradita et al., 2020), procurement planning (Deepradit et al., 2020), and transport between locations (Doungpattra et al., 2012).

This research focuses on a case study in the food industry, which outsources transportation to a third-party logistics (3PL) provider, although the transportation department of the manufacturer determines how many trucks are needed every week. In addition, there are limitations on the delivery time window and truck bans at certain times because of the Department of Transport regulations, which aim to reduce traffic jams in Bangkok and the metropolitan region. This makes the problem more difficult. Currently, the company’s transportation department is inefficient and has high turnover. The staff spend about 3 hours managing the allocation of customers to the outsourcing trucks and deliveries are often late. Our research aims to solve the truck assignment problem in this case study with time window constraints. This research compares the proposed method with that of Ongarj and Ongkunaruk (2013) and addresses the limitations that arise when problem sizes become larger. These researchers formulated integer programming (IP) and solved the problem using a Solver in Microsoft Excel. However, this method exhibits a drawback when the number of customers increases. Hence, this research proposes a heuristic to solve the same problem and compares the quality of the solutions and computational times.

The case study problem is called the bin-packing problem with time windows (BPPTW), as defined by Ongarj and Ongkunaruk (2013). The problem involves determining which customer orders will be allocated to trucks to minimize the number of trucks used while satisfying demand and truck capacity. In addition, there are delivery time window constraints. The bin-packing problem (BPP) is an NP-complete and NP-hard problem, and it takes a long time to solve in the case of large problems (Garey and Johnson, 1979; Ongkunaruk, 2005; Delorme et al., 2016). Some research on the heuristics that have been proposed to solve the BPP (Martello and Toth, 1990; Coffman and Lueker, 1991; Fleszar and Hindi, 2002; Loh et al., 2008; Hemmelmayr et al., 2012; Ayob et al., 2013). Later, Ongkunaruk (2008) proved that the asymptotic worst case ratio of first fit decreasing is 11/9 by the maximum occupied technique. There is also a variant of the BPP known as the BPP with conflicts, in which there are conflicts determining components that cannot be packed in the same bin (Gendreau et al., 2004; Fernandes-Muritiba et al., 2010).

In 2013, the number of customers in Bangkok and the surrounding metropolitan area was 690, and this number has continued to rise since then, resulting in more challenges in solving the BPP. Staff determine how many trucks will be used to deliver the products based on their experience. Customers do not know when their products will be delivered because the drivers often fail to deliver according to the company schedule. Hence, the staff must reschedule and redo invoices, causing additional costs. In addition, the staff turnover rate in the transportation department is high, and new staff take more time to solve this problem. Since the transportation cost per shipment is fixed, the number of trucks used should be minimized. The level of customer service required is 100%. The transportation cost is the same for customers located in the same zone. Six four-wheeled trucks are used, with a capacity of 220 boxes per truck. Although the delivery time is scheduled from 5 a.m. to 3 p.m., some customer orders must be delivered between 5 a.m. and 8 a.m. because of traffic regulations. The problem has been simplified to give at most two customer groups that can be delivered to using the same truck, as defined by the time window constraint. In addition, the company has established a rule that at least one truck must be dedicated to each zone.

Conclusion

This study improved the method of solving the BPPTW for a case study company by addressing the limitation of the IP approach when solving large problems. We proposed the construction heuristic to find alternative solutions to improve upon IP. The algorithm was designed to prioritize allocation for customers with time constraints, and the program was written in VBA in Excel. Our heuristic can solve a large problem within a short time, whereas the Solver cannot be used when the number of customers exceeds 32. The Solver takes a longer time than our heuristic when the problem size increases. In addition, the construction heuristic is designed to be user-friendly. In summary, the construction heuristic can be used as a decision support tool for the company, resulting in reduced computational time and lower human error. In the future, the company will be able to cooperate with the 3PL provider to solve the vehicle routing problem with time window constraints and find global optimum solutions for the company and the 3PL. Then, such heuristics as genetic algorithms can be proposed to solve the problem (Chen et al., 2016; Ongkunaruk et al., 2016).

Acknowledgement

The authors would like to thank the case company, which kindly provided information for this research. We are also grateful to the anonymous reviewers, who made valuable recommendations to improve our manuscript.

Supplementary Material
FilenameDescription
R3-IE-3366-20210201105401.jpg Figure 1
R3-IE-3366-20210201105421.jpg Figure 2
R3-IE-3366-20210201105506.jpg Figure 4
References

Ayob, M., Nazri, M.Z.A., Fei, Y.X., 2013. Local Search Heuristics for the One Dimensional Bin Packing Problems. Journal of Applied Sciences, Volume 13(6), pp. 912–923

Chen, Y., Wahab, M.I.M., Ongkunaruk, P., 2016. A Joint Replenishment Problem Considering Multiple Trucks with Shipment and Resource Constraints. Computers and Operations Research, Volume 74, pp. 53–63

Coffman, Jr., E., Lueker, G., 1991. Bin Packing Heuristics in Probabilistic Analysis of Packing and Partitioning Algorithms. Wiley & Sons New York

Deepradit, S., Ongkunaruk, P., Pisuchpen, R., 2020. Tactical Procurement Planning under Uncertainty in Aromatic Coconut Manufacturing. International Journal of Technology, Volume 11(4), pp. 698709

Delorme, M., Iori, M., Martello, S., 2016. Bin Packing and Cutting Stock Problems: Mathematical Models and Exact Algorithms. European Journal of Operational Research, Volume 255(1), pp. 1–20

Doungpattra, N., Jarupan, L., Ongkunaruk, P., 2012. Simulation for Transport Pallet Cost Reduction in Pet Food Manufacturing: An Empirical Case Study. Packaging and Technology and Science, Volume 25(6), pp. 311–319

Fernandes-Muritiba, A.E., Iori, M., Malaguti, E., Toth, P., 2010. Algorithms for the Bin Packing Problem with Conflicts. INFORMS Journal on Computing, Volume 22(3), pp. 401–415

Fleszar, K., Hindi, K.S., 2002. New Heuristics for One-Dimensional Bin-Packing. Journal of Computers & Operations Research, Volume 29(7), pp. 821–839

Garey, M., Johnson, D., 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman & Company

Gendreau, M., Laporte, G., Semet, F., 2004. Heuristics and Lower Bounds for the Bin Packing Problem with Conflicts. Journal of Computers & Operations Research, Volume 31(3), pp. 347–358

Hemmelmayr, V., Schmid, V., Blum, C., 2012. Variable Neighbourhood Search for the Variable Sized Bin Packing Problem. Journal of Computers & Operations Research, Volume 39(5), pp. 1097–1108

Loh, K.H., Golden, B., Wasil, E., 2008. Solving the One-Dimensional Bin Packing Problem with a Weight Annealing Heuristic. Journal of Computers & Operations Research, Volume 35(7), pp. 2283–2291

Martello, S., Toth, P., 1990. Lower Bounds and Reduction Procedures for the Bin Packing Problem. Journal of Discrete Applied Mathematics, Volume 28(1), pp. 59–70

Mubarak, A., Zainal, F., 2018. Development of a Framework for the Calculation of CO2 Emissions in Transport and Logistics in Southeast Asia. International Journal of Technology, Volume 9(4), pp. 787796

NESDB, 2018. Gross Domestic Product. Office of the National Economic and Social Development Council, Thailand

Ongarj, L., Ongkunaruk, P., 2013. An Integer Programming for a Bin Packing Problem with Time Windows: A Case Study of a Thai Seasoning Company. In: 10th IEEE International Conference on Service Systems and Service Management (ICSSM13), pp. 826830

Ongkunaruk, P., 2005. Asymptotic Worst-Case Analyses for the Open Bin Packing Problem. Virginia Polytechnic Institute and State University, USA

Ongkunaruk, P., 2008. The Asymptotic Worst-Case Ratio of the Bin Packing Problem by Maximum Occupied Space Technique. Industrial Engineering and Management Systems, Volume 7(2), 126–132

Ongkunaruk, P., Ongcunaruk, W., 2015. Coconut Sap Pickup Problem with Time Windows: A Case Study. International Food Research Journal, Volume 22(5), pp. 20882092

Ongkunaruk, P., Wahab, M.I.M., Chen, Y., 2016. A Genetic Algorithm for A Joint Replenishment Problem with Resource and Shipment Constraints and Defective Items. International Journal of Production Economics, Volume 175, pp. 142–152

Pamitran, A., Budiono, H.D.S., Putra, N., Asvial, M., 2015. Research Frontiers in Energy, Materials, Production, and Transportation. International Journal of Technology, Volume 6(6), pp. 905908

Pradita, S.P., Ongkunaruk, P., Leingpibul, T., 2020. Utilizing an Intervention Forecasting Approach to Improve Reefer Container Demand Forecasting Accuracy: A Case Study in Indonesia. International Journal of Technology, Volume 11(1), pp. 144–154