Đặt vấn đề VRP là bài toán xác định các lộ trình tối ưu cho đội xe vận chuyển nhằm phục vụ các khách hàng ở các vị trí khác nhau. Đây là bài toán có nhiều ứng dụng trong thực tế từ khâu cung cấp nguyên liệu thô đến khâu phân phối thành phẩm trong các nhà máy sản xuất, các công ty dịch vụ vận chuyển như bưu phẩm, hành khách, … Rõ ràng, chi phí vận chuyển sẽ giảm nếu các xe di chuyển theo các lộ trình tối ưu, từ đó giúp giảm giá thành hàng hóa. Trong thời đại kinh tế xã hội ngày càng phát triển, các yêu cầu của khách hàng ngày càng khắt khe hơn. Tiêu biểu như yêu cầu phải được đáp ứng trong một khoảng thời gian xác định; các công ty hoạt động theo một thời gian biểu chính xác, … Chính vì vậy, vấn đề lập lộ trình VRP với hạn chế thời gian (viết tắt là VRPTW) ngày càng được quan tâm hơn.
Luận văn đặt nghiên cứu trên bài toán VRPTW phù hợp với xu thế phát triển. Hơn thế, VRP là một dạng bài toán NP-khó, do đó, VRPTW cũng thuộc NP-khó. Mục tiêu của VRPTW là tối thiểu số xe vận chuyển và tổng khoảng cách di chuyển khi phục vụ các khách hàng mà không vi phạm các ràng buộc về khả năng chuyên chở của các xe và các cửa sổ thời gian đáp ứng. Để tìm lời giải khả thi cho bài toán, nhiều thuật toán đã được nghiên cứu và ứng dụng như các thuật toán dựa trên quy hoạch động, các thuật toán dựa trên sự nới lỏng Lagrange, các thuật toán dựa trên heurictic,.
Trong đó, các thuật toán heuristic được quan tâm nhiều nhất. Luận văn tiếp cận giải thuật di truyền giải quyết bài toán VRPTW. Đây là giải thuật dựa trên heuristic được ứng dụng rộng rãi trong nhiều bài toán tối ưu thực tế thuộc nhiều lĩnh vực khác nhau. Các thuật toán dựa trên heuristic thường cho các lời giải có tính khả thi cao, gần với lời giải tối ưu của bài toán.
Tuy nhiên, giải thuật phải lặp qua nhiều vòng lặp với nhiều tính toán đòi hỏi nhiều năng lực tính toán của máy tính. Tiêu biểu như thuật toán di truyền phải lặp qua nhiều thế hệ, các thao tác tính toán thực hiện trên từng n 10 cá thể của toàn bộ quần thể. Vì thế, thời gian thực hiện các thuật toán heuristic khá lâu và tiêu tốn nhiều năng lực tính toán của máy tính. Do đó, bên cạnh việc nghiên cứu và áp dụng thuật toán di truyền vào giải bài toán VRP với hạn chế thời gian, luận văn cũng tập trung phát triển thuật toán di truyền song song nhằm nổ lực rút ngắn thời gian tìm lời giải cho bài toán.2 Giới thiệu về VRP Dịch vụ vận chuyển là một khâu quan trọng trong ngành công nghiệp sản xuất.
Đầu tiên, các nguyên liệu thô phải được vận chuyển đến nhà máy từ nhiều nhà cung cấp khác nhau; kế đến, các thành phẩm thường được vận chuyển đến các kho ở các vị trí địa lý khác nhau; Sau đó, từ các kho trung tâm này, các hàng hóa được phân phối đến các khách hàng và thậm chí có thể lấy về các hàng hóa được trả về từ các khách hàng. Cả hai qui trình cung cấp và phân phối đều đòi hỏi khả năng quản lý các phương tiện vận chuyển một cách hiệu quả nhằm tiết kiệm tối đa chi tiêu. Một trong các thước đo hiệu quả nhất cho việc quản lý này chính là hiệu quả của việc lập lộ trình cho các xe vận chuyển. Yêu cầu tối ưu các lộ trình cho các xe với các ràng buộc khác nhau đã phát sinh bài toán lập lộ trình xe vận chuyển - VRP.
Bài toán lập lộ trình đơn giải và nổi tiếng nhất là bài toán người bán hàng (Traveling Salesman Problem - TSP). Người bán hàng phải ghé thăm một số thành phố và sau đó trở về vị trí xuất phát ban đầu. Một lộ trình phải được xây dựng sao cho tối ưu khoảng cách di chuyển. Mở rộng bài toán TSP, m người bán hàng xuất phát tại cùng một địa điểm và phải ghé thăm tất cả thành phố được cho.
Mỗi thành phố phải được thăm chính xác một lần bởi một người bán hàng nào đó. Bài toán cũng tối ưu tổng khoảng cách của các lộ trình. VRP chính là bài toán m-TSP với một đòi hỏi được liên kết với mỗi thành phố và mỗi xe có một khả năng vận chuyển xác định.1 Lời giải với 2 lộ trình của một thể hiện VRP 12 khách hàng (Trong Hình 1.1, ô vuông thể hiện kho hàng trung tâm, các vòng tròn thể hiện các khách hàng được đánh số thứ tự, các mũi tên có hướng thể hiện hướng đi của các lộ trình). Bài toán VRP là dạng bài toán ra quyết định, nhằm tìm các lộ trình tối ưu cho đội xe vận chuyển hàng hóa đến các khách hàng ở các địa điểm khác nhau.
Mục tiêu của bài toán thường là tối thiểu tổng khoảng cách hoặc thời gian di chuyển với nhiều ràng buộc cụ thể như khả năng chuyên chở của xe, khoảng thời gian mong muốn được đáp ứng của khách hàng,. Bài toán VRP thường bao gồm ít nhất hai bài toán con liên quan nhau: • Bài toán phân hoạch: nhằm phân chia tập khách hàng thành các tập con sao cho mỗi tập con chỉ được phục vụ bởi một xe nào đó. • Bài toán định tuyến: nhằm tìm ra lộ trình tối ưu cho mỗi xe vận chuyển. VRP là một vấn đề rộng và có thể bao gồm nhiều vấn đề con ứng với các tình huống và các ràng buộc khác nhau.
Do đó, để đơn giản khi giải quyết bài toán VRP, tùy theo mục tiêu mà người ta thường cụ thể hóa một số ràng buộc phụ. Ví dụ mục tiêu phục vụ khách hàng cao là phải phân phát chính xác, nghĩa là phân phát đúng số lượng, đúng chất lượng, đúng thời gian tại một địa điểm chính xác.3 Các tiêu chuẩn phân loại bài toán VRP Như đã trình bày trên, VRP có nhiều mục tiêu và các ràng buộc khác nhau. Vì thế, trong thực tế có rất nhiều lớp bài toán VRP tùy theo mục tiêu và sự nới lỏng hoặc thêm các ràng buộc. Các tiêu chuẩn sau đây được sử dụng để phân biệt các dạng bài toán VRP khác nhau: STT Đặc tính Tùy chọn − Đơn mục tiêu 1 Số mục tiêu − Đa mục tiêu − Tất cả các nhu cầu của khách hàng đều được đáp ứng.
− Xác định một số khách hàng nên được 2 Ràng buộc nhu cầu phục vụ. − Cho phép tách các phân phối hay không. − Không cửa sổ thời gian. 3 Ràng buộc thời gian − Cửa sổ thời gian một bên hoặc hai bên, cửa sổ thời gian cứng hoặc mềm.
− Một xe phục vụ một lộ trình. 4 Đa sử dụng xe − Một xe có thể phục vụ nhiều hơn một lộ trình. − Đoàn xe vận chuyển đồng nhất. 5 Thuộc tính của đoàn xe − Đoàn xe vận chuyển không đồng nhất.
− Một kho trung tâm chứa hàng hóa. 6 Số kho − Nhiều kho hàng hóa. n 13 STT Đặc tính Tùy chọn − Lộ trình đóng 7 Loại lộ trình − Lộ trình mở − Khoảng thời gian phân phối đơn 8 Thời gian hoạch định − Xác định khách hàng nào nên được phục vụ tại thời điểm nào của hoạch định. − Kiểu phục vụ đơn: hoặc phân phối hoặc lấy và mang hàng hóa trở về.
9 Kiểu phục vụ − Kiểu phục vụ hỗn hợp: vừ a có phân phối, vừa có mang về.4 Một số dạng chính của bài toán VRP 1.1 VRP với hạn chế khả năng chở hàng hóa VRP với hạn chế khả năng chở hàng hóa của xe (Capaciated vehicle routing problem – CVRP) là một dạng bài toán VRP nhưng có thêm ràng buộc mỗi xe đều có khả năng chuyên chở như nhau đối với một hàng hóa đơn nào đó và tổng tải của mỗi xe không vượt quá khả năng của nó. Mục tiêu của bài toán CVRP là tối thiểu số xe và tổng thời gian di chuyển, đồng thời tổng số lượng hàng hóa được gán cho mỗi lộ trình không vượt quá khả năng của xe phục vụ lộ trình đó. Như vậy, lời giải cho bài toán CVRP giống như lời giải của bài toán VRP nhưng có thêm hạn chế tổng nhu cầu của tất cả khách hàng cần được phục vụ trên lộ trình Rt không vượt quá khả năng xe Q. m ∑d ≤ Q i =1 i Trong đó: n 14 m: tổng số khách hàng được gán trên lộ trình Rt.
di: nhu cầu của khách hàng thứ i trên lộ trình. Q : khả năng của xe.2 Ví dụ VRP với hạn chế khả năng có 3 lộ trình 1.2 VRP với hạn chế thời gian VRP với hạn chế thời gian (vehicle routing problem with time windows – VRPTW) là mở rộng của bài toán CVRP bằng cách đưa thêm ràng buộc cửa sổ thời gian. Cửa sổ thời gian của một khách hàng là khoảng thời gian mong muốn được đáp ứng của khách hàng đó. Cửa sổ thời gian [e i, li] của khách hàng thứ i qui định rằng xe vận chuyển: • Phải không đến địa điểm khách hàng thứ i trước thời điểm e i hoặc phải chờ nếu nó đến ở thời điểm ti < ei.
• Phải không đến địa điểm khách hàng thứ i sau thời điểm l i ≥ ei. Bài toán VRPTW là dạng bài toán xác định nhiều mục tiêu, bao gồm: 1. Tối thiểu số lộ trình hay số xe. Tối thiểu tổng khoảng cách di chuyển.
Tối thiểu tổng thời gian cần cho các xe, kể cả thời gian chờ. n 15 Tùy theo giá trị ei , li trong cửa sổ thời gian [ei, l i ], có một số dạng cửa sổ thời gian sau: • Cửa sổ thời gian hai bên nếu 0 < e i ≤ li < ∞. • Cửa sổ thời gian một bên nếu e i = -∞ hoặc li = ∞. • Cửa sổ thời gian hai bên cứng nếu một lời giải được xem là không khả thi trong trường hợp một xe đến trước thời điểm ei hoặc sau thời điểm li tại nút i.
• Cửa sổ thời gian một bên cứng nếu một xe không đến trễ hơn l i tại nút i hoặc phải chờ nếu nó đến sớm hơn thời điểm e i tại nút i. • Cửa sổ thời gian mềm nếu thời điểm đến của xe không ảnh hưởng đến tính khả thi của lời giải, nhưng bị phạt bằng cách cộng thêm một giá trị vào hàm mục tiêu. ρ e max{0, ei − ti} + ρ l max{0, ti − li} Với ρ e ≥ 0 và ρ l ≥ 0 là các hằng số giá trị phạt cho trước.