I. Giới thiệu vấn đề
Bài toán tìm đường đi ngắn nhất (shortest path) đã thu hút sự quan tâm của nhiều nhà khoa học trong nhiều thập kỷ qua. Đặc biệt, bài toán này trở nên phức tạp hơn khi áp dụng cho đồ thị có trọng số thay đổi theo thời gian. Tại các thành phố lớn như TP. Hồ Chí Minh, việc tìm kiếm thông tin giao thông, đặc biệt là thông tin về xe buýt, gặp nhiều khó khăn do thiếu dữ liệu và công cụ hỗ trợ. Việc sử dụng công nghệ định vị GPS cho phép thu thập dữ liệu thời gian thực về vị trí xe buýt, từ đó tạo ra cơ hội để phát triển các giải thuật tìm đường hiệu quả hơn. Mục tiêu của nghiên cứu này là phát triển một giải thuật tìm đường đi xe buýt theo thời gian, nhằm tối ưu hóa thời gian di chuyển cho người dân.
II. Phạm vi nghiên cứu
Nghiên cứu này tập trung vào việc xây dựng mô hình đồ thị cho mạng lưới xe buýt tại TP. Hồ Chí Minh, với các ràng buộc về thời gian. Các bước nghiên cứu bao gồm thu thập dữ liệu từ các thiết bị định vị, phân tích và xử lý dữ liệu, và xây dựng mô hình đồ thị. Bài toán tìm đường đi ngắn nhất sẽ được giải quyết thông qua các giải thuật như Dijkstra và Bellman-Ford, với mục tiêu tìm ra lộ trình tối ưu cho người sử dụng. Việc áp dụng các giải thuật này không chỉ giúp cải thiện hiệu suất tìm kiếm mà còn cung cấp thông tin chính xác về thời gian di chuyển, từ đó nâng cao trải nghiệm của người dân khi sử dụng phương tiện công cộng.
III. Phương pháp nghiên cứu
Luận văn áp dụng phương pháp kết hợp giữa lý thuyết và thực tiễn để giải quyết bài toán tìm đường đi ngắn nhất. Dữ liệu được thu thập từ các thiết bị định vị gắn trên xe buýt, sau đó được xử lý để xây dựng mô hình đồ thị. Các giải thuật như Dijkstra và Bellman-Ford sẽ được áp dụng để tìm kiếm lộ trình tối ưu. Đặc biệt, nghiên cứu sẽ chú trọng đến việc phát triển giải thuật gán nhãn cho các bài toán có ràng buộc, nhằm tối ưu hóa thời gian và chi phí cho người sử dụng. Kết quả nghiên cứu sẽ được trực quan hóa trên nền tảng bản đồ, giúp người dân dễ dàng tra cứu thông tin giao thông.
IV. Kết quả nghiên cứu
Nghiên cứu đã thu thập thành công dữ liệu mạng lưới xe buýt với hơn 110 tuyến tại TP. Hồ Chí Minh. Mô hình đồ thị phụ thuộc thời gian đã được xây dựng và áp dụng giải thuật tìm đường đi ngắn nhất với các ràng buộc. Kết quả cho thấy giải thuật đề xuất có khả năng tìm ra lộ trình tối ưu trong thời gian ngắn, đáp ứng nhu cầu thực tiễn của người dân. Việc triển khai ứng dụng tìm đường xe buýt theo thời gian thực không chỉ giúp người dân tiết kiệm thời gian mà còn nâng cao hiệu quả sử dụng phương tiện công cộng. Điều này chứng tỏ giá trị thực tiễn của nghiên cứu trong việc cải thiện hệ thống giao thông công cộng tại TP. Hồ Chí Minh.
V. Ý nghĩa nghiên cứu
Kết quả nghiên cứu không chỉ đóng góp vào lý thuyết về tìm đường đi ngắn nhất mà còn có giá trị thực tiễn cao trong việc cải thiện hệ thống giao thông công cộng. Mô hình lưới xe buýt theo không gian và thời gian giúp các nhà phân tích có cái nhìn sâu sắc hơn về tình trạng giao thông tại TP. Hồ Chí Minh. Giải thuật tìm đường đi ngắn nhất được phát triển trong nghiên cứu này có thể áp dụng cho nhiều loại hình giao thông khác nhau, từ đó mở rộng khả năng ứng dụng trong các lĩnh vực khác nhau như logistics, quản lý giao thông và phát triển đô thị. Điều này cho thấy tầm quan trọng của việc nghiên cứu và phát triển các giải thuật tối ưu trong bối cảnh đô thị hóa ngày càng gia tăng.
