(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp(Luận văn thạc sĩ) Tìm hiểu giải thuật định tuyến xe, ứng dụng trong tối ưu lộ trình thu gom rác thải trong khu công nghiệp
TỔNG QUAN VỀ BÀI TOÁN ĐỊNH TUYẾN XE
Tổng quan về lĩnh vực tối ưu hóa tổ hợp
Tối ưu hóa bản chất là một lĩnh vực toán học quan trọng, được ứng dụng rộng rãi trong nhiều ngành khác nhau Bài toán tối ưu tổ hợp tập trung vào việc tìm kiếm một cấu hình "tốt nhất" và có nhiều ứng dụng thực tiễn Lý thuyết tổ hợp đã góp phần quan trọng trong việc phát triển các thuật toán hiệu quả, ảnh hưởng đến các lĩnh vực như công nghệ thông tin, điều khiển tự động, thiết kế chế tạo máy, quản trị kinh doanh, quy hoạch tài nguyên và kiến trúc đô thị Sự đa dạng trong các lĩnh vực của tối ưu hóa ngày càng gia tăng, đặc biệt trong việc xây dựng hệ thống hỗ trợ ra quyết định và phát triển các hệ thống lớn.
Bài toán tối ưu tổ hợp có thể phát biểu dưới hình thức toán học như sau: Tìm X∈ D : f (X) →min (max) (1.1)
Trong bài toán tối ưu, D là tập hữu hạn gồm các cấu hình thỏa mãn điều kiện bài toán, trong đó hàm f được gọi là hàm mục tiêu Tập hợp D được xem là miền xác định hay miền phương án, với mỗi phần tử của D được gọi là một phương án Phương án tốt nhất trong tập hợp này được gọi là phương án tối ưu, và giá của phương án tối ưu được xác định là giá trị tối ưu.
Trong tối ưu hóa, với tập hợp hữu hạn, luôn tồn tại ít nhất một phương án tối ưu, mặc dù có thể có nhiều phương án khác nhau Giá trị tối ưu trong từng bài toán là duy nhất Để giải quyết một bài toán cụ thể, cần xác định rõ các điều kiện của tập hợp D và phương pháp tính hàm f, có thể thông qua công thức hoặc thủ tục Hai bài toán nổi tiếng trong lĩnh vực tối ưu tổ hợp là bài toán người bán hàng (traveling salesman problem - TSP) và bài toán cây khung nhỏ nhất (minimum spanning tree problem - MST).
Bài toán định tuyến xe và một số biến thể
1.2.1 Phát biểu bài toán định tuyến xe
Bài toán Người bán hàng (Travelling Salesman Problem - gọi tắt là TSP) chính là trường hợp đơn giản nhất của bài toán định tuyến xe (Vehicle Routing
Bài toán VRP với một xe giao hàng duy nhất, cụ thể là nhân viên bán hàng, yêu cầu tìm ra lộ trình ngắn nhất cho nhân viên này Nhân viên bán hàng sẽ xuất phát từ một thành phố và phải đi qua tất cả các thành phố trong lộ trình một cách lần lượt.
Bài toán tìm lộ trình tối ưu cho người bán hàng yêu cầu họ ghé thăm mỗi thành phố chỉ một lần và quay về thành phố xuất phát với chi phí thấp nhất Mục tiêu chính là xác định lộ trình có tổng độ dài quãng đường di chuyển nhỏ nhất để đảm bảo hiệu quả trong việc giao hàng.
Bài toán TSP (Traveling Salesman Problem) được mô hình hóa bằng đồ thị, trong đó các đỉnh đại diện cho các thành phố và các cạnh thể hiện đường đi giữa chúng Khoảng cách giữa các thành phố được xem là trọng số của các cạnh nối Giải pháp tối ưu cho bài toán này là tìm kiếm chu trình Hamilton ngắn nhất, kết nối tất cả các điểm trên đồ thị với tổng khoảng cách tối thiểu.
Hình 1.1 Ví dụ cho bài toán Người bán hàng– TSP
Bài toán VRP, mở rộng từ bài toán TSP, liên quan đến một nhóm xe tập kết tại kho hàng, phục vụ các khách hàng với yêu cầu vận chuyển khác nhau Mục tiêu chính là tối ưu hóa lộ trình cho các xe để đáp ứng nhu cầu của tất cả khách hàng với chi phí vận chuyển thấp nhất.
Hình 1.2 Mô phỏng bài toán VRP
Bài toán VRP được mô phỏng trong Hình 1.2, với hình bên trái cho thấy các xe tập kết tại Depot và các khách hàng được biểu diễn bằng điểm chấm đen cùng yêu cầu vận chuyển Các cạnh nối giữa các điểm thể hiện các tuyến đường di chuyển Hình bên phải minh họa giải pháp của bài toán, trong đó các chu trình nối bởi đường nét đậm thể hiện lộ trình của các tuyến xe phục vụ khách hàng.
Trong bài toán định tuyến xe cơ bản, các xe khởi hành từ kho hàng để giao hoặc nhận hàng từ khách hàng và sau đó quay về điểm xuất phát Các khái niệm chính trong bài toán này bao gồm việc tối ưu hóa lộ trình, giảm thiểu chi phí vận chuyển và thời gian giao hàng.
Xe là phương tiện vận chuyển hàng hóa, được phân loại dựa trên các đặc điểm như sức chứa (tải trọng tối đa), loại hàng hóa (đông lạnh, khô) và chi phí vận chuyển Chi phí vận chuyển bao gồm chi phí cố định, là khoản chi cần thiết ban đầu để xe khởi hành, và chi phí động, là chi phí phát sinh theo từng đơn vị quãng đường.
Kho hàng (Depot) là địa điểm lưu trữ hàng hóa, đồng thời cũng là nơi xuất phát hoặc quay về của các phương tiện vận chuyển Trong một số trường hợp, hàng hóa cần giao có thể được lưu trữ tại nhiều kho hàng khác nhau.
Khách hàng có thể lựa chọn nhận hàng tại địa điểm giao hoặc tự chuyển hàng lên xe để vận chuyển về kho Mỗi khách hàng có nhu cầu riêng về số lượng hàng hóa và có thể đưa ra yêu cầu về thời gian giao hàng cũng như thời gian bốc dỡ hàng.
Lộ trình là hành trình bắt đầu từ điểm xuất phát và quay trở lại điểm ban đầu, thường là kho hàng của xe.
Bài toán định tuyến xe (VRP) là một trong những thách thức phức tạp và nổi bật trong lĩnh vực Vận trù học Cụ thể, bài toán này liên quan đến một nhóm 𝑀 xe giống nhau xuất phát từ một kho hàng để giao hàng cho 𝑁 khách hàng, mỗi khách hàng có nhu cầu cung cấp một lượng hàng nhất định Mục tiêu chính của bài toán là xác định lộ trình ngắn nhất cho 𝑀 xe nhằm đáp ứng đầy đủ yêu cầu của tất cả các khách hàng.
1.2.2 Các biến thể của bài toán định tuyến xe
Bài toán VRP (Vehicle Routing Problem) có nhiều biến thể tùy thuộc vào yêu cầu vận chuyển cụ thể trong thực tế, được phân loại theo các đặc điểm như đội xe, yêu cầu vận chuyển và lợi nhuận.
1.2.2.1 Dựa vào cấu trúc đường đi
Bài toán VRP với các khách hàng được biểu diễn bằng các cạnh, hay còn gọi là Bài toán Lộ trình Cạnh (Arc Routing Problem - ARP), là một dạng đặc biệt của VRP Thay vì các khách hàng được biểu diễn bằng các điểm trong đồ thị như thông thường, ARP tập trung vào các cạnh, tương ứng với các đoạn đường trong thực tế Ví dụ điển hình cho bài toán này bao gồm việc tìm lộ trình cho xe phát báo hoặc xe phun nước để làm mát mặt đường nhựa.
- Bài toán VRP có khoảng cách bất đối xứng (Asymmetric VRP- AVRP): trong bài toán này đồ thị biểu diễn đường đi là một đồ thị có hướng
1.2.2.2 Dựa vào yêu cầu vận chuyển
Bài toán VRP với yêu cầu giao hàng trước (VRPB) yêu cầu các xe phải hoàn thành việc giao hàng trước khi thực hiện các nhiệm vụ nhận hàng Trong mô hình này, tất cả các lộ trình giao nhận đều bắt đầu và kết thúc tại kho hàng, đảm bảo tính hiệu quả trong việc quản lý và tối ưu hóa lộ trình vận chuyển.
7 đến các yêu cầu nhận hàng để đảm bảo lượng hàng cần chứa vượt quá sức chứa của xe
Bài toán kết hợp yêu cầu giao và nhận hàng (Mixed VRPB) đề cập đến việc giao và nhận hàng có thể diễn ra xen kẽ hoặc độc lập Một trong những ràng buộc quan trọng trong bài toán này là tổng lượng hàng nhận từ khách hàng và lượng hàng có trên xe không được vượt quá sức chứa tối đa của xe.
TỐI ƯU LỘ TRÌNH THU GOM RÁC THẢI TRONG KHU CÔNG NGHIỆP VỚI RÀNG BUỘC KHUNG THỜI GIAN VÀ NĂNG LỰC
Hàm mục tiêu
Mục tiêu của dự án là cung cấp dịch vụ cho N khách hàng, mỗi khách hàng có nhu cầu và khoảng thời gian phục vụ nhất định (e_i, l_i), được gọi là cửa sổ thời gian Đội xe tại kho (i = 0) bao gồm K xe giống nhau, mỗi xe có khả năng chuyên chở tối đa là q_k, với k = 1,…,K Để đơn giản, đội xe được giả định là đồng nhất, nghĩa là khả năng chuyên chở tối đa của các xe là như nhau.
Sau khi thiết lập lộ trình, chúng ta áp dụng hai tiêu chuẩn c1(i,u,j) và c2(i,u,j) trong mỗi vòng lặp để chèn khách hàng mới u vào vị trí giữa hai khách hàng liền kề i và j trên lộ trình hiện tại.
Thời gian phục vụ tại khách hàng thứ i được xác định là f i và bắt đầu từ thời điểm t i trong cửa sổ thời gian liên kết với khách hàng đó Nếu xe đến trước thời điểm được phép phục vụ, tức là trước sớm nhất của cửa sổ, thì xe sẽ phải chờ một khoảng thời gian w i, được tính bằng w i = e i - (t i + f j + t ij), với j là khách hàng trước i trên lộ trình Thời gian t ij là thời gian di chuyển từ khách hàng j đến khách hàng i, dựa trên bảng khoảng cách Euclide d ij, được giả định là đối xứng (d ij = d ji) Do đó, thời điểm bắt đầu phục vụ tại khách hàng thứ i được tính là t i = max{e i , t j + f j + t ij}.
Giả sử một lộ trình Rp = (i0,i1,i2, ,im) với i0 = im = 0 chỉ kho trung tâm Để xác định vị trí chèn tốt nhất cho khách hàng u chưa có lộ trình, cần tính toán vị trí này trong lộ trình Rp, đảm bảo tuân thủ các ràng buộc về thời gian và khả năng xe.
Hai hàm c11 và c12 là các hàm dựa trên khoảng cách và thời gian:
Trong bài viết này, ℷ được xác định là hằng số, và t ju là thời điểm bắt đầu phục vụ khách hàng j khi khách hàng u được đưa vào lộ trình Việc chèn khách hàng u vào giữa các khách hàng ip-1 và ip có thể ảnh hưởng đến tất cả thời gian bắt đầu phục vụ của các khách hàng (ip, , im).
Khi đã xác định vị trí tốt nhất để chèn mỗi khách hàng chưa có lộ trình, bước tiếp theo là lựa chọn khách hàng để đạt giá trị tối ưu nhất Khách hàng u* sẽ được chọn dựa trên tiêu chí này.
Trong đó: u là khách hàng chưa có lộ trình và khả thi; c 2 (i,u, j) được tính như sau:
Trong bài toán VRPTW, việc thêm một khách hàng mới vào lộ trình yêu cầu kiểm tra tính khả thi của ràng buộc cửa sổ thời gian cho các khách hàng sau đó, mất O(N) thời gian cho mỗi khách hàng Khi N lớn, điều này gây tốn kém thời gian tính toán Để giải quyết vấn đề này, Solomon (1987) đã đề xuất thủ tục Push Forward, giả định rằng các xe xuất phát ở thời điểm sớm nhất có thể Thời điểm mới để bắt đầu phục vụ khách hàng i p được gọi là t new ip, khi có khách hàng u trong lộ trình, và cần tuân thủ bất đẳng thức tam giác.
31 giữ cả khoảng cách và thời gian di chuvển, việc chèn khách hàng u sinh ra một giá trị push forward tại i p như sau:
Hơn nữa, PFi+1 được tính là:
Nếu PF i > 0, các khách hàng ir
, với p ≤ r ≤ m , có thể trở nên không khả thi
Thủ tục kiểm tra tuần tự khách hàng nhằm xác định tính khả thi về thời gian, cho đến khi tìm thấy một khách hàng có giá trị i r (r < m).
PFi+1 = 0 hoặc i r không khả thi về thời gian Tuy nhiên, trong trường hợp xấu nhất, tất cả các khách hàng i r (p ≤r≤m) được kiểm tra
Solomon[33] đã phát biểu hình thức vấn để này như sau:
Để đảm bảo khả thi về thời gian khi chèn một khách hàng u vào giữa i p-1 và i p (1≤ p≤m) trên một lộ trình khả thi đang xây dựng (i0, i1, i2, , im) với điều kiện i0=im=0, cần thỏa mãn yêu cầu t u ≤ l u.
Lưu ý rằng PF i có thể nhỏ hơn 0 trong trường hợp khoảng cách không phải Euclide, điều này dẫn đến việc tất cả khách hàng đều có thể được phục vụ đúng thời gian Vì i m bằng 0, phát biểu của Solomon đảm bảo rằng xe vận chuyển sẽ trở về kho đúng theo lịch trình Khi không tìm thấy khách hàng nào với các thao tác chèn khả thi, quy trình chèn sẽ khởi động một lộ trình mới và tiếp tục cho đến khi tất cả khách hàng đều được phục vụ.
Trong các phương pháp xây dựng lộ trình, việc lựa chọn khách hàng đầu tiên để phục vụ đóng vai trò quan trọng trong chất lượng giải pháp Nhiều tiêu chuẩn đã được thiết lập để xác định ứng viên phù hợp nhất cho mỗi lộ trình, và rõ ràng rằng các tiêu chuẩn khác nhau sẽ dẫn đến những kết quả khác nhau.
Phương pháp heuristic chèn của Solomon là phương pháp PFIH (Push-Forward Insertion Heuristic) Thuật toán PFIH được mô tả như sau:
• Bước 1: Bắt đầu với một lộ trình rỗng xuất phát từ kho Đặt r = 1
• Bước 2: Nếu {tất cả các khách hàng đã được lập lộ trình} thì nhảy đến bước
8 Ngược lại, ứng với mỗi khách hàng j chưa được lập lộ trình: tính chi phí chèn như nút đẩu tiên
Bước 3: Lựa chọn khách hàng tối ưu từ danh sách đã có, đảm bảo chi phí thấp nhất và đáp ứng các yêu cầu về thời gian cũng như khả năng vận chuyển của phương tiện.
• Bước 4: Thêm j* vào cuối lộ trình hiện tại và cập nhật tải của lộ trình
• Bước 5: Với mọi khách hàng j chưa được lập lộ trình, ứng với mỗi cạnh
{k,l}trong lộ trình hiện tại: tính chi phí chèn khách hàng j vào giữa k và l
• Bước 6: Chọn ra khách hàng j* và cạnh {k*, l*} có chi phí ít nhất Nếu
Việc chèn khách hàng j* giữa k* và 1* là khả thi dựa trên các ràng buộc về thời gian và tải trọng xe Nếu có thể, hãy chèn khách hàng vào giữa k* và l*, sau đó cập nhật tải trọng của lộ trình r hiện tại và chuyển sang bước 5 Nếu không, hãy chuyển đến bước 7.
• Bước 7: Bắt đầu một lộ trình mới xuất phát từ kho Đặt r = r + 1 Nhảy đến bước 2
• Bước 8: Tất cả các khách hàng đã được lập lộ trình Kết xuất các kết quả
PFIH cung cấp giải pháp khả thi và hợp lý dựa trên số lượng xe sử dụng Trong tình huống xấu nhất, số lộ trình được tạo ra sẽ tương đương với số lượng khách hàng, từ đó số xe khởi tạo giúp hình dung mức tối đa của số lộ trình trong giải pháp đưa ra.
Thuật toán di truyền giải bài toán VRPTW
2.3.1 Biểu diễn nhiễm sắc thể
Thuật toán di truyền là phương pháp tìm kiếm heuristic có tính thích nghi và dựa trên một quần thể gồm các cá thể, trong đó mỗi cá thể đại diện cho một lời giải Các đặc tính quan trọng của mỗi cá thể được mã hóa thành nhiễm sắc thể, bao gồm một chuỗi các gene nắm giữ thông tin về từng đặc tính của lời giải Trong nhiều trường hợp, một nhiễm sắc thể thường được biểu diễn như một chuỗi nhị phân hoặc chuỗi số nguyên có chiều dài cố định, giúp đơn giản hóa quá trình tính toán và tìm kiếm lời giải tối ưu.
Phương pháp Thanghiah sử dụng biểu diễn chuỗi nhị phân với 33 pháp, trong đó mỗi số nguyên (gene) trong chuỗi đại diện cho một khách hàng Thứ tự các gene trong nhiễm sắc thể phản ánh thứ tự viếng thăm các khách hàng Ví dụ, một lời giải có thể được trình bày như sau.
Chuỗi số biểu diễn cho một nhiễm sắc thể tương ứng như sau:
Trong lộ trình i, khách hàng cuối cùng được viếng thăm sẽ được liên kết với khách hàng đầu tiên trong lộ trình i+1, tạo thành chuỗi lộ trình liên quan Lưu ý rằng không có ký hiệu phân tách nào được sử dụng trong chuỗi để tránh cản trở việc áp dụng các toán tử di truyền sau này Để giải mã các nhiễm sắc thể thành lộ trình, phương pháp tương tự như PFIH sẽ được áp dụng, tức là chèn các gene vào các lộ trình mới.
2.3.2 Tạo quần thể ban đầu
Quần thể khởi tạo ban đầu có ảnh hưởng đáng kể đến thời gian và chất lượng giải pháp của thuật toán di truyền Việc khởi tạo ngẫu nhiên có thể dẫn đến sự hội tụ chậm về giải pháp tối ưu, trong khi một quần thể ban đầu tốt sẽ giúp thuật toán hội tụ nhanh hơn Để đạt được các giải pháp hiệu quả, các heuristic xây dựng lộ trình thường được áp dụng trong quá trình khởi tạo quần thể, nhưng cũng cần đảm bảo tính đa dạng của các cá thể để không bỏ sót các vùng tiềm năng Do đó, Tan và các cộng sự đã phát triển phương pháp kết hợp giữa heuristic và khởi tạo ngẫu nhiên, chia quần thể thành hai phần: một phần từ heuristic và một phần ngẫu nhiên, với tỷ lệ cá thể được điều chỉnh theo tỷ số nhất định.
Phương pháp PFIH của Solomon được áp dụng rộng rãi trong các nghiên cứu về VRPTW để tìm kiếm lời giải ban đầu cho bài toán PFIH đảm bảo cung cấp một lời giải khả thi nếu có lời giải tồn tại Dựa trên giả định rằng lời giải của PFIH nằm trong vùng lân cận của lời giải tốt nhất toàn cục, một phần quần thể ban đầu được tạo ra từ các lân cận này Lời giải được thu được từ PFIH được ký hiệu là S = {R1, , Rp, , Rq, , Rk}, trong đó Rp đại diện cho tập hợp các khách hàng được phục vụ bởi xe vận chuyển p Thao tác λ-trao đổi giữa hai cặp lộ trình Rp và Rq diễn ra khi thay thế một tập con S1 ⊆ Rp với kích thước |S1| ≤ λ bằng một tập con S2 ⊆ Rq với kích thước λ ≤ |S2| Quá trình này tạo ra các lộ trình mới Rp = (Rp - S1) ∪ S2 và Rq = (Rq - S2).
Trong bài viết này, chúng ta đề cập đến lời giải lân cận S = {R1, , R p , , R q , , R k } và vùng lân cận Nλ(S) được tạo ra thông qua thao tác λ-trao đổi Một phần quần thể ban đầu được hình thành từ thao tác này, trong khi phần còn lại được tạo ngẫu nhiên, không liên quan đến lời giải của PFIH Điều này cho thấy rằng quần thể xuất phát từ vùng lân cận sẽ không đi xa điểm khởi đầu, dẫn đến việc bỏ lỡ cơ hội khám phá các vùng khác Do đó, việc khởi tạo ngẫu nhiên là cần thiết để tăng cường sự đa dạng Sự cân bằng giữa các nhiễm sắc thể liên quan và nhiễm sắc thể ngẫu nhiên được điều chỉnh bởi tham số RANDOM_RATIO; giá trị cao của tham số này làm tăng tính đa dạng của quần thể ban đầu Tham số này cũng thể hiện mức độ tin cậy của người dùng đối với lời giải của PFIH, với RANDOM_RATIO nhỏ hơn khi người dùng tin tưởng rằng tối ưu toàn cục nằm trong vùng lân cận của lời giải ban đầu, giúp quần thể nhanh chóng hội tụ đến tối ưu.
2.3.3 Đánh giá tính thích nghi
Giá trị thể hiện tính thích nghi của nhiễm sắc thể phản ánh chất lượng giải pháp, được đánh giá dựa trên số lộ trình và tổng khoảng cách di chuyển của tất cả các xe vận chuyển, theo đề xuất của Zhu.
Trong đó: f i : là độ thích nghi của nhiễm sắc thể thứ i trong quần thể
R i : là số lộ trình của một lời giải được biểu diễn bởi nhiễm sắc thể thứ i
Di: là tổng khoảng cách của một lời giải được biểu diễn bởi nhiễm sắc thể thứ i
Dmax: là tổng khoảng cách di chuyển lớn nhất
Dmax đại diện cho tổng khoảng cách trong tình huống lập lộ trình xấu nhất, với số lượng khách hàng tương ứng với số lộ trình Khoảng cách Euclide giữa kho và khách hàng thứ i được gọi là Doi Giải pháp S1 được coi là tốt hơn S2 nếu S1 có ít lộ trình hơn Nếu cả hai giải pháp có số lộ trình giống nhau, giải pháp nào có tổng khoảng cách di chuyển nhỏ hơn sẽ được đánh giá cao hơn Nói cách khác, giải pháp càng tốt thì giá trị hàm thích nghi càng nhỏ.
2.3.4 Các thao tác di truyền
Sau khi khởi tạo quần thể ban đầu, thuật toán lặp qua 500 đến 1000 thế hệ Theo lý thuyết, việc lặp nhiều thế hệ sẽ cải thiện chất lượng lời giải, trừ khi đã đạt được lời giải tối ưu Để tạo ra quần thể con, các phép toán di truyền như chọn lọc, lai và đột biến được áp dụng lên các cá thể của quần thể cha/mẹ.
Phép chọn được áp dụng để xác định các cá thể cha mẹ tốt cho quá trình lai ghép Cơ chế chọn theo vòng thi đấu cho phép mỗi thế hệ có hai bản sao 1P và 2P từ quần thể P với N cá thể Sau đó, 1P và 2P được sắp xếp ngẫu nhiên Đối với các nhiễm sắc thể liền kề trong quần thể, nhiễm sắc thể có giá trị thích nghi nhỏ hơn sẽ được chọn làm cha/mẹ tiềm năng Quá trình này tiếp tục cho đến khi tất cả các cặp nhiễm sắc thể liền kề được duyệt qua.
1P và các cặp nhiễm sắc thể liền kề trong quần thể 2P sẽ lần lượt thu được tập các cá thể cha f 0 f 1, f 2…… và tập các cá thể mẹ m 0, m 1, m 2……
Hình 2.2 Chọn cá thể theo vòng thi đấu
Cơ chế chọn lọc theo vòng thi đấu giúp các cá thể có khả năng thích nghi cao có nhiều cơ hội tham gia vào quá trình tái tổ hợp, từ đó tạo ra các cá thể con ưu việt ở thế hệ tiếp theo.
Quá trình tái tổ hợp đóng vai trò quan trọng trong chuỗi tiến hóa sinh học và cũng là yếu tố then chốt trong thuật toán di truyền (GA) Một cơ chế tái tổ hợp thông minh và hiệu quả có thể nâng cao hiệu suất của thuật toán này Trong GA, tái tổ hợp bao gồm hai thao tác chính: lai và đột biến.
Phương pháp heuristic trao đổi chéo trong lai tạo liên quan đến khoảng cách giữa các gene, thực hiện một điểm cắt ngẫu nhiên trên hai nhiễm sắc thể Sau khi cắt, phương pháp sẽ tiến hành so sánh các gene ngay sau vị trí cắt để tối ưu hóa quá trình lai tạo.
Gene B được xác định là gene đầu tiên trong nhiễm sắc thể con Để tránh sự lặp lại, gene L đã được hoán vị với gene B trong NST2 Kết quả của quá trình hoán vị này sẽ tạo ra một cấu trúc mới cho nhiễm sắc thể.
Trong NST con, sau khi so sánh khoảng cách giữa gene B với hai gene I và K, nếu gene K có khoảng cách gần hơn với gene B, tức là d(B,K) < d(B,I), thì gene I cần được hoán vị với gene K trong NST1 để tránh sự trùng lặp Kết quả sau khi thực hiện hoán vị sẽ được thu được.
Xử lý được lặp lại cho đến khi nhiễm sắc thể con có số gene bằng với số gene trong nhiễm sắc thể cha/mẹ
Thuật toán di truyền song song giải bài toán VRPTW
Trong khảo sát thuật toán di truyền, thao tác chọn lọc ảnh hưởng đến tất cả các cá thể trong quần thể, trong khi lai, đột biến và tính toán tính thích nghi chỉ liên quan đến một hoặc một vài cá thể Vì vậy, các thao tác này có thể được phân bổ cho các tiến trình khác nhau để thực hiện song song, giúp rút ngắn thời gian tính toán.
Trong thuật toán di truyền, bước đánh giá tính thích nghi của các cá thể trong quần thể thường tiêu tốn nhiều thời gian tính toán nhất do phụ thuộc vào việc giải mã nhiễm sắc thể và tính toán theo các tiêu chí mục tiêu Để tối ưu hóa quá trình này, nhiều giải thuật di truyền song song chỉ tập trung vào giai đoạn đánh giá tính thích nghi Giải thuật di truyền song song cho bài toán VRPTW được đề xuất dựa trên mô hình chủ-tớ, trong đó tiến trình chủ điều khiển thực thi và chọn lọc cá thể cha mẹ, trong khi các tiến trình tớ thực hiện lai, đột biến và tính toán giá trị thích nghi Truyền thông giữa tiến trình chủ và các tiến trình tớ diễn ra qua việc gửi các cặp cá thể cha/mẹ và nhận các cặp cá thể con từ quá trình tái tổ hợp.
Hình 2.2 Mô hình giải thuật song song dạng chủ tớ
Mô hình song song dạng chủ tớ là một trong những mô hình phổ biến nhất, được ưa chuộng nhờ tính đơn giản và hiệu quả cao Mô hình này rất thích hợp cho việc triển khai trên các hệ thống cluster, nơi nhiều máy tính kết hợp với nhau để tối ưu hóa hiệu suất làm việc.
Di truyền song song áp dụng mô hình master-slave nhằm tối ưu hóa tính toán trong các bài toán lớn bằng cách tận dụng khả năng xử lý đa luồng Quá trình phân chia công việc được thực hiện theo các bước cụ thể để nâng cao hiệu suất và giảm thời gian xử lý.
Thuật toán di truyền song song giải bài toán VRPTW:
● Bước 1: Đọc các tham số và dữ liệu đầu vào
- Tiến trình chủ thực hiện đọc các tham số cấu hình cho thuật toán từ tập tin cấu hình và gửi đến tất cả các tiến trình tớ
Tiến trình chủ thực hiện việc đọc dữ liệu đầu vào từ tập tin chứa thông tin khách hàng và sau đó gửi toàn bộ dữ liệu này đến tất cả các tiến trình con.
- Tất cả các tiến trình tớ thực hiện nhận các dữ liệu được gửi đến bởi tiến trình chủ Thiết lập môi trường thực thi cần thiết
● Bước 2: Khởi tạo quần thể ban đầu
Tiến trình chủ thực hiện khởi tạo quần thể ban đầu với N cá thể, trong đó một phần quần thể được tạo ra từ lời giải khả thi S của PFIH, còn phần còn lại được khởi tạo ngẫu nhiên.
● Bước 3: Đánh giá tính thích nghi của các cá thể trong quần thể ban đầu
- Tiến trình chủ phân chia công việc và gửi các cá thể đến các tiến trình tớ
Tiến trình của tôi nhận các cá thể từ tiến trình chủ, sau đó tiến hành đánh giá tính thích nghi của chúng và gửi giá trị đánh giá trở lại cho tiến trình chủ.
- Tiến trình chủ nhận kết quả đánh giá từ các tiên trình tớ và cập nhật các cá thể trong quần thể
● Bước 4: Lặp tuần tự từ bước 4.1 đến bước 4.5 cho đến khi số thể hệ vượt quá số thế hệ lớn nhất cho phép
• Bước 4.1: Tiến trình chủ thực hiện tìm cá thể tốt nhất trong quần thể hiện tại, cập nhật lời giải tốt nhất hiện tại
• Bước 4.2: Tiến trình chủ thực hiện chọn lựa các cá thể cha mẹ bằng phương pháp chọn theo vòng thi đầu
Bước 4.3 trong quy trình tạo cá thể con bắt đầu bằng việc tiến trình chủ phân chia công việc và gửi các cặp cha mẹ đến các tiến trình tớ Các tiến trình tớ nhận các cặp cá thể từ tiến trình chủ và thực hiện trao đổi chéo dựa trên xác suất đã định Nếu không có thao tác trao đổi chéo, cá thể con sẽ được sao chép nguyên bản từ cá thể mẹ Tiếp theo, các cá thể con mới sẽ trải qua quá trình đột biến theo xác suất đã quy định, sau đó được đánh giá tính thích nghi Cuối cùng, các cặp cá thể con mới sẽ được gửi trở lại cho tiến trình chủ để cập nhật quần thể.
• Bước 4.4: Tiến trình chủ thực hiện tìm cá thể xấu nhất trong quần thể mới
• Bước 4.5: Tiến trình chủ thực hiện thay thế cá thể xấu nhất bằng cá thể tốt nhất của quẩn thể trước
● Bước 5: Tiến trình chủ thực hiện kết xuất lời giải tốt nhất
● Bước 6: Kết thúc thuật toán.
Kết luận
Trong chương hai, bài toán VRPTW được trình bày với hàm mục tiêu là áp dụng thuật toán di truyền GA song song nhằm tối ưu hóa việc định tuyến xe thu gom rác thải trong khu công nghiệp.
Giải thuật di truyền GA song song được lựa chọn vì thao tác chọn lọc liên quan đến tất cả cá thể trong quần thể, trong khi các thao tác lai, đột biến và tính toán tính thích nghi chỉ liên quan đến một hoặc một vài cá thể Điều này giúp tối ưu hóa hiệu suất và khả năng tìm kiếm giải pháp tốt hơn trong quá trình tiến hóa.
42 toàn có thể phân bổ cho các tiến trình khác nhau để thực hiện song song nhằm rút ngắn thời gian tính toán
Giải thuật tham lam (Greedy algorithm) thường không mang lại giải pháp tối ưu toàn cục vì chúng không hoạt động hiệu quả trong mọi trường hợp Việc bám chặt vào một số lựa chọn nhất định quá sớm có thể dẫn đến việc không tìm ra các giải pháp tốt nhất trong giai đoạn sau Do sự hiểu biết hạn chế của học viên và kết quả thử nghiệm chỉ ở quy mô nhỏ, việc đánh giá tính hiệu quả của giải thuật này là tương đối, do đó không nên lựa chọn giải thuật tham lam.
Đề xuất giải pháp ứng dụng thuật toán tối ưu hóa VRPTW vào bài toán định tuyến xe trong thu gom rác thải tại khu công nghiệp, nhằm tìm kiếm kết quả tối ưu Mô hình thực nghiệm dựa trên tác tử được giới thiệu để mô phỏng môi trường gần giống thực tế, tạo cơ sở so sánh giữa kết quả thu được từ mô hình thực nghiệm và kết quả tính toán ở chương tiếp theo.
