Á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.
Nội dung trích xuất từ tài liệu:
Á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ảiHNUE JOURNAL OF SCIENCENatural Sciences 2018, Volume 63, Issue 3, pp. 90-98This paper is available online at http://stdb.hnue.edu.vnDOI: 10.18173/2354-1059.2018-0009ÁP DỤNG GIẢI THUẬT DI TRUYỀN CHO MỘT BÀI TOÁN MỚICỦA GIAO THÔNG VẬN TẢIVũ Đình Hòa1 và Đỗ Tuấn Hạnh2Khoa Công nghệ Thông tin, Trường Đại Học Sư Phạm Hà NộiTrường Đại Học Kinh Tế Kĩ Thuật Công Nghiệp, Trường Đại Học Bách Khoa Hà Nội12Tó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ôngvậ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ánnghiê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ảimộ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ở đầuNhữ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ênmô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 cungvớ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 âmc(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, tagọ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 coinhư 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ạngG  (V , E) , ta gọi luồng p trong mạng G là một phép gán cho mỗi cung e  (u, v)  E một số tựnhiên p(e)  p(u, v) (gọi là luồng trên cung e ), thoả mãn các điều kiện sau:- Luồng trên mỗi cung không vượt quá khả năng thông qua của nó: 0  p(u, v) c(u, v) ,   u, v   E ,- Với mọi đỉnh v không trùng với đỉnh nguồn s và đỉnh thu t , tổng luồng trên các cung đivào v bằng tổng luồng trên các cung đi ra khỏi v :  p(u, v)   p(u, v) . Trong đó:u ( v )w ( v )Ngày nhận bài: 12/4/2017. Ngày sửa bài: 12/3/2018. Ngày nhận đăng: 20/3/2018.Tác giả liên hệ: Vũ Đình Hòa. Địa chỉ e-mail: hoavd@hnue.edu.vn.90Á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ảiK   v   {u V |  u, v   E} ,K   v   {w V |  v, w  E} .* Bài toán luồng cực đại trên mạngCho mạng G  (V , E) với đỉnh s , đỉnh thu t và thông luồng c : E  N . Hãy tìm luồng p *trong mạng G  (V , E) sao cho p *(e)  c(e),  E và giá trị  p* (s, v)   p* (v, s) (được gọi làv ( s )v ( s )giá trị của luồng) lớn nhất có thể. Luồng như vậy gọi là luồng cực đại trong mạng và bài toán nàygọi là bài toán tìm luồng cực đại trên mạng.Bài toán luồng cực đại trên mạng được quan tâm từ rất sớm do tầm quan trọng của nó. Đã cónhiều giải thuật được đề xuất để giải quyết bài toán này, mà một trong các giải thuật quan trọngquen biết nhất là giải thuật của Ford-Fulkerson [1, 2]. Thuật toán này được cải tiến trong một sốnăm sau đó để đạt được độ phức tạp thuật toán là O(nm2 ) [4].Trong đời sống thực tế thì khả năng thông qua của các luồng trên các cạnh được thể hiện làkhả năng vận tải của đội vận tải phụ trách tuyến đường đó. Khi có một sự phân công các đội vậntải trên các cung đường thì chúng ta phải giải quyết bài toán luồng cực đại trên sơ đồ mạng tươngứng, trong đó khả năng thông qua của mỗi cung chính là khả năng vận tải của đội phụ trách cungđường đó. Trong bài toán này chúng ta xem xét vấn đề phân công mỗi đội vận tải phụ trách mộtcung đường để luồng cực đại tương ứng với phân công đó lớn hơn luồng cực đại ứng với các phâncông khác.* Bài toán phân công vận tảiCho một mạng G  (V , E) gồm n đỉnh, m cung, đỉnh nguồn s , đỉnh thu t và một tập hợpm số tự nhiên c1 , c2 ,..., cm . Hãy tìm một song ánh c : E  C sao cho luồng cực đại củamạng G  (V , E) , với khả năng thông qua của cạnh e là c(e) , lớn nhất có thể.C gồmBài toán này có ý nghĩa thực tế rất lớn, nhưng cho đến nay chưa được nghiên cứu [3].Ví dụ: Ta xét một mạng như trong Hình 1.Mạng G  (V , E) có 3 đỉnh s, t và u với hàmthông luồng c : E  {1, 2,3} . Xét hai phươngán phân công khác nhau:(i) Nếu ta phân bốc(e1 )  1, c(e2 )  2, c(e3 )  3,thì luồng cực đại là p  4.*(ii) Nếu ta phân bốc(e1 )  3, c(e2 )  2, c(e3 )  1,Hình 1thì luồng cực đại chỉ đạt giá trị p  3.*91Vũ Đình Hòa và Đỗ Tuấn Hạnh* Đánh giá độ khó của bài toán phân công vận tảiBài toán luồng cực đại trên mạng được nghiên cứu và có nhiều giải thuật giải quyết bàitoán này. Có nhiều thuật toán giải quyết bài toán này, và các thuật toán này đều là giải thuật hiệuquả. Giải thuật Ford-Fulkerson cải tiến (chọn đường tăng luồng là đường ít cạnh nhất) có độ phứctạp đa thức [4]. Độ khó của bài toán phân công vận tải tối ưu chưa được nghiên cứu trên thế giới.Chúng ta sẽ chứng minh bài toán này là bài toán NPH [5]. Để chứng minh được điều đó, ta dẫnbài toán PAR, là một bài toán NPC [5], về bài toán phân công vận tải.Bài toán Partition (PAR)Instance: Cho trước số nguyên dương n và một tập hợp A  {a1 , a2 ,..., an }  N .Question: Tồn tại hay không một phân hoạch A  A1  A2 sao choa  aai A1iai A2i.Bài toán phân công vận tải được phát biểu dưới dạng bài toán quyết định như sau.* Bài toán phân công vận tảiInstance: mạng G  (V , E ) gồm n đỉnh, m cung, đỉnh nguồn s , đỉnh thu t và một tập hợpC gồm m số tự nhiên c1 , c2 ,..., cm và một số tự nhiên B .Question: ...