TAILIEUCHUNG - Áp dụng giải thuật di truyền cho một bài toán mới của giao thông vận tải
Trong bài báo này chúng tôi đặt ra một bài toán giao thông vận tải mới chưa được khảo sát từ trước đến nay. Bài toán nghiên cứu một mạng có n đỉnh và m cạnh với một đỉnh nguồn và một đỉnh đích cùng với m đội vận tải cho trước. Mục tiêu bài toán đặt ra là tìm một cách phân công cho mỗi đội vận tải một cung đường sao cho có thể vận tải một lượng hàng lớn nhất từ đỉnh nguồn s tới đỉnh đích t. | HNUE JOURNAL OF SCIENCE Natural Sciences 2018, Volume 63, Issue 3, pp. 90-98 This paper is available online at DOI: ÁP DỤNG GIẢI THUẬT DI TRUYỀN CHO MỘT BÀI TOÁN MỚI CỦA GIAO THÔNG VẬN TẢI Vũ Đình Hòa1 và Đỗ Tuấn Hạnh2 Khoa Công nghệ Thông tin, Trường Đại Học Sư Phạm Hà Nội Trường Đại Học Kinh Tế Kĩ Thuật Công Nghiệp, Trường Đại Học Bách Khoa Hà Nội 1 2 Tóm tắt. Các bài toán giao thông và vận tải được quan tâm khá sớm trên thế giới từ vài thế kỉ trước [1, 2] như bài toán người du lịch và bài toán luồng. Hiện nay, các bài toán giao thông vận tải được nghiên cứu dưới nhiều cách tiếp cận khác nhau [3]. Trong bài báo này chúng tôi đặt ra một bài toán giao thông vận tải mới chưa được khảo sát từ trước đến nay. Bài toán nghiên cứu một mạng có n đỉnh và m cạnh với một đỉnh nguồn và một đỉnh đích cùng với m đội vận tải cho trước. Mục tiêu bài toán đặt ra là tìm một cách phân công cho mỗi đội vận tải một cung đường sao cho có thể vận tải một lượng hàng lớn nhất từ đỉnh nguồn s tới đỉnh đích t. Trong bài báo này, chúng tôi chứng minh bài toán phân công vận tải là một bài toán NPH, và đưa ra một cách tiếp cận và giải quyết bài toán này bằng giải thuật di truyền. Từ khóa: Bài toán luồng, bài toán phân công vận tải, giải thuật di truyền. 1. Mở đầu Những khái niệm cơ bản dưới đây có thể tham khảo từ [1, 2] hoặc từ các cuốn sách chuyên môn khác về đồ thị. Một mạng được hiểu là một đồ thị có hướng G (V , E) gồm n đỉnh, m cung với một đỉnh nguồn s (nhiều khi được qui ước là chỉ có cung đi ra) và một đỉnh thu t (nhiều khi được qui ước là chỉ có cung đi vào). Mỗi cung e (u, v) E được gán với một số không âm c(e) c(u, v) gọi là khả năng thông qua của cung đó. Đôi khi, để thuận tiện cho việc trình bày, ta gọi hàm c : E R đó là hàm thông luồng và qui ước rằng nếu không có cung (u, v) thì ta coi như có cung này và khả năng thông qua c(e) c(u, v) của nó được gán bằng 0. Nếu có mạng G (V , E) , ta gọi luồng p trong
đang nạp các trang xem trước
