Á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

HNUE JOURNAL OF SCIENCE<br /> Natural Sciences 2018, Volume 63, Issue 3, pp. 90-98<br /> This paper is available online at http://stdb.hnue.edu.vn<br /> <br /> DOI: 10.18173/2354-1059.2018-0009<br /> <br /> ÁP DỤNG GIẢI THUẬT DI TRUYỀN CHO MỘT BÀI TOÁN MỚI<br /> CỦA GIAO THÔNG VẬN TẢI<br /> <br /> Vũ Đình Hòa1 và Đỗ Tuấn Hạnh2<br /> Khoa Công nghệ Thông tin, Trường Đại Học Sư Phạm Hà Nội<br /> 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<br /> 1<br /> <br /> 2<br /> <br /> 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ỉ<br /> 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<br /> 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<br /> đặ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<br /> 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<br /> độ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<br /> 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.<br /> 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à<br /> đư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.<br /> 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.<br /> <br /> 1.<br /> <br /> Mở đầu<br /> <br /> 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<br /> 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<br /> 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<br /> đượ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<br /> 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<br /> 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<br /> 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<br /> G  (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ự<br /> 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:<br /> - 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) <br /> <br /> c(u, v) ,   u, v   E ,<br /> - 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 đi<br /> và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 đó:<br /> u ( v )<br /> <br /> w ( v )<br /> <br /> 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.<br /> Tác giả liên hệ: Vũ Đình Hòa. Địa chỉ e-mail: hoavd@hnue.edu.vn.<br /> <br /> 90<br /> <br /> Á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<br /> <br /> K   v   {u V |  u, v   E} ,<br /> K   v   {w V |  v, w  E} .<br /> <br /> * Bài toán luồng cực đại trên mạng<br /> Cho 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 *<br /> 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à<br /> v ( s )<br /> <br /> v ( s )<br /> <br /> 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ày<br /> gọi là bài toán tìm luồng cực đại trên mạng.<br /> 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ó<br /> 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ọng<br /> quen 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ố<br /> năm sau đó để đạt được độ phức tạp thuật toán là O(nm2 ) [4].<br /> 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à<br /> 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ận<br /> tả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<br /> ứ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<br /> đườ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ột<br /> cung đườ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ân<br /> công khác.<br /> * Bài toán phân công vận tải<br /> Cho 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ợp<br /> <br /> m 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ủa<br /> mạ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ể.<br /> C gồm<br /> <br /> Bà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].<br /> Ví dụ: Ta xét một mạng như trong Hình 1.<br /> Mạng G  (V , E) có 3 đỉnh s, t và u với hàm<br /> thông luồng c : E  {1, 2,3} . Xét hai phương<br /> án phân công khác nhau:<br /> (i) Nếu ta phân bố<br /> <br /> c(e1 )  1, c(e2 )  2, c(e3 )  3,<br /> thì luồng cực đại là p  4.<br /> *<br /> <br /> (ii) Nếu ta phân bố<br /> <br /> c(e1 )  3, c(e2 )  2, c(e3 )  1,<br /> Hình 1<br /> <br /> thì luồng cực đại chỉ đạt giá trị p  3.<br /> *<br /> <br /> 91<br /> <br /> Vũ Đình Hòa và Đỗ Tuấn Hạnh<br /> <br /> * Đánh giá độ khó của bài toán phân công vận tải<br /> "Bà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ài<br /> toá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ệu<br /> quả. 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ức<br /> tạ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.<br /> 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ẫn<br /> bà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.<br /> Bài toán Partition (PAR)<br /> Instance: Cho trước số nguyên dương n và một tập hợp A  {a1 , a2 ,..., an }  N .<br /> Question: Tồn tại hay không một phân hoạch A  A1  A2 sao cho<br /> <br /> a  a<br /> <br /> ai A1<br /> <br /> i<br /> <br /> ai A2<br /> <br /> i<br /> <br /> .<br /> <br /> "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.<br /> * Bài toán phân công vận tải<br /> Instance: mạng G  (V , E ) gồm n đỉnh, m cung, đỉnh nguồn s , đỉnh thu t và một tập hợp<br /> <br /> C gồm m số tự nhiên c1 , c2 ,..., cm và một số tự nhiên B .<br /> Question: Tồn tại hay không song ánh c : E  C sao cho luồng lớn nhất từ s đến t , với khả<br /> năng thông qua của cạnh e là c(e) , không nhỏ hơn B .<br /> Định lí. Bài toán phân công vận tải là bài toán NPH .<br /> Chứng minh: Ta sử dụng bài toán PAR, là một bài toán NPC [5], để dẫn về bài toán PCVT.<br /> Ta xây dựng phép dẫn thời gian đa thức biến mỗi instance của bài toán PAR thành một instance<br /> của bài toán phân công vận tải như sau: Với mỗi số nguyên dương n và một tập hợp<br /> A  {a1 , a2 ,..., an }  N , ta xây dựng một mạng G  (V , E) với 3 đỉnh s, t và u và m  2n<br /> cung, bao gồm n cung kép ( s, u ) , và n cung kép (u, t ) , như trong hình vẽ sau:<br /> <br /> Hình 2.<br /> n<br /> n<br /> Ta chọn C  A {an1 ,..., a2 n } với ai  0 cho mọi i  n  1 và B   ai   ai / 2 ở<br /> 1<br />  1<br /> <br /> đó [a ] kí hiệu số nguyên lớn nhất không vượt quá a . Với mỗi hàm thông luồng c : E  C Đặt<br /> <br /> A1 là tập hợp các giá trị của A ứng với các cung đi từ s đến u và A2  A  A1 . Dễ dàng thấy<br />  n <br />   ai <br /> luồng đi từ s đến t đạt giá trị B   1<br />  (  a  ký hiệu số nguyên nhỏ nhất không nhỏ hơn a )<br />  2 <br /> <br /> <br /> khi và chỉ khi có phân hoạch A  A1  A2 sao cho  ai   ai .<br /> ai A1<br /> <br /> 92<br /> <br /> ai A2<br /> <br /> Á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<br /> <br /> Ngoài ra cũng dễ dàng thấy phép xây dựng một mạng G  (V , E ) như vậy từ một instance<br /> của bài toán PAR thực hiện được trong thời gian đa thức. Do đó, phép dẫn của chúng ta là một<br /> phép dẫn thời gian đa thức từ bài toán PAR đến bài toán PCVT.<br /> Vậy PCVT là một bài toán NPH .<br /> <br /> 2. Nội dung nghiên cứu<br /> 2.1. Sử dụng giải thuật di truyền tìm phân công tối ưu<br /> 2.1.1. Lát cắt, đường tăng luồng, định lí Ford - Fulkerson<br /> Định nghĩa: Ta gọi lát cắt  S , F  là một cách phân hoạch tập đỉnh V của mạng thành hai<br /> tập rời nhau S và F , trong đó S chứa đỉnh phát s và F chứa đỉnh thu t . Khả năng thông<br /> qua của lát cắt  S , F  là tổng tất cả các khả năng thông qua của các cung  u, v  có u  S và<br /> <br /> v  F . Lát cắt với khả năng thông qua nhỏ nhất gọi là lát cắt hẹp nhất.<br /> Định lí Ford-Fulkerson:<br /> Giá trị luồng cực đại trên mạng đúng bằng khả năng thông qua của lát cắt hẹp nhất.<br /> Ford- Fulkerson xây dựng được một thuật toán tìm luồng cực đại trên mạng:<br /> Giả sử p là một luồng trong mạng G <br /> <br /> Gp  V , E p  như sau:<br /> Xét những cạnh e <br /> <br />  u, v   E , c  u , v <br /> <br /> V , E <br /> <br /> . Ta xây dựng đồ thị có trọng số<br /> <br />  0:<br /> <br /> - Nếu p(u, v)  c(u, v) thì ta thêm cung  u, v  vào E p với trọng số c(u, v)  p(u, v) ,<br /> cung đó gọi là cung thuận. Về ý nghĩa, trọng số cung này cho biết còn có thể tăng luồng p trên<br /> cung này một lượng không quá trọng số đó.<br /> - Xét tiếp nếu như p(u, v)  c(u, v) thì ta thêm cung  v, u <br /> <br /> vào E p<br /> <br /> với trọng số<br /> <br /> p(u, v)  c(u, v) , cung đó gọi là cung nghịch. Về ý nghĩa, trọng số cung này cho biết còn có thể<br /> giảm luồng p trên cung  u, v  một lượng không quá trọng số đó.<br /> Đồ thị G p được gọi là đồ thị tăng luồng.<br /> Giả sử R là một đường đi cơ bản từ đỉnh phát s tới đỉnh thu t . Gọi d là giá trị nhỏ nhất<br /> của các trọng số của các cung trên đường đi R . Ta sẽ tăng giá trị của luồng p bằng cách đặt:<br /> - p(u, v) : p(u, v)  d , nếu  u, v  là cung trong đường R và là cung thuận,<br /> - p(u, v) : p(u, v)  d , nếu  u, v  là cung trong đường R và là cung nghịch,<br /> - Còn luồng trên những cung khác giữ nguyên.<br /> Có thể kiểm tra luồng p mới xây dựng vẫn là luồng trong mạng và giá trị của luồng p mới<br /> được tăng thêm d so với giá trị luồng p cũ. Ta gọi thao tác biến đổi luồng như vậy là tăng<br /> luồng dọc đường R , đường đi cơ bản R từ s tới t được gọi là đường tăng luồng. Đến đây ta có<br /> thể hình dung ra được thuật toán tìm luồng cực đại trên mạng: khởi tạo một luồng bất kỳ, sau đó<br /> cứ tăng luồng dọc theo đường tăng luồng, cho tới khi không tìm được đường tăng luồng nữa.<br /> 93<br /> <br /> Vũ Đình Hòa và Đỗ Tuấn Hạnh<br /> <br /> Các bước của thuật toán tìm luồng cực đại trên mạng có thể mô tả như sau:<br /> Bước 1: Khởi tạo.<br /> Một luồng bất kì trên mạng, chẳng hạn như luồng 0 (luồng trên các cung đều bằng 0), sau đó:<br /> Bước 2: Lặp hai bước sau.<br /> - Tìm đường tăng luồng R đối với luồng hiện có  Tìm đường đi cơ bản từ s tới t trên đồ<br /> thị tăng luồng, nếu không tìm được đường tăng luồng thì bước lặp kết thúc.<br /> - Tăng luồng dọc theo đường R<br /> Bước 3: Thông báo giá trị luồng cực đại tìm được.<br /> Gán nhãn trong cài đặt thuật toán Ford - Fulkerson (L.R.Ford & D.R.Fulkerson - 1962)<br /> bằng cách sau:<br /> Mỗi đỉnh v được gán nhãn Trace  v  , d v  . Trong đó  Trace  v   là đỉnh liền trước<br /> <br /> v trong đường đi từ s tới v , Trace v  âm hay dương tuỳ theo (| Trace v |, v) là cung<br /> nghịch hay cung thuận trên đồ thị tăng luồng, d  v  là trọng số nhỏ nhất của các cung trên đường<br /> đi từ s tới v trên đồ thị tăng luồng. Bước lặp sẽ tìm đường đi từ s tới t trên đồ thị tăng luồng<br /> đồng thời tính luôn các nhãn Trace  v  , d v  . Sau đó tăng luồng dọc theo đường tăng luồng<br /> nếu tìm thấy.<br /> 2.1.2. Giải thuật di truyền<br /> Theo Định lí 1, Bài toán “Phân Công Vận Tải Tối ưu” là một bài toán NPH do đó ta không<br /> thể có lời giải tối ưu. Ta có thể sử dụng phương pháp vét cạn để có thể giải quyết bài toán trên tuy<br /> nhiên vì độ phức tập quá lơn không đáp ứng được, do đó chúng tôi đề xuất sử dụng giải thuật di<br /> truyền để giải quyết bài toán trên. Người được xem đặt nền móng đầu tiên cho giải thuật di truyền<br /> là John Holland [6], lần đầu nghiên cứu thuật giải này không có tên. Do nguồn gốc của phương<br /> pháp này từ gen di truyền nên nó có tên là giải thuật di truyền. GA (Genetic Algorithms) được đặc<br /> trưng bởi các chiến lược tìm kiếm dựa trên quần thể và các toán tử di truyền như là chọn lọc, đột<br /> biến và trao đổi chéo.<br /> Mã hoá dữ liệu mới cho bài toán phân công vận tải<br /> Bài toán có m đội vận tải đánh số từ 1 đến m và đồng thời đánh số các cung đường từ 1 đến m<br /> Khi đó mỗi một hoán vị từ 1 đến m là một cách phân công đội vận tải tương ứng với một<br /> cung đường. Sử dụng phương pháp mã hóa dữ liệu gen chuyển từ nhị phân 0 và 1 mã hóa gen<br /> dưới dạng thập phân [8, 9]. Ví dụ có 9 đội vận tải 9 cung đường là: (1,2); (1,3); (2,3); (2,4); (3,2);<br /> (3,5); (4,6); (5,4); (5,6) và có 6 địa điểm điểm xuất phát là 1 và kết thúc là 6. Có giá trị vận<br /> chuyển của 9 đội vận tại lầ lượt nhận các giá trị là 16; 16; 14; 4; 14; 12; 7; 4; 20<br /> Với phương pháp mã hóa trên ta có gen phân công là:134569872.<br /> Toán tử đột biến<br /> Chúng tôi áp dụng phương pháp đột biến đảo ngược như sau:<br /> Pháp sinh ngẫu nhiên 2 vị trí H1 và H2 (1