ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Tạ Tuấn Anh
THIẾT KẾ THUẬT TOÁN DI TRUYỀN ỨNG DỤNG
TRONG BÀI TOÁN TỐI ƯU THU GOM
CHẤT THẢI RẮN ĐÔ THỊ
LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN
HÀ NỘI - 2017
TẠ TUẤN ANH QUẢN LÝ HỆ THÔNG THÔNG TIN KHÓA 22 - THÁNG 10/2017
ĐẠI HỌC QUỐC GIA HÀ NÔI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Tạ Tuấn Anh
THIẾT KẾ THUẬT TOÁN DI TRUYỀN ỨNG DỤNG
TRONG BÀI TOÁN TỐI ƯU THU GOM
CHẤT THẢI RẮN ĐÔ THỊ
Chuyên ngành: Quản Lý Hệ Thống Thông Tin
Mã số: 8480205
LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. LÊ HOÀNG SƠN
HÀ NỘI - 2017
Lời cam đoan
Tôi cam đoan kết quả của luận văn là chính tôi thực hiện, các số liệu thực
nghiệm là theo đúng kết quả của chương trình. Nếu sai tôi xin chịu hoàn toàn chịu
trách nhiệm.
LỜI CẢM ƠN
Trong suốt quá trình học tập và hoàn thiện đề tài này, em đã nhận được sự
hướng dẫn, giúp đỡ quý báu của các thầy cô, anh chị và bạn bè. Với lòng kính trọng
và biết ơn sâu sắc, em xin được bày tỏ lời cám ơn chân thành tới:
Đầu tiên, em xin gửi lời cảm ơn chân thành nhất tới sự hướng dẫn tận tình của
TS. Lê Hoàng Sơn. Trong suốt thời gian thực hiện đề tài, mặc dù thầy rất bận rộn
trong công việc nhưng thầy vẫn giành rất nhiều thời gian và tâm huyết trong việc
hướng dẫn em hoàn thiện đề tài này. Trong quá trình thực hiện đề tài, Thầy luôn
định hướng, góp ý và sửa chữa những chỗ sai giúp em không bị lạc lối trong biển
kiến thức mênh mông.
Em cũng xin được gửi lời cảm ơn đến các thầy cô trong khoa Công Nghệ
Thông Tin, Trường Đại Học Công Nghệ đã dạy bảo, giúp đỡ, tạo điều kiện cho em
trong thời gian em đã học tập tại trường.
Xin được gửi lời cảm ơn các thầy cô, các anh chị và các bạn trong Trung tâm
Tính toán Hiệu năng cao, Trường Đại học Khoa Học Tự Nhiên đã giúp đỡ em trong
suốt quá trình học tập và nghiên cứu tại trung tâm.
Cuối cùng, em xin gửi lời cám ơn tới gia đình, anh chị và bạn bè đã giúp đỡ,
cổ vũ, động viên trong công việc, học tập nói chung cũng như trong quá trình thực
hiện đề tài này.
Xin chúc mọi người luôn mạnh khỏe, đạt được nhiều thành tích trong công tác,
học tập và nghiên cứu khoa học.
Em xin chân thành cảm ơn!
Học viên
Tạ Tuấn Anh
DANH MỤC BẢNG BIỂU
STT
Tên hình, bảng biểu
Trang
Bảng 2.1
Thuật toán Dijkstra cổ điển
25
Bảng 2.2
Thuật toán Dijkstra cải tiến
26
Bảng 3.1
Sức chứa chất thải của mỗi xe
36
Bảng 3.2
Sức chứa chất thải ban đầu tại tất cả các node
37
Bảng 3.3
Ký hiệu và định nghĩa
38
Bảng 3.4
Mô hình cho bài toán thu gom chất thải
39
Bảng 3.5
Lượng chất thải mỗi node (kg)
40
Bảng 3.6
Sức chứa chất thải của mỗi xe (kg)
40
Bảng 3.7
Khoảng cách giữa các node (km)
41
Bảng 3.8
Kết quả hành trình thứ nhất
42
Bảng 3.9
Kết quả hành trình thứ 2
42
Bảng 3.10
Biểu tượng của các node trên ArcGIS
44
Bảng 3.11
Kết quả thực nghiệm
45