Luận Văn Thuật giải Large Neighborhood Search và Simulated Annealing cho một biến thể thực tế của bài toán Ve

1. Giới thiệu tổng quan1.1. Giới thiệu bài toán Vehicle Routing (Vehicle Routing Problem – VRP)Bài toán Vehicle Routing Problem - gọi tắt là VRP là bài toán mà trong đó ta có sẵn một tập các xe và một tập các khách hàng, mỗi khách hàng yêu cầu một số lượng hàng nhất định, yêu cầu của bài toán là phải phân phối hàng và tìm đường đi cho các xe dựa trên một số mục tiêu cho trước sao cho tất cả các khách hàng đều phải được giao hàng, một trong những mục tiêu phổ biến nhất là cực tiểu hóa tổng thời gian vận chuyển của tất cả các xe. Bài toán quen thuộc người đưa thư (Travelling Salesman Problem - gọi tắt là TSP) chính là một trường hợp đặc biệt của bài toán VRP với một xe giao hàng duy nhất (chính là người đưa thư).
Bài toán VRP và các biến thể của nó đều thuộc lớp các bài toán NP khó. Đây là một trong những bài toán có ứng dụng thực tế rất rộng lớn và đã nhận được sự quan tâm, nghiên cứu của rất nhiều nhà khoa học trên thế giới trong suốt 50 năm qua. Trong bài toán này, các xe (vehicle) xuất phát từ các kho hàng (depot) và đi giao hàng cho các khách hàng (customer), sau đó quay trở về lại kho hàng. Một số khái niệm chính của bài toán gồm:
- Xe (vehicle): các phương tiện dùng để chuyên chở hàng, có thể có nhiều loại xe khác nhau, chẳng hạn như xe tải nhỏ, xe tải lớn, xe gắn máy, . Các khái niệm gắn liền với loại xe bao gồm: sức chứa của xe (capacity), chi phí vận chuyển (gồm hai loại thông dụng: chi phí cố định - fixed cost - là chi phí cần thiết để xe có thể khởi hành, nó không phụ thuộc vào độ dài quãng đường mà xe phải đi; chi phí động - variable cost là chi phí tiêu tốn trên từng đơn vị quãng đường mà xe phải đi), quãng đường tối đa mà xe có thể đi trong một ngày (route length), loại mặt hàng (commodit type) mà xe có thể chở,
- Kho hàng (depot): là nơi chứa hàng hóa, các xe sẽ lấy hàng tại kho để đi giao hàng cho các khách hàng, sau khi giao xong, xe sẽ quay trở về lại kho hàng
- Khách hàng (customer): khách hàng có thể chỉ nhận hàng do xe giao tới, nhưng cũng có thể vừa nhận hàng (linehaul customer), vừa lấy hàng (backhaul customer). Các khái niệm đi kèm với khách hàng gồm: số lượng hàng mà khách yêu cầu (demand), loại mặt hàng mà khách yêu cầu (commodity type), khoảng thời gian (time window) mà khách hàng cho phép xe đến giao hàng (ví dụ: khoảng thời gian của khách hàng A là [2p.m, 4p.m] nghĩa là khách hàng A chỉ cho phép xe đến giao hàng (hoặc lấy hàng) trong khoảng thời gian từ 2p.m đếm 4p.m, thời gian thực hiện việc giao (nhận) hàng (service time), .
- Tuyến đường (route): tuyến đường của một xe là một chu trình, với điểm xuất phát và điểm kết thúc là kho hàng của xe, các điểm thành phần của chu trình tương ứng với các khách hàng mà xe ghé qua để giao (lấy) hàng.
1.2. Các biến thể của bài toán VRPBài toán VRP có rất nhiều biến thể khác nhau dựa trên yêu cầu cụ thể của các bài toán thực tế. Các biến thể này đã tạo thành các nhánh nghiên cứu khác nhau, tất nhiên các phương pháp giải quyết các biến thể cũng có thể được chỉnh sửa để áp dụng qua lại lẫn nhau. Một số biến thể quan trọng của bài toán VRP bao gồm:
- Bài toán VRP với khoảng cách bất đối xứng (Asymmetric VRP, gọi tắt là AVRP): bài toán VRP mà trong đó, đồ thị biểu diễn đường đi là một đồ thị có hướng. Hầu hết các bài toán VRP trong thực tế đều thuộc dạng này.
- Bài toán VRP với nhiều kho hàng (Multi-Depot VRP, gọi tắt là MDVRP): bài toán với nhiều kho hàng khác nhau, mỗi xe sẽ phụ thuộc vào một kho hàng duy nhất, được gọi là kho hàng chủ (home depot) của xe.
- Bài toán VRP với ràng buộc sức chứa (Capacitated Vehicle Routing Problem, gọi tắt là CVRP): trong bài toán này, mỗi loại xe có một sức chứa (capacity) khác nhau, yêu cầu bài toán là phải tìm đường đi cho các xe sao cho tổng lượng hàng mà xe phải chở trong một tuyến đường không được vượt quá sức chứa của xe. Nếu thay ràng buộc sức chứa bằng ràng buộc về độ dài tối đa của quãng đường mà mỗi xe đi, ta có một biến thể khác, đó là bài toán DVRP (Distance-Constrained VRP): gắn với mỗi loại xe là một tham số thể hiện độ dài quãng đường tối đa mà mỗi xe có thể đi. Yêu cầu bài toán là phải tìm đường đi cho các xe sao cho tổng quãng đường mà mỗi xe phải đi không được vượt quá tham số này.
- Bài toán VRP với ràng buộc khoảng thời gian (VRP with Time Windows, gọi tắt là VRPTW): trong bài toán này, mỗi khách hàng sẽ chỉ cho phép xe đến giao hàng trong một khoảng thời gian cho phép (time windows) nhất định, khoảng thời gian này được biểu diễn bởi đoạn [a[SUB]i[/SUB], b[SUB]i[/SUB]] (tương ứng với khách hàng thứ i), nếu xe đến giao hàng cho khách hàng thứ i vào trước thời điểm a[SUB]i[/SUB], xe sẽ phải đứng chờ cho đến thời điểm a[SUB]i[/SUB] mới được giao hàng, đồng thời việc giao hàng của xe cho khách hàng thứ i cần kết thúc trước thời điểm b[SUB]i[/SUB].
- Bài toán VRP với yêu cầu giao và nhận hàng (VRP Pickup and Delivery, gọi tắt là VRPPD): bài toán này cho phép xe thực hiện cả hai chức năng - lấy hàng (pickup) từ một số khách hàng và đem đi giao (delivery) cho khách hàng khác, bài toán này thường áp dụng cho các dịch vụ vận chuyển hàng, trong đó, khách hàng sẽ yêu cầu xe đến chỗ mình để nhận hàng và giao đến cho người nhận (một khách hàng khác). Khi đó, tất nhiên xe phải đến gặp khách hàng thứ nhất để lấy hàng trước, rồi mới có hàng để giao đến cho người nhận. Như vậy, trong bài toán này sẽ có thêm một loại ràng buộc mới: ràng buộc thứ tự đến gặp khách hàng (precedence constraint). Các xe phải tuân thủ thứ tự này, nghĩa là phải gặp khách hàng đặt giao hàng trước, rồi mới được đến gặp khách hàng cần nhận hàng.
- Bài toán VRP với yêu cầu giao hàng trước (VRP with Backhauls, gọi tắt là VRPB): tương tự như bài toán VRPPD, bài toán này cũng cho phép xe giao hàng và nhận hàng, nhưng có một chút khác biệt: xe không đến gặp khách hàng để lấy hàng rồi giao cho khách hàng khác nữa mà ràng buộc thứ tự gặp khách hàng ở đây sẽ là: xe phải đi giao hàng cho tất cả các khách hàng cần nhận (Linehaul customers) trước, rồi sau đó mới đến gặp các khách hàng cần giao (Backhaul customers) để lấy hàng đem về kho. Wade và Salhi [10]đã đề nghị một biến thế khác của bài toán VRPB, trong đó, xe không cần phải giao hết hàng rồi mới được nhận hàng, mà có thể nhận hàng sớm hơn (tại một thời điểm nào đó trong lúc giao hàng, thời điểm này được xác định dựa trên kinh nghiệm của tài xế, trạng thái hàng của xe tại thời điểm đó, ).
- Bài toán VRP cho phép một xe đi nhiều chuyến (bài toán này có rất nhiều tên gọi khác nhau, bao gồm: VRP with multiple use of vehicles, VRP with multi-trips, VRP with multiple trips, VRP with multiple vehicle trips, gọi tắt chung là VRPM): trong bài toán này, mỗi xe có thể chạy nhiều hơn một tuyến đường, nghĩa là một chiếc xe có thể xuất phát từ kho hàng, đi giao hàng, quay trở về kho hàng và lại lấy hàng đi giao tiếp cho đến khi tổng thời gian giao hàng của xe chạm mức cho phép.
- Bài toán VRP cho phép chia nhỏ đơn hàng (VRP with split delivery) [13]: trong bài toán này, mỗi đơn đặt hàng của khách hàng được phép phân nhỏ ra thành các đơn đặt hàng với số lượng nhỏ hơn, khi đó, một khách hàng có thể được giao hàng bởi nhiều hơn một xe. Khi các đơn đặt hàng của các khách hàng có kích thước quá lớn, việc chia nhỏ các đơn đặt hàng này ra sẽ giúp tận dụng được tối đa sức chứa của xe.
- Bài toán VRP với nhiều loại xe khác nhau [11]: là bài toán với tập các loại xe có sức chứa và chi phí vận chuyển khác nhau. Bài toán này có hai biến thể con, gồm: