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

LÊ BÁ TOÀN

LẬP LỊCH BỐC XẾP
CONTAINER Ở CẢNG BIỂN
Chuyên ngành : Khoa Học Máy Tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ

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


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 : Tiến sĩ Huỳnh Tường Nguyên
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 1 : Tiến sĩ Nguyễn Văn Minh Mẫn
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
Cán bộ chấm nhận xét 2 :Tiến sĩ Tô Bá Lâm
(Ghi rõ họ, tên, học hàm, học vị và chữ ký)
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 10 tháng 07 năm 2015.
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
(Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ luận văn
thạc sĩ)
1. Tiến sĩ Phạm Trần Vũ
2. Tiến sĩ Nguyễn Đức Thái

3. Tiến sĩ Nguyễn Văn Minh Mẫn
4. Tiến sĩ Tô Bá Lâm
5. Tiến sĩ Trần Ngọc Minh
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

Phạm Trần Vũ

TRƯỞNG KHOA…………


LỜI CẢM ƠN
Thực hiện luận văn tốt nghiệp là chặng đường cuối cùng của chương
trình đào tạo cao học tại trường ĐH Bách Khoa TPHCM, tạm kết thúc giai
đoạn khởi đầu của việc nghiên cứu khoa học. Thực hiện và hồn thành một
khố luận khơng phải là vấn đề đơn giản với những người nghiên cứu khoa học
non trẻ như chúng tơi. Nếu khơng được sự hỗ trợ nhiệt tình từ nhiều phía thì kết
quả luận văn sẽ khơng được như hôm nay.
Đầu tiên, tôi xin chân thành cảm ơn Thầy Huỳnh Tường Nguyên, giảng
viên trực tiếp hướng dẫn tôi hồn thành khố luận này. Cảm ơn Thầy đã quan
tâm sâu sát và nhiệt tình ủng hộ cũng như giúp đỡ tơi mọi mặt trong q trình
thực hiện khố luận.
Tơi cũng xin cảm ơn các Thầy, Cô cũng như các bạn bè đồng mơn trong
Khoa đã nhiệt tình ủng hộ và đóng góp ý kiến để tơi hồn thiện cơng trình
nghiên cứu cửa mình.
Để thực hiện khố luận, tơi đã sử dụng thông tin thu thập từ Cảng Cát
Lái và Cảng Sài Gịn. Vì thế, tơi xin chân thành cảm ơn Ban Lãnh Đạo Cảng và
các anh em cán bộ đã hết lịng hỗ trợ chúng thơi thu thập thơng tin và tổ chức
đồn tham quan khảo sát quy trình hoạt động ở cảng.

Lời cuối cùng, tôi xin gửi lời cảm ơn sâu sắc đến gia đình, cha mẹ và
bạn bè đã luôn động viên, giúp đỡ tôi trên con đường học tập và trong cuộc
sống. Cảm ơn công ty Secude và công ty KMS đã hỗ trợ và tạo điều kiện để tơi
tham gia chương trình đào tạo của trường và thực hiện các nghiên cứu liên
quan.
Học viên thực hiện


TĨM TẮT LUẬN VĂN
Trong ngành cơng nghiệp Logistic, container là một phương tiện rất
quan trọng trong vận tải hàng hóa, đặc biệt là vận tải hàng hóa nặng và đi xa.
Vì thế, các hoạt động khai thác ở cảng container và vấn đề quản lý chi phí của
chúng đã và đang là đề tài nóng cho cả nhà quản lý và những người nghiên cứu
khoa học. Trong luận văn này, chúng tơi xem xét bài tốn giảm thiểu chi phí
bốc xếp container cho hoạt động khai thác ở cảng container. Để giải quyết bài
tốn, chúng ta cần tìm ra danh sách các vị trí trong bãi lưu trữ để xếp container
vào đó tại thời điểm thích hợp. Các container trên tàu phải được bốc dỡ từ trên
xuống và được xếp vào bãi lưu trữ một cách hợp lý nhằm tránh phát sinh chi
phí khi xuất bãi dựa trên lịch giao nhận đã có. Trong luận văn này, chúng tơi đề
xuất một giải pháp mới để giảm thiểu chi phí bốc xếp container bằng việc bốc
dỡ các container từ tàu và xếp chúng vào bãi lưu trữ sao cho chi phí bốc xếp
khi nhập và xuất bãi là nhỏ nhất. Theo đó, chúng tơi đã xây dựng mơ hình tốn
học cho bài toán và đề xuất giải thuật tham lam để giải quyết bài toán thực tiễn
trong thời gian hợp lý. Các kết quả tính tốn thực nghiệm đã chứng minh độ
hiệu quả, tính khả thi và tính đúng đắn của giải thuật trong điều kiện thực tế.

In Logistic industry, container is an important instrument in goods
transportation, especially with heavy goods and long-distance transportation.
Therefore, activities in container terminal and how to manage their cost is an
exciting topic even with manager or researcher from long time ago. In this

study, we consider the problem of saving container moving cost in port
container terminals. We need to find right positions in yards to place the
containers at the right times. The containers on vessel must be unloaded one by
one from top to bottom, and placed in the main yard in order to avoid
additional cost required for unnecessary unloading when getting out by
customer with given delivery timetable. A new approach is proposed to reduce
cost of unloading containers in yards: move the containers from vessel and
stack them onto main yard such that the cost of moving is minimal. Then a
mathematical model is developed and a greedy heuristic algorithm is proposed
to solve the problem in reasonable time. Computational experiments have
proved the efficiency, feasibility and correctness of the proposed heuristic
algorithm in realistic conditions.


LỜI CAM ĐOAN
Khoá luận này là kết quả của quá trình học tập, nghiên cứu và thực hiện
trong suốt thời gian qua của tôi. Tôi xin cam đoan mọi kết quả trong bản thuyết
minh luận văn cũng như sản phẩm phần mềm là thành quả có được do sức lao
động của chính tơi, khơng sao chép từ bất kỳ một nguồn tài liệu nào. Những tài
liệu được giới thiệu ở cuối bài luận là nguồn tham khảo chủ yếu trong q trình
thực hiện luận văn.
Nếu có bất kỳ sai phạm nào so với lời cam kết, tôi xin chịu các hình thức
xử lý theo quy định của nhà trường.
Học viên thực hiện


PHẦN LÝ LỊCH TRÍCH NGANG
Họ và tên: Lê Bá Tồn
Ngày, tháng, năm sinh: 20/08/2989
Nơi sinh: Khánh Hòa

Địa chỉ liên lạc: 705 cc 10A Trần Nhật Duật, P.Tân Định, Q.1, Tp.HCM
QUÁ TRÌNH ĐÀO TẠO
- 2007 – 2012: Hệ đại học Khoa KH&KT Máy Tính, trường ĐH Bách
Khoa TPHCM
- 2012 – nay: Hệ cao học Khoa KH&KT Máy Tính, trường ĐH Bách
Khoa TPHCM
Q TRÌNH CƠNG TÁC
- 2011 – 2013: Cơng ty TNHH Secude Việt Nam
- 2013 – nay: Công ty TNHH KMS Việt Nam


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

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: Lê Bá Toàn .....................................................MSHV: 12073132 ...........
Ngày, tháng, năm sinh: 20/08/1989 ...........................................Nơi sinh: Khánh Hòa ......
Chuyên ngành: Khoa Học Máy Tính ......................................... Mã số : 60.48.01 ...........
I. TÊN ĐỀ TÀI: Lập Lịch Bốc Xếp Container Ở Cảng Biển ........................................
.............................................................................................................................................
.............................................................................................................................................
II. NHIỆM VỤ VÀ NỘI DUNG: Tìm hiểu các hoạt động khai thác ở cảng container, xây
dựng mơ hình tốn học cho bài toán, đề xuất giải thuật heuristic để giải quyết bài tốn
thực tiễn, tính tốn thực nghiệm và đánh giá, tổng kết ..................................................
.............................................................................................................................................
.............................................................................................................................................
III. NGÀY GIAO NHIỆM VỤ : (Ghi theo trong QĐ giao đề tài) 18/08/2014 ..............

IV. NGÀY HOÀN THÀNH NHIỆM VỤ: (Ghi theo trong QĐ giao đề tài) 10/05/2015
V. CÁN BỘ HƯỚNG DẪN (Ghi rõ học hàm, học vị, họ, tên): Tiến sĩ Huỳnh Tường
Nguyên .............................................................................................................................
.............................................................................................................................................

Tp. HCM, ngày 15 tháng 06 năm 2015
CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

CHỦ NHIỆM BỘ MÔN ĐÀO TẠO
(Họ tên và chữ ký)

Huỳnh Tường Nguyên

TRƯỞNG KHOA….………
(Họ tên và chữ ký)


Mục lục
1

2

3

4

5

MỞ ĐẦU

1.1 Lý do chọn đề tài . . . . . . . .
1.2 Mục đích nghiên cứu . . . . . .
1.3 Đối tượng và phạm vi nghiên cứu
1.4 Phương pháp nghiên cứu . . . .
1.5 Cấu trúc của luận văn . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

TỔNG QUAN VỀ CÁC CƠNG TRÌNH NGHIÊN CỨU LIÊN QUAN
2.1 Cơng trình "Lập kế hoạch cẩu bãi cho cảng container" của Ng W.C. và Mak K.L.
2.1.1 Bài toán đặt ra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Giải pháp đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3 Tổng kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Cơng trình "Tái điều phối thời gian đến của xe tải nhằm giảm thiểu sự ùn tắc ở
cảng container" của Phan Thị Mai Hà và Kim Kap Hwan . . . . . . . . . . . .
2.2.1 Mơ hình TRM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ĐẶC TẢ BÀI TOÁN
3.1 Giới thiệu . . . . . . .
3.2 Bài toán . . . . . . . .
3.3 Các ràng buộc chính .
3.4 Giải pháp . . . . . . .
3.5 Các trường hợp đặc biệt

1
1
2
2
2
2
4
5

5
5
6
6
7
9

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

11
11
11
13
13
14

MÔ HÌNH TỐN HỌC
4.1 Mơ hình ngun thủy . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Các ràng buộc . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Hàm mục tiêu . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.3 Quy hoạch tuyến tính ngun (MILP) cho mơ hình bài tốn .
4.2 Mơ hình cải tiến . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Nguyên nhân cải tiến . . . . . . . . . . . . . . . . . . . . .
4.2.2 Mơ hình cải tiến . . . . . . . . . . . . . . . . . . . . . . .
4.2.3 Cải tiến các ràng buộc . . . . . . . . . . . . . . . . . . . .
4.2.4 Hàm mục tiêu cải tiến . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.

16
16
16
17
17
20
20
20
21
24

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


.
.
.
.
.

GIẢI THUẬT THAM LAM

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.

.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.

.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.

.

.
.
.
.
.

26
i


6

KẾT QUẢ TÍNH TỐN THỬ NGHIỆM

30

7

KẾT LUẬN

34

Tài liệu tham khảo

35

ii



Chương 1
MỞ ĐẦU
1.1

Lý do chọn đề tài

Những năm gần đây, khái niệm Logistic được nhắc đến khá nhiều như là một mắt xích
quan trọng trong nền kinh tế hiện đại. Logistic được hiểu là quá trình hoạch định, thực hiện và
kiểm sốt sự lưu thơng và lưu trữ một cách hiệu qủa các loại hàng hoá, nguyên vật liệu, thành
phẩm và bán thành phẩm, dịch vụ và thông tin đi kèm từ điểm khởi đầu tới điểm kết thúc theo các
yêu cầu của khách hàng. Trong đó hàng hóa của toàn bộ nền kinh tế toàn cầu phần lớn được vận
tải trong các Container, lưu thông nội địa hoặc xuyên quốc gia, xuyên lục địa. Container ra đời
đã giải quyết triệt để bài tốn vận tải hàng hóa trong thương mại tồn cầu nhờ vào sức chứa khổng
lồ của nó. Từ đó nảy sinh các bài tốn về khai thác container và giảm thiểu chi phí của hoạt động
khai thác, và đây cũng là một hướng nghiên cứu mới để tiếp tục hoàn thiện các hoạt động logistic.
Cảng biển là nơi diễn ra các hoạt động khai thác container sầm uất nhất. Đó là nơi khởi
đầu, là trạm trung chuyển và đồng thời là nơi tập kết của dòng hàng hóa lưu thơng trên tồn cầu.
Trên thế giới, có những cảng nổi tiếng có khả năng tiếp nhận những con tàu lớn với sức chứa
hàng nghìn container, phục vụ hàng chục triệu lượt container mỗi năm. Do đó, phần lớn các bài
toán nghiên cứu về hoạt động khai thác container xảy ra ở các cảng biển. Khai thác container
bao gồm nhiều quy trình, mỗi quy trình phát sinh những chi phí tương ứng địi hỏi nhà quản trị
phải hoạch định và có những giải pháp hợp lý để giảm thiểu các chi phí đó. Đã có nhiều nghiên
cứu trước đây quan tâm đến vấn đề giảm thiểu chi phí bốc xếp, vận chuyển container ở các cảng
biển bằng việc lập lịch hoạt động cho các loại cẩu tàu, cẩu bãi, xe tải trung gian, kho bãi,... Tuy
nhiên, đây vẫn còn là một mảng nghiên cứu lớn cần được tập trung phát triển và hồn thiện hơn
nữa nhằm tối thiểu hóa chi phí khai thác trong ngành cơng nghiệp tỷ đơ này. Trong các quy trình
khai thác container ở cảng biển, thì việc bốc xếp container từ tàu vào bãi lưu trữ và từ bãi xuất
cho khách hàng là một quy trình con chiếm một lượng chi phí đáng kể. Và chi phí này có thể
được tối thiểu nếu ta có một lịch biểu bốc xếp các container từ tàu vào bãi ở thời điểm và vị trí

phù hợp. Đây cũng là hướng nghiên cứu chính của luận văn này với mục tiêu mơ hình hóa và tìm
ra thuật tốn phù hợp để giải bài toán trong thực tế.

1


1.2

Mục đích nghiên cứu

Với mục đích giải quyết vấn đề giảm thiểu chi phí bốc xếp container trong quy trình nhập
container từ tàu, lưu bãi và xuất container giao cho khách hàng, luận văn được xác định với
những mục tiêu sau:
• Tìm hiểu lý thuyết lập lịch cổ điển và phương pháp của các cơng trình liên quan đến bài
tốn bốc xếp container.
• Đưa ra hướng tiếp cận khả thi cho bài toán và nghiên cứu, thiết kế giải thuật dựa trên kinh
nghiệm (heuristic) để tăng hiệu quả trong việc giải quyết bài tốn. Để hồn tất mục tiêu
này, chúng tôi cần giải quyết các vấn đề sau:
– Xác định các trường hợp đặc biệt của bài toán.
– Thiết lập mơ hình tốn học cho bài tốn.
– Dùng solver để tìm lời giải cho bài tốn dựa trên mơ hình toán học đề xuất ở trên.
– Đề xuất giải thuật heuristic để giải bài toán phù hợp với yêu cầu thực tế.

1.3

Đối tượng và phạm vi nghiên cứu

Trong phạm vi của luận văn, chúng tôi tập trung nghiên cứu các cơng trình liên quan đến vấn
đề lập lịch tối ưu chi phí khai thác ở cảng biển và tìm hiểu các quy trình khai thác cảng biển một
cách cụ thể và đầy đủ nhất. Từ đó xác định cụ thể các yếu tố tác động đến loại chi phí này bao

gồm cả yếu tố đầu vào và kết quả đầu ra mong muốn, nhằm giải quyết bài toán tối thiểu chi phí
khai thác container ở cảng biển dựa trên những lý thuyết đã tìm hiểu ở trên.

1.4

Phương pháp nghiên cứu

Về mặt lý thuyết, chúng tơi tìm hiểu những kiến thức nền tảng của lý thuyết lập lịch, kết hợp
với những kết quả nghiên cứu của các cơng trình liên quan trong lĩnh vực tối ưu hóa chi phí khai
thác container ở cảng biển.
Bên cạnh đó, chúng tơi cũng dựa trên những khảo sát về quy trình khai thác cảng biển thực
tế tại Việt Nam và các yêu cầu từ phía cơng nghiệp cho lĩnh vực khai thác này. Sau đó dựa trên
những kết quả này để xác định nhu cầu của bài toán và các ràng buộc cần thiết. Từ đó tiến đến
xây dựng mơ hình bài tốn và đề xuất các giải thuật heuristic phù hợp.
Cuối cùng, chúng tôi sử dụng phương pháp tính tốn và đánh giá Benchmarking để tạo ra
những tập dữ liệu đầu vào ngẫu nhiên và kiểm tra tính đúng đắn của giải thuật heuristic cũng
như đánh giá độ hiệu dụng của giải thuật khi so sánh với kết quả có được từ solver. Song song
với đó, chúng tơi cũng sử dụng bộ dữ liệu thật thu thập từ một số tàu cập cảng Cát Lái trong năm
2014 để làm dữ liệu kiểm tra cho các giải pháp được đề xuất.

1.5

Cấu trúc của luận văn

Phần còn lại của luận văn này được tổ chức theo cấu trúc sau:
2


• Chương 2: Trình bày các cơng trình nghiên cứu liên quan đến bài tốn tối thiểu hóa chi
phí hoạt động trong cảng biển.

• Chương 3: Trình bày đặc tả bài tốn "Tối thiểu hóa chi phí bốc xếp trong hoạt động khai
thác cảng container".
• Chương 4: Trình bày các mơ hình tốn học của bài tốn.
• Chương 5: Trình bày giải thuật tham lam (greedy heuristic) được đề xuất để giải quyết bài
tốn.
• Chương 6: Trình bày các kết quả tính tốn thử nghiệm của việc giải mơ hình bằng Gurobi
Solver và giải thuật tham lam.
• Chương 7: Tổng kết lại những đóng góp của luận văn.
• Cuối cùng là danh mục tài liệu tham khảo.

3


Chương 2
TỔNG QUAN VỀ CÁC CƠNG TRÌNH
NGHIÊN CỨU LIÊN QUAN
Ngày nay, lưu lượng trao đổi hàng hóa giữa các quốc gia, giữa các vùng miền ngày càng tăng
theo nhu cầu phát triển của kinh tế và xã hội. Trong đó, ngành Logictics được biết đến như một
ngành quan trọng trong lĩnh vực hàng hải trên thế giới. Đơn vị lao động trực tiếp trong lĩnh vực
này là các cảng biển được đóng tại khắp nơi dọc theo bờ biển của các nước. Việc ra đời của
container và các cảng biển hiện nay tạo nhiều cơ hội cũng như đặt ra các thách thức cho hệ thống
cảng biển. Trong đó, cạnh tranh về chi phí thực hiện dịch vụ ln là vấn đề được quan tâm hàng
đầu của các cảng biển. Theo đó, các giải thuật tối ưu thời gian làm việc của các thiết bị trong
quy trình khai thác nhằm giảm chi phí nhiên liệu, nhân cơng và chi phí quản lí đã, đang và sẽ
được phát triển ngày một hồn thiện. Trong phần này, chúng tơi sẽ trình bày những hiểu biết của
mình về những cơng trình nghiên cứu liên quan đến quản lý hoạt động của các thiệt bị tham gia
vào quy trình khai thác tại các cảng biển.
Đã có rất nhiều nghiên cứu liên quan đến các hoạt động khai thác cảng container từ nhiều
thập niên trước. Về cơ bản các nghiên cứu liên quan đến giảm thiểu chi phí ở cảng container
có thể được phân loại thành lập lịch cho cẩu bờ (quay crane scheduling: QCS), lập lịch cho cẩu

bãi (yard crane scheduling: YCS), lập lịch cho xe tải (truck scheduling), quản lý cấp phát kho
bãi,... Ví dụ như trong lĩnh vực lập lịch cho cẩu bờ, vào năm 2004 Kim[4] đã xây dựng một mơ
hình quy hoạch nguyên (MIP) trong đó xem xét những ràng buộc khác nhau về hoạt động của
các cẩu bờ, đồng thời tác giả cũng đề xuất một giải thuật heuristic được gọi là thủ tục tìm kiếm
thích ứng ngẫu nhiên tham lam (greedy randomized adaptive search procedure: GRASP) để giải
quyết bài tốn cho các cẩu bờ. Cịn về lĩnh vực lập lịch cho cẩu bãi, đánh dấu cho hướng nghiên
cứu này là giải thuật cuốn chiếu động (dynamic rolling-horizon decision) của Zhang Chuqian[1]
vào năm 2002, đến năm 2009 Lee Der-Horng[5] đã nghiên cứu và đề xuất giải thuật heuristic
cho bài toán lập lịch các xe tải bãi và cấp phát kho bãi ở cảng container. Về khai thác cảng biển
nói chung, Steenken cũng đã có cơng trình tổng hợp khá đầy đủ các nghiên cứu về các bài toán
vận trù ở cảng container và vận trù học trong năm 2004[9] và Stahlbock[8] cũng đã có một cơng
trình cập nhập sau đó vào năm 2008.
Tìm hiểu nhiều nghiên cứu khác nhau trong hoạt động khai thác cảng container, chúng tôi
nhận thấy có hai cơng trình nổi bật là cơng trình của Ng W.C.[6] năm 2003 nhằm lập lịch cho
các cẩu bãi để giảm thiểu thời gian chờ của các cẩu bãi cũng như xe tải bãi và cơng trình của
Phan Thị Mai Hà[7] nhằm lập lịch cho các công ty vận tải để giảm thiểu chi phí chờ của các xe
tải chở hàng đến cảng. Điều đặc biệt là khoảng trống giữa hai cơng trình này mở ra một bài tốn
4


thú việc cho luận văn, và một khi được giải quyết, đó sẽ là một sự kết nối hiệu quả cho hoạt động
khai thác ở cảng container xuyên suốt từ lúc tàu cập cảng cho đến khi hàng hóa được nhận bởi
khách hàng và ngược lại. Hai cơng trình này sẽ được trình bày chi tiết hơn trong phần dưới đây.

2.1
2.1.1

Cơng trình "Lập kế hoạch cẩu bãi cho cảng container"
của Ng W.C. và Mak K.L.
Bài toán đặt ra


Cần cẩu bãi là những thiết bị xếp dỡ container phổ biến nhất để bốc dỡ container lên hoặc
xuống xe tải trong bãi container với diện tích đất có hạn của cảng. Tuy nhiên , thiết bị này rất
cồng kềnh và thường xuyên gây ra tình trạng thắt cổ chai trong luồng di chuyển các container do
thao tác chậm chạp của nó. Do đó, nảy sinh nhu cầu cấp thiết để phát triển một lịch làm việc tốt
nhất cho các cần cẩu bãi này nhằm nâng cao năng suất thông bãi. Tác giả nghiên cứu vấn đề lập
kế hoạch cho một cẩu bãi để thực hiện một tập hợp các theo tác nâng/hạ container với thời gian
sẵn sàng khác nhau. Mục tiêu là để giảm thiểu tổng số thời gian đợi giữa các công việc này.

2.1.2

Giải pháp đề xuất

Tác giả đề xuất giải thuật nhánh và cận (Branch and Bound) để giải quyết vấn đề lập kế
hoạch cho cẩu bãi thỏa mãn yêu cầu giảm thiểu thời gian chờ giữa các công việc.
Mô hình tốn học
Vấn đề lập kế hoạch cho cẩu bãi để xử lý tất cả các công việc với thời gian sẵn sàng khác
nhau trong bãi container được xây dựng bằng mơ hình quy hoạch ngun. Tác giả đặt các biến
như sau:
• ri , i = 1, 2, 3, . . . , n, là thời điểm sẳn sàng của cơng việc thứ i (thời điểm xe tải đến).
• hi , i = 1, 2, 3, . . . , n, là khoảng thời gian được yêu cầu cho cẩu bãi để thực hiện cơng việc
i.
• di j , i = 1, 2, 3, . . . , n và j = 1, 2, 3, . . . , n, là khoảng thời gian mà cẩu bãi di chuyển từ vị trí
cơng việc thứ i sang vị trí cơng việc thứ j, và d0 j là thời gian mà cẩu bãi di chuyển từ vị
trí ban đầu đến vị trí cơng việc thứ j.
• n cơng việc được đánh chỉ số sao cho ri ≤ ri+1
• ti , i = 1, 2, 3, . . . , n, là thời điểm mà cẩu bãi hồn thành cơng việc thứ i.
Biến quyết định của bài tốn:
Xi j =


0 Nếu cơng việc thứ i được thực hiện trước công việc thứ j
1 ngược lại,

∀ti ∈ T, ∀Xi j ∈ X

5

(2.1)


Đối với xe tải được cử đến làm công việc i, thì thời gian chờ là ti − hi − ri . Với ri cho trước,
bài tốn tìm kiếm lịch tối ưu để giảm thiểu tổng thời gian chờ các cơng việc có thể được phát
biểu như sau:
(2.2)
Minimize ∑ (ti − hi − ri )
i→n

sao cho:
ti ≥ ri + hi , i = 1, 2, . . . , n

(2.3)

t j − ti ≥ di j + h j − (1 − Xi j )M, i, j = 1, 2, . . . , n; vài = j

(2.4)

Xi j + X ji = 1, i, j = 1, 2, . . . , n; vài = j

(2.5)


Xi j ∈ {0; 1}, i, j = 1, 2, . . . , n; vài = j

(2.6)

Mục tiêu của việc vập kế hoạch cho cẩu bãi (YCS) là để giảm thiểu số thời gian chờ các công
việc. Ràng buộc 4.1 là mối quan hệ giữa thời gian hoàn thành, thời gian sẵn sàng và thời gian xử
lý một công việc. Ràng buộc 4.2 là mối quan hệ giữa thời gian hoàn thành của 2 công việc kế
tiếp nhau. Ràng buộc 4.3 đảm bảo tính chính xác của các mối quan hệ ưu tiên xác định bởi X.
Ràng buộc 4.4 là ràng buộc nhị phân cho Xi j .
Giải thuật nhánh và cận
Cùng với việc xây dựng mơ hình tốn học cho bài tốn, các tác giả cũng đã đề xuất giải thuật
nhánh và cận để giải quyết bài toán một cách hiệu quả trong thực tế. Trong đó, cận dưới và cận
trên được tính tốn bởi các giải thuật kinh nghiệm và được chứng minh tính đúng đắn bằng các
Định Lý đặt ra.

2.1.3

Tổng kết

Hiệu quả của thuật toán được đánh giá bởi một tập kiểm tra được tạo ra ngẫu nhiên dựa trên
dữ liệu thực tế. Trong đó các thơng tin về kích thước mẫu và thời gian tính tốn tương ứng được
ghi lại để làm dữ liệu đánh giá độ hiểu quả của giải thuật. Kết quả cho thấy rằng thuật toán có
thể tìm thấy các trình tự tối ưu cho bài toán đặt ra với hầu hết các tập dữ liệu kiểm tra.
Nghiên cứu của tác giả tập trung vào việc giảm thiểu thời gian chờ của các cẩu bãi mà trong
đó, danh sách các thao tác di chuyển container từ vị trí này đến vị trí khác, từ tàu lên bãi hoặc
từ bãi xuất cho khách hàng là những dữ liệu biết trước. Từ đây đặt ra nhu cầu về việc xây dựng
danh sách thao tác đó một cách hiệu quả nhất, điều này cũng chính là bài tốn mà luận văn này
hướng đến. Qua đó, chúng tơi mong muốn rằng kết quả của luận văn sẽ giúp tạo ra dữ liệu quan
trọng cho nghiên cứu của cơng trình trên.


2.2

Cơng trình "Tái điều phối thời gian đến của xe tải nhằm
giảm thiểu sự ùn tắc ở cảng container" của Phan Thị Mai
Hà và Kim Kap Hwan

Tác giải dựa trên hai nghiên cứu của Giuliano[2] và Guan[3] năm 2009 về việc sử dụng hệ
thống hẹn lịch xe tải đến cảng (truck arrival system) để giảm thiểu ùn tắc tại cửa ngõ các cảng
6


biển lớn, đồng thời rút ngắn thời gian chờ của mỗi xe từ đó giảm thiểu các chi phí liên quan.
Thơng qua nghiên cứu này, tác giải muốn xóa tan nghi ngờ của Giuliano khi cho rằng "khơng
có bằng chứng nào cho thấy hệ thống hẹn lịch xe tải đã góp phần làm giảm hàng đợi ở các cửa
ngõ cảng và nhờ đó giảm thiểu khí thải từ những phương tiện vận chuyển dùng dầu diesel này"
trong nghiên cứu của mình hồi năm 2009. Theo đó, các tác giả của cơng trình nghiên cứu này
đã xây dựng một mơ hình toán học tái điều phối xe tải TRM (Truck Redistribution Model) nhằm
tối thiểu hóa chi phí về thời gian của các xe tải đến cảng. Những tính tốn thử nghiệm cũng được
đưa ra trong nghiên cứu nhằm chứng minh cho độ hiệu quả của giải pháp đề xuất so với phương
pháp truyền thống.

Hình 2.1: Hệ thống hẹn lịch xe tải TRM

2.2.1

Mơ hình TRM

Trong cơng trình này, tác giả giả định rằng lịch cập bến của tàu nhận hàng đến cảng là biết
trước, các container xuất cảng phải được vận chuyển bằng xe tải đến cảng trước khi tàu cập bến.
Một nhóm cơng việc được định nghĩa là một tập các công việc giao hàng trong cùng một khoảng

thời gian mong muốn, các cơng việc này có thể giao hàng đến hoặc nhận hàng từ cùng một khu
vực bãi (yard block) và được vận chuyển bởi xe tải của các công ty vận tải. Mỗi nhóm cơng việc
có một khung thời gian đến mong muốn dựa trên lịch giao nhận của các xe tải của cơng ty vận
tải. Bài tốn xem xét đến sự ùn tắc trong bãi, khi mà một cẩu bãi đang bận thì các xe tải phải chờ
trong một hàng đợi của khu vực bãi đó. Thời gian chờ của xe tải phụ thuộc vào độ dài của hàng
đợi đó.
Dựa trên lịch giao nhận của các xe tải, mỗi công ty vân tải được yêu cầu gửi lịch giao hàng
của mình cho cảng với khung thời gian mong muốn. Sau đó, hệ thống hẹn lịch xe tải (truck
appointment system) sẽ ước lượng độ dài của mỗi hàng đợi ở mỗi bãi vào những khoảng thời
gian nhất định (time interval) và đưa ra gợi ý khung thời gian mới cho mỗi cơng việc để tối thiểu
hóa sự xáo trộn trong lịch biểu đồng thời giảm thiểu chi phí đợi của các xe tải.
Dữ liệu đầu vào trong hệ thống hẹn lịch xe tải được ký hiệu như bên dưới.
• i: chỉ số của một nhóm cơng việc;
• j: chỉ số của một bãi;
• k: chỉ số của cơng ty vận tải, k = 1, 2, . . . , n;
• τ: chỉ số của khung thời gian;
7


• t: chỉ số của khoảng thời gian, mỗi khung thời gian có thể có nhiều khoảng thời gian;
• bli : cận dưới sớm nhất có thể của khung thời gian cho nhóm cơng việc thứ i;
• bui : cận trên sớm nhất có thể của khung thời gian cho nhóm cơng việc thứ i;
• di : số cơng việc cần hồn thành cho nhóm cơng việc thứ i;
• skτ : số xe tải sẵn có của cơng ty k trong khung thời gian τ;
• pi : khung thời gian mong muốn nhất mà các container của nhóm cơng việc th i c lu
kho hoc xut kho;
ã à jt : số dịch vụ lớn nhất của bãi j ở khoảng thời gian t;
• σ: số lượng các thời điểm ước lượng trong một khung thời gian hẹn;
• e j : hệ số phương sai của phân phối thời gian phục vụ tại bãi j;
• ai j : số container của cơng việc i có thể được lưu kho vào bãi j;

• w+
i : chi phí (về thời gian) đơn vị của thời gian đến trễ so với khung thời gian mong muốn
của cơng việc i;
• w−
i : chi phí (về thời gian) đơn vị của thời gian đến sớm so với khung thời gian mong muốn
của cơng việc i;
• wy : chi phí (về thời gian) đơn vị cho xe tải chờ tại bãi;
• G(k): tập các nhóm cơng việc cho cơng ty k;
• T (τ): tập các khoảng thời gian trong khung thời gian τ;
Biến quyết định được ký hiệu như sau:
• Xi jτ : số xe tải của nhóm cơng việc i được cử đến bãi j ở khung thời gian τ;
• V jt : số xe tải khởi hành từ bãi j ở khoảng thời gian t;
• W jt : số trung bình các xe tải ở bãi j tại khoảng thời gian t;
• Vi jt : số xe tải của nhóm cơng việc i khởi hành từ bãi j ở khoảng thời gian mơ hình hàng
đợi t;
• Wi jt : số trung bình các xe tải của nhóm cơng việc i tại bãi j ở khoảng thời gian mơ hình
hàng đợi t;
Mục tiêu của mơ hình là tối thiểu hóa chi phí phát sinh khi xe tải của nhóm cơng việc i đến
bãi j ở khung thời gian τ có thể trễ hoặc sớm hơn khung thời gian mong muốn pi . Mục tiêu này
được thể hiện trong công thức sau:
min ∑

∑ ∑(w+i ∑(Xi jτ(τ − pi)+) + w−i ∑(Xi jτ(τ − pi)+) + wy ∑(Wi jt +

k i∈G(k) j

τ

i


τ

8

λi jt −Vi jt
)) (2.7)
2


Các ràng buộc của mơ hình:

∑ ∑(Xi jτ) ≥ di, ∀i
j

(2.8)

τ

∑ ∑(Xi jτ) ≤ skτ, ∀k, ∀τ

(2.9)

i∈G(k) j

∑(Xi jτ) ≤ ai j , ∀i, ∀ j

(2.10)

τ


bli ∑(Xi jτ ) ≤ τ ∑(Xi jτ ) ≤ bui ∑(Xi jτ ), ∀i, ∀τ
j

j

λ jt =

Xi jτ
, ∀ j, ∀τ, ∀t ∈ T (τ)
σ

W j(t+1) = W jt + λ jt −V jt , ∀ j, ∀t
V jt ≤ µ jt

W jt + 1 −

λi jt =

(W jt )2 + 2(e j )2W jt + 1
, ∀ j, ∀t
1 − (e j )2

Xi jτ
, ∀i, ∀ j, ∀τ, ∀t ∈ T (τ)
σ

Wi j(t+1) = Wi jt + λi jt −Vi jt , ∀i, ∀ j, ∀t
Vi jt = V jt

Wi jt + λi jt

, ∀i, ∀ j, ∀t
W jt + λ jt

Xi jτ ,V jt ,W jt ,Vi jt ,Wi jt ≥ 0, ∀i, ∀ j, ∀t, ∀τ,

2.2.2

(2.11)

j

(2.12)
(2.13)

(2.14)
(2.15)
(2.16)
(2.17)
(2.18)

Kết luận

Mơ hình được đề xuất trong nghiên cứu này đã góp phần làm giảm đáng kể chi phí về thời
gian chờ của các cơng ty vận tải và cảng biển. Kết quả thử nghiệm cho thấy, chi phí có thể giảm
thấp nhất là 3%, cao nhất là 38%, tương đương hơn 25 nghìn won.

Hình 2.2: Bảng so sánh giá trị mục tiêu của phương pháp truyền thống và TRM (đơn vị: nghìn
won)
9



Bằng việc quan tâm đến lịch giao nhận của các công ty vận tải và sử dụng hệ thống hẹn lịch
xe tải để điều phối một cách hiệu quả việc xe ra vào cảng, cơng trình nghiên cứu này đã mở ra
một hướng mới cho bài toán lập lịch các hoạt động khai thác trong cảng biển. Từ đó nảy sinh
nhu cầu kết nối các thiết bị hoạt động trong cảng biển nhằm phối hợp nhịp nhàng với nhau dựa
trên các lịch biểu hợp lý để tối ưu hóa nguồn lực và tối thiểu hóa chi phí. Đây vừa là thách thức,
vừa là cơ hội cho các nhà nghiên cứu trong lĩnh vực này. Và đây cũng là bài toán mà chúng tôi
quan tâm trong luận văn này.

10


Chương 3
ĐẶC TẢ BÀI TOÁN
3.1

Giới thiệu

Như đã giới thiệu ở Chương 1, quy trình khai thác ở cảng container gồm một chuỗi các hoạt
động nối tiếp nhau. Hình 3.1 mơ tả các hoạt động diễn ra ở 3 khu vực chính, khu vực mặt đất là
các hoạt động giao nhận hàng hóa bằng xe tải hoặc tàu hỏa, kể cả hoạt động trung chuyển hàng
hóa, khu vực bãi là các hoạt động bốc xếp container ra/vào các bãi, khu vực bờ là nơi tàu cập
bến để giao nhận hàng hóa. Kết nối các khu vực là các xe tải nội bộ làm nhiệm vụ di chuyển
container từ bờ vào bãi, giữa các bãi với nhau và ngược lại.
Các nghiên cứu trước đây tập trung giải quyết các bài toán lập lịch cho hoạt động của từng
loại thiết bị riêng biệt, ví dụ như lập lịch cho cầu cảng, lập lịch cho cẩu bãi, lập lịch cho cẩu bờ,
lập lịch cho xe tải nội bộ hay lập lịch cho xe tải giao nhận hàng hóa. Tuy nhiên, vấn đề đặt ra là
làm sao để có được danh sách các vị trí đặt container trong bãi khi tàu cập bến mà nghiên cứu
của Ng W.C.[6] đã xem như là có sẵn. Thêm vào đó, liệu danh sách này có hiệu quả cho các
hoạt động khai thác về sau như việc xuất container từ bãi cho xe tải của khách hàng. Bên cạnh

đó, nghiên cứu của Phan Thị Mai Hà[7] cũng mang đến một cái nhìn mới cho hoạt động khai
thác container ở cảng biển khi xây dựng hệ thống hẹn lịch xe tải đến cảng giao nhận hàng. Để
lấp đầy khoảng trống giữa những nghiên cứu này, luận văn tập trung khai thác bài toán bốc xếp
container từ tàu vào bãi dựa trên lịch giao nhận của khách hàng. Bài toán sẽ được trình bày cụ
thể hơn ở phần sau.

3.2

Bài tốn

Trong phần này, chúng ta xem xét một bài toán bốc xếp container cụ thể với thơng tin biết
trước về vị trí các container trên tàu cần lưu trữ trong cảng (sau đây gọi là danh sách nhập cảng)
và thời điểm mà các container này rời khỏi bãi lưu trữ xuất cho khách hàng. Ngữ cảnh thực tế
như sau:
• Vị trí các container cần lưu trữ trên cảng được tàu cung cấp trước khi tàu cập cảng. Thời
điểm mà các container này rời khỏi bãi được khách hàng cung cấp trước khi tiến hành
bốc xếp thông qua hệ thống hẹn lịch TAS (Truck Appointment System). Bãi (nơi lưu trữ
container của cảng) phải có sức chứa lớn hơn hoặc bằng số container cần lưu bãi trên tàu
sẽ cập cảng. Các container được dỡ trên tàu theo thứ tự từ trên xuống dưới (container nằm
11


Hình 3.1: Các hoạt động khai thác ở cảng container
trên thì lấy trước). Trong quá trình bốc dỡ container từ tàu, các container có thể được đặt
trực tiếp lên các xe tải trung chuyển đến các bãi hoặc đặt vào bãi tạm bên cạnh khi chưa
thể sắp ngay vào bãi. Chi phí cho một container ở bãi tạm gấp đơi bình thường vì tốn 2 lần
di chuyển của cẩu bờ. Các container được xếp vào bãi lưu trữ từ dưới lên trên (xếp chồng
lên nhau, gọi là các lớp - tier). Các contaner trên bãi được giao cho khách hàng cũng phải
được bốc theo thứ tự từ trên xuống dưới (do xếp chồng lên nhau nên phải lấy container ở
trên trước), nếu container cần giao cho khách hàng được nằm ở vị trí bên dưới một hoặc

nhiều container khác thì các container đó phải được bốc ra vùng tạm để lấy container cần
thiết giao cho khách hàng (gọi là đảo chuyển), chi phí này do cảng chịu.
• Mục tiêu của bài tốn là tìm phương án bốc xếp container từ tàu vào bãi sao cho tổng chi
phí bốc xếp từ tàu và chi phí xuất bãi là nhỏ nhất (hạn chế sử dụng bãi tạm và đảo chuyển).

12


Hình 3.2: Minh họa quy trình bốc xếp container ở cảng biển

3.3

Các ràng buộc chính

Với mục đích tìm phương án bốc xếp container từ tàu lên bãi sao cho tổng chi phí bốc xếp từ
tàu và chi phí xuất bãi là nhỏ nhất, bài tốn được cụ thể như sau:
• Khi bốc cont trên tàu để xếp lên bãi chính phải đảm bảo việc sử dụng bãi tạm là ít nhất có
thể
– Bãi chính phải có sức chứa lớn hơn hoặc bằng số lượng các container cần bốc từ tàu
và được ký hiệu theo chuẩn vùng-dãy-hàng-lớp (tương ứng là block-bay-row-tier).
– Vùng tạm có một lớp duy nhất.
• Thứ tự sắp xếp trên bãi chính phải đảm bảo khi khách hàng vào lấy container theo lịch hẹn
trước thì khơng phải đảo chuyển. Trong đó, ta phải chú ý đến:
– Bãi chính là nơi container được lưu trữ và xuất cho khách hàng. Bãi chính được tổ
chức theo dạng các cột sắp gần nhau trong một khơng gian nhất định (hình hộp chữ
nhật).
– Việc bốc dỡ container ở hai cột khác nhau trong bãi chính là độc lập với nhau. Các
container trong cùng một cột phải được bốc dỡ từ trên xuống dưới.
– Việc đảo chuyển sẽ không xảy ra khi container có lịch xuất bãi trước được đặt phía
trên các container có lịch xuất bãi sau nó (trong cùng một cột).

• Chi phí bốc xếp được xác định dựa trên số lần di chuyển container từ vị trí này sang vị trí
khác (tàu, vùng tạm, bãi chính).

3.4

Giải pháp

Từ đặc tả của bài tốn nêu trên, ta có thể hình dung được giải pháp cho bài tốn giảm thiểu
chi phí bốc xếp ở cảng container được thiếp lập như sau:
• Các container được sắp xếp ở bãi lưu trữ (sau đây gọi là bãi chính) sao cho trong cùng một
cột thì container có lịch giao nhận trước phải được sắp ở trên;
13


• Các container được bốc xếp từ tàu vào bãi chính phải tn theo quy tắc sắp xếp trên;
• Trong q trình bốc dỡ container từ tàu, nếu khơng thể sắp một container nào đó theo quy
tắc trên, thì có thể chuyển container đó vào bãi tạm cạnh cẩu bờ;
• Container ở bãi tạm sau đó được cân nhắc để sắp vào bãi chính tại thời điểm thích hợp mà
khơng vi phạm quy tắc sắp xếp;
Như đã phân tích ở trên, các container trên tàu và bãi chính được tổ chức theo dạng bay-rowtier trong không gian 3 chiều. Việc sắp xếp này cũng có thể được biểu diễn thành những cột độc
lập với nhau trong không gian 2 chiều column-tier với tổng số cột là tích số của số lượng bay và
row tương ứng. Nhờ đó, bài tốn cũng được rút giảm số chiều cần tính tốn.
Trong hình minh họa dưới đây, quy ước lịch giao nhận các container theo thứ tự trước-sau
tương ứng với chỉ số của mỗi container, là phương án bốc xếp contaner từ tàu vào bãi có sử dụng
bãi tạm.

Hình 3.3: Minh họa phương án bốc xếp container từ tàu vào bãi

3.5


Các trường hợp đặc biệt

Một cách lý tưởng, tổng số lần di chuyển các container bằng với tổng số container trong danh
sách nhập cảng, hay nói cách khác các container được di chuyển trực tiếp từ tàu vào bãi chính
mà khơng cần phải thơng qua bãi tạm. Trong trường hợp này, giá trị mục tiêu bằng với tổng số
container cần được bốc. Tuy nhiên, có những trường hợp mà bắt buộc phải sử dụng bãi tạm để
tuân thủ quy tắc sắp xếp các container ở bãi chính. Trong trường hợp đó, giá trị mục tiêu lớn hơn
tổng số container vì phải bao gồm cả chi phí phát sinh cho các container ở bãi tạm. Dưới đây ta
tìm hiểu các trường hợp đặc biệt này.
Gọi h1 , w1 lần lượt là chiều cao và chiều rộng của các cột trên tàu (với w1 là tổng số cột trên
tàu); h2 , w2 lần lượt là chiều cao và chiều rộng của các cột trên bãi chính (với w2 là tổng số cột
trên bãi chính). Ta xét 3 trường hợp sau:
a) h1 < w2
Ở trường hợp này, luôn tồn tại một lời giải sao cho không cần dùng đến bãi tạm mà vẫn có
thể bốc các container vào bãi chính thỏa mãn các ràng buộc của bài toán. Xét một cột bất kỳ
trên tàu, giả sử bất kỳ hai container nào trong cột cũng không thể xếp vào một cột trên bãi
chính vì sự ràng buộc về quy tắc sắp xếp các container trong bãi. Khi đó, vì chiều cao của
mỗi cột trên tàu nhỏ hơn số cột trên bãi nên ta có thể xếp tất cả các container này lần lượt vào
mỗi cột trên bãi chính mà khơng vi phạm ràng buộc của bài tốn.
14


b) h1 = w2
Tượng tự, trường hợp này cũng luôn tồn tại một lời giải sao cho không cần dùng đến bãi tạm
mà vẫn có thể bốc các container vào bãi chính thỏa mãn các ràng buộc của bài tốn.
c) h1 > w2
Với điều kiện này, có thể có những trường hợp mà một hoặc một vài container bắt buộc phải
được chuyển đến bãi tạm để thỏa mãn các ràng buộc của bài tốn.
• Quy luật số 1: số container theo thứ tự tăng dần ở một cột trên tàu lớn hơn chiều rộng
của bãi chính.

Xét từ trên xuống dưới ở mỗi cột trên tàu, nếu tồn tại những container có thứ tự tăng
dần (có thể bị ngắt quãng) sao cho tổng số container đó (tạm gọi là m) lớn hơn chiều
rộng của bãi chính, thì số container phải bốc vào bãi tạm bằng với hiệu số m − w2 .

Hình 3.4: Trường hợp bắt buộc sử dụng bãi tạm
Chứng minh: xét những container theo thứ tự tăng dần này
– Vì thứ tự các container này là tăng dần nên khơng thể bốc 2 container trong đó vào
cùng 1 cột,
– vì m > w2 nên chỉ có tối đa w2 container được bốc vào các cột trên bãi chính,
– như vậy, các container còn lại phải được bốc vào bãi tạm để không vi phạm ràng
buộc sự phụ thuộc về thứ tự các container trong bãi chính.
Trong hình họa trên, container số 8 khơng thể được sắp vào bãi chính vì 3 container
trước đó là 3,4 và 7 có số thứ tự nhỏ hơn 8. Trong trường hợp này, một trong 3 container
3, 4 hoặc 7 phải được sắp vào bãi tạm để dành chỗ cho container số 8 trong bãi chính.
Như vậy, khi giải quyết bài tốn bốc xếp contaner trong cảng biển, phải đồng thời chú ý đến
quy tắc sắp xếp container và các trường hợp đặc biệt nhằm đưa ra lời giải hiệu quả.

15


Chương 4
MƠ HÌNH TỐN HỌC
4.1

Mơ hình ngun thủy

Để đơn giản hóa bài tốn trong bước đầu thực hiện ta có các giả định dưới đây:
• Bỏ qua chi phí đảo chuyển các container trên tàu nhưng không nằm trong danh sách bốc
xếp (container x).
• Kích thước bãi tạm là khơng giới hạn.

• Mỗi container được di chuyển một lần duy nhất, nếu nó được xếp vào bãi tạm thì việc
chuyển container đó vào bãi chính khơng nằm trong phạm vi giải quyết của mơ hình.
• Mỗi container đều phải được gán thứ tự xuất bãi, và thứ tự đó là duy nhất.
Quy ước các ký hiệu dùng trong bài toán như sau:
• I = {1, 2, . . . , n} là tập các container, chỉ số biểu thị cho thứ tự bốc chúng ra khỏi bãi chính
và giao cho khách hàng,
• J = {0, 1, 2, . . . , m} là tập các cột (column), với Y0 là cột biểu thị cho bãi tạm, Y1 đến Ym là
các cột biểu thị trên bãi chính,
• T = {1, . . . ,t ∗ } là tập các thời điểm mà các container được bốc từ tàu vào trong bãi chính
hoặc bãi tạm, với t ∗ = n,
• Di là tập các container nằm trên container i trên tàu, các container trong tập Di phải được
bốc ra khỏi tàu trước khi bốc đến container i, Di có thể rỗng,
• h chiều cao của các cột trên bãi chính, chiều cao này không áp dụng cho bãi tạm.

4.1.1

Các ràng buộc

Theo đặc tả bài toán ở Chương 3, các ràng buộc của bài toán cho việc di chuyển mỗi container
được phát biểu như sau:

16