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

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