ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
_____________________

NGUYỄN PHƯỚC BẢO HẬU

NGHIÊN CỨU ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO
BÀI TOÁN ĐIỀU ĐỘ THANG MÁY VẬN CHUYỂN HÀNG TẠI
MỘT KHO B2B

Chuyên ngành:

Kỹ thuật công nghiệp

Mã số:

8520117

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 07 năm 2023


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA –ĐHQG -HCM

Cán bộ hướng dẫn khoa học:
PGS. TS. Đỗ Ngọc Hiền…………………………………………………………..
PGS. TS. Lê Ngọc Quỳnh Lam……………………………………………………
Cán bộ chấm nhận xét 1: TS. Lê Đức Đạo………………………………………………
Cán bộ chấm nhận xét 2: TS. Dương Quốc Bửu...………………………………………

Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM ngày 08
tháng 07 năm 2023
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. Chủ tịch Hội đồng:

TS. Nguyễn Vạng Phúc Nguyên

2. Thư ký Hội đồng:

TS. Nguyễn Văn Thành

3. Phản biện:

TS. Lê Đức Đạo

4. Phản biện:

TS. Dương Quốc Bửu

5. Ủy viên:

PGS. TS. Đỗ Ngọc Hiền

Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành
sau khi luận văn đã được sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG

TRƯỞNG KHOA CƠ KHÍ



i

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
ĐẠI HỌC QUỐC GIA TP.HCM
Độc lập - Tự do - Hạnh phúc
TRƯỜNG ĐẠI HỌC BÁCH KHOA
______________________
_____________________

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: NGUYỄN PHƯỚC BẢO HẬU MSHV: 2170619
Ngày, tháng, năm sinh: 16/09/1996

Nơi sinh:

Tp. Hồ Chí Minh

Chun ngành: Kỹ thuật cơng nghiệp

Mã số: 8520117

I. TÊN ĐỀ TÀI:
NGHIÊN CỨU ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN ĐIỀU ĐỘ
THANG MÁY VẬN CHUYỂN HÀNG TẠI MỘT KHO B2B
(APPLICATION OF GENETIC ALGORITHM FOR ELEVATOR SCHEDULING
PROBLEM IN A B2B WAREHOUSE)
II. NHIỆM VỤ VÀ NỘI DUNG:
 Quan sát hiện trạng, xác định vấn đề, phân tích nguyên nhân của sự ùn ứ hàng ở
khu vực thang máy trong kho T&C;
 Nghiên cứu ứng dụng giải thuật dui truyền cho bài toán điều độ thang máy;

 Kiểm thử hiệu quả của giải thuật trên các tập dữ liệu.
III. NGÀY GIAO NHIỆM VỤ: 06/02/2023
IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 11/06/2023
V. CÁN BỘ HƯỚNG DẪN:

PGS. TS. Đỗ Ngọc Hiền
PGS. TS. Lê Ngọc Quỳnh Lam

Tp. HCM, ngày . . . . tháng .. . . năm 20....
CÁN BỘ HƯỚNG DẪN 1

CÁN BỘ HƯỚNG DẪN 2

CHỦ NHIỆM BỘ MÔN
ĐÀO TẠO

(Họ tên và chữ ký)

(Họ tên và chữ ký)

(Họ tên và chữ ký)

TRƯỞNG KHOA CƠ KHÍ

(Họ tên và chữ ký)


ii

LỜI CẢM ƠN

Em xin cảm ơn thầy PGS. TS. Đỗ Ngọc Hiền, cô PGS. TS. Lê Ngọc Quỳnh Lam đã ln
tận tình hướng dẫn và hỗ trợ em về cả kiến thức cũng như tinh thần, giúp em có được
phương pháp suy luận logic và sự quyết tâm để hoàn thành luận văn đúng thời hạn.
Em xin cảm ơn các anh, chị đồng nghiệp ở công ty đã hỗ trợ nhiệt tình cho em. Sự quan
tâm của các anh, chị là những nguồn động lực quý giá giúp em nỗ lực hồn thành luận
văn này.
Cuối cùng, nhưng vơ cùng quan trọng, xin cảm ơn gia đình, đã ln là hậu phương vững
chắc về mặt tinh thần, để con đi đến cùng q trình thực hiện và hồn thành luận văn.
Một lần nữa xin chân thành cảm ơn!


iii

TĨM TẮT LUẬN VĂN

Nhà kho ngày càng đóng vai trị quan trọng trong vận hành của một chuỗi cung
ứng. Trong những hoạt động của nhà kho, lấy hàng (order-picking) được đánh giá là
quan trọng vì hoạt động này chiếm tỷ lệ lớn cả về chi phí và nhân lực trong tổng chi phí
và nhận lực vận hành kho. Vì vậy, nâng cao hiệu quả của hoạt động lấy hàng là một chủ
dề luôn thu hút nhiều nhà nghiên cứu cũng như nhà quản lý.
Ở kho T&C, lấy hàng là một hoạt động quan trọng trong quá trình xuất hàng
(outbound) của kho. Do đặc thù lưu trữ theo các tầng lầu, khoảng thời gian diễn ra
(duration) của hoạt động lấy hàng ở kho T&C chịu ảnh hưởng đáng kể bởi kết quả điều
độ sử dụng thang máy để vận chuyển hàng. Hiện tại ở nhà kho nơi tác giả thực hiện
nghiên cứu này, do tác động của các chương trình khuyến mãi của các khách hàng thương
mại điện tử, khối lượng cơng việc của q trình xuất hàng tăng nhanh chóng, đặc biệt
vào các mùa kích cầu lớn trong năm (gọi là các “chiến dịch”). Tình trạng này dẫn đến
xảy ra tranh chấp sử dụng nguồn lực thang máy giữa các nhóm xuất hàng phụ trách các
danh sách hàng (list) khác nhau. Kết quả là, thời gian của rất nhiều danh sách hàng bị
kéo dài do thành phần thời gian ở thang máy lớn, ảnh hưởng cả chất lượng dịch vụ lưu

kho và dịch vụ vận tải công ty. Nhận thấy sự cấp thiết của một giải pháp cho vấn đề này,
tác giả đã cố gắng xây dựng một giải thuật điều độ ở dạng giải thuật di truyền (genetics
algorithm) nhằm cực tiểu hóa tổng thời gian trễ (tardiness) của các danh sách hàng, từ
đó cải thiện hiệu quả hoạt động lấy hàng, góp phần nâng cao uy tín chất lượng dịch vụ
của công ty.


iv

ABSTRACT

Warehouses play an increasingly important role in the operation of a supply chain.
In warehouse operations, order-picking is considered important because this activity
accounts for a large proportion of both cost and human resources in the total cost and
receives the warehouse operation force. Therefore, improving the efficiency of picking
operations is a topic that always attracts many researchers as well as managers.
In the T&C warehouse, picking is an important activity in the outbound process
of the warehouse. Due to the characteristics of storage by floors, the duration of picking
activities at T&C warehouse is significantly affected by the results of dispatching using
elevators to transport goods. Currently in the warehouse where the author conducts this
study, due to the impact of promotions of e-commerce customers, the workload of the
shipping process increases rapidly, especially in the winter. large demand stimulus
during the year (called “campaigns”). This situation leads to a dispute about the use of
elevator resources between the shipping groups in charge of different lists. As a result,
the lead times of many lists are lengthened due to the large elevator time component,
affecting both the quality of the company's warehousing and transportation services.
Realizing the urgency of a solution to this problem, the author tried to build a moderation
algorithm in the form of genetics algorithm to minimize the total delay time (tardiness)
of the lists. order book, thereby improving the efficiency of picking activities,
contributing to improving the reputation of the company's service quality.



v

LỜI CAM ĐOAN CỦA TÁC GIẢ

Tôi xin cam đoan đây là cơng trình nghiên cứu của riêng tơi. Tất cả các dữ liệu
và kết quả sử dụng trong nghiên cứu này là trung thực và chưa được công bố trong các
nghiên cứu khác. Tơi xin hồn tồn chịu trách nhiệm về nghiên cứu của mình nếu khơng
đúng như đã nêu trên.
TÁC GIẢ

Nguyễn Phước Bảo Hậu


vi

MỤC LỤC

LỜI CẢM ƠN ..................................................................................................................ii
TÓM TẮT LUẬN VĂN ................................................................................................ iii
ABSTRACT ....................................................................................................................iv
LỜI CAM ĐOAN CỦA TÁC GIẢ .................................................................................. v
DANH MỤC BẢNG BIỂU ............................................................................................ix
DANH MỤC HÌNH ẢNH ............................................................................................... x
DANH MỤC TỪ VIẾT TẮT ..........................................................................................xi
Chương 1: GIỚI THIỆU .................................................................................................. 1
1.1

Đặt vấn đề ................................................................................................. 1


1.2

Mục tiêu nghiên cứu ................................................................................. 2

1.3

Phạm vi và giới hạn nghiên cứu ............................................................... 3

1.4

Bố cục luận văn ........................................................................................ 3

Chương 2: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN..................................... 5
2.1

Cơ sở lý thuyết ......................................................................................... 5

2.1.1

Q trình lấy hàng ............................................................................. 5

2.1.2

Bài tốn điều độ máy song song ........................................................ 6

2.1.3

Giải thuật di truyền ............................................................................ 8


2.2

Các nghiên cứu liên quan ......................................................................... 9

2.3

Phương pháp luận ................................................................................... 10

Chương 3: PHÂN TÍCH ĐỐI TƯỢNG NGHIÊN CỨU VÀ PHÁT BIỂU VẤN ĐỀ .. 12
3.1

Giới thiệu công ty ................................................................................... 12


vii

3.2

Phân tích đối tượng nghiên cứu và xác định vấn đề............................... 12

3.3

Xác định nguyên nhân và đề xuất giải pháp........................................... 17

3.4

Phát biểu vấn đề ..................................................................................... 18

Chương 4: MƠ HÌNH HĨA BÀI TOÁN....................................................................... 19
4.1


Các định nghĩa ........................................................................................ 19

4.2

Các giả sử ............................................................................................... 19

4.3

Các tham số, chỉ số và tập hợp ............................................................... 19

4.4

Hàm mục tiêu, biến quyết định, ràng buộc ............................................ 20

4.5

Cách xác định thời điểm hoàn thành danh sách hàng ............................ 22

Chương 5: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN .................................................. 24
5.1

Cơ chế mã hóa ........................................................................................ 24

5.2

Mã hóa và khởi tạo quần thể ban đầu ..................................................... 25

5.3


Chọn lọc.................................................................................................. 28

5.4

Trao đổi chéo .......................................................................................... 30

5.5

Đột biến .................................................................................................. 33

5.6

Điều kiện dừng ....................................................................................... 36

Chương 6: KIỂM THỬ GIẢI PHÁP ............................................................................. 37
6.1

Phương pháp kiểm thử giải pháp ............................................................ 37

6.2

Các tập dữ liệu đầu vào .......................................................................... 37

6.3

Phương pháp chuẩn hóa dữ liệu đầu vào................................................ 38

6.4

Giải pháp kinh nghiệm ........................................................................... 40


6.5

Các chỉ số đo lường hiệu quả của giải pháp ........................................... 42

6.6

Xác định điều kiện dừng và số lần lặp ................................................... 43


viii

6.7

Kết quả kiểm thử giải pháp và phân tích ................................................ 44

6.7.1

Kiểm thử với tập dữ liệu 1 ............................................................... 44

6.7.2

Kiểm thử với tập dữ liệu 2 ............................................................... 49

6.8

Kết luận về kết quả kiểm thử.................................................................. 55

Chương 7: KẾT LUẬN VÀ KIẾN NGHỊ ..................................................................... 56
7.1


Kết luận .................................................................................................. 56

7.2

Kiến nghị ................................................................................................ 56

DANH MỤC CÔNG TRÌNH KHOA HỌC .................................................................. 58
TÀI LIỆU THAM KHẢO .............................................................................................. 59
PHỤ LỤC A: DỮ LIỆU QUÁ TRÌNH LẤY HÀNG .................................................... 61
PHỤ LỤC B: CÁC BẢNG DỮ LIỆU ĐẦU VÀO CHUẨN HÓA ............................... 80
PHỤ LỤC C: ĐOẠN MÃ LẬP TRÌNH PYTHON ....................................................... 84
PHỤ LỤC D: BIẾN ĐỔI ĐỘ THÍCH NGHI THEO CÁ THỂ ................................... 178
PHỤ LỤC E: TẤT CẢ NHIỄM SẮC THỂ ................................................................. 179
PHẦN LÝ LỊCH TRÍCH NGANG .............................................................................. 180
Q TRÌNH ĐÀO TẠO ............................................................................................. 180
Q TRÌNH CƠNG TÁC........................................................................................... 180


ix

DANH MỤC BẢNG BIỂU
Bảng 1.1. Bố cục của luận văn ......................................................................................... 3
Bảng 2.1. Các nghiên cứu ứng dụng điều độ máy song song trong nhà kho ................... 7
Bảng 3.1. Dữ liệu lấy hàng thực tế................................................................................. 16
Bảng 5.1. Ví dụ về cơ chế mã hóa ................................................................................. 26
Bảng 6.1. Tóm tắt thơng tin các tập dữ liệu đầu vào ..................................................... 37
Bảng 6.2. Mẫu Bảng dữ liệu sản phẩm .......................................................................... 39
Bảng 6.3. Mẫu Bảng dữ liệu về danh sách hàng ............................................................ 39
Bảng 6.4. Mẫu Bảng chứa dữ liệu chi tiết về hàng hóa trong danh sách hàng .............. 39

Bảng 6.5. Bảng dữ liệu năng lực thang máy .................................................................. 39
Bảng 6.6. Trình tự điều độ khối hàng vào thang máy - tập dữ liệu 1 ............................ 40
Bảng 6.7. Trình tự điều độ khối hàng vào thang máy - tập dữ liệu 2 ............................ 40
Bảng 6.8. Tóm tắt xác định điều kiện dừng và số lần lặp .............................................. 43
Bảng 6.9. Kết quả kiểm thử với tập dữ liệu 1 – giữa các lần lặp ................................... 45
Bảng 6.10. Kết quả kiểm thử với tập dữ liệu 1 - so sánh với giải pháp kinh nghiệm.... 46
Bảng 6.11. Trình tự điều độ khối hàng vào thang máy đề xuất cho tập dữ liệu 1 ......... 49
Bảng 6.12. Kết quả kiểm thử với tập dữ liệu 2 – giữa các lần lặp ................................. 50
Bảng 6.13. Kết quả kiểm thử với tập dữ liệu 2 - so sánh với giải pháp kinh nghiệm.... 50
Bảng 6.14. Trình tự điều độ khối hàng vào thang máy đề xuất cho tập dữ liệu 2 ......... 53


x

DANH MỤC HÌNH ẢNH
Hình 2.1. Các chức năng cơ bản của một nhà kho ........................................................... 5
Hình 3.1. Quy trình xuất hàng ........................................................................................ 14
Hình 3.2. Tỷ lệ trung bình hai thành phần thời gian của quá trình lấy hàng ................. 17
Hình 5.1. Lưu đồ Khối Mã hóa và Khởi tạo quần thể ban đầu ...................................... 28
Hình 5.2. Lưu đồ Khối Chọn lọc.................................................................................... 30
Hình 5.3. Ví dụ phương pháp order crossover ............................................................... 32
Hình 5.4. Lưu đồ Khối Trao đổi chéo ............................................................................ 33
Hình 5.5. Lưu đồ Khối Đột biến .................................................................................... 36
Hình 6.1. So sánh giá trị hàm mục tiêu giữa giải pháp của giải thuật và giải pháp kinh
nghiệm – tập dữ liệu 1 .................................................................................................... 47
Hình 6.2. So sánh giá trị độ thích nghi giữa giải pháp của giải thuật và giải pháp kinh
nghiệm – tập dữ liệu 1 .................................................................................................... 48
Hình 6.3. So sánh giá trị hàm mục tiêu giữa giải pháp của giải thuật và giải pháp kinh
nghiệm – tập dữ liệu 2 .................................................................................................... 52
Hình 6.4. So sánh giá trị độ thích nghi giữa giải pháp của giải thuật và giải pháp kinh

nghiệm – tập dữ liệu 2 .................................................................................................... 53


xi

DANH MỤC TỪ VIẾT TẮT
VIẾT TẮT

TỪ VIẾT TẮT

DIỄN GIẢI
Dùng đê chỉ chung các giao dịch

B2B

Business-to-Business

thương mại giữa các doanh nghiệp
với nhau

NST

Nhiễm sắc thể

SKU

Stock-Keeping-Unit

Cấu trúc di truyền cơ bản trong giải
thuật di truyền

Đơn vị lưu trữ hàng hóa trong kho
Cách gọi văn bản hợp đồng quy định

SLA

Service-Level-Agreement

các điều khoản về dịch vụ giữa công
ty nơi tác giả thực hiện luận văn và
khách hàng của công ty


1

Chương 1: GIỚI THIỆU
1.1

ĐẶT VẤN ĐỀ
Theo nghiên cứu của [1], thuê ngoài (outsourcing) đã trở thành chiến lược kinh

doanh quan trọng trên phạm vi toàn cầu trong những thập kỷ gần đây, và vai trò quan
trọng của quản lý chuỗi cung ứng đã tăng lên đáng kể kể từ giữa những năm 1990. Theo
nghiên cứu của [2], nhà kho nắm giữ những vai trò chiến lược như đạt được thời gian
chu kỳ ngắn hơn, lượng tồn kho ít hơn, chi phí thấp hơn và dịch vụ khách hàng tốt hơn.
Như vậy, việc thuê kho ngoài để lưu trữ và quản lý vật tư là một xu hướng ngày càng trở
nên quan trọng và phổ biến trong các hoạt động của chuỗi cung ứng toàn cầu.
Nghiên cứu [3] chỉ ra rằng: q trình lấy hàng (order-picking) chiếm khoảng 55%
chi phí vận hành nhà kho. Vì vậy, đây là một quá trình đáng quan tâm cải tiến để nâng
cao hiệu quả vận hành của các kho th ngồi, vì chất lượng của quá trình lấy hàng sẽ
ảnh hưởng lớn đến cạnh tranh về giá bán dịch vụ của các kho này. Một trong những vấn

đề phổ biến trong vận hành kho nói chung và q trình lấy hàng nói riêng là tranh chấp
sử dụng nguồn lực. Kho Tây Nam (T&C) không nằm ngoài hiện trạng này. Cụ thể, thời
gian diễn ra quá trình lấy hàng ở kho T&C đang gặp phải vấn đề về tranh chấp sử dụng
nguồn lực thang máy trong q trình xuất hàng, đây chính là vấn đề sẽ được tập trung
nghiên cứu trong luận văn.
Điều độ công việc là một trong những yếu tố quan trọng quyết định đến khối
lượng công việc cần phải làm. Việc điều độ công việc sẽ quyết định các yếu tố công việc
sẽ được làm vào lúc nào, với khối lượng công việc bao nhiêu, và sử dụng nguồn lực như
thế nào. Điều độ giúp giải quyết các vấn đề như giảm thiểu thời gian chờ đợi của khách
hàng, thời gian vận hành, đồng thời sử dụng hiệu quả các nguồn lực của doanh nghiệp.
Điều độ máy song song giải quyết việc gán từng hoạt động cho một trong các máy
ứng viên và sau đó sắp xếp thứ tự các hoạt động được chỉ định trên từng máy. Nhiều vấn
đề trong cuộc sống thực có thể được mơ phỏng như các vấn đề điều độ máy song song,


2

ví dụ: một trạm xăng có thể phục vụ nhiều xe cùng một lúc tại các trụ xăng và khu vực
dịch vụ của ngân hàng có thể phục vụ nhiều khách hàng cùng một lúc. Vấn đề tranh chấp
sử dụng thang máy xảy ra ở kho T&C xảy ra trên các thang máy giống nhau và các thang
máy này có thể cùng lúc vận chuyển hàng hóa, nên vấn đề hồn tồn có thể quy về bài
tốn điều độ máy song song.
Hiện tại ở nhà kho nơi tác giả thực hiện nghiên cứu này, do tác động của các
chương trình khuyến mãi của các khách hàng thương mại điện tử, khối lượng cơng việc
của q trình xuất hàng tăng nhanh chóng, đặc biệt vào các mùa kích cầu lớn trong năm
(gọi là các “chiến dịch”). Tình trạng này dẫn đến xảy ra tranh chấp sử dụng nguồn lực
thang máy giữa các nhóm xuất hàng phụ trách các danh sách hàng (list) khác nhau. Kết
quả là, thời gian của rất nhiều danh sách hàng (định lượng cụ thể trong chương 3) bị kéo
dài do thành phần thời gian ở thang máy lớn, ảnh hưởng cả chất lượng dịch vụ lưu kho
và dịch vụ vận tải công ty. Nhận thấy sự cấp thiết của một giải pháp cho vấn đề này, tác

giả đã cố gắng xây dựng một giải thuật điều độ ở dạng giải thuật di truyền (genetics
algorithm) nhằm cực tiểu hóa tổng thời gian trễ (tardiness) của các danh sách hàng, từ
đó nâng cao uy tín chất lượng dịch vụ của cơng ty.
Vì những lý do nêu trên, luận văn sẽ tập trung giải quyết vấn đề tranh chấp sử
dụng nguồn lực thang máy ở kho bằng một giải thuật điều độ máy song song phù hợp,
hướng đến cực tiểu thời gian trễ của quá trình lấy hàng sau khi áp dụng giải thuật vào
thực tế.
1.2

MỤC TIÊU NGHIÊN CỨU
Luận văn “Nghiên cứu ứng dụng giải thuật di truyền cho bài toán điều độ thang

máy vận chuyển hàng tại một kho B2B” được thực hiện nhằm cực tiểu hóa tổng thời gian
trễ tại thang máy của tất cả các danh sách hàng, góp phần vào việc giảm thời gian trễ của
tồn bộ quá trình lấy hàng.


3

1.3

PHẠM VI VÀ GIỚI HẠN NGHIÊN CỨU
Luận văn được thực hiện trong phạm vi thành phần thời gian tại thang máy của

quá trình lấy hàng ở một kho 3PL. Luận văn này chưa xem xét đến các yếu tố ngẫu nhiên,
bất định.
1.4

BỐ CỤC LUẬN VĂN
Bố cục của luận văn như được trình bày trong bảng 1.1.


Bảng 1.1. Bố cục của luận văn
CHƯƠNG

TÊN CHƯƠNG

NỘI DUNG CHƯƠNG
Sự cần thiết của đề tài luận văn đối với vận

1

Giới thiệu

hành của doanh nghiệp, cũng như mục tiêu,
phạm vi và giới hạn nghiên cứu và bố cục
của luận văn.
Trình bày những cơ sở lý thuyết được sử

2

Cơ sở lý thuyết và

dụng trong luận văn, điểm qua nghiên cứu có

phương pháp luận

liên quan đến đề tài của luận văn và trình bày
phương pháp luận của luận văn.
Giới thiệu doanh nghiệp, giới thiệu đối tượng


3

Phân tích đối tượng

nghiên cứu, phân tích hiện trạng của đối

nghiên cứu và phát

tượng nghiên cứu, xác định vấn đề, nguyên

biểu vấn đề

nhân gốc rễ, đề xuất giải pháp sơ bộ. Từ đó
phát biểu vấn đề.

4

5

Mơ hình hóa bài

Mơ hình hóa bài tốn cần giải quyết ở dạng

tốn

mơ tả bằng lời và dạng toán học.

Ứng dụng giải thuật

Ứng dụng giải thuật di truyền vào giải quyết


di truyền

bài toán


4

CHƯƠNG

TÊN CHƯƠNG

NỘI DUNG CHƯƠNG
Sử dụng các tập dữ liệu với các kích cỡ khác

6

Kiểm thử giải pháp

nhau để kiểm thử giải pháp, kết luận hiệu quả
cải tiến của giải pháp
Nêu lên những kết quả nổi bật của nghiên

7

Kết luận và kiến

cứu, cũng như đưa ra một số kiến nghị của

nghị


tác giả đối với các công ty liên quan đến giải
pháp mà nghiên cứu đề xuất.


5

Chương 2: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN
2.1

CƠ SỞ LÝ THUYẾT
2.1.1

Quá trình lấy hàng

Lấy hàng (order-picking) là quá trình giải phóng sản phẩm từ khu vực lưu trữ để
đáp ứng nhu cầu cụ thể của khách hàng [4].
Vị trí của lấy hàng (pick) trong vận hành kho thể hiện như trên hình 2.1; các hoạt
động cịn lại bao gồm: nhận hàng (receive), cất hàng (put-away), lưu trữ (storage), đóng
gói – vận chuyển (pack – ship).

Hình 2.1. Các chức năng cơ bản của một nhà kho
(nguồn: [3])

Về mặt thông tin, trước q trình lấy hàng, hệ thống thơng tin quản lý kho
(warehouse management system – WMS) đối chiếu lại với lượng tồn kho sẵn có và xác
định các thiếu hụt nếu có. Thêm vào đó, WMS sẽ tổ chức lại yêu cầu lấy hàng để phù
hợp với mặt bằng. Q trình này bao gồm việc tạo ra các dịng lấy hàng (pick line) thể
hiện rõ vị trí lấy hàng, số lượng cần lấy và đơn vị đo của sản phẩm, và gộp các dòng lấy
hàng vào các danh sách lấy hàng (pick-list), tất cả phải đảm bảo người lấy hàng (picker)

di chuyển một cách dễ dàng và tiết kiệm. Sau khi diễn ra các giai đoạn trên, danh sách
lấy hàng được gửi đến người lấy hàng [3].
[4] đã nêu ra những kiểu lấy hàng cơ bản:


6

 Lấy hàng rời rạc (discrete order picking): mỗi người lấy hàng lấy đầy đủ
các sản phẩm của một đơn hàng trong mỗi hành trình.
 Lấy hàng theo lơ (batch picking): mỗi người lấy hàng lấy một nhóm nhiều
đơn hàng cùng nằm trên một dãy kệ trong mỗi hành trình, những sản phẩm
giống nhau giữa các đơn hàng sẽ được lũy tích số lượng và được chia lại
vào các đơn hàng sau khi lấy hàng.
 Lấy hàng theo khu vực (zone picking): tổng nhu cầu lấy hàng sẽ được phân
chia vào các khu vực lưu trữ khác nhau, mỗi khu do một người lấy hàng
phụ trách. Người lấy hàng lấy tất cả những sản phẩm thuộc khu vực của
mình, những sản phẩm sau đó sẽ được phân chia vào các đơn hàng theo
đúng yêu cầu của khách hàng.
 Lấy hàng theo lượt (wave picking): các đơn hàng được gộp thành các
nhóm, mỗi nhóm sẽ được lấy vào một khung thời gian nhất định trong
ngày, theo hình thức của phương pháp lấy hàng rời rạc.
Bài toán được giải quyết trong luận văn có đối tượng nghiên cứu là một q trình
lấy hàng rời rạc.
2.1.2

Bài toán điều độ máy song song

Bài toán điều độ máy song song thường có dạng: n cơng việc độc lập (1; 2; 3; …;
n) được thực hiện trên m máy tương tự nhau (1; 2; 3; …; m). Hàm mục tiêu phổ biến
của bài toán này là thời gian trễ. Thời gian trễ được định nghĩa như sau:

 Nếu cơng việc trễ thì thời gian trễ là độ vượt của thời điểm hoàn thành so
với thời điểm tới hạn mong muốn;
 Nếu cơng việc khơng trễ thì thời gian trễ bằng 0.
Tóm tắt một số nghiên cứu ứng dụng bài toán điều độ máy song song trong môi
trường vận hành kho như ở Bảng 2.1.


7

Bảng 2.1. Các nghiên cứu ứng dụng điều độ máy song song trong nhà kho
NGHIÊN

HÀM MỤC

BIẾN QUYẾT

CỨU

TIÊU

ĐỊNH

RÀNG BUỘC
Máy chưa sẵn sàng chưa
đến khi hoàn thành thao tác

Tổng thời gian
[5]

hoàn thành của

các công việc

unloading;
Chuỗi công việc

Mỗi công việc được điều

trên các “máy”

độ duy nhất 1 lần;
Mỗi máy chỉ được thực
hiện 1 công việc tại 1 thời
điểm

Biến nhị phân
Cực tiểu tổng
thời gian trễ có
[6]

trọng số và sự
tiêu thụ năng
lượng

gán cơng việc
vào máy với
tham số tốc độ
chạy kèm theo
Thời gian bắt
đầu mỗi công


Mỗi công việc được điều
độ duy nhất 1 lần;
Mỗi máy chỉ được thực
hiện 1 công việc tại 1 thời
điểm

việc trên máy
Mỗi công việc được điều

[7]

Cực tiểu tổng

Chuỗi công việc

thời gian trễ

trên các “máy”

độ duy nhất 1 lần;
Mỗi máy chỉ được thực
hiện 1 công việc tại 1 thời
điểm

Dựa trên bảng 2.1, các bài toán ứng dụng điều độ máy song song trong nhà kho
thường có:


8


 Hàm mục tiêu là cực tiểu tổng thời gian trễ hoặc tổng thời gian hoàn thành;
 Biến quyết định là chuỗi công việc được thực hiện trên các “máy” hoặc
biến nhị phân gán công việc với “máy”;
 Ràng buộc đảm bảo tất cả công việc được điều độ, cũng như “máy”
không thực hiện cùng lúc hai công việc.
Các yếu tố thường gặp vừa nêu sẽ được áp dụng trong q trình mơ hình hóa bài tốn
của luận văn.
2.1.3

Giải thuật di truyền

Theo nghiên [8], lý thuyết chọn lọc tự nhiên cho rằng những thực vật và động vật
tồn tại ngày nay là kết quả của hàng triệu năm thích ứng với những nhu cầu của môi
trường. Tại những thời điểm nhất định, các loài khác nhau, cũng như các cá thể của cùng
một loài, cùng tồn tại hoặc đấu tranh với nhau để tranh giành nguồn lực. Những lồi có
khả năng thích nghi tốt hơn sẽ có được nguồn lực và tạo ra thế hệ con cháu cho tương
lai. Những lồi khơng thích nghi đủ tốt sẽ giảm dần số lượng hoặc khơng có con cháu.
Những lồi thích nghi tốt được gọi là những loài phù hợp (fit) hơn những lồi cịn lại.
Qua thời gian, tồn bộ hệ sinh thái tiến hóa để có được những lồi, mà về trung bình, có
độ phù hợp ở thế hệ sau cao hơn thế hệ trước, nhiều đặc trưng được tạo ra để đẩy mạnh
sự sinh tồn. Giải thuật di truyền hình thành dựa trên nền tảng này. Lời giải cần phải được
mã hóa thành các chuỗi mã thể hiện các nhiễm sắc thể (chromosome) – là cấu trúc tương
ứng trong sinh học mang thông tin di truyền của cá thể và bao gồm nhiều gen. Mỗi gen
trên nhiễm sắc thể biểu diễn một đặc điểm của cá thể. Quá trình hình thành quần thể mới
xảy ra nhờ các toán tử sinh sản. Toán tử sinh sản (reproduction operator) chủ yếu được
dùng trong giải thuật di truyền là trao đổi chéo (crossover), khi con được tạo ra bằng
cách trao đổi một hoặc nhiều đoạn con của hai nhiễm sắc thể bố mẹ. Một toán tử di
truyền khác là đột biến (mutation), khi một gen đơn lẻ trong nhiễm sắc thể được thay
bằng một gen khác. Chi tiết cách ứng dụng giải thuật di truyền trong luận văn này sẽ
được trình bày ở chương 5.



9

2.2

CÁC NGHIÊN CỨU LIÊN QUAN
Chaudhry, I. A., & Elbadawi, I. A. (2017). Minimisation of total tardiness for

identical parallel machine scheduling using genetic algorithm. Sādhanā, 42(1), 11-21.
Bài báo này xem xét việc giảm thiểu tổng thời gian trễ cho một tập hợp công việc
trên một tập hợp các máy song song. Phương pháp tiếp cận được chọn là giải thuật di
truyền (GA). Hai bài tốn có 20 và 25 cơng việc, có số máy song song lần lượt bằng 2,
4, 6, 8 và 10 được giải theo cách tiếp cận đề xuất. Mỗi tổ hợp số lượng cơng việc và máy
móc bao gồm 125 bài toán được tạo ngẫu nhiên dựa trên mơ hình tốn.
Sheremetov, L., Martínez-Moz, J., & Chi-Chim, M. (2018). Two-stage
genetic algorithm for parallel machines scheduling problem: Cyclic steam stimulation
of high viscosity oil reservoirs. Applied Soft Computing, 64, 317-330.
Nghiên cứu [9] xem xét bài tốn phân cơng tối ưu các máy phát hơi nước như một
bài toán điều độ máy song song. Tổng thời gian trễ được sử dụng làm mục tiêu. Giải
thuật được đề xuất là một dạng giải thuật di truyền và được thử nghiệm trên tập dữ liệu
thực từ tài nguyên mỏ dầu nằm ở đầm lầy ven biển của Vịnh Mexico.
Adan, J. (2022). A hybrid genetic algorithm for parallel machine scheduling
with setup times. Journal of Intelligent Manufacturing, 33(7), 2059-2073.
Nghiên cứu [10] đề xuất một giải thuật di truyền dạng lai mới để giải quyết vấn
đề điều độ máy song song, với thời gian thiết lập phụ thuộc vào trình tự và máy, cũng
như các ràng buộc về yêu cầu vận hành của máy. Giải thuật di truyền được kết hợp với
giải thuật tìm kiếm vùng cấm (tabu-search). Giải thuật được đánh giá trên 1200 kịch bản
tham số và cho thấy hiệu quả giải quyết vấn đề.



10

2.3

PHƯƠNG PHÁP LUẬN
Phương pháp luận của luận văn dựa trên phương pháp “CDIO”, được thực hiện

lần đầu ở Viện Công nghệ Massachusets (Mỹ) vào đầu những năm 1990. Theo đó,
phương pháp luận của luận văn sẽ bao gồm các giai đoạn chính:
 “C”

= Conceive

: Hình thành ý tưởng.

 “D”

= Design

: Thiết kế ý tưởng.

 “I”

= Implement

: Thực hiện.

 “O”


= Operation

: Vận hành.

Cụ thể, thiết kế chi tiết của phương pháp luận có tất cả 10 bước, phân chia vào
các giai đoạn “C”, “D”, “I”, “O”, như trình bày sau đây.
Giai đoạn “C” – Hình thành ý tưởng, gồm các bước:
1. Đặt vấn đề: Dẫn chứng những thông tin đáng tin cậy và lập luận để thể
hiện sự cần thiết của đề tài luận văn.
2. Phân tích đối tượng nghiên cứu và xác định bài tốn: Phân tích đối tượng
nghiên cứu, xác định vấn đề cần quan tâm theo quan điểm của các bên liên
quan, xác định nguyên nhân gốc rễ của vấn đề và hình thành giải pháp sơ
bộ cho bài toán.
3. Phát biểu vấn đề: Phát biểu một cách đầy đủ về vấn đề, cung cấp một bức
tranh toàn diện về khoảng cách giữa trạng thái hiện tại (hiện trạng) và trạng
thái mong muốn (kỳ vọng/ mục tiêu).
Giai đoạn “D” – Thiết kế ý tưởng:
4. Phát triển giải pháp: Dựa trên các nghiên cứu đáng tin cậy, căn cứ vào
quá trình quan sát thực tế vận hành tại kho, thực hiện phân tích và lựa chọn
giữa nhiều phương án (nếu cần), xác định giải pháp phù hợp cho vấn đề đã
phát biểu.


11

Giai đoạn “I” – Thực hiện:
5. Hình thành mơ hình tốn: Mơ hình tốn được hình thành để phản ánh bài
toán thực tế, với những giả sử phù hợp.
6. Nghiên cứu và lựa chọn giải thuật: Thực hiện nghiên cứu, phân tích, lựa
chọn giải thuật phù hợp với mơ hình tốn cũng như hồn cảnh của đối

tượng nghiên cứu.
7. Thu thập và xử lý những dữ liệu liên quan: Dựa trên mơ hình tốn và
giải thuật, xác định các dữ liệu cần thiết, sau đó xử lý dữ liệu để đưa về
dạng phù hợp (các “template”) nhằm tạo đầu vào tương thích với đoạn mã
lập trình.
8. Lập trình và kiểm tra: Sử dụng dữ liệu quá khứ để xây dựng và kiểm tra
đoạn mã lập trình thực thi giải thuật; và thực hiện hiệu chỉnh mơ hình, giải
thuật, hoặc đoạn mã lập trình nếu cần thiết cho đến khi đạt được các mục
tiêu đề ra cũng như đảm bảo dữ liệu đầu ra phản ánh đúng thực tế vận
hành.
Giai đoạn “O” – Vận hành:
9. Đánh giá hiệu quả của giải pháp: Đánh giá xem giải pháp giúp cải thiện
tình trạng vận hành tốt đến mức độ nào thông qua một số chỉ số cụ thể, có
liên quan đến mục tiêu đã đặt ra.
10. Kết luận và kiến nghị: Kết luận về kết quả đạt được, đưa ra những khuyến
nghị với phía cơng ty liên quan đến việc triển khai sử dụng giải pháp vào
thực tế, cũng như đề xuất các hướng nghiên cứu kế tiếp.


12

Chương 3: PHÂN TÍCH ĐỐI TƯỢNG NGHIÊN CỨU VÀ PHÁT
BIỂU VẤN ĐỀ
3.1

GIỚI THIỆU CÔNG TY
T&C Logistics là đơn vị cung cấp dịch vụ xử lý và vận chuyển đơn hàng đa kênh,

đa nền tảng. T&C lưu kho, đóng gói và vận chuyển những đơn đặt hàng của các khách
hàng thông qua mạng lưới kho bãi và đối tác giao nhận trên tồn quốc. Lợi thế cạnh tranh

mà cơng ty hướng tới là đáp ứng các chuẩn dịch vụ nghiêm ngặt đã cam kết với từ khách
hàng.
(Nguồn: dựa trên trang web cơng ty />3.2

PHÂN TÍCH ĐỐI TƯỢNG NGHIÊN CỨU VÀ XÁC ĐỊNH VẤN ĐỀ
Đối tượng nghiên cứu của luận văn là quá trình lấy hàng ở kho T&C. Quá trình

lấy hàng là một phần của quá trình xuất hàng (theo lưu đồ quy trình ở Hình 3.1) do Nhóm
Tồn kho thực hiện. Quá trình này bắt đầu bằng việc triển khai lấy hàng bởi các người lấy
hàng (picker) dựa trên danh sách hàng (pick-list) mà Nhóm Dữ liệu đã ban hành trước
đó. Hàng hóa sau khi được lấy từ kệ hàng sẽ được vận chuyển đến trước thang máy và
chờ di chuyển xuống lầu thấp bằng thang máy. Điểm kết thúc của quá trình lấy hàng là
khi hàng đến khu vực tập kết hàng. Do thiết kế hạ tầng ở dạng các tầng lầu, nên hiệu quả
của quá trình lấy hàng phụ thuộc rất lớn vào hiệu quả sử dụng thang máy để vận chuyển
hàng giữa các tầng lầu. Lưu đồ ở Hình 3.1 đã cho thấy rõ ràng rằng, thang máy được sử
dụng càng hiệu quả, khả năng xuất hiện nút thắt cổ chai (bottle-neck) trong quá trình lấy
hàng càng được cắt giảm, hiệu quả của quá trình lấy hàng cũng theo đó mà tăng lên.