A Construction Heuristic for the Bin-Packing Problem with Time Windows: A Case Study in Thailand
Published at : 19 Apr 2021
Volume : IJtech
Vol 12, No 2 (2021)
DOI : https://doi.org/10.14716/ijtech.v12i2.3366
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
| 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 |
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
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.
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).
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.
| Filename | Description |
|---|---|
| R3-IE-3366-20210201105401.jpg | Figure 1 |
| R3-IE-3366-20210201105421.jpg | Figure 2 |
| R3-IE-3366-20210201105506.jpg | Figure 4 |
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. 698–709
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. 787–796
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. 826–830
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. 2088–2092
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. 905–908
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