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 (Nguyễn Việt Hân)

NỘI DUNG:

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 t ựa trên phát sinh cộ ..................................................................... 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

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

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 ......

LINK 1 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 2 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 3 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 4 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK DOWNLOAD