Tóm tắt Luận văn Thạc sĩ Toán học: Bài toán sắp xếp kho vận với ràng buộc sắp xếp

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST

Báo xấu

41
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt Luận văn Thạc sĩ Toán học "Bài toán sắp xếp kho vận với ràng buộc sắp xếp" trình bày tổng quan cập nhật các nghiên cứu về chủ đề này: từ thiết kế của khu vực kho bãi đến sự cân bằng vật lý của các cấu hình sắp xếp, từ độ phức tạp tính toán đến phương pháp giải một số lớp bài toán này, từ các bài toán với dữ liệu chắc chắn đến các bài toán với dữ liệu không chắc chắn, v.v...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận văn Thạc sĩ Toán học: Bài toán sắp xếp kho vận với ràng buộc sắp xếp

BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------- Nguyễn Thanh Hòa BÀI TOÁN SẮP XẾP KHO VẬN VỚI RÀNG BUỘC SẮP XẾP Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2021
Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Người hướng dẫn khoa học: Tiến sĩ Lê Xuân Thanh Phản biện 1: Tiến sĩ Lê Hải Yến Phản biện 2: Tiến sĩ Nguyễn Đức Mạnh Luận văn được bảo vệ trước Hội đồng chấm luận văn họp tại Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi 9 giờ 00 phút ngày 12 tháng 11 năm 2021 Có thể tìm hiểu luận văn tại: - Thư viện Học viện Khoa học và Công nghệ.
1 Mở đầu Với một lượng hàng hóa khổng lồ được sắp xếp và luân chuyển qua các bến cảng trên thế giới hàng ngày, chúng ta đang chứng kiến sự bùng nổ của thương mại quốc tế và chuỗi cung ứng toàn cầu. Do đó, việc quản lý và sắp xếp hàng hóa một cách hiệu quả trong các bến cảng ngày càng trở nên quan trọng và thiết yếu. Các hoạt động kho vận tại các bến cảng có thể được phân loại theo các loại hình sau đây: sắp xếp các hàng hóa cập bến vào trong khu vực kho bãi, bốc dỡ các hàng hóa trong khu vực kho bãi để vận chuyển đến các điểm đến khác, sắp xếp lại các hàng hóa trong cùng một khu vực kho bãi, kết hợp sắp xếp và bốc dỡ hàng hóa khi một số hàng hóa cần được sắp xếp vào khu vực kho bãi trong khi một số hàng hóa cần được bốc dỡ khỏi khu vực đó. Trong các loại hình hoạt động kho vận đó, việc sắp xếp hàng hóa cập bến vào trong khu vực kho bãi đóng vai trò trung tâm, vì hiệu quả của hoạt động đó ảnh hưởng tới hiệu quả của các hoạt động khác. Sắp xếp kho vận là bài toán xuất hiện trong nhiều ngữ cảnh thực tế (chẳng hạn như trong các cảng container, các tàu con- tainer, các trạm đỗ tàu điện). Do đó, bài toán sắp xếp kho vận đã trở thành đối tượng nghiên cứu của một hướng chính trong vận trù học (như đã chỉ ra trong bài báo tổng quan [1]). Trong phần giới thiệu của bài báo [2], các tác giả đã trình bày một tổng quan cập nhật các nghiên cứu về chủ đề này: từ thiết kế của khu vực kho bãi đến sự cân bằng vật lý của các cấu hình sắp xếp, từ độ phức tạp tính toán đến phương pháp giải một số lớp bài toán này,
2 từ các bài toán với dữ liệu chắc chắn đến các bài toán với dữ liệu không chắc chắn, v.v... Trong phần tiếp theo của bài báo, các tác giả đã tổng quát hóa một số biến thể của bài toán sắp xếp kho vận, và nghiên cứu bài toán này với các ràng buộc sắp xếp. Sử dụng bài báo [2] làm tài liệu tham khảo chính, trong luận văn này, chúng tôi nghiên cứu một số bài toán tối ưu liên quan đến hoạt động sắp xếp kho vận. Mô tả một cách ngắn gọn, trong các bài toán được chúng tôi nghiên cứu, cho trước một khu vực kho bãi được tổ chức dưới dạng các ngăn xếp (stack). Khu vực kho bãi này đã chứa sẵn một số hàng hóa (items). Hàng hóa đến bến cảng theo một dãy các tập hợp và cần được sắp xếp vào khu vực kho bãi. Các ràng buộc mang tính kỹ thuật đối với quá trình sắp xếp hàng hóa vào kho bãi bao gồm: • Trong mỗi ngăn xếp, các hàng hóa được sắp xếp theo thứ tự vào sau ra trước (last-in-first-out). • Các ngăn xếp có cùng chiều cao, hay chính xác hơn là có cùng số hàng hóa có thể chứa trong ngăn xếp. • Các ràng buộc sắp xếp được cho trước, trong đó quy định hàng hóa nào được sắp xếp lên trên hàng hóa nào. Chúng tôi quan tâm đến các mục tiêu sau. • Tối thiểu tổng số ngăn xếp được sử dụng. • Tối thiểu tổng số hàng hóa được sắp xếp ở vị trí không thuận lợi cho việc bốc dỡ theo thứ tự thời gian xuất bến.
3 Chương 1 Mô tả bài toán 1.1 Khu vực sắp xếp Chúng ta được cho trước một khu vực kho bãi (còn gọi là khu vực sắp xếp) được tổ chức dưới dạng m ngăn xếp (stack), mỗi ngăn xếp có vị trí cố định. Tập hợp các ngăn xếp được ký hiệu là Q = {1, . . . , m}. Mỗi ngăn xếp có b tầng (level), và tập hợp các tầng trong một ngăn xếp được ký hiệu là L = {1, . . . , b}. Như vậy mỗi ngăn xếp có thể chứa được tối đa b đơn vị hàng hóa. Hàng hóa được sắp xếp vào trong các ngăn xếp theo thứ tự vào sau ra trước. Mỗi đơn vị hàng hóa được xếp vào trong một tầng nào đó của một ngăn xếp. Hàng hóa phải được đặt trên mặt đất, hoặc trên một đơn vị hàng hóa khác đã được đặt trong khu vực sắp xếp. 1.2 Thứ tự sắp xếp Có tất cả n hàng hóa trong tập hợp I = {1, . . . , n}, được phân hoạch thành hai tập hợp: I f ix chứa các hàng hóa đã được sắp xếp sẵn trong khu vực sắp xếp, I ∗ chứa các hàng hóa còn lại đang chờ được sắp xếp vào kho bãi. Cấu hình sắp xếp của hàng hóa trong tập hợp I f ix được cho trước cố định. Hàng hóa trong tập hợp I ∗
4 đến khu vực sắp xếp theo thứ tự I 1 → I 2 → . . . → I K , trong đó K là một số nguyên dương, I 1 , . . . , I K lập thành một phân hoạch của tập hợp I ∗ , mỗi tập hợp này chứa các hàng hóa có cùng thời gian đến bến cảng, và hàng hóa trong tập hợp I k phải được sắp xếp hết vào trong khu vực kho bãi trước khi sắp xếp hàng hóa trong tập hợp I k+1 (với k = 1, . . . , K − 1). Chúng ta có thể giả sử không ngăn xếp nào có toàn bộ các tầng chứa hàng hóa thuộc tập hợp I f ix . 1.3 Ràng buộc sắp xếp Theo thứ tự sắp xếp, hàng hóa đến trước không được phép xếp lên trên hàng hóa đến sau. Tùy theo ngữ cảnh, có thể có thêm một số ràng buộc quy định hàng hóa nào được xếp lên trên từng đơn vị hàng hóa. Các ràng buộc này có thể được mã hóa bởi ma trận sắp xếp S = (sij ) ∈ {0, 1}n×n trong đó sij = 1 nếu hàng hóa i có thể xếp được lên hàng hóa j . Để thuận tiện, chúng ta tích hợp thứ tự sắp xếp vào trong ma trận sắp xếp. Ta luôn có sii = 0 với mọi i = 1, . . . , n do không hàng hóa nào có thể xếp lên trên chính nó. Mật độ của một ma trận sắp xếp do đó được tính bởi tỉ số của số phần tử có giá trị 1 so với số phần tử nằm ngoài đường chéo chính của ma trận đó. Ràng buộc sắp xếp cũng có thể được biểu diễn bởi đồ thị sắp xếp GS = (V, A) với tập đỉnh V = {1, . . . , n} và tập các cung có hướng A = {(i, j) | i có thể xếp được lên trên j}. Các ràng buộc sắp xếp có thể có tính chất bắc cầu theo nghĩa nếu hàng hóa i có thể xếp được lên trên hàng hóa j , và hàng hóa j có thể xếp lên trên hàng hóa k , thì hàng hóa i cũng có thể xếp lên trên hàng hóa k . Ma trận sắp xếp được gọi là bắc cầu nếu với mọi i, j, k ∈ I = {1, . . . , n} ta có sij = 1 và sjk = 1 thì cũng có sik = 1.
5 1.4 Mục tiêu sắp xếp Bài toán sắp xếp kho vận đơn giản nhất là bài toán xác định xem có thể tìm được một cách sắp xếp khả thi với các ràng buộc sắp xếp nêu trên hay không. Nếu bài toán đó khả thi, ta quan tâm đến các mục tiêu sau đây. • #St: tối thiểu tổng số ngăn xếp được sử dụng. • #BI : tối thiểu tổng số hàng hóa được sắp xếp ở vị trí không thuận lợi cho việc bốc dỡ theo thứ tự thời gian xuất bến. Với mục tiêu này, mỗi hàng hóa i có một giá trị di chỉ thời gian hàng hóa đó được bốc dỡ khỏi khu vực sắp xếp. Hàng hóa i được gọi là chặn hàng hóa j nếu chúng cùng trong một ngăn xếp và j cần được bốc dỡ sớm hơn i (tức là dj < di ). Nếu hàng hóa i chặn hàng hóa j , ta nói i bị sắp xếp không thuận lợi.
6 Chương 2 Tiếp cận giải 2.1 Các trường hợp giải được trong thời gian đa thức Định lý 1. Bài toán #St với b = 2 có thể giải trong thời gian O(n2.5 ). Định lý 2. Bài toán #BI với b = 2 có thể giải trong thời gian O(n3 ). 2.2 MIP formulations Trong trường hợp b = 3, Định lý 4 [3] đã khẳng định rằng bài toán tìm phương án sắp xếp khả thi là NP-đầy đủ ngay cả khi không có hàng hóa xếp sẵn trong khu vực sắp xếp (I f ix = ∅) và ràng buộc sắp xếp có tính chất bắc cầu. Trong trường hợp b = k với k ≥ 4, kết quả tương tự đã được chỉ ra trong Định lý 2.11 [6]. 2.2.1. Mô hình 3-chỉ số Chúng ta sử dụng các biến nhị phân sau { 1 nếu hàng hóa i được xếp vào tầng ℓ của ngăn xếp q, xiqℓ = 0 nếu ngược lại.
7 Đặt F = {(i, q, l) ∈ I f ix ×Q×L|i ∈ I f ix được xếp trong ngăn q tầng ℓ}. Ta có mô hình quy hoạch nhị phân cho bài toán #St như sau. ∑∑ (St3 − index) min xiq1 (2.1) i∈I q∈Q s.t. xiqℓ = 1 ∀(i, q, ℓ) ∈ F, (2.2) ∑∑ xiqℓ = 1 ∀i ∈ I, (2.3) q∈Q ℓ∈L ∑ xiqℓ ≤ 1 ∀q ∈ Q, ℓ ∈ L, (2.4) i∈I ∑ sij xjqℓ ≥ xi,q,ℓ+1 ∀i ∈ I, q ∈ Q, ℓ ∈ L\{b}, j∈I\{i} (2.5) xiqℓ ∈ {0, 1} ∀i ∈ I, q ∈ Q, ℓ ∈ L. (2.6) Với bài toán #BI , ta sử dụng thêm các biến sau. { 1 nếu i bị xếp không thuận lợi tại tầng ℓ của ngăn q, yiqℓ = 0 nếu ngược lại. Đặt Bi = {j ∈ I | dj < di }. Ta có mô hình sau. ∑∑∑ (BI3 − index) min yiqℓ (2.7) i∈I q∈Q ℓ∈L s.t. xiqℓ = 1 ∀(i, q, ℓ) ∈ F, (2.8) ∑∑ xiqℓ = 1 ∀i ∈ I, (2.9) q∈Q ℓ∈L ∑ xiqℓ ≤ 1 ∀q ∈ Q, i∈I ∀ℓ ∈ L, (2.10)
8 ∑ sij xjqℓ ≥ xi,q,ℓ+1 ∀i ∈ I, q ∈ Q, j∈I\{i} ℓ ∈ L\{b}, (2.11) yiqℓ ≤ xiqℓ ∀i ∈ I, q ∈ Q, ℓ ∈ L, (2.12) ∑∑ |Bi |(1 − xiqℓ + yiqℓ ) ≥ xjqk ∀i ∈ I, q ∈ Q, j∈Bi k
9 Ta có mô hình sau cho bài toán #St. ∑ (StN et) min xsi (2.15) i∈V ∑ s.t. xsi ≤ m (2.16) i∈V xij = 1 ∀ (i, j) ∈ A0 (2.17) ∑ xij = 1 ∀i ∈ V (2.18) j:(i,j)∈A′ ∑ xji = 1 ∀i ∈ V (2.19) j:(j,i)∈A′ hj + b(1 − xij ) ≥ hi + 1 ∀(i, j) ∈ A (2.20) hi ≤ b − 1 ∀i ∈ V (2.21) hi ≥ 0 ∀i ∈ V (2.22) ′ xij ∈ {0, 1} ∀(i, j) ∈ A . (2.23) Với bài toán #BI , ta sử dụng thêm các biến nhị phân yi với ý nghĩa yi = 1 nếu hàng hóa i bị xếp không thuận lợi. Đặt M := max{d1 , . . . , dn }, ta có mô hình sau đây cho bài toán #BI . ∑ (BIN et) min yi (2.24) i∈V ∑ s.t. xsi ≤ m (2.25) i∈V xij = 1 ∀ (i, j) ∈ A0 (2.26) ∑ xij = 1 ∀i ∈ V (2.27) j:(i,j)∈A′ ∑ xji = 1 ∀i ∈ V (2.28) j:(j,i)∈A′ hj + b(1 − xij ) ≥ hi + 1 ∀(i, j) ∈ A (2.29) hi ≤ b − 1 ∀i ∈ V (2.30) hi ≥ 0 ∀i ∈ V (2.31) M yi ≥ di − ci ∀i ∈ V (2.32) ci ≤ cj + (1 − xij ) ∀i ∈ V (2.33)
10 ci ≤ di ∀(i, j) ∈ A (2.34) ′ xij ∈ {0, 1} ∀(i, j) ∈ A (2.35) yi ∈ {0, 1} ∀i ∈ V (2.36) 2.2.3. Mô hình đóng gói Mô hình này yêu cầu tính bắc cầu của ràng buộc sắp xếp. Trong mô hình này, ta chỉ cần xác định xem hàng hóa nào cần được xếp vào trong ngăn xếp nào. Vị trí của mỗi hàng hóa trong ngăn xếp của nó được xác định thông qua tính bắc cầu của ràng buộc sắp xếp giữa các hàng hóa trong cùng ngăn xếp. Ta sử dụng các biến nhị phân xi q với i ∈ I và q ∈ Q theo ý nghĩa { 1 nếu i được xếp vào ngăn q, xij = 0 nếu ngược lại. Ta sử dụng thêm các biến zq với q ∈ Q với ý nghĩa { 1 nếu có hàng hóa được xếp trong ngăn q, zq = 0 nếu ngược lại. Ký hiệu Fbin = {(i, q) ∈ I f ix × Q | i được xếp trong ngăn q} và top Fbin = {(i, q) ∈ I f ix × Q | i là hàng I f ix cao nhất trong q}. Ký hiệu tập hợp các ngăn xếp chứa ít nhất một hàng hóa loại I f ix bởi Qf ix . Với mỗi q ∈ Qf ix , gọi bq là số hàng hóa I f ix đã có sẵn trong ngăn xếp đó. Bài toán #St có thể mô hình hóa như sau. ∑ (StBin) min zq (2.37) q∈Q
11 s.t. xiq = 1 ∀(i, q) ∈ Fbin , (2.38) ∑ xiq ≤ bzq ∀q ∈ Q, (2.39) i∈I xiq ≤ zq ∀i ∈ I, q ∈ Q, (2.40) ∑ xiq = 1 ∀i ∈ I, (2.41) q∈Q ∑ xjq ≤ b(1 − xiq ) ∀(i, q) ∈ I ∗ × Q, (2.42) ∗ j∈I \{i} sij =sji =0 ∑ top xjq = 0 ∀(i, q) ∈ Fbin , (2.43) j∈I ∗ \{i} sji =0 xiq ∈ {0, 1} ∀i ∈ I, q ∈ Q, (2.44) zq ∈ {0, 1} ∀q ∈ Q. (2.45) Với bài toán #BI , chúng ta cần xử lý các “hàng hóa tương đương”. Ta nói các hàng hóa i, j là tương đương nếu • chúng thuộc cùng một tập hợp hàng hóa I λ trong thứ tự sắp xếp I f ix → I 1 → . . . → I K , và • sij = sji = 1. Bổ đề 1. Cho trước một ma trận sắp xếp bắc cầu S = (sij ) ∈ {0, 1}n×n và giả sử tồn tại các hàng hóa tương đương. Khi đó ta có thể chuyển S về một ma trận sắp xếp S ′ sao cho (i) không có hàng hóa tương đương theo quan hệ định nghĩa bởi S′, (ii) S ′ bắc cầu, và (iii) mỗi phương án sắp xếp khả thi theo S có thể chuyển về một phương án khả thi theo S ′ mà không làm tăng số ngăn xếp được sử dụng cũng như số hàng hóa bị xếp ở vị trí không thuận lợi. Với mỗi i ∈ I , đặt Bi′ = {j ∈ I | sij = 1, dj < di }. Ta sử dụng
12 các biến sau. { 1 nếu i được xếp không thuận lợi trong ngăn q, βiq = 0 nếu ngược lại, { 1 nếu i được xếp thuận lợi trong ngăn q, γiq = 0 nếu ngược lại. Ta có mô hình sau cho bài toán #BI . ∑∑ (BIBin) min βiq (2.46) i∈I q∈Q s.t. βiq + γiq = 1 ∀(i, q) ∈ Fbin , (2.47) ∑ (βiq + γiq ) ≤ b ∀q ∈ Q, i∈I (2.48) ∑ (βiq + γiq ) = 1 ∀i ∈ I, (2.49) q∈Q ∑ (βjq + γjq ) ≤ b(1 − βiq − γiq ) ∀(i, q) ∈ I ∗ × Q, j∈I ∗ \{i} sij =sji =0 (2.50) ∑ top (βjq + γjq ) = 0 ∀(i, q) ∈ Fbin , ∗ j∈I \{i} sji =0 (2.51) ∑ (βjq + γjq ) ≤ b(1 − γiq ) ∀(i, q) ∈ I × Q, j∈B ′ (2.52) βiq , γiq ∈ {0, 1} ∀i ∈ I, q ∈ Q. (2.53)
13 Chương 3 Thực nghiệm số 3.1 Tạo dữ liệu Một ví dụ số cụ thể của bài toán sắp xếp kho vận được xác định đầy đủ khi biết số lượng hàng hóa trong từng tập hợp theo thứ tự sắp xếp, cỡ của khu vực kho bãi (số ngăn xếp và chiều cao các ngăn xếp), cấu hình sắp xếp của các hàng hóa đã có sẵn trong khu vực kho bãi, thời gian xuất bến của mỗi hàng hóa, và ràng buộc sắp xếp thể hiện dưới dạng ma trận sắp xếp. Chúng tôi tạo ngẫu nhiên các ví dụ số cho các thử nghiệm, với số hàng hóa như sau. n ∈ {40, 60, 80, 100, 120, 240, 480, 600}. Thứ tự sắp xếp bao gồm 5 tập hợp I f ix → I 1 → I 2 → I 3 → I 4 . Số phần tử trong mỗi tập hợp này được tạo ngẫu nhiên, với tổng số phần tử bằng n xác định như trên. Số phần tử trong I f ix bị giới hạn trên bởi n5 . Để tạo cấu hình sắp xếp cho các hàng hóa có sẵn trong kho bãi, chúng tôi phân bố ngẫu nhiên số hàng hóa trong I f ix vào |I f ix | ngăn xếp sao cho không có ngăn nào bị xếp đầy bởi các hàng hóa trong tập hợp này. Thời gian xuất bến của mỗi hàng hóa được chọn ngẫu nhiên trong {1, 2, . . . , 6}.
14 Chúng tôi tạo ngẫu nhiên các ma trận sắp xếp bằng cách gán với mỗi hàng hóa một bộ 3 tham số w1 , w2 , w3 và chọn giá trị cho các tham số này trong tập hợp {1, 2, 3}. Với mỗi cặp hàng hóa i, j ∈ I f ix ta đặt sij = 1 nếu hàng hóa i được đặt ngay trên hàng hóa j trong cùng một ngăn xếp. Với mỗi hàng hóa i ∈ I ∗ = I\I f ix và bất kỳ hàng hóa j ∈ I , ta đặt sij = 1 nếu i đến sau j và wli ≤ wlj với mọi l ∈ {1, 2, 3}. Theo cách này, các ma trận sắp xếp thu được sẽ có tính chất bắc cầu. Về kích cỡ kho bãi, chúng tôi chọn giá trị {4, 5, 6} cho số tầng b trong các ngăn xếp. Với bài toán #St, chúng tôi khởi tạo giá trị số ngăn xếp m = n2 . Với bài toán #BI , chúng tôi khởi tạo giá trị số ngăn xếp m là giá trị tối ưu của bài toán #St với dữ liệu tương ứng. 3.2 Kết quả thực nghiệm Chúng tôi tiến hành các thực nghiệm trên máy tính PC In- tel(R) Core(TM) i5-4210U, CPU 1.7GHz and 4GB RAM. Dữ liệu cho các bài toán được tạo bởi Visual Basic .NET. Chúng tôi sử dụng ZIMPL 3.3.2 [8] để cài đặt các mô hình, và sử dụng GUROBI 9.1.2 [9] giải số các mô hình này. Chúng tôi đã tiến hành 3 thực nghiệm. Trong thực nghiệm đầu tiên, chúng tôi nhận thấy các mô hình sử dụng tiếp cận đóng gói có tốc độ giải số vượt trội hơn hẳn so với các mô hình sử dụng 2 tiếp cận còn lại. Trong thực nghiệm thứ hai, chúng tôi thấy rằng thời gian chạy của các mô hình sử dụng tiếp cận 3 chỉ số và tiếp cận đóng gói giảm đáng kể khi số ngăn xếp được giảm xuống. Trong thực nghiệm thứ ba, chúng tôi nhận thấy số hàng hóa bị xếp không thuận lợi giảm đáng kể khi số ngăn xếp tăng lên.
15 Kết luận Trong luận văn này, chúng tôi nghiên cứu bài toán sắp xếp kho vận nảy sinh trong hoạt động của các tàu container và cảng container. Chúng tôi trình bày một số kết quả về độ phức tạp tính toán của bài toán, một số mô hình quy hoạch nguyên hỗn hợp cho bài toán và đánh giá hiệu quả các mô hình đó. Trong Chương 1, chúng tôi trình bày cụ thể phát biểu của các bài toán được nghiên cứu trong luận văn. Trong các bài toán này, chúng ta cần sắp xếp các hàng hóa vào trong các ngăn xếp có cùng số tầng. Hàng hóa đến khu vực sắp xếp theo thứ tự trong các tập hợp. Khu vực sắp xếp có thể có sẵn một số hàng hóa trong đó. Ràng buộc sắp xếp quy định hàng hóa nào được phép xếp trên hàng hóa nào. Mục tiêu của bài toán là tối thiểu hoặc số ngăn xếp được sử dụng, hoặc số hàng hóa bị đặt ở vị trí không thuận lợi. Trong Chương 2, chúng tôi chỉ ra rằng khi mỗi ngăn xếp có số tầng bằng 2 thì các bài toán trên có thể giải trong thời gian đa thức bằng cách sử dụng kỹ thuật ghép cặp trong lý thuyết đồ thị. Bài toán sắp xếp kho vận với mỗi ngăn xếp có số tầng ít nhất là 3 được tin là NP-hard, do đó chúng tôi đề xuất 3 tiếp cận mô hình hóa mỗi bài toán được nghiên cứu dưới dạng bài toansn quy hoạch nguyên hỗn hợp. Tiếp cận thứ nhất sử dụng các biến nhị phân 3 chỉ số để ghi nhận hàng hóa nào được xếp vào tầng nào của ngăn xếp nào. Tiếp cận thứ hai biểu diễn các ràng buộc sắp xếp dưới dạng đồ thị sắp xếp, sau đó nhúng đồ thị này vào một luồng mạng và coi mỗi ngăn xếp như một luồng có độ dài tối đa
16 cho trước. Tiếp cận cuối cùng xem mỗi ngăn xếp như một hộp và xác định xem hàng hóa nào được xếp vào hộp nào, vị trí cụ thể của hàng hóa sẽ được xác định thông qua tính chất bắc cầu của các ràng buộc sắp xếp. Mục đích của Chương 3 là xác định mô hình tốt nhất trong các mô hình đã trình bày trong Chương 2. Chúng tôi trình bày quy trình tạo ngẫu nhiên các ví dụ số cho các bài toán được nghiên cứu, đánh giá hiệu quả của các mô hình trên các ví dụ số này. Kết quả thực nghiệm cho thấy tiếp cận đóng góp có hiệu quả vượt trội hơn các tiếp cận khác về tốc độ giải số, và số lượng ngăn xếp có ảnh hưởng lớn tới hiệu quả của các mô hình cũng như số lượng hàng hóa bị xếp ở vị trí không thuận lợi.
17 Tài liệu tham khảo [1] J. Lehnfeld and S. Knust. Loading, unloading and premar- shalling of stacks in storage areas: Survey and classification. European Journal of Operational Research, 239(2): 297–312, 2014. [2] T. Oelschlägel and S. Knust. Solution approaches for stor- age loading problems with stacking constraints. Computers & Operations Research, 127:105142, 2021. [3] F. Bruns, S. Knust, and N. V. Shakhlevich. Complexity results for storage loading problems with stacking constraints. Euro- pean Journal of Operational Research, 249:1074–1081, 2016. [4] S. Even and O. Kariv. An O(n2.5 ) algorithm for maximum matching in general graphs. In Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science, pages 100–112. IEEE, New York, 1975. [5] H. Gabow. An eﬀicient implementation of Edmonds’ algo- rithm for maximum matching on graphs. Journal of the ACM, 23(2):221–234, 1976. [6] X. T. Le. Robust solutions to storage loading problems under uncertainty. PhD thesis, Osnabrück Universität, 2017. [7] X. T. Le and S. Knust. MIP-based approaches for robust stor- age loading problems with stacking constraints. Computers & Operations Research, 78:138–153, 2017.
18 [8] T. Koch. Rapid Mathematical Programming. PhD thesis, Tech- nische Universität Berlin, 2004. [9] https://www.gurobi.com/