Luận văn Thạc sĩ Khoa học: Thuật toán di truyền song song giải bài toán VRP (Vehicle Routing Problem) với hạn chế thời gian

Chia sẻ: Sơ Dương | Ngày: | Loại File: PDF | Số trang:84

Thêm vào BST

Báo xấu

40
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài "Thuật toán di truyền song song giải bài toán VRP (Vehicle Routing Problem) với hạn chế thời gian" tập trung giải quyết bài toán lập lộ trình xe vận chuyển với hạn chế thời gian – VRPTW, được ứng dụng nhiều trong dịch vụ vận chuyển. Mục tiêu bài toán 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Thuật toán di truyền song song giải bài toán VRP (Vehicle Routing Problem) với hạn chế thời gian

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------   -------- Nguyễn Việt Hân THUẬT TOÁN DI TRUYỀN SONG SONG GIẢI BÀI TOÁN VRP (VEHICLE ROUTING PROBLEM) VỚI HẠN CHẾ THỜI GIAN LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2009
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------- NGUYỄN VIỆT HÂN Nguyễn Việt Hân THUẬT TOÁN DI TRUYỀN SONG SONG GIẢI BÀI TOÁN VRP (VEHICLE ROUTING PROBLEM) VỚI HẠN CHẾ THỜI GIAN LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN 2007 - 2009 NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN ĐỨC NGHĨA Hà nội Hà Nội – Năm 2009 2009
2 Lời cảm ơn Trước tiên, em xin gửi lời cảm ơn chân thành đến Thầy PGS. TS. Nguyễn Đức Nghĩa đã định hướng nghiên cứu và góp ý cho em để có được luận văn hoàn chỉnh. Em xin cảm ơn Quý Thầy cô trong Khoa, với lòng nhiệt huyết, đã vun đắp nền tảng tri thức vững chắc cho các thế hệ học viên. Đây sẽ là hành trang vô giá cho chúng em trên con đường nghiên cứu khoa học. Nhân đây, con xin gửi lời biết ơn đến cha mẹ đã vất vả nuôi nấng và tạo mọi điều kiện để con có được như ngày hôm nay. Xin cảm ơn em, người vợ luôn lo lắng, chia sẻ và động viên anh vượt qua những khó khăn, thử thách. Sau cùng, không thể thiếu lời cảm ơn đến các anh chị đồng nghiệp đã trao đổi, khích lệ và dành thời gian nhiều hơn cho tôi để hoàn thành tốt luận văn.
3 Mục lục Lời cảm ơn ................................................................................................................. 2 Mục lục ....................................................................................................................... 3 Chương 1: Giới thiệu ............................................................................................. 9 1.1 Đặt vấn đề ..................................................................................................... 9 1.2 Giới thiệu về VRP ...................................................................................... 10 1.3 Các tiêu chuẩn phân loại bài toán VRP ...................................................... 12 1.4 Một số dạng chính của bài toán VRP ......................................................... 13 1.4.1 VRP với hạn chế khả năng chở hàng hóa ...........................................13 1.4.2 VRP với hạn chế thời gian ..................................................................14 1.4.3 VRP với nhiều kho hàng hóa ..............................................................15 1.4.4 VRP định kỳ ........................................................................................16 1.4.5 VRP mở ...............................................................................................17 1.4.6 VRP tách phân phối ............................................................................17 1.4.7 VRP với khả năng chuyên chở về .......................................................17 1.4.8 VRP với khả năng nhặt và phân phối .................................................18 1.5 Tối ưu tổ hợp .............................................................................................. 19 Chương 2: Bài toán VRP với hạn chế thời gian ................................................ 20 2.1 Định nghĩa .................................................................................................. 20 2.2 Mô hình toán học ........................................................................................ 20 2.3 Các cấu trúc vùng lân cận........................................................................... 23 2.4 Các phương pháp chính tiếp cận giải bài toán ........................................... 26 2.4.1 Các phương pháp chính xác................................................................26 2.4.1.1 Dựa trên quy hoạch động ................................................................26 2.4.1.2 Dựa trên phát sinh cột .....................................................................26 2.4.1.3 Dựa trên phân rã Lagrange..............................................................26 2.4.1.4 Dựa trên K-Tree ..............................................................................27
4 2.4.2 Các phương pháp heuristic .................................................................27 2.4.2.1 Nguyên lý ........................................................................................27 2.4.2.2 Heuristic xây dựng lộ trình..............................................................28 2.4.2.3 Heuristic cải thiện lộ trình...............................................................29 Chương 3: Thuật toán di truyền song song ....................................................... 35 3.1 Giới thiệu về thuật toán di truyền ............................................................... 35 3.2 Các phép toán chính của thuật toán di truyền ............................................ 36 3.2.1 Phép chọn ............................................................................................36 3.2.2 Phép lai................................................................................................37 3.2.3 Phép đột biến.......................................................................................39 3.3 Các mô hình song song .............................................................................. 40 3.3.2 Song song dạng chủ tớ ........................................................................41 3.3.3 Song song dạng đa quần thể con có di trú ..........................................42 3.3.4 Song song dạng quần thể con chồng lấp, không di trú .......................44 3.3.5 Thuật toán di truyền song song khối lớn ............................................45 3.3.6 Song song dạng các nhóm cá thể động ...............................................45 3.3.7 Thuật toán song song trạng thái ổn định .............................................46 3.3.8 Thuật toán song song hỗn tạp .............................................................46 3.3.9 Các phương pháp lai ...........................................................................46 Chương 4: Thuật toán di truyền song song giải bài toán VRP với hạn chế thời gian ............................................................................................................. 48 4.1 Heuristic xây dựng lộ trình ......................................................................... 48 4.2 Thuật toán di truyền giải bài toán VRPTW................................................ 52 4.2.1 Biểu diễn nhiễu sắc thể .......................................................................52 4.2.2 Tạo quần thể ban đầu ..........................................................................53 4.2.3 Đánh giá tính thích nghi ......................................................................54 4.2.4 Các thao tác di truyền .........................................................................55 4.2.4.1 Chọn lọc ..........................................................................................55 4.2.4.2 Tái tổ hợp ........................................................................................56
5 4.2.5 Tạo thế hệ mới ....................................................................................57 4.3 Thuật toán di truyền song song giải bài toán VRPTW .............................. 59 Chương 5: Hiện thực và đánh giá chương trình ............................................... 63 5.1 Các vấn đề hiện thực .................................................................................. 63 5.1.1 Cấu trúc dữ liệu biểu diễn lộ trình và lời giải .....................................63 5.1.2 Hai chiến lược khởi tạo quần thể ban đầu...........................................64 5.1.3 Một số kỹ thuật song song hóa ...........................................................65 5.2 Đánh giá kết quả ......................................................................................... 67 5.2.1 Phương pháp đánh giá.........................................................................67 5.2.2 Kết quả thực hiện ................................................................................68 5.2.3 Các nhận xét........................................................................................76 Chương 6: Kết luận và hướng phát triển ........................................................... 77 6.1 Các kết luận ................................................................................................ 77 6.2 Hướng phát triển......................................................................................... 77 Tài liệu tham khảo .................................................................................................. 78 Tóm tắt ..................................................................................................................... 82 Abstract .................................................................................................................... 83
6 Danh sách các từ viết tắt GA Genetic Algorithm PGA Parallel Genetic Algorithm MIMD Multiple Instruction Multiple Data VRP Vehicle Routing Problem VRPTW Vehicle Routing Problem with Time Window PFIH Push-Forward Insertion Heuristic LSD λ-Interchange Local Search Descent TSP Travelling Salesman Problem ACS Ant Colony System ACO Ant Colony Optimization MACS- Multiple Ant Colony System for Vehicle Routing Problems with VRPTW Time Windows PMX Partially Mapped Crossover
7 Danh sách các hình Hình 1.1 Lời giải với 2 lộ trình của một thể hiện VRP 12 khách hàng.................11 Hình 1.2 Ví dụ VRP với hạn chế khả năng có 3 lộ trình .......................................14 Hình 1.3 Ví dụ VRP với 3 kho hàng hóa ...............................................................16 Hình 1.4 Ví dụ VRP với khả năng nhặt và phân phối ...........................................18 Hình 2.1 Ví dụ về một trao đổi Or-Opt .................................................................23 Hình 2.2 Ví dụ về một trao đổi 2-Opt*..................................................................24 Hình 2.3 Minh họa thao tác relocate ......................................................................24 Hình 2.4 Minh họa thao tác trao đổi (exchange) ...................................................25 Hình 2.5 Kiến trúc của MACS-VRPTW ...............................................................33 Hình 3.1 Các khái niệm cơ bản của thuật toán di truyền.......................................35 Hình 3.2 Vòng quay lựa chọn cá thể .....................................................................36 Hình 3.3 Thao tác trao đổi chéo một điểm cắt.......................................................38 Hình 3.4 Thao tác trao đổi chéo nhiều điểm cắt ....................................................38 Hình 3.5 Một số loại đột biến thường gặp .............................................................39 Hình 3.6 Phân loại các thuật toán di truyền song song .........................................41 Hình 3.7 Mô hình song song dạng chủ tớ..............................................................42 Hình 3.8 Lược đồ thuật toán di truyền song song kết mịn. Lớp thuật toán này có một quần thể được phân tán từng phần và được hiện thực rất hiệu quả trên các máy tính song song lớn. ....................................................................................................44 Hình 3.9 Các hình thức kết hợp phân cấp .............................................................46 Hình 4.1 Chọn cá thể theo vòng thi đấu ................................................................56 Hình 4.2 Mô hình giải thuật song song dạng chủ tớ..............................................60 Hình 5.1 Minh họa cấu trúc danh sách liên kết biểu diễn một lộ trình .................63 Hình 5.2 Minh họa cấu trúc dữ liệu lời giải cho VRPTW.....................................64 Hình 5.3 Hệ thống cluster thử nghiệm ..................................................................69 Hình 5.4 Biểu đồ biểu diễn giá trị Speedup theo số tiến trình trong từng phân nhóm ................................................................................................................75
8 Danh sách các bảng Bảng 5.1 Bảng so sánh kết quả trung bình từ các kết quả tốt nhất giữa các phương pháp và kết quả tốt nhất được biết ...............................................................70 Bảng 5.2 Bảng chi tiết so sánh thời gian trung bình khi thực thi tuần tự so với thời gian trung bình khi thực thi song song ứng với số tiến trình khác nhau và theo từng tập tin mẫu.........................................................................................................71 Bảng 5.3 Bảng tổng hợp so sánh thời gian trung bình thực thi tuần tự và song song trong mỗi nhóm dữ liệu ....................................................................................74 Bảng 5.4 Bảng Speedup trung bình của chương trình thực thi song song tính theo từng nhóm mẫu..................................................................................................74
9 Chương 1: Giới thiệu 1.1 Đặ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
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. 1.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.
11 Hình 1.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.
12 1.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.
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ề. 1.4 Một số dạng chính của bài toán VRP 1.4.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 i =1 i ≤Q Trong đó:
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. Hình 1.2 Ví dụ VRP với hạn chế khả năng có 3 lộ trình 1.4.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. 2. Tối thiểu tổng khoảng cách di chuyển. 3. Tối thiểu tổng thời gian cần cho các xe, kể cả thời gian chờ.
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. 1.4.3 VRP với nhiều kho hàng hóa VRP với nhiều kho hàng hóa (multi-depot vehicle routing problem – MDVRP) cũng là mở rộng của CVRP bằng cách xem xét nhiều kho hàng hóa chứ không phải chỉ một kho trung tâm như các dạng trên. Ngoài việc gán các khách hàng tới các xe vận chuyển và xác định các lộ trình cho các xe, bài toán có thêm một mức xác định nữa là gán các lộ trình (hoặc các khách hàng) đến các kho.
16 Hình 1.3 Ví dụ VRP với 3 kho hàng hóa 1.4.4 VRP định kỳ VRP định kỳ (periodic vehicle routing problem – PVRP) là mở rộng bài toán VRP bằng cách mở rộng thời gian hoạch định thành vài ngày, một tuần, ... thay vì chỉ một ngày. Trong khoảng thời gian chính xác này, mỗi khách hàng phải được ghé thăm ít nhất một lần. Như vậy, bài toán cần phải xác định thêm những khách hàng nào nên được đáp ứng vào những ngày nào để tối ưu tổng chi phí (bao gồm số xe, tổng thời gian và tổng khoảng cách). Mỗi khách hàng cho biết trước tần số phục vụ f i (số lần) và nhu cầu d i > 0 cho mỗi lần phân phối hàng hóa. Vấn đề bài toán là tạo ra một nhóm các lộ trình cho mỗi ngày sao cho các ràng buộc liên quan được thỏa mãn và tổng chi phí được tối ưu. PVRP được xem như bài toán tối ưu tổ hợp đa mức: • Mức thứ nhất: mục tiêu tạo ra một nhóm các lựa chọn khả thi (các tổ hợp) cho mỗi khách hàng. Ví dụ: nếu khoảng thời gian hoạch định là t = 3 ngày {d1, d2, d3} thì các tổ hợp có thể là 0000; 1001; 2010; 3011;4100; 5101; 6110; 7111. Nếu khách hàng đòi hỏi ghé thăm hai lần thì khách hàng này có các lựa chọn lịch ghé thăm sau: {d1, d2}, {d1, d3}, {d 2, d3}.
17 • Mức thứ hai: chọn ra một trong các lựa chọn cho mỗi khách hàng sao cho các ràng buộc theo ngày được thỏa mãn. Vì vậy, cần chọn ra các khách hàng phải được ghé thăm mỗi ngày. • Mức thứ ba: giải bài toán VRP cho mỗi ngày. 1.4.5 VRP mở VRP mở (Open vehicle routing problem – OVRP) giả định một lộ trình kết thúc ngay khi khách hàng cuối cùng trên lộ trình đó đã được phục vụ. Bài toán OVRP dễ dàng chuyển đổi thành bài toán CVRP bằng cách gán các khoảng cách từ mỗi khách hàng trở về kho bằng 0. 1.4.6 VRP tách phân phối VRP tách phân phối (Split Delivery vehicle routing problem - SDVRP) là sự nới lỏng bài toán VRP bằng cách cho phép một khách hàng có thể được phục vụ bởi các xe khác nhau nếu điều này làm giảm chi phí tổng thể. Sự nới lỏng này rất quan trọng khi nhu cầu của một khách hàng lớn hơn khả năng chở của xe. Một lời giải khả thi nếu tất cả các ràng buộc của VRP thỏa mãn ngoại trừ một khách hàng có thể được cung cấp bởi nhiều hơn một xe vận chuyển. Rõ ràng, bài toán cần phải xác định thêm phần chia sẻ yir ∈ [ 0, 1] của nhu cầu d i của khách hàng i được phân phối trên lộ trình r. Bất lợi của phương pháp phân phối này là khách hàng thường không thích nhu cầu của họ được đáp ứng nhiều lần. 1.4.7 VRP với khả năng chuyên chở về VRP với khả năng chuyên chở một số hàng hóa trở về (VRP with backhauling – VRPB) phân biệt hai nhóm khách hàng N1 và N2. Mỗi khách hàng i ∈ N 1 đòi hỏi phải được phân phối một số lượng hàng hóa cho trước từ kho. Trong khi đó, mỗi khách hàng i ∈ N 2 yêu cầu mang một số lượng hàng hóa cho trước tại khách hàng đó trở về kho. Một giả định quan trọng là mỗi lộ trình đầu tiên phải phục vụ những khách hàng thuộc nhóm N1 và sau đó có thể phục vụ các khách hàng thuộc nhóm N2
18 trên đường trở về kho. Việc trộn lẫn các khách hàng thuộc hai nhóm với nhau là không được phép, nghĩa là đầu tiên phục vụ khách hàng i ∈ N 1, kế đến phục vụ khách hàng j ∈ N 2 , sau đó phục vụ khách hàng t ∈ N 1, ... trên một lộ trình đơn. Bởi vì điều này có thể dẫn đến tiêu tốn thời gian và quá tải cho phép của xe, tức là các ràng buộc của VRP có thể bị vi phạm. 1.4.8 VRP với khả năng nhặt và phân phối VRP với khả năng nhặt và phân phối (VRP with pickup and delivery – VRPPD) giả định rằng mỗi khách hàng cũng là một yêu cầu vận chuyển. Mỗi yêu cầu vận chuyển i ∈ N được đặc trưng bởi: • Vị trí lấy hàng hóa i + và vị trí phân phối i-; • Số lượng hàng hóa d i phải được lấy tại i + và được phân phối tại i- ; • Các cửa sổ thời gian [ei , li ] và [ei , li ] tại vị trí nhặt và phân phối hàng hóa. + + − − Hình 1.4 Ví dụ VRP với khả năng nhặt và phân phối Các ràng buộc của VRPPD thường là: • Các ràng buộc thứ tự trước sau bởi vì bên đòi hỏi vận chuyển phải được viếng thăm trước bên phân phối trong cùng một lộ trình. • Vị trí nhặt i + và vị trí phân phối i- của mỗi đòi hỏi phải nằm trên cùng một lộ trình.
19 • Tải của xe không vượt quá khả năng của nó. • Thao tác nhặt và phân phối phải diễn ra trong khoảng thời gian cho phép của cửa sổ thời gian. Mô hình nhặt và phân phối này thường được sử dụng trong trường hợp vận chuyển hành khách. Khi đó, VRPPD có tính động cao và các đòi hỏi vận chuyển đến động theo thời gian. 1.5 Tối ưu tổ hợp Bài toán tối ưu có thể hình thức hóa như là tìm giá trị nhỏ nhất hoặc lớn nhất của hàm mục tiêu f . Các biến xi với i ∈ [1, k] , thường viết x =( x1 , x2 ,..., xk ) gọi là các biến quyết định. Một số ràng buộc xác định tập lời giải khả thi S. S được gọi là không gian lời giải. Bài toán tối ưu được phát biểu như sau: min f ( x) với giả thuyết x ∈ S Tập lời giải S được mô tả bằng tập hợp các phương trình và bất phương trình. Ứng với một bài toán tối ưu cho trước, có nhiều cách khác nhau để hình thức hóa tương ứng hàm mục tiêu, các biến quyết định và đặc tả không gian lời giải. Chính điều này làm nảy sinh các thuật toán khác nhau để giải quyết vấn đề và hệ quả kéo theo là hiệu quả tính toán cũng như chất lượng lời giải có thể khác nhau. Các bài toán tối ưu tổ hợp là các bài toán tối ưu với tập lời giải khả thi là xác định nhưng thường rất lớn. Các thuật toán hiệu quả chỉ tồn tại cho một số bài toán, trong khi phần lớn chỉ có thể giải bằng những phương pháp đòi hỏi thời gian theo hàm số mũ. Các bài toán thuộc dạng chỉ có thể giải bằng những phương pháp đòi hỏi độ phức tạp thời gian theo hàm số mũ được gọi là bài toán NP-khó.