- PHAN NGUYỄN BÁ THẮNG ĐIỀU KHIỂN GIAO THÔNG ĐÔ THỊ - MỘT TIẾP CẬN TỐI ƯU Chuyên ngành : Cơ sở Toán cho Tin học LUẬN VĂN THẠC SĨ KHOA HỌC TOÁN ỨNG DỤNG VÀ TIN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. - NGUYỄN QUANG THUẬN HÀ NỘI - 2018 Mục lụcMục lục iiMở đầu iii1 Lập lịch cho buýt nhanh BRT 11.1 Xe buýt nhanh BRT. - 11.2 Bài toán lập lịch cho tuyến BRT. - 31.3 Mô hình tối ưu đa mục tiêu với bài toán lập lịch cho tuyến BRT. - 51.3.2 Mô hình bài toán. - 62 Giải thuật di truyền NSGA-II 92.1 Sơ lược về tối ưu đa mục tiêu. - 92.2 Giải thuật di truyền NSGA-II. - 102.2.1 Sơ đồ chung của giải thuật NSGA-II. - 102.2.2 Cách biểu diễn cá thể và quá trình lai ghép, đột biến. - 112.2.3 Giải thuật NSGA-II. - 132.3 NSGA-II cho bài toán lập lịch buýt nhanh BRT. - 143 Ứng dụng tối ưu đa mục tiêu cho tuyến BRT Yên Nghĩa - Kim Mã 153.1 Tuyến BRT Yên Nghĩa - Kim Mã. - 153.2 Kết quả của giải thuật NSGA-II. - Trong giao thông công cộng thì hệ thống xe buýt giữvai trò cực kỳ quan trọng. - Nhằm mục đích cải thiện chất lượng đi lại của người dân,mô hình xe buýt nhanh (BRT - Bus Rapid Transit) đã được nghiên cứu và xây dựngdựa trên hệ thống xe buýt thông thường. - Với việc giải quyết bài toán lập lịch cho hệthống BRT, thời gian đi lại của người dân được đảm bảo, đồng thời hiệu quả sử dụnghệ thống của nhà vận hành cũng được nâng cao so với mô hình xe buýt truyền thống.Luận văn trình bày về vấn đề "Giao thông đô thị - Một cách tiếp cận tối ưu”, khi đóbài toán lập lịch được nhìn nhận dưới cái nhìn của tối ưu đa mục tiêu: chi phí đi lạicủa người dân và hiệu quả sử dụng hệ thống của nhà vận hành. - Với số lượng xe chotrước, bài toán có hai hàm mục tiêu và các ràng buộc là những hàm phi tuyến, khônglồi, các biến hỗn hợp nguyên. - Vì vậy, việc tìm ra một giải thuật tự nhiên và đơn giảnđể giải quyết bài toán là rất cần thiết. - Để vượt qua những khó khăn trên, luận văn sửdụng giải thuật di truyền cho tối ưu đa mục tiêu NSGA-II.Thuật giải di truyền nói chung là giải thuật dựa trên "Nguyên lý tiến hóa tự nhiên”của Charles Darwin. - Theo đó, trong một quần thể, cá thể có độ thích nghi càng caothì càng có cơ hội lớn di truyền những đặc điểm tốt đẹp của mình cho thế hệ sau thôngqua các quá trình tự nhiên: chọn lọc, sinh sản, đột biến.Giải thuật di truyền NSGA-II được ứng dụng trực tiếp vào giải quyết bài toán lậplịch cho hệ thống xe buýt nhanh BRT Yên Nghĩa - Kim Mã ở Hà Nội.Luận văn gồm ba phần:Chương I trình bày về bài toán lập lịch cho tuyến xe buýt nhanh BRT: giới thiệuvề BRT, cách mô hình hóa bài toán dưới dạng tối ưu đa mục tiêu và đánh giá mô hìnhđược đề xuất;iii Chương II giới thiệu về giải thuật di truyền NSGA II: các bước cụ thể để xây dựnggiải thuật di truyền, cách áp dụng giải thuật di truyền vào mô hình đã được đề ra;Chương III mô tả một ứng dụng cụ thể của mô hình vào tuyến xe buýt BRT YênNghĩa - Kim Mã ở Hà Nội: kết quả lập lịch là xấp xỉ của biên Pareto thể hiện sự tươngquan giữa cực tiểu thời gian đi lại của hành khách và cực đại hiệu quả sử dụng hệthống của nhà vận hành, đánh giá kết quả tìm được và hướng mở rộng mô hình.Kết quả nghiên cứu trong luận văn đã được viết thành bài báo và được nhận đăngtrong tạp chí Scopus: "International Journal of Machine Learning and Computing".Hiện nay, vấn đề lập lịch cho tuyến BRT còn đang rất mới ở Việt Nam cũng nhưmột số nước trên thế giới, nó đang được quan tâm nghiên cứu và phát triển mạnh mẽ.Vậy nên, đồ án chắc chắn còn nhiều thiếu sót, rất mong nhận được sự nhận xét, đánhgiá, bổ sung, góp ý của các thầy, cô giáo và các bạn.Đồ án được hoàn thành dưới sự giúp đỡ, hướng dẫn tận tình của TS. - Xin chân thành cảm ơn!Hà Nội, ngày 26 tháng 11 năm 2018Học viên thực hiệnPhan Nguyễn Bá Thắngiv Chương 1Lập lịch cho buýt nhanh BRTChương I trình bày về bài toán lập lịch cho tuyến xe buýt nhanh BRT: giới thiệuvề BRT, cách mô hình hóa bài toán dưới dạng tối ưu đa mục tiêu và đánh giá mô hìnhđược đề xuất.1.1 Xe buýt nhanh BRTBRT là viết tắt của Bus Rapid Transit, nghĩa là xe buýt nhanh. - Hệ thống BRT đượcxây dựng, cải tiến dựa trên mô hình xe buýt thông thường, với mục đích nâng cao khảnăng chuyên chở và tính thuận tiện. - BRT chính là sự kết hợp của khả năng vận chuyểnhành khách lớn và tốc độ của tàu điện ngầm và sự linh hoạt, đơn giản với chi phí thấpcủa hệ thống xe buýt. - Những đặc điểm sau của BRT sẽ làm sáng tỏ tại sao nó lại đượcgọi là hệ thống xe buýt nhanh:- Từng xe BRT được lập lịch dừng đỗ tại mỗi điểm dừng (có thể bỏ bến. - BRT chạy trên làn đường riêng (chiếm khoảng 3,2m chiều rộng mặt đường) đểđảm bảo tốc độ vận hành cho xe BRT;- BRT có sức chứa lớn (dài gấp đôi xe buýt thông thường hoặc sử dụng xe buýthai tầng), có thể chứa từ 80 – 100 hành khách;- Điểm dừng BRT có lối vào mua vé cho hành khách hoặc hành khách có thể thanhtoán bằng thẻ của nhà vận hành khi đi trên xe;- BRT chỉ dừng ở điểm dừng một khoảng thời gian ngắn. - Một lượng lớn hànhkhách có thể cùng lúc lên xuống xe BRT bằng nhiều cửa tự động;1 - BRT được trang bị hệ thống định vị GPS kết nối với trung tâm điều khiển, chophép xác định tốc độ hay khoảng cách từ xe tới giao lộ để tính toán ưu tiên cho xeBRT;- BRT chạy với tốc độ ổn định và chạy thường xuyên trong ngày (từ 5h-23h. - Có hệ thống xe buýt trung chuyển để gom hành khách vào tuyến chính và ngượclại. - Xe buýt trung chuyển chạy trên những tuyến ngắn và không cần phải chạy trênlàn đường riêng.Những đặc điểm trên cho thấy BRT có thể hiểu như một sự kết hợp của vận tảiđường sắt và tính chất linh hoạt của xe buýt [5]. - Qua đó, BRT có một số ưu điểm hơnhẳn xe buýt thông thường:- BRT nhanh hơn và an toàn hơn do được chạy trên tuyến đường riêng và có sựhỗ trợ bởi hệ thống tín hiệu ưu tiên tại các giao lộ;- BRT làm giảm thời gian chờ do biết trước thời điểm xe buýt đến điểm dừng, chủđộng trong việc đi lại, lên xuống xe nhanh và thuận tiện hơn;- Tránh ùn tắc, gây ảnh hưởng đến các phương tiện khác khi dừng đỗ;- Giảm lượng xe trên đường do xe BRT lớn;- Đi xe BRT có thể rút ngắn thời gian di chuyển;- Kinh nghiệm tại những thành phố của các quốc gia xây dựng BRT cho thấykhông phải trợ giá như xe buýt thông thường.Việc nâng cao chất lượng dịch vụ của hệ thống BRT phụ thuộc rất lơn vào cách xâydựng lịch trình. - Thông tin về lịch trình gồm có: tần số của tuyến xe buýt (headway -thời gian giữa hai xe buýt liên tiếp rời bến) được thể hiện ở [2], [6] và dạng lịch trìnhcủa từng xe hay lập lịch kết hợp (kế hoạch dừng đỗ ở các điểm dừng) được mô tả cụthể trong [1], [10]. - Các bài toán được mô hìnhhóa dưới dạng tối ưu đơn mục tiêu và chúng đều được giải quyết bằng cáchsử dụng các phương pháp heuristic Đặc điểm quan trọng làm BRT khác với hệ thống xe buýt thông thường đó là khảnăng lập lịch. - Theo kết quả dừng đỗ của một phương tiện BRT tại các điểm dừng,lịch trình được chia thành ba loại: lịch trình thông thường (normal scheduling – fulllength buýt), lịch trình khu vực (zone scheduling – short turn buýt) và lịch trình nhanh(express scheduling – express buýt). - Hình 1 thể hiện cụ thể các dạng lịch trình với màuđen là xe dừng còn màu trắng là xe bỏ bến.2 Hình 1: Các dạng lịch trình của xe BRT.Lịch trình thông thường: là dạng lịch trình giống với xe buýt thông thường, trongđó các xe phải dừng ở mọi điểm dừng trên tuyến (Hình 1a).Lịch trình khu vực: là dạng lịch trình mà các xe chỉ dừng ở những điểm dừng có lưulượng giao thông trung bình và cao hoặc theo vùng (Hình 1b).Lịch trình nhanh: là dạng lịch trình mà các xe chỉ dừng ở một số rất ít điểm dừngcó số lượng hành khách lên hoặc xuống lớn (Hình 1c).1.2 Bài toán lập lịch cho tuyến BRTMột tuyến BRT gồm: 2 điểm đầu cuối là 2 bến xe, có tổng số điểm dừng là N cốđịnh (hai bến cũng được xem như là điểm dừng) và được mô tả như trong Hình 2 [12]:Hình 2: Hình ảnh một tuyến BRT.Xét bài toán lập lịch cho tuyến BRT với các giả thiết ban đầu sau:- Việc khảo sát được thực hiện trên một tuyến BRT;3 - Xe BRT là hoàn toàn ưu tiên, nghĩa là nó luôn được phép chạy, dù có gặp đènđỏ hay không, và các xe ở tuyến đường giao cắt với tuyến BRT luôn phải chờ;- Xe BRT chạy với tốc độ ổn định, nên thời gian di chuyển giữa các điểm dừngluôn là một hằng số dương;- Tần suất khách đến ở mỗi điểm dừng (khách/phút) là không đổi trong thời giankhảo sát;- Thời gian dừng đỗ và thời gian tăng – giảm tốc tại mỗi điểm dừng là cố định;- Có đủ phương tiện cho đội xe BRT.Với những giả thiết trên, bài toán lập lịch cho BRT được phát biểu như sau:Đầu vào:- Tuyến đường có N điểm dừng (N ∈ N, N ≥ 2. - Có 3 dạng lịch trình cho sẵn để các xe lựa chọn: lịch trình thông thường, lịchtrình khu vực và lịch trình nhanh;- Thời gian xe chạy giữa hai điểm dừng liên tiếp;- Thời gian dừng đỗ và tăng - giảm tốc tại mỗi điểm dừng;- Ma trận tần suất khách đến cho trước;- Thời gian khảo sát T cố định;- Giá trị headway h cụ thể.Đầu ra:- Dạng lịch trình mà mỗi xe BRT lựa chọn được thể hiện dưới dạng xấp xỉ củabiên Pareto tương ứng với headway;- Chi phí về thời gian đi lại của hành khách và hiệu quả sử dụng hệ thống của nhàvận hành được thể hiện bằng giá trị tại các điểm trên xấp xỉ của biên Pareto.1.3 Mô hình tối ưu đa mục tiêu với bài toán lậplịch cho tuyến BRTSun, Zhou và Wang đã đề xuất phương pháp tối ưu đơn mục tiêu với việc tối ưuheadway và cách lập lịch kết hợp sao cho tổng chi phí (bao gồm chi phí thời gian chờcủa hành khách, thời gian hành khách đi lại trên xe và chi phí vận hành của hệ thống4 BRT) là nhỏ nhất [10]. - Điều này có vẻ không phù hợp với thực tế khi rõ ràng xe buýt BRT vớidạng lịch trình nhanh có thể vượt qua xe buýt hoạt động theo lịch trình thông thường.Trong mô hình [7] phải xem xét đến số lượng hành khách bị lỡ xe, đồng thời thứ tựxuất phát của các xe ở từng điểm dừng (thứ tự này sẽ thay đổi so với điểm xuất phátvì xét đến trường hợp xe vượt nhau) chưa được biểu diễn tường minh bằng công thứccụ thể.Trong mô hình mới cho bài toán dưới dạng tối ưu đa mục tiêu này sẽ giải quyết cácvấn đề trên với số lượng biến ít hơn, ít các ràng buộc hơn và sẽ rõ ràng hơn so với môhình [7].1.3.1 Định nghĩa các kí hiệuTrong mô hình, các kí hiệu về tham số và biến được thể hiện ở Bảng 1.1 và Bảng1.2:M - tổng số xe BRT tham gia giao thông trong khoảng thời gian khảo sát,N - tổng số điểm dừng trên một tuyến BRT được xét,i - phương tiện BRT thứ i (i = 1, 2. - M),j - Điểm dừng thứ jth trên tuyến BRT (j = 1, 2. - N),T - khoảng thời gian khảo sát,T0- thời gian dừng đỗ ở các điểm dừng,c - thời gian tăng hoặc giảm tốc của xe ở các điểm dừngL - số lượng hành khách tối ưu trên xe,h - giá trị headway,tj- thời gian xe di chuyển từ điểm dừng j − 1 đến điểm dừng j khi bỏ qua tănggiảm tốc,rj,k- tần suất khách đến tại điểm dừng j và muốn đến điểm dừng k(k > j) sau j.Bảng 1.1: Tham số5 dij- thời điểm xuất phát của xe i tại điểm dừng j,lj,k- tổng số xe dừng ở cả j và k theo lịch trình,δij- biến nhị phân, nhận giá trị 1 nếu xe i dừng tại j, ngược lại bằng 0,δij,k- biến nhị phân, nhận giá trị 1 nếu xe i dừng đồng thời tại cả j và k,ngược lại bằng 0,(I, j, k. - biến nguyên nhận giá trị là i nếu xe i thực sự xuất phát tại điểmdừng j ở vị trí thứ I trong tổng số các xe dừng đồng thời tại j và k;Ở bến (điểm xuất phát đầu tiên) thì thứ tự xuất phát tương ứng là1, 2. - Do nguyên nhân vượt nhau của các xe, thứ tự các xeBRT rời điểm dừng j 6= 1 có thể giống hoặc khác với thứ tự ban đầu.Để xác định đúng thứ tự xuất phát của các xe ở điểm dừng j có thểdựa vào giá trị của dij,Tij,k- khoảng thời gian xe i đi từ điểm dừng j đến điểm dừng k,Aij- tổng số hành khách xuống xe tại điểm dừng j từ xe i,Bij- tổng số hành khách lên xe tại điểm dừng j với xe i,Lij- tổng số hành khách hiện tại trên xe khi xe i di chuyển từ điểm dừngj tới j + 1.Bảng 1.2: Biến1.3.2 Mô hình bài toánBài toán được mô hình hóa dưới dạng tối ưu đa mục tiêu Vmin{f1, f2} (với thứnguyên trong từng hàm mục tiêu sẽ là người.thời gian. - Trong đó:• f1=NPj=1NPk=j+1lj,kPI=1rj,k.d(I,j,k)j−d(I−1,j,k)j22+NPj=1NPk=j+1lj,kPI=1d(I,j,k)j− d(I−1,j,k)j.rj,k.T(I,j,k)j,k,trong đó thành phần thứ nhất là tổng thời gian chờ xe thứ I của hành khách tại điểmdừng j trong khoảng thời giand(I,j,k)j− d(I−1,j,k)jvà thành phần thứ hai là tổng thờigian di chuyển trên xe củad(I,j,k)j− d(I−1,j,k)j.rj,khành khách từ điểm dừng j tới kbằng phương tiện I. - Như vậy hàm f1chính là tổng chi phí của hành khách;• f2=MPi=1NPj=1|Lij− L|.(tj+1+ (δij+ δij+1).c),khi số lượng hành khách trên xe Lijcao hơn hay thấp hơn lượng hành khách tốiưu mà nhà vận hành đưa ra, tất cả tình huống này đều chưa tốt. - Vì vậy hàm f2dùng6 để đánh giá độ hiệu quả hay hiệu năng sử dụng hệ thống của nhà vận hành.Các ràng buộc thời gian:Thời điểm xuất phát tại điểm dừng đầu tiên với mọi xe:di1= (i − 1).h, i = 1, M. - (1.1)Thời điểm xuất phát của xe i tại điểm dừng j bằng tổng của thời điểm xuất phát củaxe i đó tại điểm dừng j − 1 và thời gian di chuyển cộng với thời gian dừng đỗ, tănggiảm tốc của xe:dij= dij−1+ tj+ (δij−1+ δij).c + δij.T0. - (1.2)Xe i dừng đỗ đồng thời tại điểm dừng j và k hay không:δij,k= δij.δik. - (1.3)Tổng số xe dừng tại cả điểm dừng j và k:lj,k=MXi=1δij,k. - (1.4)Do xảy ra tình huống xe vượt nhau nên thứ tự của các xe rời khỏi điểm dừng j 6= 1 cóthể không giống như ban đầu. - Và xe BRT i có thể rời điểm dừng j ở vị trí thứ I trongtất cả các xe dừng đồng thời tại j và k (vì thế (I, j, k. - (1.6)phương trình (1.6) chỉ ra rằng xe i rời điểm dừng j trước hay sau xe m. - Giátrị của tổng δij,k.MPm=1,m6=iδmj,k.f(i, j, m) trong phương trình (1.5) chính là tổng số xe rờiđiểm dừng j trước xe i, trong tất cả các xe dừng ở tại j và k.7 Thời gian di chuyển của xe Ith từ j đến k bằng thời điểm xuất phát của xe Ith tại kminus thời điểm xuất phát của xe Ith tại j rồi trừ đi thời gian dừng đỗ T0:T(I,j,k)j,k= d(I,j,k)k− d(I,j,k)j− T0. - (1.7)(2) Các ràng buộc về số lượng hành khách:Tổng số lượng hành khách xuống xe i tại điểm dừng j bằng tổng số lượng hành kháchlên xe i tại tất cả các điểm dừng k trước j và muốn đi đến j:Aij= δij.j−1Xk=1δik.rk,j.d(I,k,j)k− d(I−1,k,j)k. - (1.8)Tổng số lượng hành khách lên xe i tại điểm dừng j bằng tổng số lượng hành kháchxuống xe i tại tất cả các điểm dừng k sau j và đi từ điểm dừng j:Bij= δij.NXk=j+1δik.rj,k.d(I,j,k)j− d(I−1,j,k)j. - (1.9)Tổng số lượng hành khách trên xe i khi xe đi từ điểm dừng j tới j + 1 bằng số lượnghành khách trên chính xe đó khi xe đi từ j − 1 đến j trừ đi lượng hành khách xuốngxe tại j cộng với lượng hành khách lên xe tại j:Lij= Lij−1+ Bij− Aij. - (1.10)Tóm lại, việc lập lịch kết hợp cho bài toán được mô hình hóa dưới dạng tối ưu haimục tiêu: Vmin{f1, f2}, với các ràng buộc về thời gian và các ràng buộc vềsố lượng hành khách . - Mô hình thuộc dạng tối ưu 0-1 và phi tuyến, khônglồi, dẫn đến khó giải quyết bằng các phương pháp tìm nghiệm tối ưu thông thường.Chương sau sẽ đưa ra giải thuật di truyền NSGA-II, một giải thuật tự nhiên và đơngiản để giải quyết bài toán này.8 Chương 2Giải thuật di truyền NSGA-IIChương này giới thiệu sơ lược về tối ưu đa mục tiêu và giải thuật di truyền NSGAII được sử dụng để giải quyết bài toán: định nghĩa, các bước cụ thể để xây dựng giảithuật và cách áp dụng vào mô hình đã được đề xuất.2.1 Sơ lược về tối ưu đa mục tiêuKhông mất tính tổng quát, giả sử tất cả các mục tiêu của bài toán cần được cực tiểuhóa - một mục tiêu loại cực đại hóa có thể được chuyển thành loại cực tiểu hóa bằngcách nhân với −1. - Bài toán cực tiểu hóa K mục tiêu được định nghĩa như sau: cho 1vectơ n chiều x = (x1. - xn) trong tập chấp nhận được X, tìm vectơ x∗mà nó cựctiểu tập K hàm mục tiêu đã cho z(x. - m).Một phương án chấp nhận được x được gọi là trội hơn phương án chấp nhận đượcy (x 6= y), khi và chỉ khi, zi(x. - Một phương án chấp nhận được được gọi là tối ưu Pareto nếu nó không bịtrội hơn bởi một phương án chấp nhận được nào trong tâp chấp nhận được. - Tập tấtcả các phương án chấp nhận được không bị trội hơn trong X được gọi là tập tối ưuPareto. - Với tập tối ưu Pareto đã cho, các giá trị hàm mục tiêu tương ứng trong khônggian mục tiêu được gọi là biên Pareto.Mục tiêu của các giải thuật tối ưu đa mục tiêu là xác định các lời giải trong tập tốiưu Pareto. - Thực tế, việc chứng minh một lời giải là tối ưu thường không khả thi vềmặt tính toán. - Vì vậy, một tiếp cận thực tế với bài toán tối ưu đa mục tiêu là tìm kiếmtập các lời giải là thể hiện tốt nhất có thể của tập tối ưu Pareto, một tập các lời giảinhư vậy được gọi là tập Pareto được biết tốt nhất (Best-known Pareto set).9 Với yêu cầu ở trên, cách tiếp cận tối ưu hóa đa mục tiêu cần thực hiện tốt ba tiêuchí mâu thuẫn nhau sau đây:- Tập Pareto-được-biết-tốt-nhất là một tập con của tập tối ưu Pareto.- Những phương án chấp nhận được trong tập Pareto-được-biết-tốt-nhất nên phânbố đều và đa dạng trên biên Pareto để cung cấp cho người ra quyết định một hình ảnhvề sự đánh đổi qua lại giữa các mục tiêu.- Biên Pareto-được-biết-tốt-nhất phải biểu thị toàn cảnh của biên Pareto.Với thời gian tính toán có giới hạn cho trước, tiêu chí thứ nhất được thực hiện tốtnhất bằng cách tìm kiếm trên một vùng đặc biệt của biên Pareto. - Tiêu chí thứ banhắm vào việc mở rộng biên Pareto tại hai đầu nhằm thăm dò những lời giải cực trị.2.2 Giải thuật di truyền NSGA-IIGiải thuật di truyền (GA – Genetic Algorithms) được xây dựng dựa trên cơ sở sựtiến hóa của quần thể sinh vật thuộc cùng một loài trong tự nhiên. - Từ đó, những cá thể mới có độ thíchnghi với môi trường cao hơn sẽ dễ dàng tồn tại, phát triển và di truyền những đặc tínhtốt đẹp đến thế hệ sau.Ứng dụng Thuyết tiến hóa, trong GA, mỗi cá thể sẽ được mã hóa dưới dạng mộtnhiễm sắc thể chứa N gen. - Xuất phát từ một số lượng lớn các cá thể cùng một loài(quần thể ban đầu), tiến hành đánh giá độ thích nghi từng cá thể. - Quần thể mới được sinh ra là những cá thể “tốt” trong tậphợp gồm: quần thể trước và những cá thể mới sinh ra. - Quá trình di truyền được lặpđi lặp lại cho đến khi tìm được kết quả “đủ tốt” cho bài toán.2.2.1 Sơ đồ chung của giải thuật NSGA-IIFast Non-dominated Sorting Genetic Algorithm (NSGA-II, xem tài liệu [9]) là mộtgiải thuật tiến hóa đa mục tiêu (Multi-objective Evolutionary Algoritms - MOEAs),kế thừa những ý tưởng của giải thuật di truyền. - Các phương án chấp nhận được sẽ10 nằm trên các biên mà những biên nằm ở phía trong sẽ bị trội hơn. - NSGA-II sử dụngphương pháp sắp xêp không trội với độ phức tạp thuật toán O(MN2), với M là sốmục tiêu và N là kích thước của quần thể. - Sơ đồ chung của giải thuật NSGA-II đượcthể hiện ở Hình 2.1 (Hình vẽ được lấy từ nguồn: http://oklahomaanalytics.com/data-science-techniques/nsga-ii-explained/).Hình 2.1: Sơ đồ giải thuật NSGA-II2.2.2 Cách biểu diễn cá thể và quá trình lai ghép, đột biếnBiểu diễn cá thể dưới dạng nhiễm sắc thể: Việc đầu tiên khi thực hiện giảithuật đó là phải tìm được cách biểu diễn các cá thể của loài (các phương án của bàitoán) dưới dạng nhiễm sắc thể, bằng cách ánh xạ các biến của bài toán lên một chuỗicó chiều dài xác định. - Tùy theo từng bài toán mà có những cách biểu diễn khác nhausao cho phù hợp. - Trong đó, hai cách biểu diễn thường được dùng nhất là biểu diễn nhịphân và biểu diễn sử dụng hoán vị:- Biểu diễn nhị phân: Mỗi cá thể tương ứng với một chuỗi độ dài n gồm các bit 0và 1, ý nghĩa của các bit phụ thuộc vào từng tình huống cụ thể. - Ví dụ như trong bài toán cái túi: Có n đồ vật cho trướckhối lượng và giá trị. - Khi đó, mỗi cá thể hay một phương án của bài toán sẽ là một chuỗi bit độdài n, bit thứ i nhận giá trị 1 nếu đồ vật i được cho vào túi còn bằng 0 nếu không chovào túi thỏa mãn ràng buộc bài toán;- Biểu diễn sử dụng hoán vị: Mỗi cá thể sẽ tương ứng một hoán vị của tập n kíhiệu nào đó. - Chẳng hạn với bài toán người du lịch: Một người du lịch muốn đi qua tất11 cả n thành phố và mỗi thành phố chỉ đi qua đúng một lần. - Khi đó, một phương án củabài toán chính là một hoán vị của tập n số: {1, 2. - Biểu diễn bằng giá trị trực tiếp: dùng trong các bài toán có chứa những giá trịphức tạp, chẳng hạn số thực. - Nếu dùng biểu diễn nhị phân của số thực sẽ dẫn đếnkích thước cá thể sẽ rất lớn. - Vì thế, một nhiễm sắc thể sẽ là một chuỗi các giá trị nàođó (số nguyên, số thực, kí tự. - Ví dụ như bài toán mà nghiệm là một điểm trongkhông gian, khi đó một nhiễm sắc thể sẽ là một bộ 3 số thực (x1, x2, x3).Quá trình lai ghép: Thông thường cá thể được biểu diễn dưới dạng một chuỗi nhịphân có độ dài cố định. - Việc gây đột biến vớimỗi cá thể sẽ được tiến hành với xác suất Pmthấp (thay đổi bit 0 thành 1 hoặc ngược12 lại). - Đột biến được tiến hành một cách ngẫu nhiên qua cách lựa chọn cá thể và ngẫunhiên vị trí đột biến trong cá thể đó.2.2.3 Giải thuật NSGA-IIGiả mã cho giải thuật NSGA-II được thể hiện như sau:procedure NSGA-II (N, NA)t ← 0Pt← new population(N)Qt← ∅A ← non dominated(Pt)while not stop criterion doRt← Pt∪ QtF ← fast non dominated sorting(Rt)Pt+1← ∅i ← 1while |Pt+1. - (fill Pt+1with the N − |Pt+1| less crowded individuals of Fi)Qt+1← selection(Pt+1, N)Qt+1← crossover(Qt+1)Qt+1← mutation(Qt+1)t ← t + 1A ← non dominated(A ∪ Qt)end whileend procedureTrong giải thuật:- Pt← new population(N): sinh ngẫu nhiên quần thể với kích thước N cá thểtheo phương pháp mã hóa đã biết ở trên;- A ← non dominated(Pt):trả về cá thể nằm ở biên đầu tiên (trong cùng) của13 quần thể Pt;- F ← fast non dominated sorting(Rt): thực hiện giải thuật Sắp xếp khôngtrội để tìm biên cho tất cả các phương án chấp nhận được trong quần thể Rt;- Ci← crowding distance assigment(Fi): tính toán khoảng cách quy tụ trênbiên Fiđể tìm những phương án có mật độ các phương án xung quanh nó là lớn nhất.Có thể thấy rằng, NSGA-II gồm có 2 thủ tục cơ bản:i) Thủ tục sắp xếp không trội: nó sẽ chia tất cả các phương án thành nhiều biên.Tất cả phương án trên biên thứ i sẽ trội hơn tất cả các phương án nằm trên biên j(với i < j), nghĩa là giá trị của tất cả các hàm mục tiêu của một phương án nằm trênbiên i sẽ tốt hơn tất cả các phương án thuộc biên j nằm ở trong biên i.ii) Tính toán khoảng cách quy tụ: khoảng cách quy tụ của một phương án nằmtrên một biên cho trước là trung bình khoảng cách của hai phương án gần nhất thuộccùng biên đó và nằm về hai phía của phương án đã cho. - Khoảng cách quy tụ càng nhỏthì mật độ các điểm tập trung xung quanh phương án là càng lớn. - Và trong một biên,một phương án sẽ được lựa chọn vào thế hệ tiếp theo nếu nó có khoảng cách quy tụđủ nhỏ. - Khoảng cách quy tụ chính là cơ sở cho quá trình chọn lọc.2.3 NSGA-II cho bài toán lập lịch buýt nhanh BRTLựa chọn tham số: xác định tham số tỉ lệ lai ghép thành công Pcvà tham số tỉ lệđột biến Pm.Mã hóa cá thể: đầu ra của bài toán là xấp xỉ của biên Pareto cho từng giá trị headwayh. - Như đã đề cập ở trên, việc lựa chọn lịch trình (kết quả dừng đỗ của xe i tại điểmdừng j theo dạng lịch trình l: δli,j) là biến quyết định của bài toán. - Vì vậy, phươngpháp mã hóa có thể được thực hiện như sau:– Gọi 01 là dạng lịch trình thông thường, 10 là dạng lịch trình khu vực và 11 làdạng lịch trình nhanh;– Nếu xét trong khoảng thời gian T = 15 phút, với headway h = 3, thì tổng số xesẽ là M = 5.⇒Một cá thể (hay một phương án xếp lịch cho 5 xe) có thể là Khởi tạo quần thể ban đầu: Quần thể ban đầu được khởi tạo ngẫu nhiên, gồm P0cáthể có dạng như trên.14 Chương 3Ứng dụng tối ưu đa mục tiêu chotuyến BRT Yên Nghĩa - Kim MãChương này mô tả một ứng dụng cụ thể của mô hình vào tuyến xe buýt BRTYên Nghĩa - Kim Mã ở Hà Nội: kết quả lập lịch là xấp xỉ của biên Pareto thể hiện sựtương quan giữa cực tiểu thời gian đi lại của hành khách và cực đại hiệu quả sử dụnghệ thống của nhà vận hành, đánh giá kết quả tìm được và hướng mở rộng mô hình.3.1 Tuyến BRT Yên Nghĩa - Kim MãHà Nội - thủ đô của Việt Nam. - Hợp phần xe buýt nhanh khối lượng lớn - BRTthuộc dự án "Phát triển giao thông đô thị Hà Nội”, đã đưa vào khai thác vào cuối năm2017, là một trong những dự án phát triển vận tải hành khách công cộng trọng điểmcủa Hà Nội. - Dự án nhằm góp phần thực hiện mục tiêu đáp ứng 40-50% nhu cầu đi lạicủa người dân , hạn chế số phương tiện cá nhân. - Sau Hà Nội thì Đà Nẵng và Thànhphố Hồ Chí Minh cũng đã nghiên cứu mô hình này. - Nó chạy qua một số con đường: Giảng Võ, Láng Hạ, Lê Văn Lương,Lê Văn Lương kéo dài, Lê Trọng Tấn, Quang Trung.3.2 Kết quả của giải thuật NSGA-IIÁp dụng giải thuật NSGA II vào mô hình bài toán với số liệu đầu vào sau:– Thời gian di chuyển giữa các điểm dừng cho ở Bảng 3.1;– Số điểm dừng N = 23 và thời gian xét là T = 1h;– Thời gian dừng đỗ là T0= 30s, thời gian tăng giảm tốc là c = 6s;– Vận tốc trung bình là 750m/pht, tương đương với 45km/h;– Tỉ lệ lai ghép Pc= 0.8 và tỉ lệ đột biến P m Đoạn đường Khoảng cách (m) Thời gian (phút)Yên Nghĩa Kim Mã 710 0.95Bảng 3.1: Thời gian di chuyển giữ các điểm dừngMa trận tần suất khách đến Hình 3.2 là ma trận tam giác trên với đường chéo bằng0 và có kích thước 23 × 23. - Số cho ở hàng j và cột k của ma trận cho biết số hànhkhách muốn đi từ điểm dừng j tới k trong một phút.Dựa trên ma trận tần suất khách đến ở Hình 3.2, ba dạng lịch trình được chọn nhưtrong Bảng 3.2: với dạng lịch trình thông thường xe đón trả khách ở mọi điểm dừng,dạng lịch trình khu vực xe dừng ở 12/23 điểm dừng và chỉ dừng ở 7/23 điểm dừng vớidạng lịch trình nhanh.17 Hình 3.2: Ma trận tần suất khách đến (đơn vị người/phút)Điểm dừng Lịch trình thông thường Lịch trình khu vực Lịch trình nhanhYên Nghĩa Kim Mã 1 1 1Bảng 3.2: Ba dạng lịch trình ("1" là dừng và "0" là không dừng)Giải thuật NSGA II được lập trình bằng Python và chạy trên máy tính có cấu hìnhbình thường core i5, RAM 8GB, CPU 2.49 GHz.18 NSGA II chạy với các tham số sau: số lượng thế hệ để dừng thuật toán là 500 vàkích thước của quần thể mỗi thế hệ là 150 cá thể. - Kết quả được thể hiện ở Hình 4.Với trục hoành thể hiện cho mục tiêu thư nhất (chi phí đi lại của hành khách) và trụchoành biểu diễn mục tiêu thứ hai (hiệu quả sử dụng hệ thống của nhà vận hành). - Mộtsố đánh giá về kết quả:- Dựa vào xấp xỉ của biên Pareto tìm được từ giải thuật NSGA II, số lượng các xeBRT và dạng lịch trình của từng xe cũng được xác định tùy theo tỷ lệ hợp lý giữa tổngchi phí đi lại của hành khách và hiệu năng sử dụng hệ thống của nhà vận hành.- Trên một xấp xỉ của biên Pareto, khi tăng số dạng lịch trình nhanh và lịch trìnhkhu vực thì tổng chi phí trung bình về thời gian chờ xe và thời gian hành khách dichuyển trên xe sẽ giảm và hiệu năng sử dụng hệ thống nhìn chung sẽ tăng lên.Hình 3.3: Kết quả NSGA-II19 Kết luậnNhiệm vụ chính của việc lập lịch cho tuyến BRT là xác định headway tối ưu (khoảngmấy phút thì cho một xe xuất phát tại bến) và lập lịch kết hợp cho những xe BRT đó(xe xuất phát thì chạy theo lịch trình như thế nào).Luận văn đề xuất một mô hình cải tiến để giải quyết hạn chế của mô hình cũ, đólà cho phép hai phương tiện BRT có thể vượt qua nhau. - Đồng thời bổ sung công thứctường minh cho việc xác định thứ tự xuất phát của các xe tại các điểm dừng khi xảyra hiện tượng vượt nhau. - Mô hình mới với việc bỏ qua việc xem xét thời gian hànhkhách lỡ xe do đã xác định cụ thể được xe mà hành khách sẽ lên nên số lượng biến íthơn, ít các ràng buộc hơn và sẽ rõ ràng hơn. - Bài toán được tiếp cận dưới cái nhìn củatối ưu hai mục tiêu (chi phí đi lại của hành khách và hiệu quả sử dụng hệ thống củanhà vận hành) và được giải quyết bằng giải thuật di truyền NSGA-II.Mô hình được áp dụng vào tuyến BRT Yên Nghĩa - Kim Mã của Hà Nội. - Với matrận tần suất khách đến cụ thể sẽ có đầu ra là các xấp xỉ của biên Pareto tương ứngvới các giá trị headway để người dùng có thể lựa chọn tỉ lệ phù hợp giữa lợi ích ngườidùng và lợi ích của nhà vận hành.Mô hình đề ra chỉ giải quyết trường hợp không hạn chế số lượng khách lên xe (nghĩalà nếu xe dừng lại, cứ có khách ở điểm dừng thì luôn được lên).Mô hình có thể mở rộng cho trường hợp xét đến các cột tín hiệu giao thông (trườnghợp BRT không hoàn toàn ưu tiên). - Khi đó, ta giả sử rằng cột đèn giao thông chínhlà một điểm dừng ảo với lượng khách muốn đến và rời đi từ nó luôn bằng 0, và hàmtổng chi phí sẽ thêm hàm chi phí thời gian chờ tại các điểm dừng ảo của khách trêntuyến BRT và trên tuyến thông thường giao cắt với nó.20 Tài liệu tham khảo[1] Avishai, C.: Urban transit scheduling: framework, review and examples
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt