I. Tổng Quan Về Tối Ưu Giải Đề Thi ĐH Quốc Gia HN 2019
Bài toán định tuyến xe (VRP) liên quan trực tiếp tới việc vận chuyển, giao hàng của một công ty. Bài toán yêu cầu tìm đường đi tối ưu cho các xe chở hàng xuất phát từ một hoặc nhiều kho hàng để giao hàng cho một tập khách hàng cho trước. Có nhiều tiêu chuẩn tối ưu, nhưng thông dụng nhất vẫn là tối thiểu hóa chi phí vận chuyển hoặc tổng độ dài quãng đường di chuyển của các xe. Thống kê cho thấy, chi phí vận chuyển chiếm tỉ trọng lớn trong một sản phẩm (10%). Do đó, mọi chi phí tiết kiệm được bằng cách giải tốt VRP cho dù nhỏ hơn 5%, đều có ý nghĩa lớn. Bài toán VRP cũng có nhiều ý nghĩa trong khoa học, bài toán đã được chứng minh là NP-khó. Do đó những thuật toán chính xác dùng để giải chúng chỉ có thể giải được bài toán với kích thước nhỏ. Để giải được bài toán với kích thước lớn, đã có nhiều công trình nghiên cứu áp dụng các phương pháp metaheuristic cho bài toán VRP, ví dụ như dùng giải thuật di truyền (GA – genetic algorithm), tìm kiếm Tabu (Tabu search), thuật toán luyện kim (Simulated annealing).
1.1. Bài Toán VRP và Các Khái Niệm Liên Quan
Bài toán định tuyến xe (VRP) thuộc lớp bài toán tối ưu tổ hợp, quan tâm tới việc vận chuyển hàng hóa từ một hoặc nhiều kho hàng tới một tập các khách hàng. Bài toán VRP được đề xuất lần đầu tiên bởi Dantzig và Ramser vào năm 1959, trong đó tác giả giới thiệu một bài toán thực tiễn về việc di chuyển xăng tới các trạm xăng. Với số lượng xe chở xăng cùng với dung lượng chứa của chúng được biết trước, tác giả muốn tìm cách di chuyển các xe chở xăng tới các trạm xăng sao cho mỗi trạm xăng được đến đúng một lần, tổng lượng xăng chuyển cho trạm xăng được thăm bởi một xe không vượt quá dung lượng chứa của xe đó, và đồng thời quãng đường di chuyển của các xe là nhỏ nhất có thể. Bài toán này là dạng đơn giản nhất của lớp các bài toán VRP, và sẽ được định nghĩa chi tiết ở mục 1.3.
1.2. Tầm Quan Trọng Của Việc Tối Ưu Vận Tải
Logistics tiêu tốn rất nhiều tài nguyên về con người cũng như nhiên liệu. Thống kê cho thấy logistics chiếm tới 10% GDP của châu Âu trong thập kỷ qua. Vận tải là một khâu quan trọng nhất trong khâu phân phối, chiếm tới 50% chi phí logistics (Zhu and Zhai 2017). Theo thống kê, chi phí vận chuyển sau thành 10% chi phí tạo ra một sản phẩm (Rodrigue, Comtois, and Slack 2016). Bài toán định tuyến xe - VRP (Vehicle Routing Problem) là một lớp các bài toán quan tâm tới việc tìm cách định tuyến các xe chở hàng để vận chuyển hàng hóa từ một hoặc nhiều kho hàng tới các địa điểm cần vận chuyển đến. Bài toán VRP liên quan trực tiếp tới việc vận chuyển, phân phối hàng hóa cho nên nghiên cứu nó có ứng dụng lớn trong việc giảm chi phí logistics.
II. Phương Pháp Giải Nhanh Đề Thi ĐH QGHN 2019 Phân Tích
Các phương pháp giải bài toán VRP nói riêng và các bài toán thuộc lớp NP-khó nói chung có thể được chia làm ba loại: Thuật toán chính xác, Heuristic và Metaheuristic. Với kích thước dữ liệu đầu vào bài toán VRP ngày càng trở nên ngày một lớn hơn, các thuật toán heuristic và metaheuristic phổ biến hơn so với thuật toán chính xác. Đặc biệt, metaheuristic đang là xu hướng nghiên cứu chính.
2.1. Thuật Toán Chính Xác Ưu Điểm và Hạn Chế
Thuật toán chính xác đảm bảo lời giải tối ưu sẽ được tìm thấy trong một khoảng thời gian hữu hạn. Tuy nhiên, thời gian chạy của nó trong trường hợp xấu nhất là rất lớn, do đó lớp thuật toán này chỉ giải được những bài toán có kích thước nhỏ hoặc vừa.
2.2. Heuristic Tìm Kiếm Lời Giải Gần Đúng
Heuristic có thể hiểu là một định hướng tìm kiếm lời giải. Các thuật toán heuristic thường cho ra được lời giải hợp lệ với chất lượng chấp nhận được trong thời gian ngắn.
2.3. Metaheuristic Khung Giải Quyết Bài Toán Phức Tạp
Thuật toán metaheuristic là một framework, sử dụng định hướng heuristic để tìm kiếm lời giải. Nói đơn giản, metaheuristic thực chất là heuristic với cách thức sử dụng định hướng tìm kiếm một cách thông minh, phức tạp hơn. Một heuristic khi áp dụng được với một lớp bài toán cụ thể, còn một metaheuristic có thể áp dụng được với nhiều lớp bài toán.
III. Bí Quyết Ôn Thi ĐH QGHN 2019 Chiến Lược Làm Bài
Heuristic có thể được chia làm hai loại: Heuristic xây dựng và Heuristic cải tiến. Heuristic xây dựng xây dựng lời giải bằng cách bắt đầu từ lời giải rỗng, sau đó từng bước thêm vào lời giải một thành phần hợp lý nhất cho đến khi lời giải hợp lệ hình thành. Dưới đây là một số heuristic xây dựng cho bài toán VRP.
3.1. Thuật Toán Tiết Kiệm Saving Algorithm
Thuật toán tiết kiệm (saving algorithm) (Clarke and Wright 1964) là heuristic nổi tiếng và lâu đời nhất. Thuật toán này rất hay được dùng để tìm lời giải ban đầu bởi tốc độ nhanh và kết quả tốt của nó. Thuật toán sẽ tính saving(i, j) với mọi cặp khách hàng (i, j) là chi phí tiết kiệm được khi nối hai tuyến xe, một là r1 thăm khách hàng i cuối cùng, một là r2 được khách hàng j đầu tiên. Ta có công thức saving(i, j) = d0i + d0j − di j. Sau đó, từng cặp khách hàng (i, j) được duyệt theo saving(i, j) giảm dần.
3.2. Thuật Toán Quét Góc Sweep Algorithm
Thuật toán quét góc (sweep algorithm) (Renaud and Boctor 2002) bao gồm hai giai đoạn. Đầu tiên là phân cụm (cluster), các khách hàng thuộc cùng một tuyến xe sẽ thuộc cùng một cụm. Tiếp theo, áp dụng bài toán TSP cho từng cụm. Giai đoạn phân cụm như sau. Giả sử các vị trí của khách hàng và nhà kho có thể biểu diễn trên mặt phẳng tọa độ Oxy. Sẽ có một tia có gốc trùng với gốc tọa độ. Tia này sẽ quét một vòng tròn. Khi tia “thăm” một khách hàng i, nếu có thể thêm i vào cụm hiện tại r mà vẫn đảm bảo điều kiện về dung lượng xe, ta sẽ thêm i vào r. Sau khi tia quét một vòng tròn, ta thu được một phân cụm các khách hàng.
IV. Kinh Nghiệm Giải Đề Thi ĐH QGHN 2019 Tối Ưu Thời Gian
Heuristic cải tiến còn được gọi là tìm kiếm địa phương (local search). Heuristic này xây dựng lời giải bằng cách bắt đầu từ một lời giải tối, sau đó từng bước cải tiến lời giải hiện tại bằng cách thay đổi một số thành phần của lời giải cũ. Lời giải thu được bằng cách thay đổi một số thành phần được gọi là kề nhau, hay là láng giềng với lời giải cũ. Các cách thức cải tiến lời giải thường là thay đổi thành phần trong một tuyến xe hoặc tráo đổi/thay đổi các thành phần trong một tập tuyến xe.
4.1. Cải Thiện Tuyến Đường Thay Đổi Thứ Tự Khách Hàng
Ví dụ, một khách hàng có thể bị chuyển sang tuyến xe khác, hai khách hàng ở hai tuyến xe có thể bị tráo đổi, hay thứ tự thăm khách hàng trên một tuyến xe bị thay đổi, v.v...
4.2. Tối Ưu Hóa Đa Tuyến Trao Đổi Khách Hàng Giữa Các Tuyến
Việc trao đổi khách hàng giữa các tuyến giúp cân bằng tải và giảm tổng quãng đường di chuyển. Cần xem xét kỹ các ràng buộc về dung lượng và thời gian khi thực hiện trao đổi.
V. Ứng Dụng Thực Tế Nghiên Cứu Giải Đề ĐH QGHN 2019
Nhận thấy ứng dụng thực tiễn to lớn của lớp bài toán VRP, luận văn này nghiên cứu, tìm hiểu bài toán CVRP (một bài toán đơn giản nhất của lớp VRP) và các phương pháp giải chúng đã được công bố, đồng thời đề xuất một thuật toán tối ưu đàn kiến để giải bài toán CVRP. Luận văn sẽ được tổ chức thành 4 chương như sau:
5.1. Giới Thiệu Tổng Quan Về Bài Toán VRP
Chương đầu tiên, chương này, là phần mở đầu, giới thiệu lớp bài toán VRP và ứng dụng to lớn của nó trong thực tiễn. Bài toán đơn giản nhất thuộc lớp VRP là CVRP cũng sẽ được phát biểu thật chi tiết. Đồng thời, một số biến thể khác của CVRP cũng được giới thiệu sơ qua.
5.2. Các Phương Pháp Giải Bài Toán CVRP
Chương hai giới thiệu một số phương pháp đã được áp dụng trước đó để giải bài toán CVRP.
5.3. Thuật Toán Tối Ưu Hóa Đàn Kiến
Chương ba trình bày thuật toán tối ưu hóa đàn kiến đề xuất để giải bài toán CVRP.
VI. Kết Luận Hướng Phát Triển Nghiên Cứu Đề Thi ĐH QGHN
Cuối cùng, chương bốn là phần kết quả thực nghiệm của thuật toán đề xuất, đưa ra kết luận và lên kế hoạch những công việc cần làm, phát triển trong tương lai.
6.1. Đánh Giá Kết Quả Thực Nghiệm
Phân tích và so sánh hiệu quả của thuật toán đề xuất với các phương pháp khác đã được công bố.
6.2. Hướng Phát Triển Trong Tương Lai
Đề xuất các hướng nghiên cứu tiếp theo để cải thiện thuật toán và áp dụng cho các bài toán VRP phức tạp hơn.
