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

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