chương 1, vấn đề thiết kế các mạng chuỗi cung ứng là bài toán khó và đã được rất nhiều nhà khoa học trong và ngoài nước quan tâm. Đã có rất nhiều các mô hình chuỗi cung ứng được đưa ra, tuy nhiên trong việc là này, chúng tôi chỉ quan tâm và tham khảo đến mô hình được trình bày bởi các tác giả trong [1]. Cụ thể, bài toán ở đây là bài toán thiết kế chuỗi cung ứng nhiều giai đoạn với một sản phẩm. Bài toán thiết kế chuỗi cung ứng này là một mô hình bài toán quy hoạch nguyên phi tuyến đa mục tiêu.
Các mục tiêu nhằm làm giảm tối đa tổng chi phí của chuỗi cung ứng, tối đa dịch vụ khách hàng theo thời gian đáp ứng trung bình và tối đa khả năng sử dụng cân bằng giữa các trung tâm phân phối.1 Các giả thiết o Số lượng khách hàng I, nhà cung cấp và những yêu cầu, khả năng lưu trữ được cho trước o Số nhà máy tiềm năng, các trung tâm phân phối và khả năng lưu trữ tối đa được cho trước o Nhiều khách hàng được cung cấp sản phẩm từ một nhà cung cấp Hình 3 dưới đây minh họa một chuỗi cung ứng đơn giản với ba giai đoạn trong mạng chuỗi cung ứng.2 Các ký hiệu và công thức toán - Chỉ số: o i là chỉ số của khách hàng: i I o j là chỉ số của trung tâm phân phối: jJ o k là chỉ số của nhà máy sản xuất: kK 16 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com o s là chỉ số của nhà cung cấp: sS Nhà cung cấp Nhà máy Nhà máy j Trung tâm phân phối Khách hàng s S kK j J iI 1 1 1 1 2. I K Giai đoạn 1 Giai đoạn 2 Giai đoạn 3 Hình 3: Ba giai đoạn trong chuỗi cung ứng - Biến: o bsk là số lượng nguyên liệu thô chuyển từ nhà cung cấp s đến nhà máy k o fkj là số lượng sản phẩm chuyển từ nhà máy k đến trung tâm phân phối j o qji là số lượng sản phẩm chuyển từ trung tâm phân phối j đến khách hàng i 1 khi DC j mo 1 khi nhà máy k mo zj = pk = 0 trái lai 0 trái lai 1 khi DC j phuc vu khách hàng i yji = 0 trái lai - Tham số: o Dk là sức chứa của nhà máy k o Wj là số lượng tiêu thụ hàng năm của trung tâm phân phối j o sups là sức chứa nguyên liệu thô của nhà cung cấp s 17 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com o di là nhu cầu sản phẩm của khách hàng i o W là số lượng trung tâm phân phối tối đa o P là số lượng nhà máy tối đa o Vj là chi phí cố định hàng năm cho hoạt động của trung tâm phân phối j o gk là chi phí cố định hàng năm cho hoạt động của nhà máy k o cji là giá thành vận chuyển một đơn vị sản phẩm từ trung tâm phân phối j tới khách hàng i o akj là giá thành vận chuyển một đơn vị sản phẩm từ nhà máy l tới trung tâm phân phối j o tsk là giá thành vận chuyển và giá mua nguyên liệu thô từ nhà cung cấp s tới nhà máy k o u là tỉ lệ sử dụng nguyên liệu thô trên một đơn vị sản phẩm o hji là thời gian đáp ứng (tính bằng giờ) từ trung tâm phân phối j tới khách hàng i o là thời gian đáp ứng tối đa cho phép (giờ) từ kho đến khách hàng o C(j) là tập các khách hàng nằm trong phạm vi đáp ứng của trung tâm phân phối j trong giờ, hay C(j) = {i | hji } o OD là tập các trung tâm phân phối đang mở o OP là tập các nhà máy đang mở o r1, r2 lần lượt là cân nặng weight của nhà máy và trung tâm phân phối 18 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 3 Mục tiêu o f1 là tổng chi phí của chuỗi cung ứng, bao gồm cả chi phí cố định để hoạt động và mở các nhà máy và trung tâm phân phối, chi phí vận chuyển nguyên liệu thô từ nhà cung cấp đến nhà máy, chi phí vận chuyển sản phẩm từ nhà máy tới khách hàng qua trung tâm phân phối o f2 là tổng nhu cầu của khách hàng (theo %) mà có thể đáp ứng trong điều kiện thời gian o f3 là tính hợp lý của tỉ lệ sử dụng năng lực của nhà máy và trung tâm phân phối và nó được đo bởi sai số bình phương trung bình (MSE: mean square error) của tỉ lệ sử dụng. Giá trị càng nhỏ thì càng gần với tỉ lệ sử dụng khả năng của nhà máy và trung tâm phân phối, vì thế đảm bảo những yêu cầu được phân phối hợp lý qua các trung tâm phân phối và nhà máy đang mở, như thế sẽ tăng tối đa sự thăng bằng trong sử dụng năng lực min f 1 g k pk v j z j tsk bsk akj f kj c ji q ji (1) k j s k k j j i n ( q ji ) jOD iC ( j ) min f 2 (2) di i 1/2 1/2 2 2 jOd fkj fkj i qji qji ( kOP Dk ) ( kOP jOd ) ( jOd Wj ) ( jOd i ) Dk Wj min f 3 r 1 |Op| kOP r 2 |OD| jOd (3) 19 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com y 1, i j ji (4) d y W z , j i i ji j j (5) n z W j j (6) qji diyji, i, j (7) f q , j k kj i ji (8) b sup , s k sk s (9) u f kj bsk , k (10) j s u f kj Dkpk , k (11) j p P k k (12) zj {0,1}, j (13) pk {0,1}, k (14) yji {0,1}, i, j (15) bsk 0, s, k (16) fkj 0, j, k (17) qji 0, i, j (18) 20 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com - Đẳng thức (1), (2), (3) cho biết các mục tiêu.
Trong khi (1) định nghĩa tổng chi phí của chuỗi cung ứng thì (2), (3) lần lượt nêu mục tiêu về dịch vụ khách hàng và tính hợp lý của tỷ lệ sử dụng các khả năng. - Ràng buộc (4) thể hiện tính gán duy nhất giữa một trung tâm phân phối và một khách hàng - (5) là ràng buộc sức chứa của các trung tâm phân phối - (6) giới hạn số trung tâm phân phối được mở - (7) và (8) lần lượt cho biết sự thỏa mãn của khách hàng và sự thỏa mãn của các trung tâm phân phối về các sản phẩm được yêu cầu - (9) mô tả sự hạn chế của việc cung cấp các nguyên liệu thô - (10) thể hiện ràng buộc khả năng của các nhà cung cấp - (11) thể hiện ràng buộc khả năng sản xuất của các nhà máy - (12) giới hạn số nhà máy được mở - (13), (14), (15): áp đặt miền giá trị của các biến quyết định zj, pk, yji - (16), (17), (18): áp đặt không âm đối với các biến quyết định bsk, fkj, qij Vì mục tiêu thứ 3 là không tuyến tính nên mô hình nêu ra ở trên là mô hình chương trình nguyên phi tuyến hỗn tạp. Bài toán tối ưu đa mục tiêu trình bày ở trên thường bao gồm một số giải pháp tối ưu. Chúng là các giải pháp tối ưu đa mục tiêu Pareto [9].
Tập hợp các giải pháp tối ưu Pareto của một bài toán tối ưu đa mục tiêu bao gồm tất cả các vector mục tiêu mà những vector đối tượng phù hợp không thể được cải tiến trong một chiều nhất định mà không ảnh hưởng xấu đến những chiều còn lại [9]. 21 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Với bài toán nhỏ có 2 vector mục tiêu X và Y, lý thuyết tối ưu Pareto có thể được định nghĩa như sau: X chi phối Y (hay X Y) nếu: fi(X) fi(Y) với i {1, 2…m} và fi(X) < fi(Y) với ít nhất một i {1, 2…m} Tất cả các vector mục tiêu mà không chi phối các vector mục tiêu khác trong tập hợp được gọi là vector không bị chi phối trong tập quan tâm. Có một loạt giải pháp tiếp cận để giải quyết bài toán đa mục tiêu. Một trong những công nghệ được sử dụng rộng rãi là tối ưu liên tiếp, phương pháp ràng buộc , phương pháp lấy trọng số, lập trình mục tiêu, đạt được mục tiêu, phương pháp dựa trên khoảng cách và phương pháp dựa trên hướng (direction).
Gần đây, thuật toán GA đã được áp dụng rất tốt để giải quyết những giải pháp tối ưu Pareto cho bài toán tối ưu đa mục tiêu [10-12]. GA xử lý đồng thời một tập các giải pháp khả thi thay vì thực hiện một loạt các công việc riêng rẽ của công nghệ lập trình toán học truyền thống. Đặc điểm này làm tăng tính phổ biến của tối ưu đa mục tiêu. Phần tiếp theo sẽ trình bày chi tiết cách tiếp cận di truyền để thực hiện giải pháp tối ưu Pareto cho bài toán thiết kế chuỗi cung ứng.
22 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 3: THIẾT KẾ CHUỖI CUNG ỨNG BẰNG GIẢI THUẬT DI TRUYỀN 3. Thuật giải di truyền 3. Ý tưởng của thuật toán di truyền Thuật toán di truyền được xây dựng dựa trên quy luật tiến hóa sinh học hay phát triển tự nhiên của một quần thể sống. Các cá thể trải qua một quá trình phát triển và sinh sản để tạo ra những cá thể mới cho thế hệ tiếp theo.
Trong quá trình tăng trưởng và phát triển những cá thể xấu (theo một tiêu chuẩn nào đó hay còn gọi là độ phù hợp của nó trong môi trường) sẽ bị đào thải, ngược lại, những cá thể tốt sẽ được giữ lại (đây chính là quá trình chọn lọc) và được lai ghép (quá trình lai ghép) để tạo ra những cá thể mới cho thế hệ sau.