Tổng quan nghiên cứu

Ùn tắc giao thông tại các đô thị lớn ở Việt Nam, đặc biệt là khu vực Thành phố Hồ Chí Minh, đang là một thách thức nghiêm trọng đối với sự phát triển kinh tế và bảo vệ môi trường. Theo các báo cáo kinh tế đô thị, vấn nạn kẹt xe gây thiệt hại ước tính lên tới 1.2 tỷ USD mỗi năm cho nền kinh tế thành phố. Nguyên nhân cốt lõi bắt nguồn từ mật độ phương tiện cá nhân dày đặc và thói quen chưa mặn mà với phương tiện công cộng của người dân. Hệ thống xe buýt Thành phố Hồ Chí Minh với 220 tuyến và 4,243 trạm dừng đóng vai trò then chốt trong hạ tầng vận tải, nhưng các ứng dụng dẫn đường truyền thống chỉ cung cấp một lộ trình đơn lẻ hoặc đưa ra các phương án trùng lặp, thiếu tính thực tiễn theo thời gian thực.

Nghiên cứu này tập trung giải quyết bài toán xác định tập K lộ trình buýt tối ưu dựa trên thời gian thực, đáp ứng linh hoạt sở thích di chuyển cá nhân và tình trạng giao thông tại thời điểm truy vấn. Mục tiêu cụ thể của đề tài bao gồm việc mô hình hóa mạng lưới xe buýt thành đồ thị có trọng số phụ thuộc thời gian, xây dựng các ràng buộc hình học và phi chu trình để loại bỏ đường vòng (detour) hoặc đi bộ liên tiếp, đồng thời tích hợp 4 độ đo sai biệt tập hợp vào giải thuật tìm K đường đi ngắn nhất. Phạm vi nghiên cứu áp dụng trực tiếp trên toàn bộ dữ liệu vận hành xe buýt tại Thành phố Hồ Chí Minh trong giai đoạn 2016 - 2017 với khung giờ cao điểm từ 7:30 đến 8:00 sáng. Kết quả nghiên cứu mang ý nghĩa thực tiễn to lớn trong việc nâng cao tỷ lệ lựa chọn giao thông công cộng, tối ưu hóa thời gian phản hồi truy vấn dưới 500 mili-giây và giảm thiểu hơn 80% các lộ trình dư thừa so với thuật toán truyền thống.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng Lý thuyết đồ thị phụ thuộc thời gian (Time-Dependent Graph Theory) và Lý thuyết đường đi ngắn nhất (Shortest Path Theory). Khác với mô hình Time-Expanded vốn biểu diễn mỗi mốc thời gian thành một đỉnh riêng biệt gây bùng nổ kích thước đồ thị, mô hình Time-Dependent biểu diễn mỗi trạm dừng là một đỉnh cố định và trọng số trên cạnh được tính toán trực tiếp theo hàm chi phí thời gian khởi hành thực tế, thỏa mãn nghiêm ngặt nguyên lý First-In-First-Out (FIFO).

Mô hình nghiên cứu kế thừa và mở rộng giải thuật Yen tìm K đường đi đơn giản ngắn nhất, kết hợp giải thuật tìm đường đi ngắn nhất phụ thuộc thời gian (TDSP) với độ phức tạp tính toán tối ưu. Để đảm bảo tính độc lập và hữu ích của từng giải pháp gợi ý, đề tài ứng dụng 4 lý thuyết độ đo sai biệt tập hợp tuyến xe: Độ đo Jaccard, Độ đo Szymkiewicz-Simpson, Độ đo Sørensen–Dice và Độ đo Erkut-Vertex.

Các khái niệm then chốt trong mô hình bao gồm:

  1. Đồ thị hợp nhất không gian - thời gian biểu diễn trạng thái chờ tại trạm, di chuyển trên xe, lên xe, xuống xe và đi bộ chuyển tuyến.
  2. Ngưỡng sai biệt alpha xác định mức độ khác biệt tối thiểu về mặt tỷ lệ tuyến xe giữa hai hành trình.
  3. Ràng buộc đi bộ liên tiếp và ràng buộc đường vòng nhằm đảm bảo tính hợp lý của hành vi di chuyển.
  4. Quan hệ thay thế lộ trình dựa trên chi phí thời gian và mức độ bao phủ tuyến.

Phương pháp nghiên cứu

Nghiên cứu sử dụng nguồn dữ liệu thực tế từ mạng lưới giao thông xe buýt Thành phố Hồ Chí Minh gồm 220 tuyến buýt hai chiều, 4,243 trạm đón trả khách và 9,151 kết nối vận hành. Tập dữ liệu kiểm thử được thiết lập với cỡ mẫu gồm 1,000 truy vấn ngẫu nhiên phân bố trên toàn địa bàn thành phố. Phương pháp chọn mẫu là lấy mẫu ngẫu nhiên phân tầng không gian và thời gian, với điều kiện khoảng cách thực địa giữa điểm đi và điểm đến tối thiểu từ 5 km trở lên, thời gian khởi hành tập trung trong khung giờ cao điểm sáng từ 7:30 đến 8:00 nhằm phản ánh đúng áp lực giao thông thực tế.

Lý do lựa chọn phương pháp phân tích đồ thị Time-Dependent kết hợp giải thuật rẽ nhánh Yen có kiểm soát ngưỡng duyệt F bằng 5000 là nhằm cân bằng hoàn hảo giữa độ chính xác học thuật và tốc độ tính toán. Thay vì phải xử lý hàng trăm nghìn đỉnh như phương pháp cổ điển, giải pháp này cô đọng mạng lưới thành 13,614 đỉnh và 31,056 cạnh, giúp loại bỏ các nhánh duyệt vô hạn và đảm bảo thời gian phản hồi tức thì. Toàn bộ quy trình mô hình hóa, lập trình giải thuật và phân tích thực nghiệm được triển khai đồng bộ trong khoảng thời gian từ tháng 8 năm 2016 đến tháng 6 năm 2017.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích thực nghiệm trên 1,000 câu truy vấn thực tế đã chứng minh tính ưu việt của mô hình và mang lại những phát hiện học thuật quan trọng:

Thứ nhất, mô hình đồ thị Time-Dependent đã tối ưu hóa toàn bộ 220 tuyến buýt và 9,151 kết nối thành không gian đồ thị rút gọn gồm 13,614 đỉnh và 31,056 cạnh. Điều này giúp hệ thống mô phỏng chính xác thời gian chuyển tuyến và đi bộ với ngưỡng cự ly tối đa 150 mét ở vận tốc đi bộ 2 km/h mà không làm suy giảm hiệu năng xử lý.

Thứ hai, việc tích hợp các ràng buộc đường đi hợp lý đã giải quyết triệt để hiện tượng lộ trình rác. Trong một cấu trúc mạng lưới cơ bản sinh ra 12 đường đi ứng viên từ giải thuật Yen thuần túy, có tới 10 đường đi (tương đương 83.3%) bị loại bỏ do chứa đường vòng hoặc trùng lặp tuyến, chỉ giữ lại đúng 2 lộ trình (chiếm 16.7%) thực sự có giá trị sử dụng cho hành khách.

Thứ ba, nghiên cứu xác lập mối quan hệ tỷ lệ nghịch giữa ngưỡng sai biệt alpha, số lượng lộ trình K và tập truy vấn thành công. Khi tăng alpha từ 0.1 lên 0.9, số lượng truy vấn thành công có xu hướng giảm nhưng tỷ lệ đa dạng tuyến và tính mới của lộ trình lại tăng vọt. Với K = 2 và alpha = 0.5 ở độ đo Jaccard, hệ thống đạt điểm cân bằng tối ưu với tổng giá trị chất lượng nghiệm vượt mốc 150%.

Thứ tư, hiệu năng tính toán được kiểm chứng qua số lượng đường đi ứng cử viên trung bình và số đường đi duyệt qua trên tập truy vấn chung, chứng minh giải thuật duy trì thời gian đáp ứng ở mức mili-giây ngay cả khi K tăng lên 5.

Thảo luận kết quả

Sự suy giảm của số lượng truy vấn thành công khi nâng cao ngưỡng sai biệt alpha bắt nguồn từ cấu trúc hình học của mạng lưới xe buýt đô thị. Tại các khu vực ngoại thành hoặc các trục đường độc đạo, số lượng tuyến xe buýt chạy song song bị giới hạn, do đó việc áp đặt một ngưỡng khác biệt quá cao (như alpha trên 0.8) sẽ khiến không gian tìm kiếm không đủ số tuyến mới để tạo thành K hành trình hoàn chỉnh.

So sánh với các giải thuật tìm K đường đi truyền thống không ràng buộc, giải pháp đề xuất vượt trội hoàn toàn về mặt chất lượng nghiệm thực tế. Giải thuật truyền thống chỉ phân biệt đường đi đơn giản hay không đơn giản dựa trên đỉnh lặp lại, dẫn đến việc gợi ý các lộ trình chỉ khác nhau một trạm dừng không đáng kể. Ngược lại, phương pháp mới đảm bảo mỗi lộ trình trong tập kết quả đều mang lại một phương án tiếp cận giao thông hoàn toàn khác biệt về mặt tuyến xe.

Dữ liệu thực nghiệm của nghiên cứu được trực quan hóa sinh động thông qua hệ thống biểu đồ đường hai trục tọa độ và các bảng thống kê đa biến. Cụ thể, các biểu đồ phân tích đánh đổi giữa mức độ suy giảm truy vấn và mức gia tăng độ đa dạng giúp xác định trực quan giao điểm tối ưu cho từng cặp tham số. Đồng thời, bảng so sánh đa chỉ số thể hiện chi tiết độ lệch thời gian di chuyển trung bình, độ lệch số lần chuyển tuyến, số đường ứng viên và thời gian phản hồi, tạo nên một cơ sở dữ liệu định lượng vững chắc cho việc lựa chọn độ đo sai biệt phù hợp nhất.

Đề xuất và khuyến nghị

Dựa trên kết quả thực nghiệm, 4 giải pháp chiến lược được đề xuất nhằm chuyển hóa kết quả nghiên cứu vào thực tiễn quản lý đô thị:

Thứ nhất, tích hợp trực tiếp giải thuật tìm K lộ trình tối ưu có ràng buộc sai biệt vào ứng dụng giao thông công cộng và cổng thông tin xe buýt thông minh của Thành phố Hồ Chí Minh. Trung tâm Quản lý Giao thông công cộng cần chủ trì triển khai giải pháp này nhằm đạt mục tiêu thời gian đáp ứng truy vấn dưới 200 mili-giây cho hơn 100,000 lượt tra cứu mỗi ngày, hoàn thành trong giai đoạn Quý 1 đến Quý 2 năm 2025.

Thứ hai, chuẩn hóa và nâng cấp hệ thống định vị GPS tự động trên toàn bộ 220 tuyến xe buýt để truyền dữ liệu thời gian thực vào hàm chi phí của đồ thị Time-Dependent. Sở Giao thông Vận tải Thành phố Hồ Chí Minh chịu trách nhiệm điều hành, đảm bảo độ sai lệch thời gian đến trạm thực tế giảm xuống dưới 30 giây vào Quý 4 năm 2025.

Thứ ba, cải tạo và đồng bộ hạ tầng điểm dừng, nhà chờ nhằm rút ngắn cự ly đi bộ chuyển tuyến trung bình giữa 4,243 trạm dừng xuống dưới 100 mét. Ban Quản lý Dự án Đầu tư Xây dựng Công trình Giao thông cần thực hiện quy hoạch lại các điểm kết nối chuyển tuyến trọng điểm trong giai đoạn 2025 - 2026.

Thứ tư, mở rộng giải thuật sang mô hình giao thông công cộng đa phương thức kết hợp tuyến buýt nhanh BRT và mạng lưới đường sắt đô thị Metro số 1, số 2. Các viện nghiên cứu công nghệ thông tin phối hợp cùng doanh nghiệp phần mềm phát triển thuật toán mở rộng, hướng tới mục tiêu tăng trưởng 25% tỷ lệ hành khách sử dụng phương tiện công cộng trong giai đoạn 2026 - 2027.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang giá trị tham khảo sâu sắc cho 4 nhóm đối tượng chuyên môn:

Nhóm thứ nhất là các Kỹ sư phần mềm và Chuyên gia phát triển hệ thống giao thông thông minh (ITS). Nhóm này có thể ứng dụng trực tiếp thuật toán nén mạng lưới Time-Dependent với 13,614 đỉnh và cơ chế lọc lộ trình rác để xây dựng các công cụ tìm đường thương mại có độ trễ dưới 500 mili-giây.

Nhóm thứ hai là các Nhà quản lý đô thị và Chuyên viên quy hoạch mạng lưới giao thông tại các Sở Giao thông Vận tải. Số liệu phân tích về độ lệch chuyển tuyến và tính đa dạng trên 220 tuyến buýt cung cấp cơ sở định lượng để điều chỉnh các điểm nghẽn và tối ưu hóa luồng tuyến vận tải.

Nhóm thứ ba là Giảng viên, Học viên cao học và Nghiên cứu sinh ngành Khoa học máy tính, Hệ thống thông tin. Đây là tài liệu tham khảo mẫu mực về kỹ thuật mở rộng giải thuật Yen với độ phức tạp tính toán tối ưu kết hợp lý thuyết độ đo sai biệt tập hợp.

Nhóm thứ tư là các Doanh nghiệp công nghệ bản đồ số và dịch vụ điều hướng định vị. Doanh nghiệp có thể tích hợp khung đánh giá Lost và Gain để cá nhân hóa đề xuất lộ trình cho khách hàng, nâng cao độ chính xác và mức độ hài lòng lên trên 90%.

Câu hỏi thường gặp

Tại sao cần gợi ý K lộ trình thay vì chỉ một lộ trình ngắn nhất duy nhất?

Trong thực tế giao thông biến động, một lộ trình ngắn nhất trên lý thuyết có thể bị tắc nghẽn hoặc không phù hợp với sở thích cá nhân như hạn chế chuyển tuyến hay tránh đi bộ xa. Gợi ý K lộ trình mang lại sự linh hoạt, giúp hành khách chủ động chọn tuyến xe phù hợp với điều kiện thực tế tại thời điểm khởi hành.

Mô hình Time-Dependent vượt trội hơn Time-Expanded như thế nào?

Mô hình Time-Expanded tạo đỉnh cho từng mốc thời gian của 44 chuyến xe mỗi ngày, làm đồ thị phình to hàng trăm nghìn đỉnh. Mô hình Time-Dependent chỉ tạo 13,614 đỉnh cho toàn mạng lưới và tính trọng số động khi duyệt, giúp tiết kiệm bộ nhớ và tăng tốc độ xử lý gấp nhiều lần.

Vai trò chính của 4 độ đo sai biệt trong giải thuật là gì?

Các độ đo sai biệt (Jaccard, Simpson, Dice, Erkut-Vertex) định lượng tỷ lệ trùng lặp tuyến giữa các hành trình. Nhờ đó, giải thuật tự động loại bỏ những lộ trình gần như giống hệt nhau, đảm bảo mỗi phương án trong tập K kết quả đều mang lại giá trị di chuyển hoàn toàn mới cho người dùng.

Quy trình Lost và Gain giúp tối ưu hóa tham số như thế nào?

Quy trình Lost và Gain cân bằng giữa số lượng truy vấn thành công bị mất đi (Lost) và chất lượng đa dạng, tính mới thu được (Gain) khi tăng ngưỡng sai biệt. Qua đó, hệ thống tìm ra chính xác cặp tham số alpha và K tối ưu trên tập dữ liệu ổn định với ngưỡng chấp nhận 70%.

Giải thuật này có thể áp dụng cho hệ thống tích hợp cả xe buýt và tàu điện ngầm không?

Hoàn toàn khả thi. Bằng cách bổ sung các cạnh kết nối đại diện cho tuyến Metro và áp dụng hàm chi phí thời gian biểu của tàu điện, giải thuật vẫn vận hành tối ưu trên đồ thị phụ thuộc thời gian đa phương thức mà không cần thay đổi cấu trúc cốt lõi.

Kết luận

  • Xây dựng thành công mô hình đồ thị Time-Dependent nén toàn bộ mạng lưới 220 tuyến và 4,243 trạm buýt Thành phố Hồ Chí Minh thành cấu trúc tối ưu gồm 13,614 đỉnh và 31,056 cạnh.
  • Thiết lập 2 hệ thống ràng buộc cốt lõi giúp loại bỏ hơn 80% lộ trình rác, ngăn chặn triệt để hiện tượng đi bộ liên tiếp và đường vòng không hợp lý.
  • Ứng dụng thành công 4 độ đo sai biệt tập hợp vào giải thuật rẽ nhánh Yen, đảm bảo K lộ trình gợi ý luôn có sự phân tách rõ ràng về mặt tuyến xe.
  • Đề xuất quy trình đánh giá thực nghiệm Lost và Gain trên 1,000 truy vấn ngẫu nhiên, xác định chuẩn xác ngưỡng sai biệt tối ưu cho từng giá trị K từ 2 đến 5.
  • Đạt hiệu năng tính toán xuất sắc với thời gian phản hồi ở mức mili-giây dưới ngưỡng giới hạn 5000 đường đi, sẵn sàng triển khai trên các hệ thống thực tế.

Đóng góp chính của luận văn là đã giải quyết trọn vẹn bài toán gợi ý đa lộ trình có ý nghĩa thực tế trên mạng lưới giao thông công cộng phụ thuộc thời gian. Kế hoạch phát triển tiếp theo trong giai đoạn 2025 - 2027 tập trung vào việc mở rộng giải thuật cho mạng lưới vận tải đa phương thức và tích hợp dữ liệu tắc nghẽn giao thông trực tiếp qua GPS. Các cơ quan quản lý đô thị và doanh nghiệp công nghệ giao thông thông minh hãy cùng hợp tác ứng dụng giải pháp này để nâng tầm trải nghiệm giao thông công cộng hiện đại.