Thiết kế mạng chuỗi cung ứng bằng giải thuật di truyền - Lại Thị Nhung

Thiết kế mạng chuỗi cung ứng bằng giải thuật di truyền Lại Thị Nhung Trường Đại học Khoa học Tự nhiên Luận văn Thạc sĩ ngành: Bảo đảm toán học cho máy tính & các hệ thống tính toán Mã số: 60 46 35 Người hướng dẫn: TS. Lê Trọng Vĩnh Năm bảo vệ: 2011 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. Nghiên cứu mô hình toán học của bài toán. Tìm hiểu về giải thuật di truyền và chi tiết việc áp dụng giải thuật di truyền để giải bài toán: thuật giải di truyền (ý tưởng của thuật toán di truyền, các vấn đề cơ bản về thuật toán 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). Keywords: Toán học; Giải thuật di truyền; Chuỗi cung ứng; Thiết kế mạng Content MỞ ĐẦU Toàn cầu hóa là một xu hướng tất yếu kéo theo nó là sự cạnh tranh gay gắt giữa các nhà sản xuất, những tập đoàn và các công ty xuyên quốc gia. Để tồn tại trong bối cảnh này, mục tiêu đầu tiên mà các công ty đều hướng tới là tăng năng suất, giảm chi phí và tạo nên những lợi thế riêng có của mình. Bên cạnh việc khai thác tối đa những lợi thế khách quan từ môi trường bên ngoài thì một yêu cầu quan trọng đối với mỗi một công ty là cải tiến các yếu tố nội sinh liên quan tới quy trình sản xuất của bản thân doanh nghiệp. 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. 2 Theo truyền thống, các giai đoạn (chức năng) tiếp thị, phân phối, lập kế hoạch sản xuất và tổ chức mua bán theo chuỗi cung được tổ chức một cách độc lập. Tuy nhiên, những cách thức tổ chức khác nhau có những mục tiêu riêng và chúng thường mâu thuẫn nhau. Do đó cần phải có một kỹ thuật qua đó các chức năng khác nhau có thể hợp nhất lại với nhau, và đây là bài toán tối ưu hóa đa mục tiêu. 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. Luận văn có bố cục như sau: 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 2: Trình bày mô hình toán học của bài toán. Chương 3: Trình bày về giải thuật di truyền và chi tiết việc áp dụng giải thuật di truyền để giải bài toá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]. Việc sắp xếp năng lực của các thành viên trong chuỗi cung ứng ở phía trên hay phía dưới nhằm mục đích tạo ra giá trị lớn hơn cho người sử dụng, với chi phí thấp hơn cho toàn bộ chuỗi cung ứng. 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]. Các hãng bị buộc phải duy trì các cấp độ dịch vụ cao cho khách hàng trong khi cùng lúc đó họ bị buộc phải cắt giảm chi phí và duy trì lợi nhuận. Theo truyền thống, các giai đoạn (chức năng) tiếp thị, phân phối, lập kế hoạch sản xuất và tổ chức mua bán theo chuỗi cung được tổ chức một cách độc lập. Những cách thức tổ chức này có những mục tiêu riêng và chúng thường mâu thuẫn nhau. Tuy nhiên, cần phải có một kỹ thuật qua đó các chức năng khác nhau có thể hợp nhất lại với nhau. Bài toán thiết kế mạng cung ứng ra đời nhằm giải quyết vấn đề liên kết các khâu trong sản xuất và tổ chức, đưa ra một mạng lưới hoạt động tối ưu liên kết được các chức năng hoạt động của doanh nghiệp với nhau, để từ đó tăng lợi nhuận và giảm chi phí sản xuất. 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. 3 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ợ. Thêm vào đó, chúng ta cũng phải thiết lập các kênh phân phối và số lượng những nguyên liệu và hàng hóa được tiêu dùng, sản xuất và vận chuyển từ nhà cung ứng đến khách hàng. Vấn đề thiết kế mạng chuỗi cung ứng có thể bao quát khoảng rộng các dạng sản phẩm đơn giản, độc lập với những thiết kế phức tạp hơn và từ các mô hình chuỗi cung ứng xác định tuyến tính đến các mô hình chuỗi cung ứng ngẫu nhiên phi tuyến phức tạp phức tạp hơn. 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. Toàn cầu hóa là một xu hướng tất yếu kéo theo nó là sự cạnh tranh gay gắt giữa các nhà sản xuất, những tập đoàn và các công ty xuyên quốc gia. Để tồn tại trong bối cảnh này, mục tiêu đầu tiên mà các công ty đều hướng tới là tăng năng suất, giảm chi phí và tạo nên những lợi thế riêng có của mình. Bên cạnh việc khai thác tối đa những lợi thế khách quan từ môi trường bên ngoài thì một yêu cầu quan trọng đối với mỗi một công ty là cải tiến các yếu tố nội sinh liên quan tới quy trình sản xuất của bản thân doanh nghiệp. 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. Chuỗi cung ứng cần phải đáp ứng được một loạt các ràng buộc như:  Rút ngắn vòng đời sản phẩm  Tốc độ thay đổi về công nghệ  Yêu cầu ngày càng cao của khách hàng và người tiêu dùng  Ranh giới thị trường thay đổi và xuất hiện nhiều kênh phân phối mới  Tiến bộ trong CNTT, thương mại điện tử  Môi trường và các vấn để rủi ro . Những ràng buộc này đặt ra cho những nhà quản trị chuỗi cung ứng những khó khăn trong việc giải quyết tốt vấn đề cung ứng để vừa tăng hiệu quả sản xuất cho bản thân doanh nghiệp vừa cạnh tranh tốt với những đối thủ của mình. Chính những khó khăn này đã buộc các 4 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  Phía mua: tập hợp các nhà cung cấp (suppliers)  Nội bộ: tập hợp các nhà kho (Plants) và các trung tâm phân phối (Distritbution Centers (DCs))  Phía bán: Tập hợp các khách hàng (Customers) Hình 1: Cấu trúc của chuỗi cung cấp Qua sự minh họa trong hình 1 chúng ta thấy rằng, thành phần của một chuỗi cung ứng bao gồm tất cả các giai đoạn liên quan, kể cả trực tiếp hay gián tiếp, trong việc đáp ứng yêu cầu khách hàng, bao gồm các nhà sản xuất, nhà cung ứng, hãng vận tải, kho bãi, người bán lẻ và khách hàng, trong đó nguồn tạo ra doanh thu trong chuỗi cung ứng là khách hàng và nguồn tạo ra chi phí là các luồng thông tin, sản phẩm hoặc tiền giữa các giai đoạn của chuỗi cung ứng 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:  Mua: o Mua nguyên vật liệu o Quản lý tồn kho nguyên vật liệu o Lưu kho nguyên vật liệu 5 o Lưu kho phụ liệu đóng gói  Sản xuất: o Lịch trình sản xuất o Lưu kho sản phẩm dở dang o Đóng gói thành phẩm hoàn thiện  Phân phối: o Vận chuyển từ nơi sản xuất đến kho o Quản lý tồn kho thành phẩm o Lưu kho thành phẩm o Giao hàng tới khách hàng cuối cùng 1.3 Các cách tiếp cận trước đây 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. Trong khi chi phí, tỷ lệ hoàn thành và mức độ linh động được xem xét như là những mục tiêu, phương pháp psilon-cố định được sử dụng như một cách thức giải quyết vấn đề. Phương pháp -cố định là phương pháp tối ưu hóa một trong những hàm mục tiêu sử dụng những hàm mục tiêu còn lại như những ràng buộc. Những giải pháp tối ưu được phát sinh tỏ ra là những giải pháp hiệu quả cho bài toán đa mục tiêu dưới những điều kiện cụ thể. 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. Cách tiếp cận này xem xét việc tối thiểu hóa tổng chi phí của hệ thống, tổng số ngày đưa hàng, số ngày giao hàng và giá trị của tỷ lệ tối ưu hóa cho người sản xuất như là những mục tiêu. 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. Nó kết hợp quá trình phân cấp phân tích với những giải thuật di truyền học. 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ể. Thuật giải được đề xuất cho phép những người ra quyết định có thể xác định trọng lượng cho tiêu chuẩn đang sử dụng. Những kết quả thể hiện bằng các con số thu được từ thuật giải được đề xuất sẽ được so sánh với cái thu được từ cách tiếp cận lập trình số nguyên hỗn tạp đa mục tiêu. Sự so sánh này chỉ ra rằng thuật được đề xuất là đáng tin cậy và linh hoạt. Ngoài ra, nó còn cung cấp nhiều sự kiểm 6 soát và thông tin hơn cho những người ra quyết định để đạt được một sự hiểu thấu tốt hơn hơn về mạng cung ứng 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]. Những nhu cầu thị trường không chắc chắn được lập thành mô hình như là một số kịch bản riêng biệt với những khả năng được biết đến và những tập hợp mờ được sử dụng để mô tả những ý muốn không tương đồng về giá sản phẩm của người bán và người mua. Mô hình chuỗi cung ứng đang được xây dựng lên như một vấn đề lập trình phi tuyến hỗn tạp nguyên để thỏa mãn một vài mục tiêu xung đột như là phân phối lợi nhuận công bằng giữa những người tham gia, những mức lưu kho an toàn, những mức dịch vụ khách hàng tối đa, và sự linh hoạt trong các quyết định có liên quan tới những nhu cầu không chắc chắn về sản phẩm, trong trường hợp này mức độ ưa thích được thỏa hiệp dựa trên giá cả sản phẩm từ quan điểm của người bán và người mua đồng thời được tính đến. Sự linh hoạt của độ đo như là một phần của mục tiêu có thể giảm một cách đáng kể tính biến thiên của những giá trị mục tiêu có liên quan tới những sự không chắc chắn trong nhu cầu về sản phẩm. Với mục đích đạt được giải pháp bù đắp giữa những người tham gia trong chuỗi cung ứng, một phương pháp ra quyết định gồm có hai pha mờ được nêu lên và ứng dụng của nó là gia tăng ảnh hưởng trong việc cung cấp một giải pháp được dàn xếp trong một mạng cung ứng nhiều cấp bậc không chắc chắn. 1.4 Tiếp cận dựa trên giải thuật di truyền Trong thời đại CNTT phát triển như ngày nay thì việc giải quyết các bài toán tối ưu là mối quan tâm hàng đầu của các nhà khoa học trong mọi lĩnh vực đời sống. Các nhà khoa học đã không ngừng nghiên cứu và đưa ra rất nhiều giải pháp cho bài toán tối ưu, đặc biệt là các bài toán tối ưu. Tuy nhiên giải pháp nào cũng tồn tại những khó khăn nhất định và lời giải của bài toán không phải lúc nào cũng đạt được kết quả tối ưu. Thuật toán di truyền (GA-Genetic Algorithm) xuất hiện vào khoảng năm 1975 đã khắc phục được những nhược điểm của các thuật toán trước đó (hội tụ về nghiệm toàn cục). Thuật toán di truyền được coi là công cụ tốt nhất để giải quyết những vấn đề trong tìm kiếm và tối ưu tổ hợp. Ngày nay các thuật toán tiến hóa đã được chứng minh là các công cụ hiệu quả để giải quyết các vấn đề trong lĩnh vực sinh học và kinh tế xã hội. 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 7 mô hình đó là tốt hay xấu, có lợi hay không có lợi để từ đó có những sàng lọc hiệu quả. Ở mỗi bước, ta sẽ kết hợp những mô hình trước đó để sinh ra những mô hình mới, từ đó giữ lại những mô hình cho kết quả tốt khi áp dụng hàm mục tiêu và đào thải những mô hình không phù hợp 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: 1. Giảm tối đa tổng chi phí bao gồm cả những chi phí cố định của kho và các trung tâm phân phối. 2. Nâng tối đa dịch vụ đáp ứng khách hàng, với thuật ngữ là thời gian đáp ứng có thể chấp nhận được (trung bình). 3. Tối đa khả năng sử dụng cân bằng giữa các trung tâm phân phối (tính hợp lý tỉ lệ sử dụng giữa các trung tâm). 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. 2.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.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: jJ o k là chỉ số của nhà máy sản xuất: kK 8 o s là chỉ số của nhà cung cấp: sS 1 s S 1 2 k K 1 j J 2 1 3 I . . . . . . . . . . . . . . . . . . . . . i . . . Nhà cung cấp s  S Giai đoạn 2 Nhà máy j Giai đoạn 1 Giai đoạn 3 Nhà máy k  K Trung tâm phân phối j J Khách hàng i  I 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 zj =    lai trái0 mo j DC khi 1 pk =    lai trái0 mok máy nhà khi 1 yji =    lai trái0 i hàngkhách vu phuc j DC khi 1 2. 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 9 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 1min k k j j sk sk kj kj ji ji k j s k k j j i f g p v z t b a f c q         (1) ( ) 2 ( ) min D n ji j O i C j i i q f d       (2) 1/2 1/2 2 2 ( ) ( ) ( ) ( ) 3 1 2 | | | | min d P d d P d P d kj kj jiji j O k O j O j O ii k j k O j O k j k O j O p D f f qq D W D W O O f r r                                                                                                      (3) 1,ji j y i  (4) ,j ji ji i d y W z j  (5) n j j z W (6) , ,ji i jiq d y i j  (7) ,kj ji k i f q j   (8) sup ,ssk k b s  (9) ,kj sk j s u f b k   (10) ,k kkj j u f D p k  (11) k k p P (12) {0,1},jz j  (13) 10 {0,1},kp k  (14) {0,1}, ,jiy i j  (15) 0, ,skb s k  (16) 0, ,kjf j k  (17) 0, ,jiq i j  (18) - Đẳ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. Chương 3: THIẾT KẾ CHUỖI CUNG ỨNG BẰNG GIẢI THUẬT DI TRUYỀN 3.1. Thuật giải di truyền 3.1.1. Ý 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. 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). Những cá 11 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ẹ. Di truyền và đột biến là hai cơ chế có vai trò như nhau trong quá trình tiến hóa, mặc dù hiện tượng đột biến xảy ra với xác suất nhỏ hơn nhiều so với xác suất của hiện tượng di truyền. Và quá trình lai ghép và chọn lọc là hai quá trình cơ bản xuyên suốt quá trình tiến hóa tự nhiên. 3.1.2. Các vấn đề cơ bản về thuật toán di truyền Thuật toán di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm các giải pháp thích hợp cho các bài toán tối ưu tổ hợp. Giải thuật di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến hóa như di truyền, đột biến, lai ghép (trao đổi chéo) và chọn lọc tự nhiên. Giải thuật di truyền thường được ứng dụng nhằm sử dụng ngôn ngữ máy tính để mô phỏng quá trình tiến hóa của một tập hợp những đại diện trừu tượng (gọi là cá thể) của các giải pháp có thể (gọi là những cá thể) cho bài toán tối ưu hóa vấn đề. Tập hợp này sẽ tiến triển theo hướng chọn lọc những giải pháp tốt hơn. Liên quan đến giải thuật di truyền có các khái niệm sau: 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ó rất nhiều các dạng biểu diễn khác nhau như biểu diễn nhị phân, biểu diễn nguyên, biểu diễn bằng ma trận, .... 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. Tuy nhiên khi thuật toán di truyền đã được áp dụng để giải nhiều bài toán trong nhiều lĩnh vực khác nhau, cách biểu diễn nhị phân đôi khi gây những khó khăn cho các thao tác khác. Vì vậy, tùy theo các bài toán thực tế, người giải bài toán có thể lựa chọn các cách biểu diễn cho phù hợp nhất với chúng. b) Đánh giá độ thích nghi (fitness function) Độ 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). Việc xây dựng độ thích nghi cũng là một bước quan trọng trong thuật toán di truyề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 . Hàm Fitness là hàm dùng để đánh giá độ tốt của một lời giải hoặc cá thể. Hàm Fitness nhận vào một tham số là xâu mã hóa nhị phân của một cá thể và trả ra một số thực. Tùy theo giá trị của số thực này mà ta biết độ tốt của cá thể đó (chẳng hạn với bài toán tìm cực đại thì giá trị 12 trả ra càng lớn thì cá thể càng tốt, và ngược lại, với bài toán tìm cực tiểu thì giá trị trả ra càng nhỏ thì cá thể càng tốt). c) Lai ghép (crossover operator) 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ẹ. - Lai ghép đơn điểm (single-point crossover): Lai ghép đơn điểm được mô tả như sau: 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. o Tạo một số ngẫu nhiên trong khoảng từ 1 đến m-1, số này sẽ được gọi là điểm lai. Điểm lai chia các chuỗi cá thể cha mẹ ra thành hai nhóm chuỗi con dài m1 và m2. Hai chuỗi cá thể con mới sẽ là m11+m22 và m21+m12. Đư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. 13 Ví dụ: giả sử ta có 2 cá thể A và B như sau: C á thể A C á thể B Giả sử điểm lai là k=6. C á thể A C á thể B Khi đó hai cá thể con A’ và B’ sẽ có bộ gen được biểu diễn như sau: Cá thể con A’ C á thể con B’ - Lai ghép đa điểm (multi-point crossover) Lai ghép đa điểm là dạng tổng quát của lai ghép đơn điểm và được mô tả như sau: 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. o Chọn nhiều điểm lai ghép: k1, k2, , km, m điểm lai ghép này sẽ chia đoạn mã gen của cha-mẹ ra thành m+1 đoạn o Hai cá thể mới được tạo ra bằng cách ghép các đoạn của hai bộ gen cha mẹ với nhau theo quy tắc: các đoạn ở vị trí lẻ được giữ nguyên, các đoạn ở vị trí chẵn được chuyển hóa cho nhau như trong lai ghép đơn điểm . 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 14 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 C á thể B Giả sử các vị trí lai ghép là 2, 4, 7; biểu diễn như trong hình sau: Cá thể A C á thể B Hai cá thể con có bộ gen được biểu diễn như sau: Cá thể con A’ C á thể con B’ Quá trình lai ghép: Phép lai xảy ra với xác suất là pc (đây là tham số do người dùng tự định nghĩa). Xác suất pc này cho ta số cá thể tham gia lai ghép là pc* pop_size (pop_size là kích thước quần thể). Quá trình được tiến hành như sau: 1. Chọn cặp cá thể từ quần thể hiện tại 2. Sinh ngẫu nhiên một số hữu tỷ r trong khoảng [0..1]. 3. Nếu r < pc chọn điểm lai ghép bằng cách tạo một số ngẫu nhiên k với 1≤ k ≤ độ dài xác định của xâu 4. Thực hiện lai ghép. d) Đột biến (mutation operator) 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 15 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ó. Nếu sử dụng biểu diễn nhị phân thì phép đột biết thường sử dụng là bit flipping, nghĩa là nếu gen là 1 thì được đổi thành 0 và ngược lại. Ví dụ: ta chọn k=3 là vị trí thay đổi khi đó ta có Cá thể A Cá thể đột biến Quá trình đột biến: Tương tự như quá trình lai ghép, quá trình đột biến cũng được thực hiện với một xác suất đột biến pm (tham số này do người dùng tự định nghĩa). Quá trình đột biết xảy ra như sau: 1. Chọn một cá thể trong quần thể. 2. Sinh ngẫu nhiên một số hữu tỷ r trong khoảng [0..1]. 3. Nếu r < pm Chọn điểm đột biến bằng cách tạo một số ngẫu nhiên k với 1≤ k ≤ độ dài xác định của xâu 4. Thay đổi 0 thành 1 hoặc ngược lại (Flipping) gen thứ k e) Chọn lọc và thay thế (selection and replacement) 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. Những cá thể có độ thích nghi lớn hơn hoặc bằng với độ thích nghi tiêu chuẩn sẽ được giữ lại và độ thích nghi của các cá thể trong quần thể sẽ hoàn thiện hơn sau nhiều thế hệ. Để 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. Quá trình này được mô tả như sau: 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à Fi, tổng dồn thứ i là Fti, tổng độ thích nghi của toàn quần thể là Fm. o Tạo một số ngẫu nhiên F trong trong đoạn từ 0 đến Fm. o Chọn cá thể thứ k đầu tiên thỏa mãn F ≥ Ftk đưa vào quần thể của thế hệ mới f) Điều kiện dừng (stopping conditions) 1 0 0 1 1 0 1 0 1 1 1 0 16 Thuật toán di truyền là một quá trình ngẫu nhiên, nên chúng ta không thể đảm báo chắc chắn thuật toán di truyền sẽ dừng sau hữu hạn bước. Vì vậy, để đảm bảo thuật toán di truyền sẽ kết thúc, người dùng thường phải định nghĩa điều kiện dừng cho thuật toán. 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óm lại, mã giả của một thuật toán di truyền được viết như sau: Bắt đầu a. t=0; b. Khởi tạo p(t); c. Tính độ thích nghi cho các cá thể thuộc P(t); d. Khi (điều kiện dừng chưa thoả mãn) lặp i. t=t+1; ii. Tái sinh P’(t) từ P(t); iii. Lai Q(t) từ P(t-1); iv. Đột biến R(t) từ P(t-1); v. Chọn lọc P(t) từ P(t-1)  Q(t)  R(t)  P(t); e. Hết lặp; Kết thúc; 3.2. 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. Sự biểu diễn dạng cây là một cách để trình bày những bài toán về mạng. Về cơ bản, có 3 cách mã hóa cây: (1) mã hóa dựa trên cạnh, (2) mã hóa dựa trên đỉnh và (3) mã hóa dựa trên cạnh và đỉnh [1] Ứng dụng đầu tiên của GAs cho bài toán vận tải/phân phối đã được tiến hành bởi [13]. Trong cách thiếp cận này, các tác giả đã sử dụng sự biểu diễn dạng ma trận theo cách mã hóa dựa trên cạnh để trình bày quá trình vận tải. Khi |K| and |J| là số nguồn và kho chứa, tương ứng với ma trận |K| * |J| chiều. Mặc dù đây là một sự biểu diễn trực tiếp của quá trình vận tải, nhưng cách biểu diễn này sẽ gây nên sự dư thừa bộ nhớ và cần tới những cơ chế di truyền đặc biệt thì mới có thể đạt được những giải pháp khả thi. Sự biểu diễn khác của quá trình vận tải được trình bày trong [12]. Cách biểu diễn này theo sự mã hóa dựa trên đỉnh và chỉ cần |K| + |J| – 2 số để thể hiện một quá trình vận tải với các nguồn và các kho. Mặc dù cách tiếp cận này thực sự được phát triển để mã hóa các cây bao 17 trùm, và được ứng dụng thành công cho những bài toán vận chuyển, tuy nhiên nó cần tới một số kỹ thuật sửa chữa để đạt tới các giải pháp khả thi sau những thao tác di truyền cổ điển. 3.2.2 Hàm đo độ thích nghi 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. Trong các nghiên cứu trước, có nhiều kỹ thuật khác nhau để định nghĩa các chức năng phù hợp [12], một trong số những kỹ thuật đó và cũng là cách tiếp cận đơn giản nhất là kỹ thuật tổng trọng số (weight-sum). Giả sử m là các chức năng mục tiêu, chức năng phù hợp có thể đạt được bằng cách phối hợp các chức năng mục tiêu. 1 ( ) m i i i eval f w f    Trong đó wi không đổi, thể hiện trọng số cho fi và 1 w 1 m i i  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. 18 Để xác định các giá trị trọng số (weight), chúng ta điều chỉnh hai cách tiếp cận đã được nêu lên trong [14], [15]. Cách tiếp cận thứ nhất dựa trên cách tiếp cận trọng số ngẫu nhiên mà các trọng số được xác định một cách ngẫu nhiên cho từng bước của quá trình tiến hóa [14]. Cách tiếp cận này đã tìm ra một không gian giải pháp toàn diện để tránh được tối ưu địa phương và do đó sẽ đem đến một sự thay đổi đồng bộ để tìm ra những giải pháp Pareto khả thi. Trong cách tiếp cận thứ hai, các trọng số được xác định dựa trên một điểm lí tưởng được tạo nên trong mỗi quá trình tiến hóa. Và thông thường, mỗi mục tiêu, chúng được tính theo công thức dưới đây , min , max , min ' i i i i i f f f f f    i=1,2m (20) Trong đó fi, min và fi, max là giá trị nhỏ nhất và lớn nhất của mục tiêu thứ i ở thế hệ hiện tại Cách tiếp cận 1: Các trọng số trong cách tiếp cận này được được chỉ ra với đẳng thức (21) trong mỗi thế hệ. 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) randomi ~ U (0, 1) wi = randomi / (random1 + .+ randomm) (21) trong đó i = 1, 2m 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) ' ' 1 2 1 2 ' ' ' ' 1 2 1 2 , w w w w w w w w     Trong đó w’1 = f ’ 1(x) - f ’ 1, min(x) w ’ 2 = f ’ 2(x) - f ’ 2, min(x) f ’ 1, min(x), f ’ 2, min(x) là giá trị nhỏ nhất của f ’ 1(x) và f ’ 2(x) trong quần thể hiện tại, tức là chúng là điểm lý tưởng trong không gian mục tiêu mà giá trị của nó đã được bình thường hóa. 3.2.3 Các toán tử di truyền a) Lai ghép Toán tử lai ghép được thực hiện để tìm ra không gian giải pháp mới bằng cách hoán đổi của chuỗi giữa các cặp bố mẹ được lựa chọn. Trong toán tử này, mỗi phân đoạn của con cái được lựa chọn một cách ngẫu nhiên với xác suất bằng nhau giữa các phân đoạn tương ứng của 19 bố mẹ. 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. Trong khi “0” có nghĩa là cặp bố mẹ đầu tiên sẽ chuyển nguồn gen của nó cho con cái, “1” có nghĩa là con cái sẽ lấy nguồn gen từ cặp bố mẹ thứ hai cho phân đoạn tương ứng. Toán tử nối này có xu hướng bảo tồn các phân đoạn gen tốt của cả hai cặp bố mẹ Hình 7: Minh họa toán tử nối Hình 8: Minh họa toán tử đột biến b) Đột biến Toán tử đột biết sự đột biến được sử dụng để ngăn chặn chuỗi hội tụ sớm và khám phá ra không gian giải pháp mới. tuy nhiên, không giống như crossover, sự đột biến thường được dùng bằng cách sửa đổi gen trong phạm vi một cá thể. Trong toán tử này, trước tiên, một quyết định về những phân đoạn sẽ được làm đột biến được đưa ra với xác suất 0.5 và sau đó chọn những phân đoạn được đột biến. Vì trong cá thể bao gồm hai cấu trúc mã hóa khác nhau, sự đột biến trên các cấu trúc là cũng khác nhau. Toán tử hoán đổi (swap) được sử dụng cho hai phân đoạn đầu tiên tại nơi mà sự mã hóa dựa trên độ ưu tiên được sử dụng. Toán tử này chọn lựa hai gen từ phân đoạn tương ứng và trao đổi vị trí của chú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ể. Trong toán tử này, giá trị gen được lựa chọn ngẫu nhiên sẽ được thay thế bởi một giá trị mới nằm trong khoảng giữa 1 và số lượng trung tâm phân phối ngoại trừ giá trị hiện tại của nó. 20 c) Sự lựa chọn Trong GA được đề xuất, quần thể ban đầu được sinh ra ngẫu nhiên và tập hợp tối ưu hóa Pareto được tạo ra bởi các giải pháp không trội trong quần thể ban đầu. 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ệ. Là một kỹ thuật có chọn lọc, chúng ta đã điều chỉnh chiến lược chọn lựa (+). Trong chiến lược này,  và  thể hiện số bố mẹ và con cái cấu thành nên một vùng tiến hóa trong thế hệ hiện tại và cạnh tranh với những vùng đang tồn tại. 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. Thêm đó, chúng ta đã tận dụng một chiến lược phân hóa để gia tăng khả năng tìm kiếm các giải pháp tối ưu Pareto tốt hơn của GA được đề xuất. Chiến lược này được dựa trên sự khởi động lại của việc tìm kiếm di truyền. Nếu tập giải pháp tối ưu Pareto không được cập nhật trong những sự di chuyển cuối cùng (số lượng của sự sinh ra/5 , như trong nghiên cứu của chúng ta) thì quần thể sẽ được thiết lập lại. Trong khi 10% của quần thể được lấp đầy bởi các giải pháp không chiếm ưu thế được chọn lựa ngẫu nhiên từ tập giải pháp tối ưu Pareto thì các giải pháp di truyền ngẫu nhiên được lập ra từ phần còn lại của quần thể. Nếu không có đủ các giải pháp không ưu thế trong tập tối ưu hóa Pareto để lấp đầy 10% quần thể thì tất cả các giải pháp không ưu thế sẽ được sử dụng trong một quần thể mới. KẾT LUẬN VÀ ĐỀ XUẤT Trong luận văn này, chúng tôi đã trình bày được 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 Phát biểu bài toán dưới dạng chương trình nguyên phi tuyến hỗn tạp và chi tiết việc áp dụng giải thuật di truyền để giải bài toán. Hướng phát triển trong tương lai 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. Tuy nhiên, quá trình lai ghép và đột biến của giải thuật này gây tốn thời gian thực hiện chương trình. Vì vậy, trong tương lai, cách tiếp cận dựa trên kỹ thuật tối ưu hóa theo nhóm bầy (PSO- Particle Swarm Optimization) nên được sử dụng. o Các kỹ thuật khác như Tabu Search cũng nên được sử dụng để có thể dành được các giải pháp tối ưu đa mục tiêu Pareto. References 21 [1] Altiparmak. F, Gen & Lin (2005). “A genetic algorithm for supply chain network design,” In Proceeding of the 35th International Conference on Computers and Industrial Engineering. [2] Thomas, D. J., & Griffin, P. M. (1996), "Coordinated supply chain management,” European Journal of Operational Research, No.94, pp.1–115. [3] Vidal, C. J., & Goetschalckx, M. (1997), “Strategic production-distribution models: a critical review with emphasis on global supply chain model,” European Journal of Operational Research, No.98, pp.1–18. [4] Beamon, B. M. (1998), “Supply chain design and analysis: models and method,” International Journal of Production Economics, No.55, pp.281–294. [5] Jayaraman, V., & Pirkul, H. (2001), “Planning and coordination of production and distribution facilities for multiple commodities,” European Journal of Operational Research, No.133, pp.394–408. [6] Chan, F. T. S., Chung, S. H., & Wadhwa, S. (2004), “A hybrid genetic algorithm for production and distribution,” Omega, No.33, pp.345–355. [7] Chen, C., & Lee, W. (2004), “Multi-objective optimization of multi-echelon supply chain networks with uncertain product demands and prices,” Computers and Chemical Engineering, No.28, pp.1131–1144. [8] Erol, I., & Ferrell, W. G. Jr., (2004), “A methodology to support decision making across the supply chain of an industrial distributor,” International Journal of Production Economics, No. 89, pp.119–129. [9] Chankong, V., & Haimes, Y. Y. (1983), “Multiobjective decision making theory and methodology”. NewYork: Elsevier. [10] Ceollo, C. A. C., Van Veldhuizen, D. A., & Lamont, G. B. (2002), “Evolutionary algorithms for solving multi-objective problems,” New York: Kluwer. [11] Deb, K. (2001), “Multi-objective optimization using evolutionary algorithms,” Chichester: Wiley. [12] Gen, M., & Cheng, R. (2000), “Genetic algorithms and engineering optimization,” New York: Wiley. [13] Michalewicz, Z., Vignaux, G. A., & Hobbs, M. (1991), “A non-standard genetic algorithm for the nonlinear transportation problem,” ORSA Journal on Computing, No.3, pp.307–316. 22 [14] Murata, T., Ishibuchi, H., & Tanaka, H. (1996), “Multi-objective genetic algorithm and its applications to flowshop scheduling,” Computers and Industrial Engineering, Vol. 4, No.30, pp.957–968. [15] Zhou, G., & Gen, M. (1999), “Genetic algorithm approach on multi-criteria minimum spanning tree problem,” European Journal of Operational Research, No.114, pp.141–152.