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
NGUY ỄN VIỆT HÂN
B O ỘGIÁO DỤC VÀ ĐÀO TẠ
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
2007 2009-
LUẬN VĂN TH C SĨ KHOA HẠ ỌC
CHUY ÀNH TH ÊN NG : CÔNG NGHỆÔNG TIN
NGƯ I HƯỜ ỚNG DẪN KHOA HỌC:
TS. NGUYỄN ĐỨC NGHĨA
Hà nội
2009
Hà Nội – Năm 2009
2
L ời cảm ơn
Trư m ơn chân thành đớc tiên, em xin gửi lời cả ế ầ ễ ứ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 i lòng nhi t huy n t, vớ ệ ế ắt, đã vun đ p nề ảng
tri th c v c cho các thứ ững chắ ế ệ ọ 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 t mđã vất vảnuôi nấng và ạo ọi điều
ki luôn ngệ ển đ con có đượ ả ờ ợc như ngày hôm nay. Xin cm ơn em, ngư i v lo lắ, 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 ục lụ
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 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
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