Luận Văn Thạc Sĩ: Xây Dựng Lộ Trình Định Hướng Giao Thông Tránh Kẹt Xe Theo Thời Gian Thực

Luận văn thạc sĩ khoa học máy tính nghiên cứu lộ trình định hướng giao thông, giúp giảm thiểu kẹt xe theo thời gian thực hiệu quả.

• Tác giả: Trần Ngọc Sơn
• Người hướng dẫn: TS. Phạm Trần Vũ
• Trường học: Đại học Quốc gia TP. HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Lộ Trình Giao Thông Thông Minh: Giải Pháp Tránh Kẹt Xe Thời Gian Thực
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CÁM ƠN
• TÓM TẮT ĐỀ TÀI
• ABSTRACT
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Lý do chọn đề tài
• 1.2. Mục tiêu của đề tài
• 1.3. Phạm vi nghiên cứu
• 1.4. Cấu trúc của đề tài
• 2. CHƯƠNG 2: TỔNG QUAN
• 2.1. Các công trình liên quan
• 2.2. Mô hình tổng quan
• 3. CHƯƠNG 3: CƠ SỞ LÝ THUYẾT
• 3.1. Lý thuyết đồ thị
• 3.2. Các giải thuật tìm đường
• 4. CHƯƠNG 4: GIẢI PHÁP
• 4.1. Xây dựng dữ liệu bản đồ
• 4.2. Viết chương trình thử nghiệm
• 4.3. Thử nghiệm các giải thuật tìm đường
• 4.4. Phát triển giải thuật Tránh kẹt xe
• 5. CHƯƠNG 5: THỬ NGHIỆM VÀ ĐÁNH GIÁ
• 5.1. Dữ liệu thử nghiệm
• 5.2. Phương pháp thử nghiệm
• 5.3. Đánh giá giải thuật
• 6. CHƯƠNG 6: KẾT LUẬN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về lộ trình giao thông thông minh

Trong bối cảnh giao thông ngày càng trở nên phức tạp, giao thông thông minh đã trở thành một giải pháp khả thi để tránh kẹt xe. Hệ thống này không chỉ giúp người dùng có được thông tin về tình trạng giao thông hiện tại mà còn dự đoán được tình hình trong tương lai. Việc sử dụng công nghệ hiện đại như GPS và smartphone đã tạo ra một nền tảng vững chắc cho việc thu thập và phân tích dữ liệu giao thông. Theo nghiên cứu, việc quản lý giao thông hiệu quả có thể giảm thiểu thời gian di chuyển và nâng cao trải nghiệm của người tham gia giao thông.

1.1. Tình trạng kẹt xe hiện nay

Tình trạng kẹt xe tại các thành phố lớn như Hà Nội và TP. Hồ Chí Minh đang ở mức báo động. Nguyên nhân chủ yếu là do cơ sở hạ tầng giao thông chưa đáp ứng được nhu cầu ngày càng tăng. Theo các chuyên gia, mật độ đường bộ trên diện tích đất đô thị tại Việt Nam chỉ bằng 1/5 so với các thành phố phát triển khác. Điều này dẫn đến tình trạng ùn tắc giao thông diễn ra thường xuyên, đặc biệt vào giờ cao điểm. Việc áp dụng giải pháp giao thông thông minh là cần thiết để cải thiện tình hình này.

II. Giải pháp giao thông thông minh

Giải pháp giao thông thông minh được xây dựng dựa trên việc thu thập và phân tích dữ liệu giao thông theo thời gian thực. Hệ thống này sử dụng smartphone để thu thập dữ liệu GPS, từ đó gửi về máy chủ trung tâm để xử lý. Dữ liệu này không chỉ giúp xác định tình trạng giao thông hiện tại mà còn dự đoán tình hình trong tương lai. Việc tối ưu hóa lộ trình di chuyển sẽ giúp người dùng tránh được các khu vực kẹt xe. Hệ thống này có thể hoạt động hiệu quả nhờ vào việc sử dụng công nghệ hiện đại và dữ liệu lớn.

2.1. Hệ thống thu thập dữ liệu

Hệ thống thu thập dữ liệu giao thông bao gồm hai phần chính: smartphone và máy chủ trung tâm. Smartphone sẽ thu thập dữ liệu GPS và gửi về máy chủ qua các kết nối như 3G hoặc GPRS. Máy chủ sẽ phân tích dữ liệu này để xác định tình trạng giao thông và gửi thông tin trở lại cho người dùng. Việc này không chỉ giúp người dùng nắm bắt được tình hình giao thông mà còn giúp họ điều chỉnh lộ trình di chuyển một cách hợp lý. Hệ thống này có thể được áp dụng rộng rãi và mang lại nhiều lợi ích cho người tham gia giao thông.

III. Phân tích và đánh giá giải pháp

Việc áp dụng giải pháp tránh ùn tắc giao thông thông minh không chỉ giúp giảm thiểu thời gian di chuyển mà còn nâng cao hiệu quả sử dụng hạ tầng giao thông. Hệ thống này cho phép người dùng nhận được thông tin giao thông theo thời gian thực, từ đó có thể điều chỉnh lộ trình di chuyển. Đặc biệt, việc sử dụng smartphone làm công cụ thu thập dữ liệu giúp giảm chi phí và tăng tính khả thi của hệ thống. Tuy nhiên, để đạt được hiệu quả tối ưu, cần có sự phối hợp chặt chẽ giữa các cơ quan chức năng và người dân trong việc cung cấp dữ liệu.

3.1. Lợi ích và thách thức

Lợi ích của hệ thống giao thông thông minh là rất rõ ràng. Nó không chỉ giúp giảm thiểu tình trạng kẹt xe mà còn nâng cao trải nghiệm di chuyển của người dân. Tuy nhiên, thách thức lớn nhất vẫn là việc thu thập dữ liệu chính xác và kịp thời. Để hệ thống hoạt động hiệu quả, cần có sự tham gia tích cực từ người dùng trong việc cung cấp thông tin về tình trạng giao thông. Ngoài ra, việc phát triển hạ tầng công nghệ thông tin cũng là yếu tố quan trọng để đảm bảo hệ thống hoạt động ổn định và hiệu quả.

Nội dung chính

Tổng quan nghiên cứu

Tình trạng kẹt xe tại các đô thị lớn của Việt Nam, đặc biệt là Hà Nội và thành phố Hồ Chí Minh, ngày càng trở nên nghiêm trọng và lan rộng không chỉ vào giờ cao điểm mà còn trong suốt cả ngày. Theo ước tính, mật độ đường bộ tại các thành phố này chỉ bằng khoảng 1/5 đến 1/20 so với các thành phố phát triển ở Mỹ và châu Âu, dẫn đến sự mất cân bằng trong kết cấu mạng lưới giao thông. Việc mở rộng hạ tầng đường bộ gặp nhiều khó khăn do quỹ đất hạn chế và chi phí giải phóng mặt bằng cao. Trước thực trạng này, việc ứng dụng công nghệ thông tin, đặc biệt là hệ thống thu thập dữ liệu giao thông và cảnh báo kẹt xe dựa trên điện thoại thông minh, được xem là giải pháp hiệu quả và khả thi.

Mục tiêu chính của luận văn là nghiên cứu và phát triển một giải thuật xây dựng lộ trình, định hướng giao thông theo thời gian thực nhằm giúp người dùng tránh các khu vực kẹt xe. Phạm vi nghiên cứu tập trung tại khu vực Hồ Con Rùa, Quận 1, thành phố Hồ Chí Minh, với kế hoạch mở rộng ra toàn thành phố và các khu vực khác trong tương lai. Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện hiệu quả lưu thông, giảm thiểu thời gian di chuyển và góp phần giảm ùn tắc giao thông, từ đó nâng cao chất lượng cuộc sống đô thị.

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

Khung lý thuyết áp dụng

Luận văn dựa trên lý thuyết đồ thị để mô hình hóa mạng lưới giao thông, trong đó các giao lộ được biểu diễn dưới dạng đỉnh (nodes) và các đoạn đường nối các giao lộ là các cạnh (edges). Các loại đồ thị được sử dụng bao gồm đơn đồ thị có hướng và đa đồ thị có hướng, phù hợp với đặc điểm giao thông Việt Nam, nơi có nhiều tuyến đường một chiều và đa dạng về vận tốc theo thời gian.

Các giải thuật tìm đường truyền thống như Dijkstra và Floyd-Bellman được phân tích, tuy nhiên do tính chất động của giao thông theo thời gian thực, các giải thuật này không đáp ứng được yêu cầu. Giải thuật A* được lựa chọn làm cơ sở do khả năng tìm đường heuristic hiệu quả, tuy nhiên vẫn chưa đủ để xử lý dữ liệu giao thông thay đổi liên tục. Do đó, luận văn phát triển một giải thuật mới mang tên "Giải thuật Tránh kẹt xe" dựa trên dữ liệu vận tốc thay đổi theo thời gian thực, nhằm tối ưu thời gian di chuyển thay vì chỉ tối ưu khoảng cách.

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

Nguồn dữ liệu chính được sử dụng là dữ liệu bản đồ mở OpenStreetMap (OSM) của khu vực nghiên cứu, được chuyển đổi sang dạng dữ liệu đồ thị có cấu trúc gồm bảng nodes (giao lộ) và edges (đoạn đường) với các thuộc tính như chiều dài, vận tốc theo thời gian. Dữ liệu vận tốc giao thông theo thời gian thực được giả lập cho khu vực Hồ Con Rùa từ 7 giờ đến 12 giờ để phục vụ thử nghiệm.

Phương pháp phân tích bao gồm xây dựng chương trình thử nghiệm trên nền web sử dụng PHP, MySQL và Google Maps API để biểu diễn bản đồ và tình trạng giao thông. Giải thuật Tránh kẹt xe được phát triển và so sánh với giải thuật A* về thời gian di chuyển, độ dài quãng đường và thời gian chạy thuật toán. Cỡ mẫu thử nghiệm gồm nhiều lần chạy với các điểm xuất phát và kết thúc khác nhau trong khu vực nghiên cứu. Timeline nghiên cứu kéo dài từ việc thu thập, xử lý dữ liệu đến thử nghiệm và đánh giá giải thuật.

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

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

1. Hiệu quả của giải thuật Tránh kẹt xe trong việc giảm thời gian di chuyển: Kết quả thử nghiệm cho thấy giải thuật Tránh kẹt xe giúp giảm thời gian di chuyển trung bình khoảng 5-10% so với giải thuật A*, mặc dù quãng đường có thể dài hơn hoặc ngắn hơn tùy trường hợp. Ví dụ, trong thử nghiệm lần 1, thời gian di chuyển của giải thuật Tránh kẹt xe là 14274 giây so với 1462 giây của A* (số liệu giả lập), thể hiện sự ưu việt trong việc tránh các khu vực kẹt xe.

2. Tính chính xác trong dự báo tình trạng giao thông theo thời gian thực: Dữ liệu giả lập vận tốc giao thông từ 7 giờ đến 12 giờ cho thấy tốc độ di chuyển chậm nhất vào khoảng 7-8 giờ sáng, sau đó tăng dần đến 12 giờ trưa. Giải thuật Tránh kẹt xe tận dụng tốt dữ liệu này để điều chỉnh lộ trình phù hợp với tình trạng giao thông hiện tại.

3. Thời gian chạy thuật toán: Giải thuật Tránh kẹt xe có thời gian chạy trung bình từ 0.38 đến 0.58 giây, so với 0.43 đến 0.53 giây của giải thuật A*, cho thấy độ phức tạp tính toán cao hơn nhưng vẫn đảm bảo khả năng xử lý trong thời gian thực.

4. Khả năng ứng dụng thực tế: Hệ thống thu thập dữ liệu và cảnh báo giao thông dựa trên điện thoại thông minh có chi phí thấp, dễ dàng triển khai và có thể mở rộng quy mô, phù hợp với điều kiện hạ tầng và đặc thù giao thông Việt Nam.

Thảo luận kết quả

Nguyên nhân chính giúp giải thuật Tránh kẹt xe vượt trội là do nó sử dụng dữ liệu vận tốc thay đổi theo thời gian thực để tính toán trọng số cạnh trong đồ thị, từ đó xây dựng lộ trình tối ưu về thời gian di chuyển thay vì chỉ dựa trên khoảng cách địa lý. So với các nghiên cứu trước đây sử dụng giải thuật tĩnh như Dijkstra hay A*, giải thuật này phù hợp hơn với môi trường giao thông động và phức tạp.

Kết quả thử nghiệm có thể được trình bày qua biểu đồ so sánh thời gian di chuyển và độ dài quãng đường giữa hai giải thuật theo từng lần thử nghiệm, giúp minh họa rõ ràng ưu điểm của giải thuật Tránh kẹt xe. Ngoài ra, bảng tổng hợp thời gian chạy thuật toán cũng cho thấy tính khả thi của giải pháp trong ứng dụng thực tế.

Việc sử dụng dữ liệu giả lập là một hạn chế, tuy nhiên nó phản ánh khá sát thực tế kẹt xe vào giờ cao điểm tại khu vực nghiên cứu. Khi có dữ liệu thực tế từ hệ thống thu thập GPS, độ chính xác và hiệu quả của giải thuật sẽ được nâng cao hơn nữa.

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

1. Triển khai hệ thống thu thập dữ liệu giao thông qua điện thoại thông minh rộng rãi: Tăng cường số lượng người dùng tham gia để thu thập dữ liệu GPS chính xác và đa dạng, giúp cải thiện độ tin cậy của dự báo giao thông. Chủ thể thực hiện: các cơ quan quản lý giao thông, nhà phát triển phần mềm; Timeline: 6-12 tháng.

2. Phát triển và tích hợp giải thuật Tránh kẹt xe vào các ứng dụng bản đồ và điều hướng hiện có: Đảm bảo người dùng được cập nhật lộ trình tối ưu theo thời gian thực, giảm thiểu kẹt xe cá nhân và cộng đồng. Chủ thể thực hiện: các công ty công nghệ, nhà phát triển ứng dụng; Timeline: 3-6 tháng.

3. Mở rộng phạm vi nghiên cứu và thử nghiệm ra toàn thành phố và các khu vực khác: Thu thập dữ liệu thực tế đa dạng hơn, đánh giá hiệu quả giải thuật trong nhiều điều kiện giao thông khác nhau. Chủ thể thực hiện: các viện nghiên cứu, trường đại học; Timeline: 12-18 tháng.

4. Kết hợp dữ liệu từ nhiều nguồn khác nhau như xe buýt, camera giao thông, báo cáo người dùng: Tăng cường độ chính xác và khả năng dự báo của hệ thống, từ đó nâng cao hiệu quả điều hướng giao thông. Chủ thể thực hiện: các cơ quan quản lý giao thông, nhà cung cấp dịch vụ dữ liệu; Timeline: 6-12 tháng.

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

1. Các nhà quản lý và hoạch định chính sách giao thông đô thị: Luận văn cung cấp giải pháp công nghệ mới giúp giảm ùn tắc giao thông, hỗ trợ ra quyết định về đầu tư và phát triển hạ tầng.

2. Các nhà phát triển phần mềm và công nghệ giao thông thông minh: Tham khảo phương pháp xây dựng giải thuật và hệ thống thu thập dữ liệu thời gian thực để phát triển ứng dụng điều hướng và cảnh báo giao thông.

3. Các nhà nghiên cứu trong lĩnh vực khoa học máy tính và giao thông: Cung cấp cơ sở lý thuyết, mô hình và kết quả thử nghiệm để phát triển các nghiên cứu tiếp theo về giao thông thông minh.

4. Các tổ chức vận tải công cộng và doanh nghiệp logistics: Áp dụng giải pháp để tối ưu hóa lộ trình vận chuyển, giảm thiểu thời gian chờ và chi phí vận hành.

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

1. Giải thuật Tránh kẹt xe khác gì so với các giải thuật tìm đường truyền thống?
   Giải thuật Tránh kẹt xe sử dụng dữ liệu vận tốc thay đổi theo thời gian thực để tính toán thời gian di chuyển tối ưu, trong khi các giải thuật truyền thống như Dijkstra hay A* chỉ dựa trên khoảng cách hoặc trọng số tĩnh.

2. Hệ thống thu thập dữ liệu giao thông hoạt động như thế nào?
   Hệ thống sử dụng điện thoại thông minh có GPS để thu thập vị trí và vận tốc người dùng, gửi dữ liệu về máy chủ qua mạng 3G, GPRS hoặc SMS, sau đó xử lý và phân tích để cảnh báo tình trạng giao thông.

3. Dữ liệu giả lập có ảnh hưởng thế nào đến kết quả nghiên cứu?
   Dữ liệu giả lập được thiết kế sát với thực tế kẹt xe vào giờ cao điểm, giúp đánh giá hiệu quả giải thuật trong điều kiện gần giống thực tế. Tuy nhiên, dữ liệu thực tế sẽ nâng cao độ chính xác và khả năng ứng dụng.

4. Giải thuật có thể áp dụng cho các thành phố khác không?
   Có thể áp dụng cho các thành phố có đặc điểm giao thông tương tự, tuy nhiên cần điều chỉnh dữ liệu đầu vào và tham số giải thuật phù hợp với đặc thù từng địa phương.

5. Thời gian chạy giải thuật có đáp ứng được yêu cầu thời gian thực không?
   Thời gian chạy giải thuật Tránh kẹt xe trung bình dưới 0.6 giây, đủ nhanh để xử lý và cập nhật lộ trình trong thời gian thực cho người dùng.

Kết luận

• Luận văn đã phát triển thành công giải thuật Tránh kẹt xe dựa trên dữ liệu giao thông theo thời gian thực, giúp xây dựng lộ trình tối ưu về thời gian di chuyển.
• Giải thuật này vượt trội hơn các giải thuật tìm đường truyền thống về khả năng thích ứng với tình trạng giao thông động.
• Hệ thống thu thập dữ liệu giao thông qua điện thoại thông minh được thiết kế với chi phí thấp và khả năng mở rộng cao.
• Kết quả thử nghiệm tại khu vực Hồ Con Rùa, Quận 1 cho thấy hiệu quả rõ rệt trong việc giảm thời gian di chuyển và tránh kẹt xe.
• Các bước tiếp theo bao gồm mở rộng phạm vi nghiên cứu, tích hợp giải thuật vào ứng dụng thực tế và thu thập dữ liệu giao thông thực tế để nâng cao độ chính xác.

Khuyến khích các cơ quan quản lý và doanh nghiệp công nghệ phối hợp triển khai thử nghiệm thực tế, đồng thời phát triển hệ thống thu thập dữ liệu quy mô lớn nhằm góp phần cải thiện giao thông đô thị Việt Nam.

Trích đoạn nội dung tài liệu

Chương 1: Giới thiệu dé tài - Ly do chọn đề tài. - Muc tiêu và phạm vi nghiên cứu của đề tài. Chương 2: Tổng quan về dé tài - _ Phân tích, đánh giá các công trình liên quan đến dé tài. - _ Đưa ra mô hình tong quan của hệ thống, từ đó xác định các van dé mà dé tài tập trung nghiên cứu giải quyết.

Chương 3: Cơ sở lý thuyết - Trinh bày một phân về lý thuyết đồ thi dùng để biểu diễn bản đô. - Tim hiểu một số giải thuật tìm đường trên đồ thị. Chương 4: Giải pháp thực hiện Xây dựng dữ liệu bản đồ để dùng cho tìm đường. - _ Viết chương trình biểu diễn ban đồ, tình trạng giao thông, cập nhật tình trạng giao thông.

- _ Thử nghiệm các giải thuật tìm đường trên ban dé như Dijkstra, A*. - Phat triển giải thuật Tránh kẹt xe dựa trên tình trạng giao thông theo thời gian thực. Chương 5: Thử nghiệm và đánh giá - Chuan bị đữ liệu về tình trạng giao thông cho giải thuật Tránh ket xe. - Chay thử nghiệm giải thuật Tránh ket xe và giải thuật A*.

- _ Đánh giá ưu và nhược điểm của giải thuật Tránh kẹt xe. Chương 6: Kết luận - _ xác định các công việc đã làm được trong đề tài. - _ Đóng góp của dé tài cho đất nước. - _ Hướng phát triển của dé tài.

Chương 2: TONG QUAN 2. Các công trình liên quan Trên thế giới đã có nhiều công trình liên quan đến vấn đề giao thông và việc xây dựng lộ trình theo thời gian thực như: đánh giá các hiệu quả việc di chuyển trong các ứng dụng giao thông thời gian thực [1], dùng giải thuật D* dé lập kế hoạch theo thời gian thực [2], chia sẻ thông tin tình trang giao thông qua các phương tiện liên lạc [3],[4], xác định thời gian di chuyển bằng cách dùng xe thăm dò gan GPS [5]. xác định thông tin các xe ở gần dựa vào thiết bị gắn trên xe [7], tìm đường trên mang ad hoc giữa các phương tiện dựa vào dữ liệu thời gian thực [8], xác định tình trang giao thông dựa trên dữ liệu theo thời gian thực của hệ thống xe taxi [9]. Ngoài ra, Google Maps [14] cũng đã hỗ trợ hiển thi thong tin tình trạng giao thông thời gian thực tại hầu hết các thành phố lớn tại Mỹ.

Tuy nhiên, không biết bao giờ Google Maps mới hé trợ hiển thị tình trạng giao thông ở Việt Nam? (| Maes oochaven 4 Coumtry Club 3 —— Gateway) iW It Park © t = — 1 3; Meadowbrook Municpal GC ‘ ` _—t Google Maps thêm vào các đường giao thông một lớp chứa thông tin tốc độ di chuyển trung bình tại vi trí đó như màu xanh lá, vàng, đỏ hoặc xám. Cac mau sắc tượng trung cho tốc độ di chuyển trung bình trên vị trí tương ứng như sau: o Màu xanh lá: tốc độ trên 50 dặm / | giờ. o Màu vàng: tốc độ từ 25 đến 50 dặm/ 1 giờ. o Màu đỏ: tốc độ dưới 25 dặm/ 1 giờ.

o Màu xám: Không có dữ liệu Đặc biệt, ở Việt Nam cũng có hệ thống lớn hỗ trợ về thông tin giao thông, đó là kênh VOV giao thông phát trên sóng FM 91Mhz. Đây là kênh thông tin toàn cảnh về giao thông tại hai thành phố lớn là Hà Nội và thành phố Hồ Chí Minh, nơi giải đáp mọi thắc mắc về các vấn đề giao thông cho thính giả khi gọi đến chương trình, đồng thời còn có thể chia sẻ tình hình giao thông trên đường phó, nhất là vào giờ cao điểm. Các thông tin về giao thông và ùn tắc, kẹt xe liên tục được cập nhật bởi hệ thống camera được lắp đặt tại các nút giao thông và lực lượng phóng viên tác nghiệp tại hiện trường.2: Nhiéu sinh viên trường Cao đăng PTTH 2 dang kỷ làm CTV VOV giao thông thành phố Hô Chí Minh Tuy nhiên, giao thông ở Việt Nam lại rất đặc thù, không giống như giao thông ở các quốc gia khác chủ yếu là xe hơi, các phương tiên giao thông ở Việt Nam chủ yếu 1a xe máy. Do đó các giải pháp về giao thông ở các nước khác chưa chắc đã hoạt động tốt nếu áp dụng ở Việt Nam.

Từ các van dé trên, mô hình tổng quan của hệ thống thu thập dữ liệu và cảnh báo tình trạng giao thông được đưa ra, từ đó xác định các van dé mà dé tài tap trung nghién cứu giải quyết. Mô hình tổng quan Hình 2.3 đưa ra cái nhìn tong thể về hệ thống thu thập dữ liệu và cảnh báo tình trạng giao thông. Hệ thông bao gồm hai phan chính: điện thoại thông minh (Smartphone) và máy chủ trung tâm (Server). Ngoải ra máy chủ còn bao gồm cả website cho phép người dùng xem tình hình giao thông ngay trên trình duyệt của máy tính, laptop.

Server I Web Applicati Smartphone SR ER APSE Traffic Visualizer GPS Sensor [14 al Browser Traffic Visualizer ADN CODUUE | Traffic Routt LỘ J Traffic Notifier ——————— OOO —=—== Traffic Data Extractor | i— Traffic Monitoring | :— a | GPS Data Filter & Clean | | | | Traffic Analyzer : ij lã | | | GPS-Locahon Mapper | | Traffic Notifier | | | c —ŸÝŸ- “an ——= — | Hình 2.3: Hệ thống thu thập dữ liệu và cảnh báo tình trạng giao thông 2. Điện thoại thông minh Điện thoại thông minh là thành phần chính tương tác giữa hệ thống với người dùng. Mỗi điện thoại sẽ được cài đặt một phân mềm có ba chức năng chính sau: - Thu thập dữ liệu GPS (GPS Sensor) như vị trí, tốc độ của người dùng cùng với thời gian ma dữ liệu được thu thập trong các khoảng thời gian cố định. Các dữ liệu này sẽ được gửi lên máy chủ trung tâm thông qua 3G, GPRS hoặc tin nhắn SMS.

Mức độ thu thập dữ liệu và gửi dữ liệu lên máy chủ trung tâm có thể khác nhau. Biểu diễn giao thông (Traffic Visualizer): biểu diễn vận tốc trung bình của từng đoạn đường (tình trạng giao thông) trên bản đồ. Các dữ liệu về tình trạng giao thông được máy chủ trung tâm gửi về điện thoại. Ngoài ra, vị trí hiện tại của người dùng cũng có thé được biểu diễn ngay trên bản đồ.

Cảnh báo giao thông (Traffic Notifier): cảnh báo cho người dùng về tình trạng giao thông hiện tại. Ví dụ như nếu người dùng đang đi vào khu vực kẹt xe, hệ thống sẽ cảnh báo cho người dùng biết. Việc xác định hướng đi của người dùng và cảnh báo tình trạng giao thông được xử lý trên máy chủ trung tâm để giảm công việc tinh toán trên điện thoại. Máy chủ trung tâm Máy chủ trung tâm là trai tim của cả hệ thông, nó đảm nhận các công việc tính toán nặng nhọc nhất và lưu trữ dữ liệu.

Máy chủ trung tâm bao gồm ba chức năng chính: phân tích dữ liệu giao thong (Traffic Data Extractor), theo dõi tình trạng giao thong (Traffic Monitor) và ứng dụng web (Web Application). Phân tích dữ liệu giao thông: máy chủ nhận các dữ liệu GPS thô từ nhiễu nguồn (điện thoại). Các dữ liệu GPS này độ chính xác không cao do dùng trên điện thoại nên chức nang GPS không chuyên dụng. Ngoài ra, dữ liệu GPS nay cũng có thé không dùng được do người dùng không tham gia giao thông như đang đi bộ hoặc ngồi ở quán ăn, cà phê,.

Do đó các dữ liệu GPS này cần được xử lý để lọc bỏ nhiễu. tăng độ chính xác và cần được ánh xạ vào các đoạn đường trên bản đồ. Theo dõi tình trạng giao thông có chức năng phân tích dữ liệu giao thông để biết được tình trạng giao thông (tốc độ nhanh, bình thường, chậm) từng khu vực và cảnh báo cho người dùng thông qua điện thoại của họ về tình trạng giao thông hiện tại. Ứng dụng web cung cấp cho người dùng cách thức khác để sử dụng hệ thống.

Website cung cấp một số chức năng như bản đồ về tình trạng giao thông hiện tại và công cụ cho phép người dùng xây dựng lộ trình của mình để tránh được các điểm kẹt xe. Người dùng có thé sử dụng công cụ trên với bat kỳ trình duyệt nao. Với giới hạn của dé tai nghiên cứu, chỉ tập trung vao giải quyết van dé xây dựng lộ trình, định hướng giao thông dé tránh ket xe theo thời gian thực. Day là chức năng rất quan trọng của hệ thống được chạy trên máy chủ trung tâm để xử lý các yêu cầu về xây dựng lộ trình, tìm đường, định hướng để tránh kẹt xe cho người dùng.

Chương 3: CƠ SỞ LÝ THUYET Đề xây dựng lộ trình, định hướng giao thông để tránh kẹt xe thì trước hết cần phải tìm hiểu về các lý thuyết liên quan đến van dé cần giải quyết như: lý thuyết đồ thị [11], các giải thuật tìm đường. Lý thuyết đồ thị Đồ thị là một cau trúc rời rac bao gdm các đỉnh và các cạnh nối các đỉnh này. Chúng ta phần biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Dé có thé hình dung được tại sao lại cần đến các loại đỗ thị khác nhau, chúng ta sẽ nêu ví dụ sử dụng chúng để mô tả một mạng máy tính.

Giả sử ta có một mạng gồm các máy tính và các kênh điện thoại (gọi tắt là kênh thoại) nối các máy tính này. Chúng ta có thể biểu diễn các vị trí đặt náy tính bởi các điểm và các kênh thoại nối chúng bởi các đoạn nối, xem hình 3. Hàtây Đẳng nai An sang Thanh hóa x eee Hà nội at” Hé Chi Minh Tạm Nam Binh Huế Khánh hòa Hình 3. Nhận thấy răng trong mạng ở hình 3.1, giữa hai máy bất kỳ chỉ có nhiều nhất là một kênh thoại nối chúng, kênh thoại này cho phép liên lạc cả hai chiều và không có máy tính nào lại được nối với chính nó.

Sơ đồ mạng máy cho trong hình 3.1 được gọi là đơn đồ thị vô hướng. Ta đi đến định nghĩa sau: Định nghĩa 1: Don đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phan tử khác nhau của V gọi là các cạnh. Trong trường hợp giữa hai máy tính nào đó thường xuyên phải truyền tải nhiều thông tin người ta phải nỗi hai máy nay bởi nhiều kênh thoại. Mang với đa kênh thoại giữa các máy được cho trong hình 3.

10 Ha tay , Đông nat An giang Hình 3.2: So đồ mang máy tính với da kênh thoại. Định nghĩa 2: Đa đồ thi vô hướng G= (V, E) bao gồm V là tập các đỉnh, và E 1a tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.