Mục tiêu nghiên cứu của đề tài là tìm lời giải tốt nhất trong các lời giải có thể và không gian tìm kiếm lời giải của bài toán là rời rạc. Nhiều bài toán tối ưu tổ hợp có độ phức tạp tính toán cao và được phân loại thuộc lớp NP khó. Việc tìm ra lời giải tối ưu cho các bài toán này cho các hệ thống song song lớn nhất cũng không thể hoàn thành được trong giới hạn thời gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng xấp xỉ đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ ) trong giới hạn thời gian cho phép. Bài toán người du lịch (TSP) là một bài toán cổ điển thuộc lớp NP được nghiên cứu sâu trong lĩnh vực tối ưu tổ hợp. | ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LÊ MỸ HẠNH PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN CHO BÀI TOÁN ĐIỀU PHỐI XE LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội-2014 2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LÊ MỸ HẠNH PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN CHO BÀI TOÁN ĐIỀU PHỐI XE Ngành Công nghệ thông tin Chuyên ngành Kỹ thuật phần mềm Mã số 60480103 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC XUÂN HUẤN ĐỨC ĐÔNG Hà Nội-2014 3 Lời cam đoan Với mục đích học tập nghiên cứu để nâng cao kiến thức và trình độ chuyên môn nên tôi đã làm luận văn này. Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của cá nhân tôi thực hiện dưới sự hướng dẫn của PGS. TS Hoàng Xuân Huấn và TS Đỗ Đức Đông. 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 cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn đúng quy định. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà nội ngày . tháng . năm 2014 Học viên Lê Mỹ Hạnh 4 LỜI CẢM ƠN Với những dòng chữ đầu tiên này tôi xin dành để gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy giáo PGS. TS. Hoàng Xuân Huấn Thầy giáo TS. Đỗ Đức Đông- hai người thầy đã tận tình hướng dẫn chỉ bảo và tạo cho tôi những điều kiện tốt nhất từ khi bắt đầu cho tới khi hoàn thành công việc của mình. Đồng thời tôi xin gửi lời cảm ơn tới các thầy cô giáo khoa Công nghệ thông tin - trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo cho tôi một môi trường học tập thuận lợi cung cấp nhiều kiến thức bổ ích để tôi có thể thực hiện công việc của mình. Tôi xin cảm ơn các nhà khoa học các tác giả của các bài báo báo cáo kỹ thuật và báo cáo hội thảo đã ghi ở phần tài liệu tham khảo nhờ những tài liệu hữu ích này mà tôi có thêm sự phong phú và đa dạng trong khóa luận của mình. Cuối cùng xin cảm ơn tất cả những người thân yêu trong gia đình tôi và bạn bè những
