- Thiết kế mạng chuỗi cung ứng bằng giải thuật di truyền. - Abstract: Trình bày các khái niệm liên quan đến chuỗi cung ứng, các yêu cầu về quản trị chuỗi cung ứng và các cách tiếp cận trước đây đặc biệt là việc sử dụng giải thuật di truyền. - thuật giải di truyền giải bài toán thiết kế chuỗi cung ứng (sự biểu diễn của cá thể, hàm đo độ thích nghi, các toán tử di truyền).. - Chuỗi cung ứng. - Vấn đề về quản trị chuỗi cung ứng chính là một trong những yếu tố nội sinh làm nên sức mạnh trong cạnh tranh cho các doanh nghiệp.. - Đây là một vấn đề không mới bởi ngay từ khi nền kinh tế thế giới bắt đầu có sự cạnh tranh thì việc quản trị tốt chuỗi cung ứng đã được đặt ra như một yêu cầu cấp thiết.. - Trong quản trị chuỗi cung ứng (supply chain management), việc thiết kế mạng chuỗi cung ứng (supply chain networks) còn gọi là thiết kế chuỗi cung ứng là rất quan trọng và nó là bài toán quản trị hoạt động chiến lược. - Thiết kế chuỗi cung ứng cung cấp một nền tảng tối ưu đem lại hiệu quả và thực tế cho việc quản trị chuỗi cung ứng, nó thường bao gồm nhiều mục tiêu và thường mâu thuẫn nhau như là giá, cấp độ dịch vụ và tận dụng tài nguyên.. - Vì vậy, mục tiêu của luận văn này sẽ trình bày giải pháp tối ưu dựa trên thuật toán di truyền (Genetic Algorithms) để tìm ra một tập các giải pháp tối ưu đa mục tiêu cho bài toán thiết kế chuỗi cung ứng. - Chương 1: Trình bày các khái niệm liên quan đến chuỗi cung ứng, các yêu cầu về quản trị chuỗi cung ứng và các cách tiếp cận trước đây đặc biệt là việc sử dụng giải thuật di truyền.. - Chương 1: CHUỖI CUNG ỨNG - SUPPLY CHAIN 1.1 Giới thiệu. - Mạng chuỗi cung ứng là tập hợp của những yếu tố vật chất, khách hàng, các sản phẩm và những phương thức quản lý hàng trong kho, mua bán và phân phối. - Chuỗi cung ứng này liên kết các nhà cung cấp và các khách hàng, bắt đầu từ việc sản xuất các nguyên liệu thô bởi các nhà cung cấp và kết thúc với việc tiêu dùng hàng hóa của khách hàng. - Trong một chuỗi cung ứng, dòng hàng hóa giữa một nhà cung ứng và khách hàng trải qua một vài giai đoạn và mỗi một giai đoạn có thể bao gồm nhiều yếu tố vật chất [1]. - Trong những năm gần đây, bài toán thiết kế mạng chuỗi cung ứng SCN (Supply chain networks) hay chuỗi cung ứng đang ngày càng quan trọng bởi vì tính cạnh tranh gia tăng trong sự toàn cầu hóa thị trường [2]. - Việc thiết kế và quản trị các nhân tố trong chuỗi cung ứng có mối quan hệ chặt chẽ với thành công của chuỗi cung ứng.. - Vấn đề thiết kế mạng chuỗi cung ứng là một trong những vấn đề quyết định mang tính chiến lược toàn diện nhất, những vấn đề cần phải được tối ưu hóa cho việc tổ chức hiệu quả về dài hạn của toàn bộ chuỗi cung ứng. - Thiết kế chuỗi cung ứng chúng ta cần quan tâm đến rất nhiều yếu tố như: lựa chọn đối tác, địa điểm, năng lực của các cơ sở như kho bãi, trung tâm phân phối, sản xuất, sản phẩm, phương thức vận tải, hệ thống thông tin hỗ trợ. - Có những nghiên cứu khác nhau giải quyết vấn đề thiết kế của mạng chuỗi cung ứng và những nghiên cứu được điều tra bởi [3]. - 1.2 Quản trị chuỗi cung ứng. - Để trình bày bài toán quản trị chuỗi cung ứng, ta cần xem xét đến bối cảnh hiện tại làm nảy sinh bài toán. - Vấn đề về quản trị chuỗi cung ứng chính là một trong những yếu tố nội sinh làm nên sức mạnh trong cạnh tranh cho các doanh nghiệp. - Chuỗi cung ứng cần phải đáp ứng được một loạt các ràng buộc như:. - nhà nghiên cứu đặt ra một bài toán về thiết kế chuỗi cung ứng có thể giải quyết tốt những vấn đề trên.. - Một chuỗi cung ứng đặc trưng được mô tả như hình 1, thường có cấu trúc gồm ba thành phần là: phía mua, nội bộ và phía bán. - Hình 1: Cấu trúc của chuỗi cung cấp. - Thông thường, một chuỗi cung ứng có giai đoạn đầu tiên là mua nguyên vật liệu và giai đoạn kết thúc là giao hàng, trong đó phân ra làm ba quá trình:. - Việc tối ưu hóa đa mục tiêu của chuỗi cung ứng được xem xét bởi nhiều nhà nghiên cứu khác nhau đã được đưa ra trong một số tài liệu. - Trong [4], các tác giả đã phát triển một mô hình chuỗi cung ứng đa mục tiêu có tính tương tác trong việc lên kế hoạch xây dựng chiến lược hoạt động chuỗi cung ứng dựa trên những yếu tố thay đổi như sản phẩm, việc giao hàng và nhu cầu.. - Các tác giả trong [6] đã đề xuất một quy trình tối ưu hóa đa mục tiêu dựa trên sự tiến hóa cho những vấn đề phân phối đặt hàng theo nhu cầu được chỉ dẫn bởi chuỗi cung ứng. - Nghiên cứu này phát triển một thủ tục tối ưu hóa di truyền đa mục tiêu, đặc biệt được thiết kế để giải quyết những vấn đề tối ưu hóa trong quản trị chuỗi cung ứng. - Giải thuật được đề xuất thảo luận với vấn đề phân phối theo đơn đặt hàng trong một một chuỗi cung ứng được định hướng theo nhu cầu. - Quá trình phân cấp được dùng ước lượng những giá trị thích hợp những cá thể. - Một mô hình khác là mô hình kế hoạch đa sản phẩm, đa giai đoạn, đa quá trình trong nhiều giai đoạn của mạng chuỗi cung ứng đã được đưa ra trong [7]. - Với mục đích đưa ra một mô hình để đạt được tất cả các giải pháp tối ưu đa mục tiêu cho bài toán thiết kế chuỗi cung ứng và cho phép ra quyết định để đánh giá một số lớn hơn các giải pháp khác, thuật giải di truyền phù hợp để giải quyết vấn đề này.. - Thuật giải di truyền phù hợp với bài toán thiết kế chuỗi cung ứng vì với mỗi một mô hình sẽ là tổ hợp của những lựa chọn mà khi áp dụng hàm mục tiêu vào chúng ta sẽ biết được. - Trong luận văn này, chúng tôi nghiên cứu cách tiếp cận dựa trên thuật toán di truyền cho việc tối ưu hóa đa mục tiêu của chuỗi cung ứng nhằm đạt được ba mục tiêu sau đây:. - Chương 2: THIẾT KẾ CHUỖI CUNG ỨNG. - Như đã trình bày trong 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.. - 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.. - Hình 3: Ba giai đoạn trong chuỗi cung ứng - Biến:. - Chương 3: THIẾT KẾ CHUỖI CUNG ỨNG BẰNG GIẢI THUẬT DI TRUYỀN 3.1. - 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. - Những cá thể mới được sinh ra mang những tính trạng của cá thể cha-mẹ (còn gọi là hiện tượng di truyền). - thể được giữ lại có độ thích nghi khác nhau và quá trình lai ghép được thực hiện hoàn toàn ngẫu nhiên giữa các cá thể trong quần thể. - Các cá thể được tạo ra trong quá trình lai ghép có thể sẽ xảy ra hiện tượng đột biến và tạo ra những cá thể khác với cá thể cha-mẹ. - Cá thể này có thể tốt hơn hoặc xấu hơn cá thể cha-mẹ. - a) Sự diểu diễn của cá thể (encoding mechanism). - Để áp dụng được thuật toán di truyền thì việc đầu tiên là phải tìm được cách biểu diễn của các cá thể sao cho mỗi cá thể biểu diễn một giải pháp của bài toán đang được quan tâm. - Các thuật toán di truyền ban đầu đều sử dụng biểu diễn nhị phân, trong đó một cá thể là một xâu bít 0 và 1. - Độ thích nghi là khả năng phù hợp của mỗi cá thể (giải pháp) đối với môi trường (bài toán). - Để đánh giá được độ thích nghi của các cá thể giải thuật di truyền sử dụng một hàm đo gọi là Fitness Function. - Là quá trình tạo ra cá thể mới dựa trên nhiều cá thể đã có, gọi là các cá thể cha-mẹ. - Hai cá thể con được tạo ra bằng cách hoán đổi các gen từ cá thể cha mẹ.. - o Chọn ngẫu nhiên hai cá thể trong quần thể bằng các phương pháp chọn lọc. - Giả sử cá thể của cha mẹ có m gen.. - Điểm lai chia các chuỗi cá thể cha mẹ ra thành hai nhóm chuỗi con dài m 1 và m 2 . - Hai chuỗi cá thể con mới sẽ là m 11 +m 22 và m 21 +m 12.. - Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến hóa tiếp theo.. - Ví dụ: giả sử ta có 2 cá thể A và B như sau:. - Khi đó hai cá thể con A’ và B’ sẽ có bộ gen được biểu diễn như sau:. - Cá thể con A’. - o Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến hóa tiếp theo.. - Ví dụ: giả sử có hai cá thể A và B được chọn lọc theo một phương pháp chọn lọc.. - Cá thể A. - Hai cá thể con có bộ gen được biểu diễn như sau:. - Xác suất p c này cho ta số cá thể tham gia lai ghép là p c * pop_size (pop_size là kích thước quần thể). - Chọn cặp cá thể từ quần thể hiện tại. - Là quá trình tạo ra cá thể mới từ một cá thể ban đầu bằng cách thay đổi một số gen của nó. - Cá thể đột biến. - Chọn một cá thể trong quần thể.. - Chọn lọc và thay thế (cũng được biết như là reproduction) là quá trình chọn những cá thể từ quần thể hiện tại để tạo ra thế hệ sau của nó. - Trong quá trình này diễn ra sự đào thải những cá thể xấu chỉ giữ lại những cá thể tốt. - Để cho đơn giản chúng ta thường sắp xếp độ thích nghi của các cá thể theo thứ tự giảm dần. - o Tính độ thích nghi của từng cá thể trong quần thể hiện hành, lập bảng cộng dồn các giá trị thích nghi ( theo số thứ tự gán cho cá thể. - Giả sử quần thể có n cá thể. - Gọi độ thích nghi của cá thể thứ i là F i , tổng dồn thứ i là F ti , tổng độ thích nghi của toàn quần thể là F m. - o Chọn cá thể thứ k đầu tiên thỏa mãn F ≥ F tk đưa vào quần thể của thế hệ mới. - Ví dụ, nó sẽ dừng sau một số hữu hạn các thế hệ hoặc tối ưu toàn cục đã đạt được, hoặc giá trị trung bình của độ thích nghi trên tất cả các cá thể của quần thể không thay đổi.... - Tính độ thích nghi cho các cá thể thuộc P(t);. - Thuật giải di truyền giải bài toán thiết kế chuỗi cung ứng 3.2.1 Sự biểu diễn của cá thể. - Sự biểu diễn của cá thể là một trong những vấn đề quan trọng ảnh hưởng tới hiệu năng của các thuật toán di truyền. - Một vấn đề quan trọng trong tối ưu đa mục tiêu là làm thế nào để xác định giá trị phù hợp của cá thể còn tồn tại. - Giá trị phù hợp của mỗi cá thể phản ánh sự đạt được mục tiêu ở mức độ tốt như thế nào. - Hình 5: Minh họa của NST, quá trình vận tải và chi phí vận chuyển cho mỗi giai đoạn trong chuỗi cung ứng.. - Sau khi các trọng số được xác định, giá trị thích hợp của mỗi cá thể trong một quần thể được tính theo công thức (19). - Cách tiếp cận 2: Vì ý tưởng trong cách tiếp cận này là để đạt tới giải pháp tối ưu Pareto sử dụng điểm lý tưởng được tạo ra trong mỗi quá trình tiến hóa, trọng số của mỗi mục tiêu cho một cá thể trong thế hệ hiện tại được xác định sử dụng công thức (22). - Như thấy trong hình 7, toán tử nối đã tận dụng từ một mặt nạ nhị phân, chiều dài của nó bằng số giai đoạn trong chuỗi cung ứng. - Toán tử đột biến quy ước được sử dụng cho phân đoạn cuối cùng của cá thể. - Tập hợp này được cập nhật bằng cách các cá thể mới đạt tới các toán tử di truyền tại mỗi thế hệ. - Sau khi lựa chọn ngẫu nhiên hai cá thể trong tập hợp tối ưu Pareto, phần còn lại của quần thể được lấp đầy bởi. - 2) các cá thể khác biệt tốt nhất được lựa chọn từ vùng tiến hóa. - Nếu không có sẵn các cá thể khác nhau, vùng trống của quần thể sẽ lấp đầy với các cá thể được phát sinh ngẫu nhiên. - o Tổng quan về chuỗi cung ứng bao gồm các khái niệm cơ bản liên quan, quản trị chuỗi cung ứng và các cách tiếp cận để giải bài toán.. - o Thuật giải di truyền đạt được hiệu quả tốt đối với bài toán tối ưu hóa đa mục tiêu trong việc thiết kế chuỗi cung ứng