Kết luận
Bài toán vận tải thông thường chỉ cho phép
chuyển hàng trực tiếp từ các trạm phát (điểm cung
cấp hàng) đến các trạm thu (điểm thu nhận hàng).
Bài toán vận tải thông thường được mở rộng thành
mô hình vận tải có trung chuyển, trong đó hàng hóa
có thể cần phải chuyển qua các điểm trung gian để
lưu giữ hay xử lý, sau đó được chuyển tiếp tới các
trạm thu. Ta có thể xem các điểm trung gian vừa là
điểm nhận hàng (trạm thu), vừa là điểm giao hàng
(trạm phát). Để tìm lời giải tối ưu cho bài toán vận
tải có trung chuyển ta giải một bài toán vận tải thông
thường với (m + p) điểm phát và (n + p) điểm thu,
trong đó m là số điểm cung cấp hàng, n là số điểm
thu nhận hàng và p là số điểm trung chuyển.
Mô hình vận tải có trung chuyển cho phép mở
rộng rất nhiều phạm vi ứng dụng của bài toán vận tải
trong thực tiễn.
6 trang |
Chia sẻ: hachi492 | Ngày: 17/01/2022 | Lượt xem: 347 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Mô hình vận tải có trung chuyển và ứng dụng trong thị trường xuất khẩu gạo của Việt Nam hiện nay, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
SỐ 63 (8-2020)
KHOA HỌC - CÔNG NGHỆ
105
TẠP CHÍ ISSN: 1859-316X
KHOA HỌC CÔNG NGHỆ HÀNG HẢI
JOURNAL OF MARINE SCIENCE AND TECHNOLOGY
MÔ HÌNH VẬN TẢI CÓ TRUNG CHUYỂN VÀ ỨNG DỤNG
TRONG THỊ TRƯỜNG XUẤT KHẨU GẠO CỦA VIỆT NAM HIỆN NAY
THE TRANSSHIPMENT MODEL AND ITS APPLICATIONS IN THE CURRENT RICE
EXPORT MARKET IN VIETNAM
VŨ TUẤN ANH
Khoa Cơ sở - Cơ bản, Trường Đại học Hàng hải Việt Nam
Email liên hệ: anhvt246@vimaru.edu.vn
Tóm tắt
Bài báo này đề cập đến mô hình vận tải có trung
chuyển (mở rộng của bài toán vận tải cổ điển) với
nội dung và ý nghĩa của mô hình, điều kiện tồn tại
nghiệm của mô hình, cách đưa mô hình về bài
toán vận tải dạng bảng và cách xây dựng bảng
vận tải tương ứng cùng thuật toán giải. Cuối bài
báo, tác giả nêu một ứng dụng minh họa của mô
hình trong thị trường xuất khẩu gạo của Việt Nam
hiện nay.
Từ khóa: Bài toán vận tải, mô hình vận tải có
trung chuyển, chi phí vận chuyển, chi phí gửi
hàng vào kho, thuật toán thế vị, phương án tối ưu.
Abstract
This article studies the transshipment model (the
expansion of classic transportation problems).
Specifically, the author presents the model, its
meaning, and its existing conditions. In addition,
the author introduces the way to turn the
transshipment model into a transportation model
and how to create a transportation table as well
as an algorithm for solving the problem. An
example of the model in the rice export market in
Vietnam is also discussed.
Keywords: Transportation problem,
transshipment model, transportation cost,
delivery cost, potential algorithm, optimal
solution.
1. Đặt vấn đề
Bài toán vận tải (Transportation problem) đã khá
quen thuộc trong toán ứng dụng (Chẳng hạn, xem [1],
[2], [3], [5]). Trong bài toán vận tải dạng bảng, có
một loại hàng (ví dụ như gạo, thực phẩm hay rau
quả,) được vận chuyển từ các điểm giao hàng (gọi
là trạm phát) đến các điểm nhận hàng (gọi là trạm
thu). Tuy nhiên, thay cho việc vận chuyển hàng trực
tiếp đến các trạm thu, đôi khi hàng hóa có thể phải
được chuyển qua một trong số các điểm trung gian
(intermediate or trans-shipment points), sau đó hàng
hóa tiếp tục được chuyển tiếp tới các trạm thu. Các
điểm trung gian đó có thể là các trung tâm phân phối
(với hàng bách hóa), các trạm chiếu xạ (với rau quả)
hay các điểm xay sát (với thóc, gạo), Mô hình bài
toán với những mô tả bổ sung này được gọi là mô
hình vận tải có trung chuyển (Transshipment model).
Điều đáng chú ý là bất kỳ mô hình vận tải có
trung chuyển nào cũng có thể dễ dàng biến đổi tương
đương về một bài toán vận tải dạng bảng. Vì thế, để
tìm lời giải cho mô hình vận tải có trung chuyển,
trước hết ta đưa mô hình đó về bài toán vận tải tương
đương và sau đó giải nó bằng cách cải biên phương
pháp đã có (phương pháp thế vị) sẽ thu được lời giải
tối ưu. Nhờ đó góp phần mở rộng hơn nữa phạm vi
ứng dụng của bài toán vận tải trong thực tiễn.
Mô hình vận tải có trung chuyển được tập trung
nghiên cứu rất nhiều trong thời gian gần đây vì
những ứng dụng đa dạng của nó trong nhiều lĩnh vực
(xem minh họa [6], [7], [8]). Trong bài viết này, tác
giả nghiên cứu mô hình vận tải có trung chuyển với
một số kết quả mới: Đưa mô hình về bài toán quy
hoạch tuyến tính, phát biểu và chứng minh điều kiện
cần và đủ để mô hình có nghiệm, đưa ra thuật toán
thế vị cải biên để tìm nghiệm tối ưu của mô hình, áp
dụng thực tế mô hình vào thị trường xuất khẩu gạo
của Việt Nam hiện nay.
2. Mô hình toán học và điều kiện có nghiệm của
mô hình vận tải có trung chuyển
Ta sẽ dùng một số thuật ngữ như sau:
Điểm cung cấp hàng hay trạm phát (supply
point). Đó là điểm có thể gửi hàng tới các điểm khác,
nhưng không được nhận hàng từ bất cứ điểm nào khác.
Điểm thu nhận hàng hay trạm thu (demand
point). Đó là điểm có thể nhận hàng từ các điểm khác,
nhưng không được gửi hàng tới bất cứ điểm nào khác.
Điểm trung gian hay trung chuyển (intermediate or
trans-shipment point). Đó là điểm có thể vừa nhận hàng
từ các điểm khác, vừa gửi hàng tới các điểm khác.
KHOA HỌC - CÔNG NGHỆ
106 SỐ 63 (8-2020)
TẠP CHÍ ISSN: 1859-316X
KHOA HỌC CÔNG NGHỆ HÀNG HẢI
JOURNAL OF MARINE SCIENCE AND TECHNOLOGY
Mô hình vận tải có trung chuyển đặt ra là làm thế
nào để vận chuyển hàng từ các trạm phát tới các
điểm trung chuyển (giai đoạn I) và từ các điểm trung
chuyển tới các trạm thu (giai đoạn II) sao cho tổng
chi phí vận chuyển ở cả hai giai đoạn, cộng với chi
phí gửi hàng ở điểm trung chuyển là nhỏ nhất?
Ta xét các ký hiệu: m là số trạm phát, n là số trạm
thu và p là số điểm trung chuyển.
Trạm phát Ai (i = 1,, m) có khả năng cung cấp
ai đơn vị hàng;
Trạm thu Bj (j = 1, , n) cần nhận bj đơn vị
hàng;
Điểm trung chuyển Dk (k = 1,, p) có thể nhận,
phát tối đa dk đơn vị hàng.
Cho biết: chi phí vận chuyển (transportation
cost) một đơn vị hàng từ trạm phát Ai tới điểm trung
chuyển Dk là 𝑐𝑖𝑘
1 , chi phí vận chuyển một đơn vị hàng
từ điểm trung chuyển Dk tới trạm thu Bj là 𝑐𝑘𝑗
2 và chi
phí lưu giữ hay xử lý (warehousing) một đơn vị hàng
tại điểm trung chuyển Dk là ck.
Biến số: 𝑥𝑖𝑘 là số đơn vị hàng cần vận chuyển
từ trạm phát Ai tới điểm trung chuyển Dk, 𝑦𝑘𝑗 là số
đơn vị hàng cần vận chuyển từ điểm trung chuyển Dk
tới trạm thu Bj.
Mô hình vận tải có trung chuyển được mô tả dưới
dạng bài toán vận tải của quy hoạch tuyến tính, ký
hiệu bài toán (P), có dạng như sau:
𝑓 = ∑ ∑ 𝑐𝑖𝑘
1 𝑥𝑖𝑘
𝑝
𝑘=1
𝑚
𝑖=1 + ∑ ∑ 𝑐𝑘𝑗
2 𝑦𝑘𝑗
𝑛
𝑗=1
𝑝
𝑘=1 +
∑ (𝑐𝑘 ∑ 𝑦𝑘𝑗
𝑛
𝑗=1 )
𝑝
𝑘=1
= ∑ ∑ 𝑐𝑖𝑘
1 𝑥𝑖𝑘
𝑝
𝑘=1
𝑚
𝑖=1 + ∑ ∑ (𝑐𝑘 + 𝑐𝑘𝑗
2 )𝑦𝑘𝑗
𝑛
𝑗=1
𝑝
𝑘=1 (1)
với điều kiện:
∑ 𝑥𝑖𝑘 =
𝑝
𝑘=1 𝑎𝑖 ; 𝑖 = 1, ,𝑚
(2)
∑ 𝑦𝑘𝑗 = 𝑏𝑗
𝑝
𝑘=1 ; 𝑗 = 1, , 𝑛 (3)
∑ 𝑥𝑖𝑘 =
𝑚
𝑖=1 ∑ 𝑦𝑘𝑗 ≤
𝑛
𝑗=1 𝑑𝑘; 𝑘 = 1, , 𝑝 (4)
𝑥𝑖𝑘 ≥ 0, 𝑦𝑘𝑗 ≥ 0; 𝑖 = 1, ,𝑚;
𝑗 = 1, , 𝑛; 𝑘 = 1, , 𝑝. (5)
Hàm mục tiêu (1) gồm chi phí vận chuyển (cả
hai giai đoạn) cộng chi phí gửi hàng ở điểm trung
chuyển.
Ràng buộc (2) biểu thị điều kiện: các trạm phát
Ai giao hết hàng.
Ràng buộc (3) biểu thị điều kiện: các trạm thu Bj
nhận đủ hàng.
Ràng buộc (4) biểu thị điều kiện: số đơn vị hàng
nhận và giao tại điểm trung chuyển Dk là bằng nhau
và không vượt quá khả năng tối đa dk.
Ràng buộc (5) là điều kiện các biến không âm.
Định lý sau đây cho phép ta dễ dàng nhận biết
khi nào mô hình vận tải có trung chuyển có phương
án tối ưu:
Định lý 1: Bài toán vận tải (P) có phương án tối
ưu khi và chỉ khi:
∑ 𝑎𝑖 =
𝑚
𝑖=1 ∑ 𝑏𝑗
𝑛
𝑗=1 và ∑ 𝑎𝑖 ≤ ∑ 𝑑𝑘
𝑝
𝑘=1
𝑚
𝑖=1 ;
∀ 𝑖 = 1, ,𝑚; 𝑗 = 1, , 𝑛; 𝑘 = 1, , 𝑝. (6)
Chứng minh: (⇒) Giả sử bài toán (P) có
phương án tối ưu {𝑥𝑖𝑘 , 𝑦𝑘𝑗}. Khi đó, {𝑥𝑖𝑘 , 𝑦𝑘𝑗} phải
thỏa mãn các ràng buộc (2), (3), (4), (5) tức là:
∑ 𝑥𝑖𝑘 =
𝑝
𝑘=1 𝑎𝑖 , ∑ 𝑦𝑘𝑗 =
𝑝
𝑘=1
𝑏𝑗 , ∑ 𝑥𝑖𝑘 =
𝑚
𝑖=1 ∑ 𝑦𝑘𝑗 ≤
𝑛
𝑗=1 𝑑𝑘 , 𝑥𝑖𝑘 ≥ 0, 𝑦𝑘𝑗 ≥ 0
∀ 𝑖 = 1, ,𝑚; 𝑗 = 1, , 𝑛; 𝑘 = 1, , 𝑝.
Từ đó ta có:
∑ 𝑎𝑖 =
𝑚
𝑖=1 ∑ ∑ 𝑥𝑖𝑘 =
𝑝
𝑘=1
𝑚
𝑖=1 ∑ ∑
𝑥𝑖𝑘
=
𝑝
𝑘=1
𝑚
𝑖=1 ∑ ∑ 𝑦𝑘𝑗 =
𝑛
𝑗=1
𝑝
𝑘=1
∑ 𝑏𝑗
𝑛
𝑗=1
và ∑ ∑ 𝑥𝑖𝑘 = ∑ 𝑎𝑖
𝑝𝑚
𝑖=1
𝑚
𝑖=1 ≤ ∑ 𝑑𝑘
𝑝
𝑘=1
𝑝
𝑘=1 .
(⇐) Giả sử điều kiện (6) thỏa mãn, ta cần chứng
minh bài toán (P) có nghiệm tối ưu.
- Trước hết, ta cần chứng minh luôn tồn tại một
phương án chấp nhận được {�̅�𝑖𝑘 , �̅�𝑘𝑗} của bài toán
(P) thỏa mãn các ràng buộc (2) - (5).
Thật vậy, ta phân phối lượng hàng 𝑎1 của trạm
phát 𝐴1 vào điểm trung chuyển 𝐷1. Khi đó xảy ra
một trong các trường hợp sau:
+ Nếu 𝐴1 phát hết và 𝐷1 thu đủ thì tiếp theo ta
phân phối lượng hàng 𝑎2 của trạm phát 𝐴2 vào điểm
trung chuyển 𝐷2.
+ Nếu 𝐴1 phát hết và 𝐷1 thu thiếu thì tiếp theo ta
phân phối lượng hàng 𝑎2 của trạm phát 𝐴2 vào 𝐷1.
+ Nếu 𝐴1 phát chưa hết và 𝐷1 thu đủ thì tiếp
theo ta phân phối lượng hàng còn lại của 𝐴1vào
điểm trung chuyển 𝐷2.
Tiếp tục quá trình trên, sau hữu hạn lần phân phối
và từ điều kiện ∑ 𝑎𝑖 ≤ ∑ 𝑑𝑘
𝑝
𝑘=1
𝑚
𝑖=1 toàn bộ lượng
hàng của 𝑚 trạm phát đã được chuyển đến 𝑝 điểm
trung chuyển, tức là tồn tại phương án chấp nhận �̅�𝑖𝑘
của giai đoạn vận chuyển thứ nhất.
Trong giai đoạn vận chuyển thứ hai, ta cũng tiến
hành phân phối hàng như trong giai đoạn vận chuyển
thứ nhất. Từ điều kiện (6) đảm bảo toàn bộ lượng hàng
từ 𝑝 điểm trung chuyển được vận chuyển hết đến 𝑛
KHOA HỌC - CÔNG NGHỆ
107 SỐ 63 (8-2020)
TẠP CHÍ ISSN: 1859-316X
KHOA HỌC CÔNG NGHỆ HÀNG HẢI
JOURNAL OF MARINE SCIENCE AND TECHNOLOGY
trạm thu hay tồn tại phương án chấp nhận được �̅�𝑘𝑗.
- Như vậy, tập chấp nhận được của bài toán (P)
khác rỗng. Do các ràng buộc (2), (3) và (5) nên
phương án chấp nhận được bất kì {𝑥𝑖𝑘 , 𝑦𝑘𝑗} luôn
phải có:
0 ≤ 𝑥𝑖𝑘 ≤ 𝑎𝑖 , 0 ≤ 𝑦𝑘𝑗 ≤ 𝑏𝑗 ∀ 𝑖 = 1, ,𝑚; 𝑗 =
1, , 𝑛; 𝑘 = 1, , 𝑝.
Suy ra tập chấp nhận được bị chặn. Theo điều kiện
tồn tại nghiệm của bài toán quy hoạch tuyến tính (xem
[1], tr. 68-71) thì bài toán (P) có phương án tối ưu.
3. Bài toán vận tải dạng bảng tương đương (dạng
bài toán vận tải có ô cấm) và thuật toán giải
Theo [6], nhà toán học Nga V. A. Maš đã đề xuất
đưa (P) về bài toán vận tải cổ điển dạng bảng, tuy
nhiên trước đó ít lâu một ý tưởng tương tự cũng đã
được nhà toán học Mỹ A. Orden nêu ra. Phương
pháp Orden - Maš thiết kế một bảng vận tải thích
hợp (Bảng 1), gồm (m + p) trạm phát và (n + p) trạm
thu (do p điểm trung chuyển vừa là điểm nhận vừa là
điểm gửi hàng).
Trong bảng trên, hàng 0 (trên cùng) và cột 0 (bên
trái) là các hàng, cột tiêu đề; mỗi hàng (từ 1 tới m +
p) đại diện cho một trạm phát, mỗi cột (từ 1 tới p + n)
đại diện cho một trạm thu và mỗi ô (giao của hàng và
cột) của bảng tương ứng với một cặp "phát - thu",
chẳng hạn ô ở hàng 1 cột 1 tương ứng với cặp "phát -
thu" A1 - D1; ô ở hàng m + 1 cột p + 1 tương ứng với
cặp "phát-thu" D1- B1. Trong mỗi ô, góc trên bên trái
ghi cước phí và góc dưới bên phải ghi số đơn vị hàng
cần vận chuyển, ví dụ xmp chỉ số đơn vị hàng sẽ vận
chuyển từ trạm phát Am tới điểm trung chuyển Dp,
xm+1,p + 2 chỉ số đơn vị hàng sẽ vận chuyển từ điểm
trung chuyển D1 tới trạm thu B2.
Chú ý 1: Các ô tô sẫm mầu là các ô không được
phép vận chuyển hàng trực tiếp từ các trạm phát đến
các trạm thu, cũng như giữa các điểm trung chuyển
với nhau, vì thế cước phí đặt bằng số M khá lớn (so
với bất cứ cước phí thực tế nào trong bài toán).
Các biến số xm + k, k (k = 1,,p) trong bảng dùng để
chỉ khả năng (dung lượng) của điểm trung chuyển Dk
không sử dụng hết (còn dư), các ô tương ứng có cước
phí đặt bằng 0.
Bảng 1. Bảng vận tải của bài toán vận tải tương đương
Thu →
Phát ↓
D1 D2 Dp B1 B2 Bn
d1 d2 dp b1 b2 bn
A1 a1
𝑐11
1 𝑐12
1 𝑐1𝑝1 M M M
x11 x12 x1p x1,p+1 x1,p+2
x1,p+n
A2 a2
𝑐21
1 𝑐22
1 𝑐2𝑝1 M M M
x21 x22 x2p x2,p+1 x2,p+2
x2,p+n
Am am
𝑐𝑚1
1 𝑐𝑚2
1 𝑐𝑚𝑝1 M M M
xm1 xm2 xmp xm,p+1 xm,p+2
xm,p+n
D1 d1
0 M M 𝑐112 + 𝑐1 𝑐122 + 𝑐1 𝑐1𝑛2 + 𝑐1
xm+1,1 xm+1,2 xm+1,p
xm+1,p+1
xm+1,p+2
xm+1,p+n
D2 d2
M 0 M 𝑐212 + 𝑐2 𝑐222 + 𝑐2 𝑐2𝑛2 + 𝑐2
xm+2,1 xm+2,2 xm+2,p
xm+2,p+1
xm+2,p+2
xm+2,p+n
Dp dp
M M 0 𝑐𝑝12 + 𝑐𝑝 𝑐𝑝22 + 𝑐𝑝 𝑐𝑝𝑛2 + 𝑐𝑝
xm+p,1 xm+p,2 xm+p,p xm+p,p+1 xm+p,p+2
xm+p,p+n
Nguồn: Tác giả tự lập
KHOA HỌC - CÔNG NGHỆ
108 SỐ 63 (8-2020)
TẠP CHÍ ISSN: 1859-316X
KHOA HỌC CÔNG NGHỆ HÀNG HẢI
JOURNAL OF MARINE SCIENCE AND TECHNOLOGY
Cải biên một trong những thuật toán (hay chương
trình máy tính) đã có, chẳng hạn thuật toán thế vị,
giải bài toán vận tải tương đương ta sẽ nhận được lời
giải tối ưu của bài toán.
Từ đó, tập hợp các giá trị {𝑥𝑖𝑘 , 𝑦𝑘𝑗 =
𝑥𝑚+𝑘,𝑝+𝑗}; 𝑖 = 1, ,𝑚; 𝑗 = 1, , 𝑛; 𝑘 = 1, , 𝑝 . sẽ
cho ta lời giải tối ưu của bài toán vận tải có trung
chuyển (P).
Các thuật toán giải bài toán vận tải cổ điển dạng
bảng đã được trình bày khá đầy đủ trong nhiều giáo
trình, sách tham khảo về tối ưu hóa bằng tiếng Việt ([1]
và [2]), nên ở đây không cần nhắc lại.
Chú ý 2:
- Trong thuật toán thế vị đã biết giải bài toán vận
tải tương đương, phương án cực biên xuất phát được
tìm bằng phương pháp cực tiểu chi phí cải biên với
trình tự như sau:
a) Phân phối hàng ở giai đoạn vận chuyển thứ nhất
(từ các trạm phát tới các điểm trung chuyển).
b) Phân phối hàng ở giai đoạn vận chuyển thứ hai
(từ các điểm trung chuyển tới các điểm thu) tùy vào
lượng hàng thực tế nhận tại các điểm trung chuyển sau
giai đoạn vận chuyển thứ nhất.
- Các ô ghi dung lượng của điểm trung chuyển Dk
không sử dụng hết có thể trở thành ô chọn của
phương án cực biên.
4. Ví dụ minh họa mô hình vận tải có trung
chuyển trong thị trường xuất khẩu gạo của Việt
Nam hiện nay
Theo [4], Việt Nam hiện nay nằm trong nhóm ba
quốc gia xuất khẩu gạo lớn nhất thế giới, trong đó
các tỉnh tại khu vực đồng bằng sông Cửu Long
chiểm 95,17% tổng sản lượng xuất khẩu của cả nước.
Từ các cảng nội thủy tại đồng bằng sông Cửu Long
(Mỹ Thới, Mỹ Tho, Vĩnh Long, Sa Đéc, Hàm
Luông), gạo xuất khẩu được vận chuyển đến các
cảng tập kết (cảng trung chuyển) Sài Gòn và Cần
Thơ. Sau đó, từ hai cảng này gạo được vận tải chủ
yếu đến các các quốc gia nhập khẩu lớn nhất của Việt
Nam: Philippines (cảng Manila), Indonesia (cảng
Jakarta), Nigeria (cảng Lagos) theo đường biển.
Ta xét mô hình vận tải có trung chuyển gạo xuất
khẩu nêu trên với các dữ liệu đầu vào:
- Khối lượng gạo xuất khẩu (đơn vị: nghìn tấn)
tại các cảng phát theo thứ tự: Mỹ Thới, Mỹ Tho,
Vĩnh Long, Sa Đéc, Hàm Luông được cho dưới dạng
véc tơ lượng phát: 𝑎 = (20, 10, 10, 15, 10)𝑇.
- Khối lượng gạo cần nhập (đơn vị: nghìn tấn) tại
các cảng thu Manila, Jakarta, Lagos theo thứ tự dưới
dạng véc tơ lượng thu: 𝑏 = (30, 20, 15)𝑇 .
- Khối lượng gạo tối đa (đơn vị: nghìn tấn) chứa
được và chi phí lưu trữ hàng (đơn vị: USD/tấn) của
các cảng trung chuyển Sài Gòn và Cần Thơ theo thứ
tự được cho trong véc tơ dung lượng: 𝑑 =
(40, 30)𝑇 và ma trận chi phí lưu trữ 𝐶 = (1 2).
- Chi phí vận chuyển 1 tấn gạo (đơn vị: USD/tấn)
giữa các cảng nội địa (cảng phát - cảng trung chuyển),
các cảng quốc tế (cảng trung chuyển - cảng thu) được
cho lần lượt qua hai ma trận chi phí vận chuyển:
𝐶1 =
(
12 11
12 12
11 13
12 11
12 13
)
, 𝐶2 = (
25 26 42
24 26 42
)
Bài toán đặt ra là tìm phương án vận chuyển sao
cho tổng chi phí (vận chuyển + lưu kho) là nhỏ nhất?
Từ các dữ liệu đầu vào của mô hình, ta đưa về bài
toán vận tải dạng bảng tương đương với (m + p) = 7
trạm phát và (p + n) = 5 trạm thu. Ta có bảng vận tải
tương ứng như sau (Bảng 2.).
Bảng 2. Bảng vận tải của Ví dụ minh họa
Thu →
Phát ↓
S. Gòn C. Thơ Manila Jakarta Lagos
40 30 30 20 15
Mỹ Thới 20
12 11 M M M
x11 x12 x13 x14 x15
Mỹ Tho 10
12 12 M M M
x21 x22 x23 x24 x25
Vĩnh
Long
10
11 13 M M M
x31 x32 x33 x34 x35
Sa Đéc 15
12 11 M M M
x41 x42 x43 x44 x45
Hàm
Luông
10
12 13 M M M
x51 x52 x53 x54 x55
Sài Gòn 40
0 M 26 27 43
x61 x62 x63 x64 x65
Cần Thơ 30
M 0 26 28 44
x71 x72 x73 x74 x75
Nguồn: Tác giả tự lập
KHOA HỌC - CÔNG NGHỆ
109 SỐ 63 (8-2020)
TẠP CHÍ ISSN: 1859-316X
KHOA HỌC CÔNG NGHỆ HÀNG HẢI
JOURNAL OF MARINE SCIENCE AND TECHNOLOGY
Dễ dàng kiểm tra bài toán (P) tương ứng thỏa
mãn điều kiện có nghiệm (6), do đó mô hình đặt ra
có lời giải tối ưu.
Dùng thuật toán thế vị cải biên giải bài toán vận
tải với dữ liệu ở Bảng 2, các số liệu tính toán tại các
vòng lặp được ghi tóm tắt theo thứ tự ở các Bảng 3,
4, 5 dưới đây:
Bảng 3. Bảng vận tải của Ví dụ minh họa tại vòng
lặp thứ nhất
Thu →
Phát ↓
Sài
Gòn
Cần
Thơ
Manila Jakarta Lagos
𝑢𝑖
40 30 30 20 15
Mỹ
Thới
20
12 11 M M M
0
0 20 0 0 0
Mỹ Tho 10
12 12 M M M
0
10 0 0 0 0
Vĩnh
Long
10
11 13 M M M
-1
10 0 0 0 0
Sa Đéc 15
12 11 M M M
0
5 10 0 0 0
Hàm
Luông
10
12 13 M M M
0
10 0 0 0 0
Sài Gòn 40
0 M 26 27 43
-12
5 0 30 5 0
Cần
Thơ
30
M 0 26 28 44
-11
0 0 0 15 15
𝑣𝑗 12 11 38 39 55
Nguồn: Tác giả tự lập
Bảng 4. Bảng vận tải của Ví dụ minh họa
tại vòng lặp thứ hai
Thu →
Phát ↓
Sài
Gòn
Cần
Thơ
Manila Jakarta Lagos
𝑢𝑖
40 30 30 20 15
Mỹ
Thới
20
12 11 M M M
0
0 20 0 0 0
Mỹ Tho 10
12 12 M M M
0
10 0 0 0 0
Vĩnh
Long
10
11 13 M M M
-1
10 0 0 0 0
Sa Đéc 15
12 11 M M M
0
5 10 0 0 0
Hàm
Luông
10
12 13 M M M
0
10 0 0 0 0
Sài Gòn 40
0 M 26 27 43
-12
5 0 15 20 0
Cần
Thơ
30
M 0 26 28 44
-12
0 0 15 0 15
𝑣𝑗 12 11 38 39 56
Bảng 5. Bảng vận tải của Ví dụ minh họa tại vòng
lặp thứ ba
Thu →
Phát ↓
Sài
Gòn
Cần
Thơ
Manila Jakarta Lagos
𝑢𝑖
40 30 30 20 15
Mỹ
Thới
20
12 11 M M M
0
0 20 0 0 0
Mỹ Tho 10
12 12 M M M
0
10 0 0 0 0
Vĩnh
Long
10
11 13 M M M
-1
10 0 0 0 0
Sa Đéc 15
12 11 M M M
0
5 10 0 0 0
Hàm
Luông
10
12 13 M M M
0
10 0 0 0 0
Sài Gòn 40
0 M 26 27 43
-12
5 0 0 20 15
Cần
Thơ
30
M 0 26 28 44
-11
0 0 30 0 0
𝑣𝑗 12 11 37 39 55
Nguồn: Tác giả tự lập
Vậy phương án tối ưu cần tìm của mô hình vận
tải có trung chuyển gạo xuất khẩu là:
(𝑥12, 𝑥21, 𝑥31, 𝑥41, 𝑥42, 𝑥51, 𝑥64, 𝑥65, 𝑥73) =
(20, 10, 10, 5, 10, 10, 20, 15, 30) với chi phí tối ưu
𝑓𝑚𝑖𝑛 = 2705000 USD.
Chú ý 3: Trong các bảng tại các vòng lặp, ô in
đậm là ô điều chỉnh, chu trình đi qua ô in đậm và các
ô in nghiêng.
5. Kết luận
Bài toán vận tải thông thường chỉ cho phép
chuyển hàng trực tiếp từ các trạm phát (điểm cung
cấp hàng) đến các trạm thu (điểm thu nhận hàng).
Bài toán vận tải thông thường được mở rộng thành
mô hình vận tải có trung chuyển, trong đó hàng hóa
có thể cần phải chuyển qua các điểm trung gian để
lưu giữ hay xử lý, sau đó được chuyển tiếp tới các
trạm thu. Ta có thể xem các điểm trung gian vừa là
điểm nhận hàng (trạm thu), vừa là điểm giao hàng
(trạm phát). Để tìm lời giải tối ưu cho bài toán vận
tải có trung chuyển ta giải một bài toán vận tải thông
thường với (m + p) điểm phát và (n + p) điểm thu,
trong đó m là số điểm cung cấp hàng, n là số điểm
thu nhận hàng và p là số điểm trung chuyển.
Mô hình vận tải có trung chuyển cho phép mở
rộng rất nhiều phạm vi ứng dụng của bài toán vận tải
trong thực tiễn.
Nguồn: Tác giả tự lập
KHOA HỌC - CÔNG NGHỆ
110 SỐ 63 (8-2020)
TẠP CHÍ ISSN: 1859-316X
KHOA HỌC CÔNG NGHỆ HÀNG HẢI
JOURNAL OF MARINE SCIENCE AND TECHNOLOGY
Lời cảm ơn
Bài báo này là sản phẩm của đề tài nghiên cứu
khoa học cấp Trường năm học 2019-2020: “Nghiên
cứu mô hình vận tải có trung chuyển và áp dụng
trong thị trường xuất khẩu gạo của Việt Nam”,
được hỗ trợ kinh phí bởi Trường Đại học Hàng hải
Việt Nam.
TÀI LIỆU THAM KHẢO
[1] Nguyễn Thị Bạch Kim, Giáo trình các phương
pháp tối ưu: Lý thuyết và Thuật toán, NXB Bách
khoa Hà Nội, 2008.
[2] Trần Vũ Thiệu, Giáo trình tối ưu tuyến tính, NXB
Đại học Quốc gia Hà Nội, 2004.
[3] Trần Vũ Thiệu, Giáo trình tối ưu phi tuyến tính,
NXB Đại học Quốc gia Hà Nội, 2011.
[4] Nguyễn Thị Liên, Tối ưu hóa hệ thống vận tải
gạo xuất khẩu của Việt Nam, Luận án Tiến sĩ
kinh tế, Trường ĐH Hàng hải Việt Nam, 2017.
[5] H. A. Eiselt, C. L. Sandblom, Linear Programming
and its Applications, Springer, 2007.
[6] B. Martina, Transshipment Model in the Function
of Cost Minimization in a Logistics System,
Teaching Assistant, Faculty of Economics in
Osijek, Croatia, 2010.
[7] Y. Chen, I. E. Grossmann, D. C. Miller,
Computational strategies for large-scale MILP
transshipment models for heat exchanger
network synthesis, Computers & Chemical
Engineering, Vol.82, pp.68-83, Elsevier, 2015.
[8] D. Nakandala, H. Lau, P. K. C. Shum, A lateral
transshipment model for perishable inventory
management, International Journal of Production
Research, Vol.55(18), pp.5341-5354, Taylor &
Francis, 2017.
Ngày nhận bài: 23/3/2020
Ngày nhận bản sửa: 10/4/2020
Ngày duyệt đăng: 22/4/2020
Các file đính kèm theo tài liệu này:
- mo_hinh_van_tai_co_trung_chuyen_va_ung_dung_trong_thi_truong.pdf