I. Động cơ nghiên cứu
Vấn đề ùn tắc giao thông tại các thành phố lớn, đặc biệt là TP. Hồ Chí Minh, đã trở thành một thách thức lớn đối với sự phát triển bền vững. Theo thống kê, ùn tắc giao thông gây thiệt hại kinh tế lên đến 1.2 tỷ USD mỗi năm. Nguyên nhân chủ yếu được chỉ ra là do người dân chưa chú trọng đến việc sử dụng phương tiện giao thông công cộng, cụ thể là xe buýt. Để giải quyết vấn đề này, việc khuyến khích người dân sử dụng xe buýt là cần thiết. Luận văn tập trung vào việc tìm kiếm 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, nhằm đáp ứng nhu cầu di chuyển của người dân một cách hiệu quả.
1.1 Mục đích nghiên cứu
Mục tiêu của luận văn là 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. Việc áp dụng các giải thuật tìm K đường đi có thể dẫn đến những lộ trình không thực tế như detour hay overlap. Do đó, luận văn đề xuất sử dụng các độ đo sai biệt và các ràng buộc để đảm bảo rằng các lộ trình được gợi ý thực sự có nghĩa và phù hợp với nhu cầu của người dùng.
II. Tổng quan tài liệu
Bài toán tìm K đường đi ngắn nhất trong đồ thị không chứa chu trình âm đã được nghiên cứu từ lâu. Các giải thuật như Yen và Lawler được sử dụng để tìm ra K đường đi ngắn nhất, trong đó độ phức tạp của giải thuật Yen là O(m + nlogn). Tuy nhiên, chưa có giải pháp nào cải tiến đáng kể độ phức tạp trong trường hợp xấu nhất. Luận văn sẽ trình bày các giải thuật này và phân tích sự phù hợp của chúng trong việc tìm K lộ trình buýt trong môi trường thực tế.
2.1 Giải thuật tìm K đường đi tối ưu
Giải thuật tìm K đường đi tối ưu được chia thành hai loại: loại cho phép đỉnh lặp lại và loại không cho phép. Trong đó, giải thuật tìm đường đi đơn giản thường khó hơn và yêu cầu nhiều tài nguyên tính toán hơn. Luận văn sẽ phân tích các giải thuật này, đồng thời chỉ ra ưu nhược điểm của từng phương pháp trong việc áp dụng vào bài toán giao thông công cộng.
III. Giải pháp đề xuất
Luận văn đề xuất một quy trình đánh giá thực nghiệm để xác định K lộ trình buýt dựa trên các độ đo sai biệt và các ràng buộc. Mô hình hóa mạng lưới xe buýt thành đồ thị có yếu tố thời gian sẽ giúp tăng tính chính xác trong việc gợi ý lộ trình. Việc áp dụng các độ đo sai biệt sẽ giúp loại bỏ những lộ trình không thực tế và mang lại giá trị thực tiễn cho người dùng.
3.1 Mô hình hóa mạng lưới xe buýt
Mô hình hóa mạng lưới xe buýt thành đồ thị thời gian là bước quan trọng trong việc xác định K lộ trình tối ưu. Điều này cho phép hệ thống gợi ý lộ trình dựa trên thời gian thực và các yếu tố ảnh hưởng khác. Luận văn sẽ trình bày chi tiết về cách thức mô hình hóa này và các dữ liệu cần thiết để thực hiện.
IV. Kết quả thực nghiệm
Kết quả thực nghiệm cho thấy việc áp dụng các độ đo sai biệt có thể cải thiện đáng kể chất lượng các lộ trình được gợi ý. Số lượng truy vấn thành công đã tăng lên đáng kể nhờ vào việc sử dụng các phương pháp phân tích và đánh giá chất lượng lộ trình. Luận văn sẽ trình bày các số liệu thực nghiệm và phân tích kết quả để chứng minh tính hiệu quả của giải pháp đề xuất.
4.1 Đánh giá chất lượng nghiệm
Quy trình đánh giá chất lượng nghiệm dựa trên các tiêu chí rõ ràng sẽ giúp xác định được tập K lộ trình buýt phù hợp nhất với nhu cầu của người dùng. Kết quả cho thấy rằng việc áp dụng các độ đo sai biệt không chỉ giúp cải thiện chất lượng lộ trình mà còn tăng cường sự hài lòng của người dùng với dịch vụ giao thông công cộng.
