đặt vấn đề cho bài toán và trình bày động lực nghiên cứu. Ngoài ra, chương này cũng sẽ trình bày các thách thức và đóng góp mà luận văn. Chương 2 tập trung vào tổng quan về bài toán, bao gồm giới thiệu về bài toán, các lý thuyết quan trọng liên quan đến bài toán và phân tích các công trình nghiên cứu liên quan đến bài toán. Chương 3 mô tả chi tiết về hệ thống, bao gồm các thành phần và chức năng của hệ thống.
Ngoài ra, chương này cũng sẽ giới thiệu về phương pháp và quy trình thiết kế hệ thống. Chương 4 tiến hành xây dựng hệ thống, cài đặt thử nghiệm và đánh giá hiệu suất của hệ thống. Cuối cùng, Chương 5 tổng kết kết quả nghiên cứu và đánh giá hiệu quả của hệ thống. Ngoài ra, chương này cũng sẽ đề cập đến những hạn chế của nghiên cứu và đề xuất các hướng phát triển trong tương lai.
Cơ Sở Lý Thuyết Và Các Công Trình Nghiên Cứu Liên Quan 2.1 Giới thiệu Chương này sẽ trình bày các kiến thức lý thuyết cơ bản về chủ đề của nghiên cứu, nhằm đưa ra một nền tảng vững chắc cho phần thực tiễn của luận văn. Đầu tiên, chương này sẽ giới thiệu về bối cảnh và ngữ cảnh của bài toán, nhấn mạnh vào sự quan trọng của vấn đề và cần thiết của việc nghiên cứu. Sau đó, chương sẽ đi sâu vào các cơ sở lý thuyết quan trọng liên quan đến bài toán, bao gồm các khái niệm cơ bản, các mô hình toán học và các phương pháp phân tích và giải quyết vấn đề. Chương về các cơ sở lý thuyết sẽ cũng giới thiệu các nghiên cứu liên quan đến bài toán trong quá khứ, phân tích và so sánh các phương pháp và kết quả của các nghiên cứu này.
Ngoài ra, chương này cũng sẽ trình bày các công trình liên quan mới nhất, để cập nhật và giới thiệu các nghiên cứu mới nhất trong lĩnh vực liên quan.2 Một số cơ sở lý thuyết 2.1 Facility Location Các vấn đề vị trí cơ sở (Facility Location Problem - FLP) là một quá trình quan trọng trong quản lý chuỗi cung ứng, trong đó các vị trí được chọn cho các cơ sở sản xuất, kho hàng hay cửa hàng để tối ưu hóa hiệu quả của các hoạt động kinh doanh. Các yếu tố được xem xét trong quá trình này bao gồm chi phí vận chuyển, thời gian giao hàng, hiệu quả chi phí, quy mô sản xuất và thu nhập của người lao động. Các công nghệ tiên tiến như trí tuệ nhân tạo và học máy đã được áp dụng để tối ưu hóa quá trình này. FLP đã và đang được nghiên cứu rộng rãi do ứng dụng của chúng trong nhiều tình huống thực tế.
Các mô hình này có thể khác nhau về chức năng mục tiêu, số lượng phương tiện để định vị, không gian giải pháp trong đó vấn đề được xác định và một số yếu tố quyết định khác. Bài toán được gọi là bài toán vị trí cơ sở rời rạc (discrete facility location) nếu có một số hữu hạn các vị trí cơ sở ứng viên. Nếu các cơ sở có thể được đặt ở bất kỳ đâu trong một số vùng liên tục, thì bài 10 toán được gọi là bài toán vị trí cơ sở liên tục (continuous facility location). Trong luận văn này, học viên tập trung vào các mô hình vị trí cơ sở rời rạc.
FLP rời rạc liên quan đến việc chọn vị trí tốt nhất cho các cơ sở từ một tập hợp các địa điểm tiềm năng nhất định để giảm thiểu tổng chi phí trong khi đáp ứng nhu cầu của khách hàng. FLP có thể được chia thành hai loại: giới hạn dung lượng và không giới hạn dung lượng [1][2][3]. Trong bài toán đặt vị trí cơ sở sản xuất không giới hạn dung lượng (Uncapacitated Facility Location Problem – UFLP), mỗi cơ sở được giả định là không có giới hạn về dung lượng và mỗi khách hàng sẽ nhận được toàn bộ nhu cầu của mình từ đúng một cơ sở. Trong bài toán đặt vị trí cơ sở sản xuất có giới hạn dung lượng (Capacitated Facility Location Problem – CFLP) đề cập đến việc mỗi cơ sở sản xuất chỉ có thể chứa một lượng hàng hóa tối đa nhất định và việc này phải được xem xét khi đưa ra quyết định về vị trí cũng như khối lượng hàng hóa được chuyển đi từ mỗi cơ sở.2 Capacitated Facility Location Problem CFLP bao gồm việc định vị một tập hợp các cơ sở có năng lực hạn chế để phục vụ một nhóm khách hàng.
Mục tiêu của nó là giảm thiểu tổng chi phí, bao gồm thiết lập cơ sở vật chất và đáp ứng nhu cầu. Cả hai vị trí tiềm năng cho các cơ sở và nhu cầu của khách hàng đều được biết trước. Đây là một vấn đề nổi tiếng được nghiên cứu chi tiết trong [4][5]. Hai mô hình phân bổ thường được xem xét cho CFLP là: nhiều nguồn cung ứng (một khách hàng có thể được phục vụ từ một số cơ sở) và một nguồn cung ứng (mỗi khách hàng được phân bổ cho một và chỉ một cơ sở [6][7].
Trong luận văn này này, học viên tập trung vào trường hợp đa nguồn. Ngày nay, CFLP vẫn thu hút sự chú ý của cộng đồng khoa học về mặt phát triển các thuật toán giải pháp hiệu quả hơn hoặc bằng cách xem xét các phần mở rộng nắm bắt các khía cạnh liên quan đến thực tế. Trên thực tế, đây là một vấn đề mà chúng ta thường thấy ở cốt lõi của các vấn đề phức tạp hơn (Ví dụ: Thiết kế mạng lưới Logistics). Trong CFLP, khi một cơ sở hết công suất/sản xuất, các cơ sở khác sẽ được gọi đến để đáp ứng nhu cầu của khách hàng.
Điều này thường dẫn đến sự gia tăng chi phí, bởi vì cần phải lắp đặt nhiều cơ sở hơn hoặc do nhu cầu của khách hàng 11 được đáp ứng với chi phí phân phối cao hơn bởi các cơ sở vẫn còn công suất. Tuy nhiên, trên thực tế, các khả năng khác có thể được khuyến khích, chẳng hạn như năng lực của một cơ sở có thể được đưa vào phục vụ các cơ sở khác. Cụ thể, thay vì mở thêm cơ sở hoặc phục vụ khách hàng với chi phí phân phối cao hơn, những cơ sở có công suất dư thừa có thể chuyển phần dư thừa đó. (ví dụ: một phần sản xuất của họ) cho các cơ sở thiếu hụt.
Cách tiếp cận này được gọi là chuyển giao năng lực (capacity transfer).3 Facility Location Problem With Capacity Transfer Bài toán đặt vị trí cơ sở với sự chuyển giao năng lực (Facility Location Problem With Capacity Transfer – FLPCT) [8] là một bài toán tối ưu hóa trong lĩnh vực quản lý sản xuất và phân phối hàng hóa. Bài toán này đặt ra câu hỏi về việc xác định vị trí tối ưu cho các cơ sở sản xuất và phân phối, sao cho chi phí vận chuyển hàng hóa giữa các cơ sở này là thấp nhất. Trong FLPCT, các cơ sở sản xuất và phân phối có khả năng chuyển giao khối lượng sản phẩm cho nhau, tạo ra một mô hình mạng với các đường ống dẫn. Tại mỗi cơ sở, có một giới hạn về khả năng sản xuất và lưu trữ hàng hóa.
Mục tiêu của bài toán là tìm ra một phân bố các cơ sở sao cho tổng sản lượng được sản xuất và phân phối đáp ứng được nhu cầu của thị trường và các ràng buộc về khả năng sản xuất và lưu trữ. FLPCT là một bài toán phức tạp và thường được giải quyết bằng các phương pháp tối ưu hóa toán học như lập trình tuyến tính và quy hoạch nguyên. Các ứng dụng thực tế của FLPCT bao gồm quản lý chuỗi cung ứng, lập kế hoạch sản xuất và phân phối hàng hóa, và quản lý kho. Trong FLPCT, công suất thực tế của một cơ sở không được giả định là (đầy đủ) được biết trước vì nó trở thành quyết định đưa ra sức chứa của một cơ sở là kết quả của giá trị ban đầu và số tiền được chuyển đến/từ các cơ sở khác.
Việc chuyển giao công suất có thể cung cấp các giải pháp với tổng chi phí nhỏ hơn.4 Tìm kiếm Tabu (Tabu search) 12 Thuật toán Tìm kiếm Tabu (Tabu Search) [9][10] là một thuật toán tìm kiếm được sử dụng để giải quyết các bài toán tối ưu hóa. Thuật toán này được đặt tên theo khái niệm “tabu”, có nghĩa là “cấm”, vì nó sử dụng một danh sách các giá trị bị cấm, được gọi là “danh sách tabu”, để tránh lặp lại các giá trị đã được thử nhưng không cho kết quả tốt. Thuật toán Tabu Search được phát triển từ thuật toán Leo đồi (Hill Climbing), đó là một phương pháp tìm kiếm địa phương, nghĩa là nó chỉ tìm kiếm các giải pháp gần với giải pháp hiện tại. Thuật toán Tìm kiếm Tabu mở rộng thuật toán Leo đồi bằng cách sử dụng danh sách Tabu để tìm kiếm các giá trị mới nhất, thay vì lặp lại các giá trị đã được thử.
Các bước chính của thuật toán Tabu Search như sau: Bước 1. Khởi tạo giá trị ban đầu Thuật toán Tabu Search bắt đầu với một giải pháp ban đầu, có thể được chọn ngẫu nhiên hoặc được tạo ra bằng các phương pháp khác. Giải pháp ban đầu này sẽ được sử dụng làm giải pháp hiện tại để bắt đầu quá trình tìm kiếm. Tìm kiếm các giải pháp lân cận Sau khi có giải pháp ban đầu, thuật toán sẽ tìm kiếm các giải pháp mới bằng cách thay đổi một số giá trị trong giải pháp hiện tại.
Các giá trị mới này được gọi là “giải pháp lân cận”. Các giải pháp lân cận có thể được tạo ra bằng cách thay đổi một hoặc nhiều giá trị của giải pháp hiện tại, hoặc bằng cách kết hợp các giá trị từ các giải pháp khác. Ví dụ, nếu ta đang tìm kiếm lời giải cho một bài toán lập lịch, ta có thể tạo ra các giải pháp lân cận bằng cách đổi chỗ thứ tự các công việc, thay đổi thời gian bắt đầu hoặc kết thúc các công việc, hoặc thay đổi thời gian thực hiện của các công việc. Đánh giá các giải pháp lân cận Sau khi có các giải pháp lân cận, thuật toán sẽ đánh giá mức độ tối ưu của các giải pháp lân cận bằng cách sử dụng một hàm mục tiêu.
Hàm mục tiêu này sẽ đo lường độ tối ưu của mỗi giải pháp lân cận. Ví dụ, trong bài toán lập lịch, hàm mục tiêu có thể đo lường độ phù hợp giữa thời gian thực hiện các công việc và thời gian được yêu cầu để hoàn thành dự án. Lựa chọn giải pháp lân cận tốt nhất Sau khi đã đánh giá các giải pháp lân cận, thuật toán sẽ chọn giải pháp lân cận tốt nhất từ các giải pháp lân cận tìm được.