Mở đầu 1. Động cơ nghiên cứu Trong những năm gần đây, ùn tắc giao thông ngày càng trở nên trầm trọng tại các thành phố lớn tại Việt Nam nói chung và thành phố Hồ Chí Minh nói riêng. Thực tế chỉ ra rằng kẹt xe gây thiệt hại rất lớn về kinh tế và môi trường, ảnh hưởng lớn đến việc phát triển đô thị bền vững. Theo bài tham luận của PGS.
Nguyễn Minh Hòa, Trưởng khoa Đô thị học, ĐH KHXHNV TP.HCM trong hội thảo quốc tế “Cơ hội và thách thức cho phát triển đô thị bền vững” tổ chức ngày 15/09/2014 tại ĐH KHXHNV TP.HCM, tắc nghẽn giao thông là một trong những vấn nạn nghiêm trọng, khó giải quyết nhất tại thành phố Hồ Chí Minh, làm tổn thất hằng năm lên đến 1.2 tỷ USD (http://tuoitre.vn/tin/chinh-tri-xa-hoi/ 20140915/tphcm-ket-xe-gay-thiet-hai-12-ty-usd-nam/646060.html) Nguyên nhân gây ùn tắc giao thông được chỉ ra chủ yếu là do người dân thờ ơ với phương tiện giao thông công cộng (xe buýt) so với phương tiện giao thông cá nhân (xe máy, loại hình đi lại gây kẹt xe nhiều nhất). Do đó, một trong những giải pháp giảm ùn tắc giao thông là khuyến khích người dân sử dụng các phương tiên công cộng. Cụ thể là cần xây dựng một hệ thống dịch vụ giao thông công cộng cung cấp những thông tin cần thiết, có khả năng đáp ứng được những nhu cầu di chuyển mà các phương tiện giao thông cá nhân hiện có. Dịch vụ giao thông công cộng là cần thiết đối với các thành phố hiện đại, cùng với sự phát triển nhanh chóng của các thiết bị hỗ trợ cá nhân như điện thoại thông minh, máy tính bảng hay các hệ thống gợi ý lộ trình sẽ giúp đỡ cho người dân có thể lập kế hoạch cho hành trình của họ một cách hiệu quả hơn.
Phần lớn các ứng dụng không chỉ gợi ý 1 lộ trình mà còn gợi 8 ý nhiều lộ trình tương tự khác, do đó sẽ linh động hơn cho người dùng cuối trong việc lựa chọn lộ trình phù hợp với tình hình giao thông hiện tại. Mặc khác, lộ trình buýt được gợi ý có tính chất “động”, nghĩa là cùng 1 câu truy vấn sẽ gợi ý các lộ trình buýt khác nhau phụ thuộc vào thời gian truy vấn của người dùng. Vì vậy, luận văn tập trung vào bài toán xác định K lộ trình tối ưu cho người sử dụng xe buýt dựa trên thời gian thực, nghĩa là phụ thuộc vào thời gian truy vấn của người dùng mà hệ thống sẽ gợi ý tập K lộ trình khác nhau. Ví dụ, nếu người dùng cùng sử dụng một truy vấn (cùng điểm khởi hành và điểm kết thúc) tại thời điểm 7h sáng và 9h sáng thì hệ thống sẽ gợi ý các lộ trình khác nhau.
Bài toán tìm đường đi tối ưu là một trong những bài toán được áp dụng rộng rãi nhất trong cuộc sống. Trong số đó, tìm đường đi tối ưu giữa hai địa điểm trên bản đồ số trong giao thông là phổ biến hơn cả. Các bài toán thường tập trung vào việc tìm ra 1 đường đi tối ưu dựa trên một tiêu chí nào đó (thời gian di chuyển ít nhất, quãng đường ngắn nhất, số lần chuyển tuyến ít nhất. Mặc khác, sở thích của người dùng có thể nhiều nhưng việc gợi ý một lộ trình tối ưu có thể không thỏa mãn hết các nhu cầu cần thiết của họ.
Do đó, thay vì gợi ý một lộ trình tối ưu từ điểm khởi hành đến điểm kết thúc thì việc gợi ý nhiều lộ trình tương tự sẽ hữu ích hơn cho người dùng lựa chọn theo sở thích cá nhân và linh động hơn trong việc lựa chọn lộ trình phù hợp với tình trạng giao thông hiện tại. Xét về gốc độ thực tiễn: Xuất phát từ bài toán thực tế có nhu cầu tìm K lộ trình buýt. Xét về gốc độ học thuật: Để xác định tập K lộ trình có 2 hướng tiếp cận: Phương pháp xấp xỉ và Phương pháp chính xác. Trong đó, các giải thuật của phương pháp chính xác chỉ phân biệt được lộ trình có chứa chu trình (loop) hoặc không chứa chu trình (loop-less), chứ không phân biệt được các lộ trình thực sự khác nhau bao nhiêu phần trăm, lộ trình có ý nghĩa với người dùng không.
Vì vậy, để gợi ý K lộ trình buýt “hợp lý” cho người dùng cuối, đề tài sử dụng thêm các độ đo sai biệt để loại bỏ những lộ trình thật sự không khác nhau nhiều và các ràng buộc để kết quả lộ trình thực sự có nghĩa. Tuy nhiên, cùng 1 truy vấn ứng với mỗi độ đo sai biệt sẽ gợi ý tập K lộ trình buýt khác nhau. Rõ ràng, mỗi độ đo sai biệt chỉ phù hợp với một đặc tính nào đó. Do đó, đề tài đề xuất quy trình đánh giá chất lượng nghiệm (tức tập K lộ trình buýt) của các độ đo sai biệt dựa trên một số tiêu chí.
Những thông tin và lý do trên đã trở thành động lực để chúng ta thực hiện luận văn này. Mục đích nghiên cứu Mục tiêu của luận văn xác định K lộ trình buýt dựa trên điểm xuất phát, điểm kết thúc và thời gian khởi hành. Tuy nhiên, việc áp dụng các giải thuật tìm K đường đi sẽ tồn tại những lộ trình không có nghĩa về mặt thực tế: detour, đi bộ liên tiếp, 9 những lộ trình overlap. Do đó, để gợi ý K lộ trình thực sự có nghĩa đối với người dùng, chúng ta đề xuất sử dụng các độ đo sai biệt và các ràng buộc.
Vì vậy, để giải quyết mục tiêu tổng quát đã đề ra, cần thực hiện từng bước những mục tiêu nhỏ sau: • Mô hình hóa mạng lưới xe buýt thành một đồ thị có thêm yếu tố thời gian (thời gian mỗi chuyến xe buýt hoạt động trong ngày và thời gian truy vấn của người dùng cuối). • Xây dựng các ràng buộc về lộ trình buýt, xây dựng giải thuật tìm K lộ trình buýt dựa trên các ràng buộc và độ đo sai biệt. • Quy trình đánh giá thực nghiệm để chọn ra tập K lộ trình buýt phù hợp với tiêu chí của người dùng dựa trên mỗi độ đo sai biệt. Đối tượng và phạm vi nghiên cứu Phạm vi nghiên cứu của luận văn chỉ tập trung vào đối tượng giao thông công cộng là xe buýt và cụ thể là Tp.Hồ Chí Minh.
Thời gian hoạt động hằng ngày của mỗi chuyến xe buýt và hành trình của các tuyến xe buýt là không có sự thay đổi. Không xem sét các yếu tố “điều kiện giao thông” khi tìm lộ trình buýt dựa trên thời gian. Phương pháp nghiên cứu Để đạt được các mục tiêu đã đề ra cho luận văn, các bước thực hiện bao gồm: • Thu thập dữ liệu từ hệ thống xe buýt Tp.Hồ Chí Minh. • Mô hình hóa mạng lưới xe buýt, xây dựng đồ thị, chọn lựa các độ đo sai biệt.
• Xây dựng bài toán tìm K lộ trình buýt có ràng buộc và đề xuất giải thuật để giải quyết bài toán đã đặt ra. • Xây dựng các tiêu chí thực nghiệm để đánh giá tập K lộ trình buýt trong mỗi độ đo và giữa các độ đo sai biệt với nhau. Cấu trúc luận văn Phần còn lại của luận văn này được tổ chức theo cấu trúc sau: 10 • Chương 2: Trình bày cơ sở lý thuyết gồm tổng quan về các công trình nghiên cứu liên quan đến bài toán tìm K đường đi và các hướng mô hình hóa mạng lưới xe buýt. • Chương 3: Đề xuất giải pháp để giải quyết bài toán xác định K lộ trình buýt dựa trên các độ đo sai biệt.
• Chương 4: Trình bày các kết quả đánh giá thực nghiệm dựa trên tập dữ liệu của xe buýt Tp.Hồ Chí Minh. 11 Chương 2 Cơ sở lý thuyết 2. Tổng quan tài liệu Bài toán tìm K đường đi ngắn nhất trong một đồ thị không chứa chu trình âm là bài toán cổ điển, không chỉ tìm ra một đường đi ngắn nhất từ đỉnh nguồn tới đỉnh đích mà còn tìm thêm (K − 1) đường đi ngắn nhất với K > 1, theo thứ tự tăng dần trong số của đường đi. Bài toán này được giải quyết đầu tiên vào năm 1959 bởi Hoffman và Pavley [6].
Kể từ đó, nhiều giải thuật khác nhau đã được đề xuất. Để hiểu rõ hơn các giải thuật này, người đọc có thể tham khảo tài liệu online tại http: //liinwww.de/bibliography/Theory/index. Nói chung, tất cả các giải thuật để giải quyết bài toán K đường đi ngắn nhất được chia làm 2 loại. Loại thứ nhất, cho phép có đỉnh lặp lại trong các đường đi ngắn nhất hay còn gọi là đường đi non-simple [7].
Loại thứ hai, không cho phép có đỉnh lặp lại trong các đường đi ngắn nhất hay còn gọi là đường đi simple, và loại này thường khó hơn loại thứ nhất [8]. Giải thuật tốt nhất để tìm ra K đường đi simple ngắn nhất trong một đồ thị có hướng (directed) hoặc vô hướng (undirected) là Yen [8] và Lawler [9]. Độ phức tạp trong trường hợp xấu nhất của giải thuật là O(m + nlogn) là độ phức tạp của giải thuật tìm đường đi ngắn nhất nguồn đơn nếu sử dụng cấu trúc dữ liệu hiện đại (Fibonaci-heap). Nhiều kỹ thuật [10, 11] được đề xuất để cải tiến giải thuật này trong đồ thị có hướng và thật sự hiệu quả.
Tuy nhiên, vẫn chưa cải tiến độ phức tạp trong trường hợp xấu nhất của giải thuật Yen. Ngược lại, nếu đồ thị là vô hướng, độ phức tạp của giải thuật Yen được cải tiến thành O(K(m + nlogn)) bởi Katoh, Ibaraki và Mine [12]. Giải thuật tốt nhất để tìm ra K đường đi non-simple ngắn nhất trong một đồ thị có hướng là Eppstein [13] và độ phức tạp O(m + nlogn + K). 12 Mặc khác, các giải thuật trong loại thứ hai được phần thành 4 nhóm.
Nhóm 1 sử dụng phương pháp vét cạn (Brute-force) gồm các giải thuật [14] phương pháp này không hiệu quả bởi vì nó sẽ liệt kê hết tất cả các đường đi có thể từ đỉnh nguồn tới đỉnh đích. Nhóm 2 sử dụng phương pháp nguyên tắc tối ưu (Optimality principle) gồm các giải thuật [15]. Nhóm 3 sử dụng phương pháp rẽ hướng đường đi (Path deviation) gồm các giải thuật [8]. Nhóm 4 sử dụng phương pháp thay thế đường đi (Replacement paths) gồm các giải thuật [16] tuy nhiên phương pháp này gặp một vấn đề là đường đi ngắn nhất được sinh ra có thể chứa các đỉnh lặp lại trong một số trường hợp.
Để giảm thời gian thực thi cho bài toán K đường đi ngắn nhất, một hướng tiếp cận khác là sử dụng phương pháp tính toán song song [17] hoặc phương pháp heuristic [18]. Tuy nhiên, phương pháp heuristic không tìm chính xác tập K đường đi ngắn nhất, có nghĩa một số đường đi ngắn nhất có thể bị thiếu sót.
