Tính liên tục
Cho hàm số f xác định trên tập mở X ⊆R n Hàm f được gọi là liên tục tại điểm x 0 ∈ X nếu với mọi > 0, tồn tại δ > 0sao cho |f(x) − f(x 0 )| < với mọi x ∈ X thỏa mãn x − x 0
< δ Nói cách khác, hàm f liên tục tại x 0 ∈ X nếu với mọi dãy {x n } ⊂ X hội tụ đến x 0 , ta có {f (x n )} → f (x 0 ).
Hàm f được gọi là nửa liên tục dưới (t.ư, nửa liên tục trên) tại điểm x 0 ∈ X nếu với mọi > 0, tồn tại δ > 0 sao cho f (x) ≥ f (x 0 ) − (t.u., f(x) ≤ f(x 0 ) + (1.1) với mọi x ∈ X thỏa mãn x − x 0
≤ δ Nói cách khác, hàm f là nửa liên tục dưới (t.ư., nửa liên tục trên) tại x 0 ∈ X nếu với mọi dãy {x n } ⊂ X hội tụ đến x 0 và dãy {f(x n )} ⊂R hội tụ, ta có n→∞ lim f(x n ) ≥ f (x 0 ) (t.u., lim n→∞ f(x n ) ≤ f (x 0 )) (1.2)
Nếu hàm f là nửa liên tục dưới tại điểm x0, thì hàm -f sẽ là nửa liên tục trên tại điểm x0 Nếu hàm f vừa nửa liên tục trên vừa nửa liên tục dưới tại x0, thì hàm này sẽ liên tục tại điểm đó.
Hàm f được xem là liên tục trên tập X nếu nó duy trì tính liên tục tại mọi điểm trong tập này Điều này bao gồm cả trường hợp hàm liên tục dưới và liên tục trên.
Đạo hàm riêng
Cho hàm số f xác định trên tập mở X ⊆R n và x 0 = (x 0 1 , , x 0 n ) T là một điểm thuộc X Khi đó với mỗi số h ∈R đủ nhỏ, điểm
(x 0 1 , , x 0 i−1 , x 0 i + h, x 0 i+1 , , x 0 n ) T cũng nằm trong X Giới hạn h→0 lim f (x 0 1 , , x 0 i−1 , x 0 i + h, x 0 i+1 , , x 0 n ) − f (x 0 1 , , x 0 i−1 , x 0 i , x 0 i+1 , , x 0 n ) h nếu tồn tại, được gọi làđạo hàm riêng củaf theo biến x i tại điểm x 0 , ký hiệu là
Đối với hàm một biến f: R → R, ký hiệu đạo hàm được thay bằng d Đạo hàm riêng f x₀ᵢ(x) của hàm nhiều biến có thể được tính bằng cách lấy đạo hàm theo biến xᵢ, trong khi coi các biến còn lại là hằng số.
Giả sử đạo hàm riêng ∂f(x) ∂x i tồn tại với mọi x ∈ R, thì phép tương ứng x 7→ ∂f(x) ∂x i xác định một hàm ∂x ∂f i: X → R Nếu tại x₀, đạo hàm riêng theo biến x j của hàm ∂x ∂f i tồn tại, ta gọi đó là đạo hàm riêng cấp hai theo các biến x i và x j của hàm f tại x₀, ký hiệu là ∂²f(x₀) / ∂x i ∂x j hoặc f''(x i, x j)(x₀) Tương tự, ta cũng có thể định nghĩa đạo hàm riêng cấp k.
∂x i 1 ∂x i 2 ∂x i k theo các biến x i 1 , x i 2 , , x i k của f tại điểm x 0
Gradient và ma trận Hesse
Cho hàm f xác định trên tập mở X ⊆ R n Giả sử rằng tại x 0 , các đạo hàm riêng của hàm f theo mọi biến tồn tại Khi đó, véc tơ
∂x n T được gọi làgradient của f tạix 0 và ký hiệu là∇f (x 0 ) Nếu các đạo hàm riêng cấp hai theo mọi biến của f tại x 0 đều tồn tại thì ma trận
được gọi là ma trận Hesse của f tại x 0 và ký hiệu là ∇ 2 f(x 0 ).
Tập lồi
Cho hai điểm x 1 và x 2 thuộc R n Tập tất cả các điểm có dạng x = λx 1 + (1 − λ)x 2 = x 2 + λ(x 1 − x 2 ), 0 ≤ λ ≤ 1 (1.3) được gọi là đoạn thẳng nối x 1 và x 2
Tập M ⊆ R n được gọi là tập lồi (convex set) nếu nó chứa trọn đoạn thẳng nối hai điểm bất kì thuộc nó, tức với mọi x 1 , x 2 ∈ M và 0 ≤ λ ≤ 1 ta có λx 1 + (1 − λ)x 2 ∈ M
Hàm lồi
Hàm f được gọi là hàm lồi (convex function) xác định trên tập lồi X ⊆ R n nếu f(λx 1 + (1 − λ)x 2 ) ≤ λf(x 1 ) + (1 − λ)f(x 2 ) (1.4) với bất kì x 1 , x 2 ∈ X và số thực λ ∈ [0, 1].
Hàm f được gọi là hàm lồi chặt (strictly convex function) xác định trên tập lồi X ⊆R n nếu f(λx 1 + (1 − λ)x 2 ) < λf(x 1 ) + (1 − λ)f(x 2 ) (1.5) với bất kì x 1 , x 2 ∈ X và số thực λ ∈ [0, 1].
Miền xác định hữu hiệu của hàm f là domf := {x ∈ X | f (x) < +∞} (1.6)
Epigraph của hàm f là tập epi(f ) := {(x, ξ) ∈ X ×R | ξ ≥ f (x)} ⊂ R n+1 (1.7) Hypograph của hàm f là tập hypo(f ) := {(x, ξ) ∈ X ×R | ξ ≤ f (x)} ⊂ R n+1 (1.8)
Hàm f được gọi là hàm lõm (concave function) (t.ư., hàm lõm chặt (stricty concave function)) nếu −f là hàm lồi (t.ư., hàm lồi chặt)
Hàm lồi là một khái niệm quan trọng trong toán học, đặc biệt khi xét đến các hàm khả vi liên tục hai lần Định lý 1 chỉ ra rằng, với một tập lồi không rỗng X ⊆ R n, hàm f: X → R sẽ được coi là hàm lồi trên X nếu và chỉ nếu ma trận Hesse của hàm này thỏa mãn điều kiện nhất định.
Trong bài viết này, chúng ta xem xét các tính chất của hàm số trong không gian lồi Định lý 2 chỉ ra rằng hàm số f xác định trên tập lồi khác rỗng X ⊆ R n là hàm lồi nếu và chỉ nếu epi(f) là tập lồi Đồng thời, hàm số g xác định trên tập lồi khác rỗng X ⊆ R n là hàm lõm khi và chỉ khi hypo(g) là tập lồi Điều này nhấn mạnh mối liên hệ giữa tính lồi và tính lõm của hàm số với các tập hợp liên quan đến chúng.
Dưới gradient, dưới vi phân
Cho f : R n → R là hàm lồi và x 0 ∈ dom(f) Ta gọi g ∈ R n là dưới gradient (subgradient) của f tại x 0 nếu: f(x) ≥ f(x 0 )+ < g, x − x 0 >, ∀x ∈R n (1.9)
Tập hợp tất cả các dưới gradient của f tại x 0 được gọi là dưới vi phân (sub- derivative) của f tại x 0 , kí hiệu là ∂f(x 0 ):
Trong trường hợp f khả vi tại x 0 thì ∂f(x 0 ) = {∇f (x 0 )}
Ví dụ 1.6.1 Xét hàm f (x) = |x|, x ∈R Với x > 0 thì f(x) = x, do đó f 0 (x) = 1 nên ∂f(x) = {1}
Với x < 0 thì f(x) = −x, do đó f 0 (x) = −1 nên∂f (x) = {−1}
Phương pháp hàm phạt
Xét bài toán min{f(x) | x ∈ D} (1.11) trong đó D là tập compac xác định bởi
Phương pháp hàm phạt là một kỹ thuật tối ưu hóa, trong đó thay vì giải bài toán tối ưu có ràng buộc, ta chuyển sang giải một chuỗi bài toán tối ưu không ràng buộc Cụ thể, bài toán được biểu diễn dưới dạng: min f(x) + αP(x), với x ∈ R^n, trong đó P(x) là hàm phạt và α là tham số điều chỉnh Ý tưởng là dãy nghiệm của các bài toán không ràng buộc này sẽ hội tụ đến nghiệm tối ưu của bài toán tối ưu có ràng buộc ban đầu Các hàm f và g_i (i = 1, 2, , m) đều là các hàm khả vi liên tục, và miền D được xác định bởi điều kiện g_i(x) ≤ 0.
Định lý phạt nêu rõ rằng, với D là một tập lồi đa diện không rỗng, f là hàm lõm hữu hạn trên D và p là hàm lừm khụng õm trên D, thì tồn tại một giá trị a0 ≥ 0 sao cho với mọi a ≥ a0, hai bài toán này có cùng tập nghiệm và cùng giá trị tối ưu.
Mục này trình bày cách tiếp cận phương pháp phạt các biến nhị phân. Hàm phạt được xác định bởi:
Hàm P(x) = X x∈bin(D) x(1 − x) thể hiện các biến nhị phân trong bài toán (1.11), trong đó α là lượng phạt Khi x là phương án chấp nhận được, lượng phạt bằng 0, nhưng nếu không, x sẽ chịu phạt αx(1 − x) Chương 1 đã cung cấp cái nhìn tổng quan về kiến thức cơ bản của toán cao cấp và toán tối ưu, giúp người đọc nắm bắt các nội dung tiếp theo trong đồ án này.
Quy hoạch DC và DCA
Chương này giới thiệu các khái niệm và tính chất cơ bản của quy hoạch DC và DCA (Thuật toán DC).
Hàm DC
Hàm DC là một loại hàm trên tập lồi không rỗng X ⊆ R n, được định nghĩa là hàm f : X → R có thể biểu diễn dưới dạng hiệu của hai hàm lồi g(x) và h(x) trên X Cụ thể, hàm f(x) được xác định bằng công thức f(x) = g(x) − h(x), trong đó g(x) và h(x) đều là các hàm lồi.
The functions g and h are referred to as the convex DC components of f, while the expression g - h is known as a DC representation or DC decomposition of f Here are some examples of DC functions.
Ví dụ 2.1.1 Hàm lồi f bất kì là một hàm DC vì ta có phân tích f = 2f − f Hàm lõm f bất kì là một hàm DC vì ta có phân tích f = (−f ) − (−2f ).
Ví dụ 2.1.2 Hàm toàn phương f (x) = hx, Qxi trong đó Q là ma trận đối xứng là một hàm DC.
Trong bài viết này, chúng ta đặt x = U y, với U = [u 1 , u 2 , , u n ] là ma trận chứa các vector riêng đã chuẩn hóa của ma trận Q Các trị riêng tương ứng với các vector riêng u 1 , u 2 , , u n được ký hiệu là λ 1 , λ 2 , , λ n Kết quả cho thấy rằng U T QU = diag(λ 1 , λ 2 , , λ n ).
Do đó f (x) = f (U y) = hU y, QU yi = hy, U T QU yi =X λ i y 2 i Đặt g(x) = X λ i ≥0 λ i y i 2 , h(x) = −X λ i với y k thuộc ∂h(x k ) Mục tiêu của phương pháp này là tối thiểu hóa hàm lồi này.
Bài toán quy hoạch DC tổng quan được định nghĩa dưới dạng α = inf {f (x) := g(x) − h(x) : x ∈ X}(P dc ), trong đó g và h là các hàm lồi Hàm f này được gọi là hàm DC, trong khi g − h được xem là một biểu diễn DC hoặc phân rã DC của f Các thành phần g và h là những thành phần DC lồi của hàm f.
Lược đồ giải DCA tổng quát
Ta có thể thấy h k (x) = h(x k ) + hx − x k , y k i = h(x k ) + hx, y k i − hx k , y k i Vì tập nghiệm với bài toán min{g(x) − hx, y k i , x ∈ X} Thuật toán DCA tổng quát có thể rút gọn lại như sau:
6: until kx k+1 − x k k 2 ≤ (kx k k 2 + 1) Để hiểu rõ hơn về DCA và phương pháp hàm phạt, ta xét ví dụ dưới đây.
Ví dụ 2.2.1 (Trang 216 trong [5]) Xét bài toán quy hoạch tuyến tính:
Ta có thể dễ dàng tìm ra nghiệm của bài toán (P1) bằng thuật toán nhánh cận là x opt = (0, 0, 1, 1).
Bài toán có hàm mục tiêu f(x) = 5x 1 + x 2 + 9x 3 + 3x 4 Bây giờ, thay vì tối đa f(x), ta sẽ tối thiểu −f (x) và bằng cách thêm hàm phạt p(x) =
X i=1 x i (1 − x i ) vớiàđủ lớn ta cú bài toỏn mới tương đương tập nghiệm với bài toỏn gốc (P1) như sau:
X i=1 x i (1 − x i ) (2.5) v.d.k 4x 1 + 2x 2 + 7x 3 + 3x 4 ≤ 10 (2.6) x i ∈ [0, 1], i = 1, 2, 3, 4 (2.7) Hàm mục tiờu của bài toỏn (P2) làF (x) = −5x 1 −x 2 −9x 3 − 3x 4 + àP4 i=1 x i (1 − x i ) = −(x 2 1 + x 2 2 + x 2 3 + x 2 4 ) + (à − 5)x 1 + (à − 1)x 2 + (à − 9)x 3 + (à − 3)x 4
Sử dụng DCA để giải bài toán (P 2)
Trước hết ta cần tìm các phân rã DC của bài toán (P 2) Để đơn giản ta sẽ chọn
G(x) là hàm tuyến tính nên G(x) là hàm lồi, H(x) là hàm bậc hai với hệ số ứng với x 2 dương nên H(x) là hàm lồi Do đó
Có nhiều phương pháp để khởi tạo x0, và nghiệm tìm được sẽ phụ thuộc vào giá trị khởi tạo này Trong trường hợp cụ thể, giả sử ta khởi tạo x0 = (1, 2, 3, 4) với a = 10 và epsilon = 10^(-4).
VìH(x) là hàm khả vi liên tục nên dưới vi phân của H(x)tại x k bất kì chính là vi phõn của H(x) tại x k Khi đú, y k = ∇H(x) = −à(1 − 2x i ).
Bước 3.1:Tìm x 1 bằng cách giải bài toán tìm min G(x) − hx, y 0 i với các ràng buộc (2.6, 2.7): min −5x 1 − x 2 − 9x 3 − 3x 4 − (10x 1 + 30x 2 + 50x 3 + 70x 4 ) (2.8) v.d.k 4x 1 + 2x 2 + 7x 3 + 3x 4 ≤ 10 (2.9) x i ∈ [0, 1], i = 1, 2, 3, 4 (2.10) ta tìm được nghiệm x 1 = (0, 0, 1, 1).
Bước 4.1: Xét điều kiện dừng kx k+1 − x k k 2 ≤ kx k k 2 + 1 : kx 1 − x 0 k 2 = 18, kx 0 k 2 + 1 = 30 × 10 − 4 + 1 = 1.003,
Vì 18 > 1.003 nên thuật toán tiếp tục.
Bước 3.2:Tìm x 2 bằng cách giải bài toán tìm min G(x) − y 1 với các ràng buộc (2.6, 2.7): min −5x 1 − x 2 − 9x 3 − 3x 4 − (−10x 1 − 10x 2 + 10x 3 + 10x 4 ) (2.11) v.d.k 4x 1 + 2x 2 + 7x 3 + 3x 4 ≤ 10 (2.12) x i ∈ [0, 1], i = 1, 2, 3, 4 (2.13) ta tìm được nghiệm x 2 = (0, 0, 1, 1).
Bước 4.2: Xét điều kiện dừng kx k+1 − x k k 2 ≤ kx k k 2 + 1 : kx 2 − x 1 k 2 = 0, kx 1 k 2 + 1 = 10 − 4 + 1 = 1.0004.
Vì 0 ≤ 1.0004 nên thuật toán dừng.
Như ta đã thấy sau 1 vòng lặp, thuật toán DCA đã tìm được nghiệm x 2 = x opt = (0, 0, 1, 1).
DCA là một thuật toán địa phương, vì vậy nghiệm tìm được không nhất thiết là nghiệm tối ưu Chất lượng kết quả phụ thuộc vào điểm khởi tạo x0 ban đầu và cách chọn các thành phần DCg(x) và h(x).
Thuật toán DC tăng tốc - ADCA
Trong lược đồ giải thuật DC, mỗi vòng lặp yêu cầu tính toán y k ∈ ∂H (x k ) và giải bài toán con để xác định x k+1 Thuật toán DC tăng tốc (Accelerated DCA - ADCA) nhằm tìm một điểm z k tối ưu hơn x k để từ đó xác định x k+1 Cụ thể, z k được tính theo công thức: z k = x k + t k − 1 t k+1 (x k − x k−1), với t k+1 = 1 +.
2 Nếu z k có hàm mục tiêu tốt hơn một trong q vòng lặp gần nhất x k−q , , x k−1 , x k , tức là F z k
Khi áp dụng điều kiện ≤ max t=max(0,k−q), ,k F x t, giá trị z k sẽ được sử dụng để tìm y k thay vì x k, giúp tăng giá trị hàm mục tiêu F và thoát khỏi cực trị địa phương Về lý thuyết, việc chọn giá trị q lớn sẽ nâng cao khả năng sử dụng điểm z k trong ADCA, từ đó tăng tốc quá trình tối ưu Cần lưu ý rằng nếu q = 0, thì F (z k ) sẽ luôn nhỏ hơn hoặc bằng F (x k), khiến ADCA trở thành DCA.
Kết hợp với DCA rút gọn, ADCA được trình bày như dưới đây
5: Nếu F(z k ) ≤ max t=max(0,k−q), ,k F(x t ) thì đặt v k = z k , nếu không đặt v k = x k
Chương này đã trình bày về bài toán quy hoạch DC tổng quát và thuật toán DCA, được khẳng định là một giải pháp hiệu quả cho nhiều bài toán khó Sự gia tăng quan tâm đối với trí tuệ nhân tạo và máy học đã làm cho DCA trở nên phổ biến hơn Chương tiếp theo sẽ đề cập đến ứng dụng của thuật toán DC trong việc giải quyết bài toán định tuyến kho hàng, một vấn đề quan trọng đối với các doanh nghiệp.
Giới thiệu bài toán
Ngày nay, sự quan tâm đến kho chứa và vận chuyển hàng hóa ngày càng tăng nhờ công nghệ thông tin Các doanh nghiệp, đặc biệt là tập đoàn lớn, nhận ra rằng tối ưu hóa chuỗi cung ứng giúp tiết kiệm chi phí, thời gian và tài nguyên Nhiều bài báo đã nghiên cứu các mô hình cụ thể trong phân phối khí gas hóa lỏng bằng tàu thủy và thực phẩm tới siêu thị.
Trong bài toán định tuyến kho hàng (IRP), mục tiêu chính là tối thiểu hóa tổng chi phí, bao gồm chi phí vận chuyển và lưu kho, với yêu cầu phục vụ khách hàng trong một chu kỳ thời gian nhất định bằng các phương tiện có sức chứa giới hạn Các phương tiện này cần bắt đầu và kết thúc tại một kho hàng Gần đây, nhiều mục tiêu mới đã được đề xuất để nâng cao hiệu suất chuỗi cung ứng Một biến thể của IRP là bài toán IRP - LR, trong đó thay vì tối thiểu hóa tổng chi phí, mục tiêu là tối thiểu hóa tỉ lệ logistic, tức là tỷ lệ giữa tổng chi phí vận chuyển và tổng lượng hàng hóa được vận chuyển, phản ánh chi phí trung bình cho mỗi đơn vị hàng Chương này sẽ áp dụng phương pháp DCA vào mô hình IRP - LR đã được đề cập.
Phát biểu bài toán
Cho một chu kì thời gian có H khoảng thời gian, bài toán có thể được định nghĩa trên 1 đồ thị vô hướng G = (N, E) Ta có các kí hiệu sau:
T: Tập hợp các khoảng thời gian, T = 1, 2, , H.
N: Tập hợp các khách hàng và cảng, N = 0, 1, 2, , n trong đó nút 0 biểu diễn kho hàng (hay cảng) ban đầu và các điểm còn lại biểu diễn các khách hàng.
E = {(i, j), i, j ∈ N, i < j} là tập hợp các cạnh trong đồ thị.
A = {(i, j), (j, i) : {i, j} ∈ E} là tập hợp các cung trong đồ thị.
Tại mỗi khoảng thời gian t ∈ T ta có: r 0t đơn vị hàng sẵn sàng để vận chuyển ở kho. r it đơn vị được tiêu thụ ở khách hàng i ∈ N 0
Tại mỗi nút i ∈ N có: h i :Chi phí giữ hàng.
U i: lượng hàng tối đa có thể lưu kho của khách hàng. m: số phương tiện để vận chuyển hàng hóa.
Q: sức chứa của mỗi phương tiện.
Lượng hàng ở khách hàng i vào cuối khoảng thời gian t được ký hiệu là \( I_{it} \) Biến nhị phân \( Z_{it} \) có giá trị 1 nếu nút i được tiếp cận trong khoảng thời gian t Số lượng hàng chuyển đến khách hàng i trong khoảng thời gian t được biểu thị bằng \( Q_{it} \) Số lần cạnh (i, j) được đi qua trong khoảng thời gian t được ký hiệu là \( Y_{t}^{ij} \) Lượng hàng vận chuyển từ i đến j trong khoảng thời gian t được biểu diễn bằng \( L_{t}^{ij} \) Cuối cùng, biến nhị phân \( X_{t}^{ij} \) có giá trị 1 nếu cạnh (i, j) được đi qua trong khoảng thời gian t, ngược lại giá trị là 0.
Bài toán IRP-LR yêu cầu xác định lượng hàng hóa cần vận chuyển đến từng khách hàng i ∈ N 0 trong mỗi khoảng thời gian t ∈ T, đồng thời tìm ra lộ trình tối ưu nhằm giảm thiểu tỷ lệ logistic trong toàn bộ chu kỳ thời gian.
Đảm bảo rằng khách hàng luôn có sẵn hàng hóa là rất quan trọng, vì vậy cần duy trì lượng hàng trong kho để sẵn sàng chuyển đi và đảm bảo các yêu cầu về phương tiện vận chuyển được đáp ứng đầy đủ.
Có 2 chính sách làm đầy:
• Chính sách OU (order up-to level): mỗi lần chuyển hàng phải phải đưa lượng hàng trong kho của khách lên mức tối đa (maximum level - ML)
• Chính sách ML: có thể đưa bao nhiêu hàng cũng được miễn là không vượt quá ML tại kho của khách hàng đấy.
Trong mỗi khoảng thời gian trong chu kì, các công việc sau xảy ra ở kho:
Lượng hàng hóa sẵn sàng để chuyển đi, lượng hàng đã được chuyển và lượng hàng tồn kho đều thay đổi theo thời gian Tương tự, ở mỗi khách hàng, lượng hàng được chuyển đến, lượng hàng tiêu thụ và lượng hàng tồn kho cũng có sự biến động Thứ tự thực hiện các hoạt động này sẽ ảnh hưởng đến công thức toán học được trình bày ở phần sau.
Trong [6], thứ tự của các hoạt động này là "tính toán lượng hàng trong kho
Vận chuyển và tiêu thụ hàng hóa có mối liên hệ chặt chẽ, trong đó lượng hàng tại thời điểm t được xác định bằng tổng lượng hàng tại thời điểm t - 1, cộng với lượng hàng được chuyển tới tại thời điểm t - 1, và trừ đi lượng hàng tiêu thụ tại thời điểm t - 1.
Trong nghiên cứu [7], các tác giả cho rằng việc tính toán lượng hàng trong kho là bước cuối cùng tại cả kho hàng và khách hàng, với chuỗi hành động gồm "vận chuyển - tiêu thụ - tính toán" Cụ thể, lượng hàng tại thời điểm t được xác định bằng lượng hàng tại thời điểm t − 1 cộng với lượng hàng vận chuyển tại thời điểm t, trừ đi lượng hàng tiêu thụ tại thời điểm t Nghiên cứu [8] đưa ra giả thuyết rằng lượng hàng trong kho có thể được tính toán ở cuối khoảng thời gian, nhưng không bao giờ vượt quá mức tối đa (ML) vì nó được tính toán sau khi tiêu thụ Điều này có nghĩa là lượng hàng tại thời điểm t không bao giờ vượt quá ML.
Trong đồ án này, tôi sẽ áp dụng giả thiết từ tài liệu [7], cụ thể là "vận chuyển - tiêu thụ - tính toán lượng hàng trong kho" Đặc biệt, lượng hàng tồn kho tại thời điểm t sẽ không bao giờ vượt quá mức tối đa ML.
I it ≥ 0 i ∈ N, t ∈ T, (3.4) q it ≥ U i z it − I it−1 i ∈ N, t ∈ T, (3.5) q it ≤ U i − I it−1 i ∈ N 0 , t ∈ T, (3.6) q it ≤ U i z it i ∈ N 0 , t ∈ T, (3.7)
X j:(j,i)∈A x t ji − X j:(i,j)∈A x t ij = 0 i ∈ N, t ∈ T, (3.11) x t ij + x t ji = y ij t (i, j) ∈ E, t ∈ T, (3.12)
X j:(0,j )∈A x t 0j ≤ m t ∈ T, (3.13) q it ≥ 0 i ∈ N 0 , t ∈ T, (3.14) z it ∈ {0, 1} i ∈ N, t ∈ T, (3.15) y ij t ∈ {0, 1} (i, j) ∈ E, t ∈ T, (3.16) x t ij ∈ {0, 1}, l ij t ≥ 0 (i, j) ∈ A, t ∈ T (3.17)
P t∈T q it là tổng lượng hàng được vận chuyển đến các khách hàng trong tất cả chu kì thời gian, P
P t∈T c ij y ij t là chi phí vận chuyển.
(3.2)-(3.4): các ràng buộc về tính toán lượng hàng như đã quy ước.
(3.5),(3.6),(3.7): các ràng buộc về chính sách làm đầy OU, nếu bỏ (3.5) đi thì chính sách làm đầy trở thành ML.
(3.8),(3.11): ràng buộc tại mỗi nút chỉ có tối đa 1 lần vào và 1 lần ra.
(3.9): ràng buộc bảo toàn luồng.
(3.10): ràng buộc về sức chứa phương tiện.
(3.12): để đảm bảo sự nhất quán giữa x và y.
Bài toán này liên quan đến việc xác định ràng buộc về cận trên của số phương tiện, thuộc loại quy hoạch nguyên hỗn hợp Mục tiêu của bài toán là tối ưu hóa một phân thứ, và nó được xác định là một bài toán NP-khó.
Phân rã DC của bài toán IRP-LR
Ta thêm một số kí hiệu như sau: z(R): Tổng chi phí di chuyển:
X t∈T c ij y ij t (3.18) z(D): Tổng lượng hàng được vận chuyển:
Kết quả của DCA phụ thuộc vào cách lựa chọn các thành phần DCg(x) và h(x), cũng như việc khởi tạo x0 Trong bài viết này, chúng tôi sẽ trình bày cách biến đổi hàm mục tiêu ban đầu thành phân rã DC được áp dụng trong đồ án này.
Bằng cách áp dụng logarit tự nhiên cho hàm mục tiêu, chúng ta có thể chuyển đổi bài toán ban đầu thành một bài toán mới với cùng tập nghiệm Cụ thể, ta có thể tối thiểu hóa biểu thức ln(z(R)) − ln(z(D)), từ đó dẫn đến việc đặt P bin = P.
Thêm hàm phạt P = P x : nhị phân (1 − x)x với trọng số à, chuyển đổi các biến nhị phân (x, y, z) sang các biến trong khoảng [0, 1] tạo ra một bài toán mới có cùng tập nghiệm toàn cục với P gốc Mục tiêu là tối thiểu hóa hàm ln(z(R)) − ln(z(D)) + à(P bin ) Các biến z it, y it k và x t ij đều nằm trong khoảng [0, 1], với điều kiện l t ij ≥ 0 Đặt g(X) = −ln(z(D)), h(X) = −ln(z(R)) + àP bin và f(X) = g(X) − h(X).
Vì −ln(z(D)) là hàm hàm lồi nên g(X) là hàm lồi, −ln(z(R)) là hàm lồi,
Hàm P bin là hàm lõm, do đó, -P bin là hàm lồi Hàm h(X) là tổng của hai hàm lồi, vì vậy h(X) cũng là hàm lồi Do đó, hàm mục tiêu (3.24) có thể được viết lại dưới dạng: f(x) = g(X) - h(X).
Tuy nhiên đây chưa phải là quy hoạch DC cuối cùng, để có được quy hoạch
DC đấy, trước hết ta có định lí: Định lí 4 Tồn tại ρ ≥ 0 sao cho hàm H(X) = 1 ρkXk 2 − f (X)là hàm lồi trên
C (C là tập chấp nhận được của bài toán (P DC1 ).
Cuối cùng ta được bài toán quy hoạch DC như dưới đây: min G(X) − H(X) (3.30) v.d.k X ∈ C (3.31)
Ta có lược đồ tổng quát giải DCA đối với bài toán IRP-LR như sau:
Algorithm 4 Thuật toán DCA IRP-LR
6: Tìm X k+1 bằng cách giải min G(X) − hX, Y k i
Kết quả tính toán
Thuật toán DCA đã được sử dụng trên bộ dữ liệu được sinh ra theo cách [1] đã đề cập, cụ thể như sau:
• Lượng tiêu thụ r it ở khách hàng i trong khoảng thời gian t là hằng số: r it = r i , ∀t ∈ T và là số nguyên được sinh ngẫu nhiên trong đoạn [10, 100];
• Lượng hàng được sẵn sàng chuyển đi ở kho ở thời điểm t bằng P i∈N 0 r i ;
• Lượng hàng tối đa U i ở khách hàng i: r i g i với g i được sinh ngẫu nhiên trong tập {2, 3}.
• Lượng hàng ban đầu ở kho hàng I 00 : P i∈N 0 U i ;
• Lượng hàng ban đầu ở các khách hàng: I i0 = U i − r i;
• Chi phí lưu kho ở i ∈ N 0 :h i được sinh ngẫu nhiên trong đoạn [0.01, 0.05];
• Chi phí ở lưu kho ở kho hàng h 0 : 0.03.
• Tổng tải trọng của từng xe Q = 3 2
• Tọa độ điểm i (X i , Y i ) được sinh ngẫu nhiên trong [0,500];
• Chi phí di chuyển c ij = bp
Chương trình được phát triển bằng Python 3.7 và sử dụng solver CPLEX 12.9 Thiết bị chạy chương trình trang bị chip Intel(R) Core (TM) i5-4210H 2.90GHz với 8GB RAM Thời gian tối đa để giải quyết một bài toán con bằng solver là 30 phút.
The data analysis presents a comparison of various parameters across multiple datasets, highlighting the performance differences in time and percentage differences For instance, data_01 shows a time of 3.3584 seconds for ALG2, with a diff of -0.97524% In contrast, data_06 records a time of 4.3603 seconds, demonstrating a minimal diff of -0.47849% Notably, data_19 and data_20 illustrate significant variations, with times of 3.3247 and 3.3437 seconds, respectively, and percentage differences of -1.63721% and -9.71604% Overall, the results indicate fluctuations in performance metrics across the datasets, emphasizing the need for further investigation into the underlying causes of these discrepancies.
Bảng 3.1: Kết quả tính toán
• |H| là chu kì thời gian.
• ALG2 là kết quả tìm được của bài toán bằng bằng thuật toán 2 trong [1].
• DCA IRP-LR là kết quả tìm được của bài toán bằng thuật toán DCA IRP-LR.
• Time(s) là thời gian giải của thuật toán tương ứng được tính bằng giây.
Diff(%) là tỷ lệ phần trăm chênh lệch giữa nghiệm tìm được từ thuật toán DCA IRP-LR và thuật toán gốc của tác giả Nếu giá trị này âm, điều đó cho thấy thuật toán DCA IRP-LR đã tìm ra nghiệm tốt hơn.
Thuật toán DCA -IRP LR được khởi tạo với x 0 bằng cách giải bài toán min z(R) − t.z (D), với t thường được chọn là 2 Kết quả cho thấy thuật toán DCA IRP-LR vượt trội hơn so với thuật toán gốc của tác giả, đạt hiệu suất tốt hơn tới 9.7% và thời gian giải nhanh hơn đáng kể trên nhiều bộ dữ liệu.
Khi số chiều tăng, thời gian giải quyết cả hai thuật toán đều gia tăng Mặc dù thuật toán DCA IRP-LR vẫn có thể đưa ra kết quả, nhưng chất lượng chưa chắc đảm bảo, trong khi thuật toán gốc không thể hoàn thành trong thời gian quy định cho mỗi bài toán con.
Trong đồ án này, chúng tôi đã giới thiệu các khái niệm và kiến thức cơ bản về toán tối ưu, đồng thời nghiên cứu hàm DC và thuật toán liên quan.
DC, triển khai DCA trên một bài toán định tuyến kho hàng và so sánh kết quả với thuật toán khác.
Trong tương lai, chúng ta có thể nâng cao hiệu quả của thuật toán DC bằng cách xác định điểm xuất phát x0 tốt hơn thông qua các thuật toán heuristic, chẳng hạn như giải thuật di truyền hoặc thuật toán đàn kiến.
Gần đây, các thuật toán học tăng cường đang thu hút sự chú ý lớn từ các nhà khoa học nhằm giải quyết các bài toán tối ưu, đặc biệt là các bài toán IRP Đây có thể là một hướng nghiên cứu quan trọng trong tương lai.
[1] Archetti, Leandro C Coelho, and M Grazia Speranza, “An exact al- gorithm for the inventory routing problem with logistic ratio,” Trans- portation Research Part E: Logistics and Transportation Review, vol 131, pp 96–107, Nov 2019.
In the chapter titled "Transportation Planning and Inventory Management in the LNG Supply Chain," authors Marielle Christiansen Andersson and Kjetil Fagerholt explore the critical aspects of optimizing logistics and inventory within the liquefied natural gas (LNG) sector This work, featured in the book "Energy, Natural Resources and Environmental Economics," edited by Endre Bjørndal and others, highlights the significance of efficient transportation planning and inventory strategies in enhancing the overall performance of the LNG supply chain The findings presented in this research contribute valuable insights to the field of energy systems, emphasizing the need for effective management practices to address the complexities of LNG distribution.
[3] Christiansen, “Decomposition of a Combined Inventory and Time Con- strained Ship Routing Problem,” Transportation Science, vol 33, pp 3–
[4] Mercer and X Tao, “Alternative Inventory and Distribution Policies of a Food Manufacturer,” The Journal of the Operational Research Society, vol 47, no 6, pp 755–765, 1996.
[5] 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 Nhà xuất bản Bách Khoa- Hà Nội.
[6] Archetti, Luca Bertazzi, Gilbert Laporte, and M.Grazia Speranza, “ABranch-and-Cut Algorithm for a Vendor-Managed Inventory-RoutingProblem,” Transportation Science, vol 41, pp 382–391, Aug 2007.
[7] Coelho Leandro C., J.-F Cordeau, and G Laporte, “Consistency in multi- vehicle inventory-routing,” Transportation Research Part C: Emerging Technologies, vol 24, pp 270–287, Oct 2012.
[8] Archetti, Luca Bertazzi, Alain Hertz, and M Grazia Speranza, “A Hy- brid Heuristic for an Inventory Routing Problem,” INFORMS Journal on Computing, vol 24, pp 101–116, Feb 2011.
[9] Archetti, Nicola Bianchessi, Stefan Irnich, and M Grazia Speranza, “For- mulations for an inventory routing problem,” International Transactions in Operational Research, vol 21, no 3, pp 353–374, 2014.
[10] J E Fokkema, M J Land, L C Coelho, H Wortmann, and G B. Huitema, “A continuous-time supply-driven inventory-constrained rout- ing problem,” Omega, vol 92, p 102151, Apr 2020.
[11] H A L Thi, “DC programming and DCA for supply chain and produc- tion management: state-of-the-art models and methods,” International Journal of Production Research, vol 0, pp 1–37, Aug 2019.
[12] H A Le Thi and T Pham Dinh, “DC programming and DCA: thirty years of developments,” Mathematical Programming, vol 169, pp 5–68, May 2018.
In their 2005 paper published in the Annals of Operations Research, L T H An and P D Tao revisit the concept of Difference of Convex (DC) Programming and the DCA (DC Algorithm), applying these methods to real-world non-convex optimization problems Their work provides valuable insights into the effectiveness of DC models in addressing complex optimization challenges.
[14] T P Dinh and H A L Thi, “Convex analysis approach to d.c program- ming: Theory, Algorithm and Applications,” 1997.
[15] D N Phan, H M Le, and H A Le Thi, “Accelerated Difference of Con- vex functions Algorithm and its Application to Sparse Binary Logistic
Regression,” in 27th International Joint Conference on Artificial Intelli- gence, IJCAI 2018, (Stockholm, Sweden), pp 1369–1375, July 2018.
TÓM TẮT LUẬN VĂN THẠC SĨ Đề tài : Thuật toán DCA và ứng dụng trong bài toán định tuyến kho hàng với tỉ lệ logistic
Tác giả luận văn: Nguyễn Chí Thảo Khóa: 2020B
Người hướng dẫn: TS Tạ Anh Sơn
Từ khóa: IRP, Logistic Ratio, DCA, DC Decomposition
Nội dung tóm tắt: a) Lý do chọn đề tài
Ngày nay, sự quan tâm đến kho chứa và vận chuyển hàng hóa đang gia tăng nhờ công nghệ thông tin Các doanh nghiệp, đặc biệt là các tập đoàn lớn, nhận thấy việc tối ưu hóa chuỗi cung ứng giúp tiết kiệm chi phí, thời gian và tài nguyên Trong bối cảnh dịch bệnh hiện tại, đảm bảo chuỗi cung ứng trở nên ngày càng cấp thiết.
Nhiều giải pháp đã được đề xuất để tối ưu hóa chi phí vận hành trong chuỗi cung ứng Mục đích nghiên cứu của luận văn này là phân tích và đánh giá hiệu quả của các giải pháp đó, đồng thời xác định đối tượng và phạm vi nghiên cứu nhằm cung cấp cái nhìn sâu sắc hơn về vấn đề này.
Mục tiêu của luận văn này là nghiên cứu một mô hình tối ưu chi phí cho bài toán IRP-LR, nhằm cung cấp giải pháp hiệu quả cho những người ra quyết định trong lĩnh vực vận chuyển hàng hóa.
Mô hình nghiên cứu tập trung vào bài toán IRP-LR, bao gồm các đối tượng chính như nhà bán lẻ (khách hàng), kho hàng cung cấp hàng hóa và các phương tiện vận chuyển hàng hóa.
Nghiên cứu các tính chất và đối tượng liên quan đến bài toán IRP-LR nhằm kết hợp với thuật toán DC để xây dựng và cải thiện mô hình bài toán Tác giả đã tóm tắt các nội dung chính và nhấn mạnh những đóng góp mới trong nghiên cứu này.
