Một Thuật Toán Tối Ưu Đàn Kiến Giải Bài Toán Điều Phối Xe

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ







TRẦN LAN PHƯƠNG

MỘT THUẬT TOÁN TỐI ƯU ĐÀN KIẾN

GIẢI BÀI TOÁN ĐIỀU PHỐI XE

LUẬN VĂN THẠC SĨ

Ngành: Kỹ thuật phần mềm

Hà Nội, năm 2019

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ







TRẦN LAN PHƯƠNG

MỘT THUẬT TOÁN TỐI ƯU ĐÀN KIẾN

GIẢI BÀI TOÁN ĐIỀU PHỐI XE

Ngành : Kỹ thuật phần mềm

Chuyên ngành : Kỹ thuật phần mềm

Mã số : 8480103.01

LUẬN VĂN THẠC SĨ

Ngành: Kỹ thuật phần mềm

Người hướng dẫn khoa học: PGS. TS Hoàng Xuân Huấn

Hà Nội, năm 2019

LỜI CAM ĐOAN

Tôi xin cam đoan rằng luận văn này của tự cá nhân tôi tìm hiểu, nghiên cứu dưới sự

hướng dẫn giúp đỡ của PGS.TS Hoàng Xuân Huấn. Trong toàn bộ nội dung của luận văn,

những điều đã được trình bày hoặc là của chính cá nhân tôi hoặc là được tổng hợp từ nhiều

nguồn tài liệu. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. Các số liệu được

trích dẫn trong luận văn này là trung thực. Kết quả nghiên cứu này không trùng với bất cứ

công trình nào đã được công bố trước đây.

Tôi xin hoàn toàn chịu trách nhiệm với lời cam đoan của mình.

TÁC GIẢ LUẬN VĂN

Trần Lan Phương

LỜI CẢM ƠN

Luận văn “Một thuật toán tối ưu đàn kiến giải bài toán điều phối xe” được hoàn thành

với sự giúp đỡ tận tình của các thầy giáo, cô giáo trường Đại học công nghệ - Đại học Quốc

gia Hà Nội, các đồng nghiệp, gia đình và sự nỗ lực của bản thân trong suốt quá trình học

tập và thực hiện luận văn.

Trước tiên, em xin chân thành cảm ơn tới Ban giám hiệu nhà trường, phòng Đào tạo

Đại học và Sau đại học, khoa Công nghệ thông tin và các thầy giáo, cô giáo trong trường

đã tận tình truyền đạt kiến thức, giúp đỡ em trong suốt quá trình học tập chương trình cao

học tại trường.

Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS Hoàng Xuân Huấn,

Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tận tình chỉ dẫn, giúp đỡ

và cung cấp cho em những kiến thức, tài liệu cần thiết để hoàn thành luận văn này.

Cuối cùng, em xin gửi lời cảm ơn tới gia đình, bạn bè đồng nghiệp và người thân

đã tin tưởng, giúp đỡ, động viên, khích lệ em trong suốt quá trình làm luận văn tốt

nghiệp. Do thời gian và kiến thức có hạn chắc chắn luận văn cũng không thể tránh khỏi

những thiếu sót, hạn chế. Kính mong nhận được sự chỉ bảo và góp ý của quý Thầy, Cô.

Em xin chân thành cảm ơn!

Hà Nội, tháng 06 năm 2019

Học viên

Trần Lan Phương

MỤC LỤC

MỞ ĐẦU..........................................................................................................................1

CHƯƠNG 1: GIỚI THIỆU BÀI TOÁN ĐỊNH TUYẾN XE.............................................3

1.1. Phát biểu bài toán định tuyến xe ..........................................................................3

1.2. Các biến thể quan trọng của bài toán định tuyến xe..............................................5

1.2.1. Dựa vào cấu trúc đường đi ..............................................................................5

1.2.2. Dựa vào yêu cầu vận chuyển...........................................................................5

1.2.3. Dựa vào ràng buộc nội tuyến ..........................................................................6

1.2.3.1. Ràng buộc về lượng hàng hóa ..................................................................6

1.2.3.2. Ràng buộc về độ dài lộ trình ....................................................................7

1.2.3.3. Ràng buộc về việc tái sử dụng xe.............................................................7

1.2.3.4. Ràng buộc về thời gian cho mỗi lộ trình ..................................................7

1.2.4. Dựa vào đặc điểm đội xe.................................................................................8

1.2.5. Dựa vào ràng buộc liên tuyến..........................................................................9

1.2.6. Dựa vào hàm mục tiêu ..................................................................................10

1.3. Các hướng tiếp cận và ứng dụng của bài toán định tuyến xe ..............................10

1.4. Kết luận chương ................................................................................................12

CHƯƠNG 2: THUẬT TOÁN TỐI ƯU ĐÀN KIẾN.......................................................13

2.1. Giới thiệu về thuật toán......................................................................................13

2.2. Từ kiến tự nhiên đến kiến nhân tạo ....................................................................13

2.2.1. Đàn kiến tự nhiên..........................................................................................14

2.2.2. Đàn kiến nhân tạo .........................................................................................15

2.3. Trình bày giải thuật............................................................................................15

2.3.1. Đồ thị cấu trúc ..............................................................................................16

2.3.2. Trình bày về thuật toán ACO cơ bản.............................................................18

2.3.3. Quy tắc cập nhật vết mùi...............................................................................19

2.3.3.1. Thuật toán AS ....................................................................................19

2.3.3.2. Thuật toán ACS..................................................................................22

2.3.3.3. Thuật toán Max-Min ..........................................................................23

2.3.3.4. Thuật toán Min- Max trơn..................................................................25

2.4. Một số vấn đề liên quan khi áp dụng ACO.........................................................26

2.4.1. Đặc tính hội tụ ..............................................................................................26

2.4.2. Thực hiện song song .....................................................................................26

2.4.3. ACO kết hợp với tìm kiếm cục bộ.................................................................27

2.4.4. Thông tin heuristic ........................................................................................27

2.4.5. Số lượng kiến................................................................................................28

2.4.6. Tham số bay hơi ...........................................................................................28

2.5. Kết luận chương. ...............................................................................................28

CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN

MPDPTW.......................................................................................................................29

3.1. Phát biểu bài toán ..............................................................................................29

3.1.1. Giới thiệu bài toán ........................................................................................29

3.1.2. Xây dựng mô hình toán học ..........................................................................30

3.2. Một số phương pháp giải quyết bài toán MPDPTW...........................................32

3.3. Thuật toán ACO giải quyết bài toán MPDPTW .................................................33

3.3.1. Đồ thị cấu trúc ..............................................................................................33

3.3.2. Xây dựng giải pháp.......................................................................................34

3.3.3. Quy tắc cập nhật mùi ....................................................................................36

3.3.4. Thủ tục tìm kiếm cục bộ ...............................................................................36

3.4. Kết luận chương ................................................................................................38

CHƯƠNG 4: CÀI ĐẶT VÀ ĐÁNH GIÁ THỰC NGHIỆM ...........................................39

4.1. Cài đặt chương trình ..........................................................................................39

4.2. Mô tả dữ liệu thực nghiệm.................................................................................41

4.3. Hiệu năng lời giải mô hình toán học ..................................................................42

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.......................................................................50

TÀI LIỆU THAM KHẢO ..............................................................................................51

PHỤ LỤC.......................................................................................................................54