Về bài toán Bin Packing 2D và ứng dụng trong vận tải hàng hải

 chiều (d là một số nguyên dương, d ≥ 1), có các thùng chứa là 
các siêu cúp d chiều kích thước là BBB12, ,...,d ) và dãy các đồ vật a12, a ,..., an , trong đó đồ vật ai 
có kích thước là s1(ai) × s2(ai) ×  × sd(ai). sj(ai) là kích thước chiều thứ j của đồ vật ai; 0 < sj(ai) 
≤ Bj; 1 ≤ i ≤ n; 1 ≤ j ≤ d. 
 Một cách xếp các đồ vật gọi là hợp lệ nếu mỗi đồ vật ai sẽ được gán một vector tọa độ p(ai) = 
(x1(ai), x2(ai),, xd(ai)) sao cho: 
 (1) xj(ai) ≥ 0 ; 1 ≤ i ≤ n; 1 ≤ j ≤ d. 
 (2) xj(ai) + sj(ai) ≤ Bj ; 1 ≤ i ≤ n; 1 ≤ j ≤ d. 
 (3) (xj(ai); xj(ai) + sj(ai)) ∩ (xj(ak); xj(ak) + sj(ak)) = ∅; 1 ≤ i ≠ k ≤ n; 1 ≤ j ≤ d 
 Điều kiện (1) và (2): tất cả các đồ vật đều nằm gọn trong không gian của thùng chứa. 
 Điều kiện (3): trong mọi thùng chứa, các đồ vật không được xếp chồng lên nhau. 
 Các điều kiện trên áp dụng với bài toán đóng thùng đa chiều hình học (geometric multi-
dimension bin packing), tức là mỗi chiều kích thước là một chiều không gian. Nếu mỗi chiều kích 
thước không phải là một chiều không gian, ví dụ chiều thứ nhất biểu diễn độ dài, chiều thứ 2 biểu 
diễn khối lượng, chiều thứ 3 biểu diễn thời gian, thì điều kiện ràng buộc chỉ là tổng kích thước 
các đồ vật theo một chiều sẽ không vượt quá dung lượng chiều đó của thùng chứa: 
 n
 si ( ai ) = B , j 1, d
 j=1
 Yêu cầu của bài toán là hãy xếp các đồ vật hợp lệ sao cho số lượng thùng cần sử dụng là ít nhất. 
 Dễ thấy với d = 1 thì bài toán suy biến về bài toán đóng thùng dạng cơ bản. 
2.1.3. Ứng dụng của bài toán đóng thùng 
 Không chỉ đóng vai trò quan trọng trong nghiên cứu lý thuyết, đặc biệt là các nghiên cứu về 
thuật toán xấp xỉ, bài toán đóng thùng còn có nhiều ứng dụng trong thực tiễn. 
 Dưới đây là một số ứng dụng trong đó bài toán đóng thùng đóng vai trò là bài toán chính: 
 1) Bài toán xẻ gỗ (stock cutting): Cho các miếng gỗ xẻ nguyên tấm có chiều ngang cố định và 
chiều dài giống nhau bằng C. Cần chia các miếng gỗ xẻ nguyên tấm đó thành các mẩu nhỏ {ai} 
hơn dùng để làm nhà. Hãy cưa các miếng gỗ nguyên tấm đó thành các mẩu {ai} sao cho số 
miếng gỗ nguyên tấm phải dùng là ít nhất. Cũng thấy dạng tương tự khi phải chia các cuộn dây 
cáp, ống dẫn nước nguyên vẹn,... thành các đoạn nhỏ để lắp đặt cho một hệ thống nào đó và cần 
chia khéo sao cho đỡ lãng phí nhất. 
 2) Lưu dữ liệu trên máy tính (memory allocation): Các dữ liệu là một tập hợp các file cần 
được lưu trên một tập hợp các thiết bị nhớ giống nhau (đĩa CD, đĩa cứng, đĩa mềm, hoặc bộ nhớ 
bán dẫn USB,...). Cần phải lưu các file trên các thiết bị nhớ sao cho 1 file chỉ được nằm trong 1 
thiết bị nhớ và số thiết bị nhớ cần dùng là ít nhất. 
 3) Bài toán vận tải (transportation): Cần xếp một dãy các đồ vật (đồ đạc, hàng hóa,...) {ai} 
lên các phương tiện vận tải (xe tải, toa xe lửa,...). Biết rằng mỗi đồ vật có kích thước (3 chiều) và 
trọng lượng xác định. Các phương tiện vận tải là giống nhau có cùng sức chứa và trọng tải xác 
định. Cần xếp các đồ vật lên các phương tiện vận tải sao cho số phương tiện cần dùng là ít nhất 
mà vẫn đảm bảo các đồ vật đều nằm gọn trong khoang chứa và tổng trọng lượng của chúng 
không vượt quá trọng tải của phương tiện vận tải. Bài toán này có thể quy về bài toán đóng thùng 
4 chiều với 3 chiều đầu là 3 chiều không gian, chiều thứ 4 là trọng lượng. 
 230 Email: jst@tnu.edu.vn 
 TNU Journal of Science and Technology 226(07): 226 - 234 
 4) Xếp lịch chương trình truyền hình (television programming): thông thường các mẩu chương 
trình quảng cáo được xếp vào các khoảng thời gian xen kẽ trong các chương trình truyền hình chính. 
Các khoảng thời gian này có độ dài cố định (ví dụ 5 phút). Yêu cầu là hãy xếp các mẩu quảng cáo vào 
những khoảng thời gian này sao cho số khoảng thời gian cần sử dụng là ít nhất. 
 Ngoài ra trong một số ứng dụng, bài toán đóng thùng đóng vai trò là bài toán phụ hỗ trợ việc 
giải tối ưu bài toán chính, ví dụ bài toán lập lộ trình vận chuyển có hạn chế khả năng (capacitated 
vehicle routing problem) trong đó phải bố trí các xe chở hàng có trọng tải hữu hạn đi chuyển 
hàng cho các vị khách sao cho mọi khách hàng đều nhận được hàng theo đơn đặt hàng và chi phí 
vận chuyển là thấp nhất. Thông thường đội xe sẽ chia thành các nhóm nhỏ, mỗi nhóm gồm một 
vài xe đi phục vụ theo một tuyến đường. Trên mỗi tuyến đường, cần xếp các hàng hóa của các vị 
khách trên tuyến đường đó lên các xe sao cho số xe trong nhóm cần dùng là ít nhất. Đó chính là 
bài toán đóng thùng. 
2.2. Tổng quan các phương pháp giải bài toán đóng thùng 
 Bài toán đóng thùng là một bài toán tối ưu tổ hợp nổi tiếng và có nhiều thuật toán để giải, đặc 
biệt là các thuật toán xấp xỉ. Bài toán đóng thùng đóng vai trò quan trọng trong việc nghiên cứu 
các thuật toán xấp xỉ khi được chọn là một trong những bài toán đầu tiên để nghiên cứu xây dựng 
các thuật toán xấp xỉ và đánh giá hiệu năng của chúng, ví dụ như đánh giá hiệu quả thuật toán 
xấp xỉ trong thời gian tồi nhất, đánh giá cận dưới cho hiệu năng các thuật toán tức thì (online 
algorithms), phân tích hiệu năng thuật toán dựa trên xác xuất thống kê, 
 Phần dưới đây sẽ trình bày một số thuật toán quan trọng để giải bài toán đóng thùng, qua đó 
giới thiệu được phần nào các kết quả nghiên cứu hiện nay về bài toán đóng thùng. 
2.2.1. Các thuật toán trực tiếp 
2.2.1.1. Khái niệm thuật toán trực tiếp 
 Một thuật toán được gọi là thuật toán trực tiếp (online algorithm) khi nó phải thực hiện xếp đồ 
vật đang xét vào thùng chứa mà không được biết bất kì thông tin gì về các đồ vật xuất hiện sau 
nó. Đây là một ràng buộc thường gặp trong thực tế, ví dụ như người bán hàng thì không biết 
khách hàng tiếp theo sẽ có yêu cầu như thế nào. 
 Các thuật toán online phổ biến bao gồm Next Fit, First Fit và Best Fit. 
2.2.1.2. Thuật toán Next Fit 
 Mô tả quy tắc xếp các đồ vật của Next Fit (NF) 
 NF sẽ đặt đồ vật đang xét vào ngay thùng đang mở (trong NF có 1 và chỉ 1 thùng được mở tại 
một thời điểm) và cũng là thùng tiếp nhận đồ vật vừa được xét gần đây nhất nếu như thùng đó 
còn đủ chỗ trống. Ngược lại, nó sẽ đóng thùng đó lại, mở thùng mới rồi đặt đồ vật vào đó. Sau đó 
tiếp tục xét đến đồ vật tiếp theo. Quá trình bắt đầu với đồ vật đầu tiên và kết thúc khi tất cả các đồ 
vật đều đã được xếp hết vào thùng. 
 Next Fit có thể được mô tả bằng đoạn giả ngôn ngữ sau: 
 bin_index = 1; // chỉ số cho biết đã có bao nhiêu thùng đã được sử dụng item_index = 1; 
 // chỉ số cho biết đang xét đồ vật thứ bao nhiêu 
 Open B[bin_index]; // mở thùng đầu tiên để tiếp nhận đồ vật active_bin = B[bin_index]; 
 // B[] là một mảng chứa các thùng được sử dụng trong thuật toán while (item_index <= n) 
 { 
 active_item = a[item_index]; 
 if (Size(active_item) <= FreeSize(active_bin)) Pack active_item into active_bin; 
 else{ 
 Close active_bin; bin_index ++; Open B[bin_index]; 
 active_bin = B[bin_index]; 
 231 Email: jst@tnu.edu.vn 
 TNU Journal of Science and Technology 226(07): 226 - 234 
 Pack active_item into active_bin; 
 } 
 item_index++; } // while 
 Dễ thấy NF có độ phức tạp tính toán là O(n). 
2.2.1.3. Thuật toán First Fit 
 Mô tả quy tắc xếp đồ vật của First Fit (FF): 
 Thuật toán FF sẽ xếp đồ vật đang xét vào thùng đầu tiên (tức là thùng có chỉ số nhỏ nhất) 
trong số những thùng đã mở và còn đủ chỗ để chứa đồ vật đó. Nếu trong số những thùng đã mở 
không có thùng nào còn đủ chỗ trống để xếp đồ vật đang xét thì FF sẽ mở một thùng mới và đặt 
đồ vật vào đó. Sau đó chuyển sang xét đồ vật tiếp theo. Quá trình đóng thùng kết thúc khi đã xếp 
hết tất cả các đồ vật vào thùng chứa. Dễ thấy FF không đóng một thùng nào và số lượng thùng ở 
trạng thái hoạt động là không cố định. 
 Đoạn giả ngôn ngữ sau mô tả hoạt động của FF: 
 bin_index = 1; // chỉ số cho biết đã có bao nhiêu thùng đã được sử dụng item_index = 1; 
 // chỉ số cho biết đang xét đồ vật thứ bao nhiêu Open B[bin_index]; 
 // mở thùng đầu tiên để tiếp nhận đồ vật 
 // B[] là một mảng chứa các thùng được sử dụng trong thuật toán while (item_index <= n) 
 { 
 test = false; count = 1; do{ 
 if (Size(a[item_index] <= FreeSize(B[count]){ 
 Pack a[item_index] into B[count]; test = true; 
 }else count++; 
 }while (test = = false) && (count <= bin_index); if (test = = false){ 
 bin_index ++; Open B[bin_index]; 
 Pack a[item_index] into B[bin_index]; 
 } 
 item_index++; 
 } 
 Độ phức tạp tính toán của thuật toán FF là O(nlogn). 
2.2.1.4. Thuật toán Best Fit 
 Mô tả xếp đồ vật 
 Quy tắc đóng thùng của Best Fit (BF) khá đơn giản, BF sẽ xếp đồ vật đang xét vào thùng còn 
ít chỗ trống nhất trong số những thùng đã mở và còn đủ chỗ trống để tiếp nhận đồ vật. Nếu không 
có thùng đã mở nào có đủ chỗ để tiếp nhận đồ vật đang xét, BF sẽ mở một thùng mới và đặt đồ 
vật vào đó. Sau đó chuyển sang xét thùng tiếp theo. Quá trình kết thúc khi tất cả các đồ vật đều 
đã được xếp hết vào thùng. Như vậy BF ưu tiên tìm thùng “vừa vặn” (fit) với đồ vật nhất. 
 BF có thể được mô tả qua đoạn giả ngôn ngữ sau:: 
 bin_index = 1; // chỉ số cho biết đã có bao nhiêu thùng đã được sử dụng item_index = 1; 
 // chỉ số cho biết đang xét đồ vật thứ bao nhiêu Open B[bin_index]; 
 // mở thùng đầu tiên để tiếp nhận đồ vật 
 // B[] là một mảng chứa các thùng được sử dụng trong thuật toán while (item_index <= n) 
 { 
 index = bin_index + 1; 
 fit = 1 – Size(a[item_index]); for(j = 1; j<=bin_index; j++){ 
 temp = FreeSize(B[j]) – Size(a[item_index]); if (0 <= temp) && (temp < fit){ 
 fit = temp; index = j; 
 } 
 } 
 232 Email: jst@tnu.edu.vn 
 TNU Journal of Science and Technology 226(07): 226 - 234 
 if (index < bin_index + 1) 
 Pack a[item_index] into B[index]; 
 else{ 
 bin_index ++; 
 Open B[bin_index]; 
 Pack a[item_index] into B[bin_index]; 
 } 
 item_index++; 
 } 
 Thuật toán BF đã được chứng minh là có hiệu quả tương đương với FF. 
 Ngoài các thuật toán NF, BF và FF vừa đề cập ở trên, còn có một số thuật toán online khác 
như Group- X Fit (GXF), thuật toán First Fit cải tiến (Refined First Fit), Tuy nhiên chúng tôi 
sẽ không trình bày những thuật toán này ở đây. 
2.2.2. Các phương pháp không trực tiếp: First Fit Decreasing và Best Fit Decreasing 
 Khác với ràng buộc trong các thuật toán online, trong thuật toán không trực tiếp (off-line 
algorithm), được biết trước toàn bộ danh sách các đồ vật trước khi xếp chúng vào thùng và điều 
này cho phép thực hiện một số thao tác tiền xử lý để nâng cao hiệu quả công việc. 
 Mục này sẽ đề cập đến 2 thuật toán off-line phổ biến và cũng rất hiệu quả là First Fit 
Decreasing (FFD) và Best Fit Decreasing (BFD). Về cơ chế hoạt động của FFD và BFD thì rất 
đơn giản, chỉ việc sắp xếp dãy các đồ vật cho trước theo thứ tự giảm dần về kích thước, sau đó áp 
dụng thuật toán online tương ứng (FF cho FFD hoặc BF cho BFD) để xếp các đồ vật vào thùng. 
 Chi phí thời gian cho FFD và BFD đều là Ω( nlogn), bởi vì việc sắp xếp theo chiều tăng dần 
về kích thước dãy n đồ vật cần thời gian là Ω (nlogn), còn việc xếp các đồ vật vào thùng theo quy 
tắc BF hoặc FF đều cùng yêu cầu thời gian là O(nlogn) như đã nói ở phần trước. 
3. Kết quả và bàn luận 
 Vấn đề tối ưu trong ngành vận tải ngày càng được nhiều nhà khoa học quan tâm nghiên cứu, điều 
đó giúp thúc đẩy quá trình lưu thông hàng hóa, tiết kiệm được chi phí vận chuyển cho các doanh 
nghiệp vận tải. Trong bài báo này, chúng tôi đã đưa ra vấn đề tối ưu trong quá trình vận tải, cụ thể là 
tối ưu sắp xếp trong bài toán Bin Packing 2D và các lĩnh vực ứng dụng của bài toán. Bài toán Bin 
Packing 2D là bài toán tối ưu tổ hợp có độ phức tạp cao, có nhiều thuật toán để giải, đặc biệt là các 
thuật toán xấp xỉ. Trong đó chúng tôi đã đưa ra một số hướng để giải quyết bài toán này: Các thuật 
toán trực tiếp (Next Fit, First Fit và Best Fit), các phương pháp không trực tiếp (First Fit Decreasing, 
Best Fit Decreasing), cũng như giả ngôn ngữ và đánh giá độ phức tạp của các thuật toán. 
 Đối với bài toán tối ưu sắp xếp container tại cảng biển có thể quy về bài toán Bin Packing 2D, 
trong đó chính là quá trình tối ưu sắp xếp container tại kho bãi. Khi có một đoàn tàu chở hàng cập 
cảng, sau khi hoàn thành các thủ tục hành chính được tiến hành bốc dỡ hàng hoá. Hàng hoá rất đa 
dạng bao gồm các sản phẩm xuất nhập khẩu như các sản phẩm công - nông nghiệp, các sản phẩm 
điện tử - điện lạnh,... Hàng được chứa trong các container hàng, có các đặc tính như kích thước, 
trọng lượng, tính chất,... riêng. Sau đó, các container hàng sẽ được các cần trục bốc lên các xe 
chở hàng chuyên dụng và sắp xếp vào kho hàng (sân bãi) theo từng khu vực riêng biệt, tuỳ thuộc 
vào đặc tính. Tiếp theo, dựa vào nhu cầu của tàu hàng mà các container hàng xuất sẽ được lấy ra 
và sắp xếp lên tàu. Mặt khác, một số lượng lớn container hàng sẽ được cho lên các xe đầu kéo (xe 
ôtô container) để chuyển hàng đi trên đất liền. Do đó bài toán tối ưu sắp xếp container tại cảng 
biển cũng là một vấn đề đáng được quan tâm nghiên cứu. 
4. Kết luận 
 Trong nghiên cứu này chúng tôi nêu và giải quyết bài toán Bin Packing 2D bằng các phương 
pháp xấp xỉ. Tuy nhiên trong thực tế còn một số hướng nghiên cứu và giải quyết với nhiều 
 233 Email: jst@tnu.edu.vn 
 TNU Journal of Science and Technology 226(07): 226 - 234 
phương pháp khác như sử dụng tính toán mềm, sử dụng tính toán tiến hóa, giải thuật di truyền, 
Đây là những hướng quan tâm nghiên cứu trong thời gian sắp tới. 
 Mặt khác, trong bài báo mới chỉ đưa ra và giải quyết bài toán Bin Packing 2D, trong thời gian 
tới chúng tôi sẽ nghiên cứu và giải quyết bài toán Bin Packing 3D [6]. Đây là bài toán tối ưu với 
không gian 3 chiều, với độ phức tạp tính toán lớn. Lời giải của bài toán này nhằm áp dụng cho 
bài toán tối ưu sắp xếp container tại cảng biển. 
Lời cám ơn 
 Nghiên cứu này được tài trợ bởi Trường Đại học Công nghệ Thông tin và Truyền thông – Đại 
học Thái Nguyên trong đề tài mã số T2020-07-18. 
 TÀI LIỆU THAM KHẢO/ REFERENCES 
[1] D. Topolšek, K. Čižiūnienė, and T. C. Ojsteršek, “Defining transport logistics: a literature review and 
 practitioner opinion based approach,” Transport, vol. 33, no. 5, pp. 1196-1203, 2018. 
[2] T. E. Notteboom, “Container shipping and ports: an overview,” Review of network economics, vol. 3, 
 no. 2, pp. 86-106, 2004. 
[3] J. F. Gonçalves and M. G. Resende, “A biased random key genetic algorithm for 2D and 3D bin 
 packing problems,” International Journal of Production Economics, vol. 145, no. 2, pp. 500-510, 
 2013. 
[4] N. Kemme, Design and operation of automated container storage systems. Springer Science & 
 Business Media, 2012. 
[5] C. Blum and V. Schmid, “Solving the 2D bin packing problem by means of a hybrid evolutionary 
 algorithm,” Procedia Computer Science, vol. 18, pp. 899-908, 2013. 
[6] Y. Wu, W. Li, M. Goh, and R. de Souza, “Three-dimensional bin packing problem with variable bin 
 height,” European journal of operational research, vol. 202, no. 2, pp. 347-355, 2010. 
 234 Email: jst@tnu.edu.vn