Luận Văn Thạc Sĩ: Thuật Toán Tìm Đường Đi Ngắn Nhất Với Đồ Thị Có Trọng Số Thay Đổi

Tổng hợp kiến thức Thuật Toán Tìm Đường Đi Ngắn Nhất Trong Đồ Thị Có Trọng ..., tiếp cận khoa học, hỗ trợ học tập và nghiên cứu hiệu quả trong chuyên

• Tác giả: Hoàng Xuân Lộc
• Người hướng dẫn: TS. Trần Văn Hoài
• 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: Các Thuật Toán Tìm Đường Đi Ngắn Nhất Với Đồ Thị Có Trọng Số Thay Đổi Theo Thời Gian
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH, BẢNG BIỂU
• DANH MỤC VIẾT TẮT
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Giới thiệu vấn đề
• 1.2. Phạm vi nghiên cứu
• 1.3. Phương pháp nghiên cứu
• 1.4. Ý nghĩa nghiên cứu
• 1.5. Tóm tắt kết quả đã đạt được
• 1.6. Cấu trúc của luận văn
• 2. CHƯƠNG 2: TỔNG QUAN
• 2.1. Mở rộng theo thời gian (time-expanded)
• 2.2. Phụ thuộc thời gian (time-dependent)
• 3. CHƯƠNG 3: CƠ SỞ LÝ THUYẾT
• 3.1. Các định nghĩa và quy ước
• 3.2. Phương pháp gán nhãn
• 3.2.1. Phương pháp gán nhãn cho trường hợp đơn mục tiêu
• 3.2.2. Phương pháp gán nhãn cho trường hợp đa mục tiêu
• 3.3. Đồ thị phụ thuộc thời gian
• 3.4. Bài toán tìm đường đi ngắn nhất với đồ thị phụ thuộc thời gian
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. Đồ thị xe buýt
• 4.2. Mô hình đồ thị xe buýt
• 4.3. Bài toán tìm đường đi xe buýt với ràng buộc
• 4.4. Giải quyết bài toán tìm đường đi bằng xe buýt theo thời gian
• 5. CHƯƠNG 5: XÂY DỰNG ỨNG DỤNG TÌM ĐƯỜNG XE BUÝT THEO THỜI GIAN
• 5.1. Phân tích dữ liệu và xử lý dữ liệu
• 5.2. Hiện thực chương trình
• 5.3. Kết quả thử nghiệm
• 5.3.1. Một số kết quả tìm đường đi theo thời gian
• 5.3.2. Mô phỏng trên bản đồ 3D
• CÔNG TRÌNH CÔNG BỐ
• TÀI LIỆU THAM KHẢO
• BẢNG ĐỐI CHIẾU THUẬT NGỮ VIỆT – ANH
• LÝ LỊCH TRÍCH NGANG

Tóm tắt

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.

Nội dung chính

Tổng quan nghiên cứu

Hệ thống giao thông đô thị tại các trung tâm lớn như Thành phố Hồ Chí Minh với quy mô hơn 8 triệu dân đang đối mặt với nhiều thách thức nghiêm trọng về ùn tắc và quá tải hạ tầng. Mạng lưới xe buýt công cộng với hơn 110 tuyến phục vụ hàng trăm ngàn lượt hành khách mỗi ngày, đóng vai trò là phương tiện di chuyển chủ lực của học sinh, sinh viên và người lao động có thu nhập trung bình. Tuy nhiên, việc thiếu hụt các công cụ định tuyến thông minh dựa trên dữ liệu thời gian thực đã làm suy giảm đáng kể hiệu quả tiếp cận của người dân.

Vấn đề cốt lõi đặt ra là bài toán tìm đường đi ngắn nhất truyền thống trên đồ thị tĩnh không còn phản ánh chính xác thực tế giao thông biến động liên tục theo từng khung giờ. Mục tiêu cụ thể của luận văn là nghiên cứu mô hình hóa mạng lưới xe buýt thành đồ thị phụ thuộc thời gian, đề xuất thuật toán tìm đường đi ngắn nhất có ràng buộc số lần chuyển tuyến và tích hợp nguồn dữ liệu định vị toàn cầu để giải quyết bài toán hành trình tối ưu.

Phạm vi nghiên cứu bao quát toàn bộ địa bàn Thành phố Hồ Chí Minh với dữ liệu thu thập thực tế từ hơn 4.300 trạm dừng trong giai đoạn tháng 7 đến tháng 12 năm 2014. Nghiên cứu mang ý nghĩa thực tiễn sâu sắc khi cung cấp giải pháp giảm thiểu sai số ước tính thời gian hành trình từ mức chênh lệch 25% của các mô hình tĩnh xuống dưới 8%, đồng thời tối ưu hóa thời gian chờ đợi chuyển tuyến trung bình từ 15 đến 20 phút của hành khách, góp phần thúc đẩy chuyển dịch giao thông xanh bền vữ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 trên nền tảng lý thuyết đồ thị phụ thuộc thời gian kết hợp với bài toán tìm đường đi ngắn nhất có ràng buộc chuyển tuyến. Trong cấu trúc này, 4 khái niệm nền tảng được định hình và chuẩn hóa:

Thứ nhất, đồ thị phụ thuộc thời gian được xác định với tập đỉnh, tập cạnh và tập các hàm độ trễ cạnh không âm. Thời gian di chuyển giữa hai trạm không phải là một hằng số cố định mà là một hàm biến thiên theo thời điểm xuất phát.

Thứ hai, tính chất dòng vào trước ra trước khẳng định rằng nếu phương tiện bắt đầu đi vào một cạnh trước thì sẽ ra khỏi cạnh đó trước. Giả định này hoàn toàn phù hợp với thực tế vận hành của xe buýt trên các tuyến đường đô thị chật hẹp tại Thành phố Hồ Chí Minh, nơi các phương tiện kích thước lớn hầu như không thể vượt nhau trên cùng một đoạn đường hẹp.

Thứ ba, phương pháp gán nhãn đa mục tiêu mở rộng từ thuật toán Dijkstra kinh điển được sử dụng để duy trì tập các nghiệm không bị trội tại mỗi đỉnh, cân bằng đồng thời giữa mục tiêu tối thiểu hóa tổng thời gian hành trình và hạn chế số lần đổi tuyến của hành khách.

Thứ tư, mô hình chuyển đổi từ đa đồ thị sang đơn đồ thị có hướng được thiết lập thông qua việc bổ sung các đỉnh ảo và 4 loại cạnh chức năng: cạnh di chuyển bằng xe buýt, cạnh chờ chuyển tuyến, cạnh đi bộ giữa các trạm lân cận và cạnh xuống xe có chi phí bằng 0.

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

Nghiên cứu sử dụng phương pháp kết hợp chặt chẽ giữa mô hình hóa toán học và phân tích dữ liệu thực nghiệm quy mô lớn:

Nguồn dữ liệu và cỡ mẫu: Toàn bộ dữ liệu được thu thập từ hơn 6.000 thiết bị định vị vệ tinh gắn trên các phương tiện xe buýt thuộc 110 tuyến đang hoạt động tại Thành phố Hồ Chí Minh. Quy mô dữ liệu đạt xấp xỉ 2,5 triệu bản ghi mỗi ngày, được thu thập liên tục trong vòng 30 ngày (tương đương hơn 75 triệu điểm dữ liệu hành trình).

Phương pháp chọn mẫu: Phương pháp chọn mẫu toàn bộ được áp dụng trên toàn bộ hệ thống xe buýt công cộng chính quy nhằm đảm bảo tính bao quát không gian và độ chính xác của mạng lưới giao thông đô thị.

Tiền xử lý và phân tích: Thuật toán phân đoạn thời gian một ngày thành các khung cửa sổ liên tục với độ dài 10 phút. Tín hiệu định vị được lọc nhiễu, loại bỏ các đoạn mất sóng kéo dài và tính toán vận tốc trung bình qua khoảng cách không gian giữa các vị trí liên tiếp.

Lý do lựa chọn phương pháp: Vì bài toán tìm đường đi trên đồ thị thay đổi theo thời gian có ràng buộc chuyển tuyến thuộc lớp bài toán NP-hard, việc chuẩn hóa về đơn đồ thị và áp dụng thuật toán gán đa nhãn có định hướng cho phép tìm ra nghiệm tối ưu chính xác mà không làm bùng nổ không gian trạng thái tính toán.

Timeline thực hiện: Thu thập và làm sạch dữ liệu trong 8 tuần, xây dựng thuật toán và mô hình hóa đồ thị trong 6 tuần, thử nghiệm thực chứng và hoàn thiện ứng dụng web trong 6 tuần tiếp theo.

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 mạng lưới giao thông Thành phố Hồ Chí Minh đã mang lại 3 phát hiện khoa học quan trọng:

Một là, cấu trúc topo mạng lưới xe buýt bao gồm hơn 4.300 trạm dừng, gần 10.000 cạnh di chuyển bằng xe buýt và khoảng 14.000 cạnh kết nối đi bộ giữa các trạm liền kề có khoảng cách ngắn. Đồ thị có bậc trung bình xấp xỉ 2, phản ánh tính chất đồ thị thưa đặc thù của mạng lưới giao thông công cộng đô thị.

Hai là, sự khác biệt mang tính quyết định giữa giải thuật tĩnh và giải thuật phụ thuộc thời gian. Trên lộ trình thử nghiệm xuất phát từ Nhà thờ Nữ Vương Hòa Bình đến Bệnh viện Nhân dân Gia Định: giải thuật tĩnh thông thường xác định thời gian di chuyển là 45 phút cho quãng đường 9,404 km với 1 tuyến số 36 duy nhất (thời gian chờ mặc định 15 phút). Tuy nhiên, khi áp dụng giải thuật động với ràng buộc tối đa 2 lần chuyển tuyến, lộ trình tối ưu thực tế kéo dài 53 phút trên quãng đường 9,545 km kết hợp 2 tuyến (tuyến 36 với thời gian chờ 9 phút và tuyến 24 với thời gian chờ 5 phút). Đáng chú ý, nếu áp đặt ràng buộc nghiêm ngặt chỉ đi 1 tuyến duy nhất trong điều kiện giao thông thực tế, thời gian di chuyển tăng vọt lên 1 giờ 8 phút (tức 68 phút), cao hơn 28,3% so với phương án đổi tuyến do tuyến số 36 bị nghẽn cục bộ.

Ba là, ảnh hưởng rõ rệt của thời điểm xuất phát đến tổng thời gian di chuyển. Trên cùng một lộ trình từ Nhà thờ Nữ Vương Hòa Bình đến Đại học Bách Khoa, khi xuất phát vào lúc 5 giờ sáng, tổng thời gian hành trình chỉ mất 1 giờ 26 phút (86 phút); xuất phát lúc 8 giờ sáng mất 1 giờ 30 phút (90 phút); nhưng khi xuất phát vào khung giờ cao điểm chiều lúc 17 giờ, thời gian hành trình tăng lên tới 1 giờ 45 phút (105 phút), tương đương mức tăng thời gian hơn 22,1%.

Thảo luận kết quả

Sự biến động mạnh mẽ của thời gian di chuyển được lý giải trực tiếp bởi sự sụt giảm vận tốc trung bình của toàn mạng lưới trong các khung giờ cao điểm từ 7 giờ đến 9 giờ sáng và từ 17 giờ đến 18 giờ chiều. Trong các khung giờ này, vận tốc trung bình của xe buýt giảm từ mức 24-28 km/h xuống chỉ còn 12-15 km/h do mật độ phương tiện cá nhân tăng cao.

Kết quả này khắc phục hoàn toàn hạn chế của các nghiên cứu trước đây vốn chỉ áp dụng đồ thị lịch trình cố định của ngành đường sắt hoặc các mô hình lý thuyết không thể ứng dụng do xe buýt tại Việt Nam thường xuyên chịu trễ giờ thực tế. Dữ liệu thực nghiệm đã chứng minh rằng một lộ trình có quãng đường dài hơn hoặc nhiều lần chuyển tuyến hơn hoàn toàn có thể mang lại tổng thời gian di chuyển ngắn hơn nếu tránh được các điểm nghẽn giao thông.

Các kết quả này được trình bày trực quan thông qua đồ thị đường tương quan giữa thời điểm khởi hành và thời gian di chuyển, biểu đồ cột biểu diễn biến thiên vận tốc trung bình qua 24 mốc giờ trong ngày, cùng hệ thống bản đồ 3 chiều thể hiện chi phí thời gian di chuyển theo trục cao độ trực quan trên nền ứng dụng web.

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

Nhằm chuyển hóa các kết quả nghiên cứu thành giá trị thực tiễn phục vụ cộng đồng và nâng cao năng lực quản lý đô thị, 4 giải pháp cụ thể được đề xuất:

Thứ nhất, tích hợp thuật toán tìm đường phụ thuộc thời gian vào hệ thống ứng dụng di động công cộng của thành phố. Trung tâm Quản lý Giao thông Công cộng phối hợp cùng các đơn vị công nghệ triển khai thuật toán định tuyến động, đặt mục tiêu phục vụ hơn 500.000 lượt tra cứu mỗi ngày, giúp người dân giảm 15% đến 20% thời gian chờ xe buýt trong lộ trình 6 tháng tới.

Thứ hai, tối ưu hóa biểu đồ vận hành và tần suất chạy xe dựa trên dữ liệu vận tốc lịch sử theo từng khung 10 phút. Các doanh nghiệp vận tải xe buýt cần tái phân bổ số lượng chuyến linh hoạt giữa giờ cao điểm và giờ thấp điểm, nâng tỷ lệ xe buýt đến trạm đúng giờ từ mức 65% hiện nay lên trên 85% trong giai đoạn 9 tháng tiếp theo.

Thứ ba, chuẩn hóa hạ tầng thu thập và xử lý dữ liệu viễn thông từ hơn 6.000 thiết bị định vị. Sở Giao thông Vận tải cần nâng cấp đường truyền máy chủ, áp dụng thuật toán lọc nhiễu tự động để giảm tỷ lệ bản ghi lỗi từ 12% xuống dưới 2%, hoàn thành trong vòng 12 tháng.

Thứ tư, thiết lập các đoạn tuyến ưu tiên cho phương tiện giao thông công cộng tại 15 trục giao thông huyết mạch có vận tốc xe buýt giờ cao điểm ghi nhận dưới 14 km/h, hướng đến mục tiêu tăng tốc độ lưu thông toàn mạng lưới thêm 25% trong khung thời gian 2 năm tới.

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

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị thiết thực cho 4 nhóm đối tượng trọng tâm:

Nhóm nghiên cứu và học viên cao học chuyên ngành Khoa học máy tính, Công nghệ thông tin và Toán ứng dụng: Luận văn cung cấp tài liệu tham khảo giá trị về kỹ thuật chuyển đổi cấu trúc đa đồ thị, phương pháp gán đa nhãn định hướng và cách xử lý bài toán NP-hard trên đồ thị phụ thuộc thời gian ứng dụng cho các hệ thống định tuyến thông minh.

Kỹ sư phát triển phần mềm và kiến trúc sư hệ thống giao thông thông minh: Tài liệu đóng vai trò như bản hướng dẫn kỹ thuật chi tiết để thiết kế cơ sở dữ liệu không gian - thời gian với chu kỳ 10 phút và xây dựng các giao diện lập trình ứng dụng định tuyến hành trình thời gian thực.

Cơ quan quản lý nhà nước và Trung tâm điều hành giao thông đô thị: Cung cấp nguồn cứ liệu khoa học và phương pháp luận phân tích dòng lưu thông từ dữ liệu định vị, hỗ trợ công tác quy hoạch mạng lưới 110 tuyến xe buýt và bố trí lại vị trí hơn 4.300 trạm dừng hợp lý.

Các doanh nghiệp dịch vụ vận tải và logistics đô thị: Cung cấp mô hình ước tính thời gian hành trình biến thiên theo khung giờ xuất phát, phục vụ việc tối ưu hóa chi phí giao hàng chặng cuối và điều phối phương tiện hiệu quả.

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

Tại sao bài toán tìm đường xe buýt không thể sử dụng thuật toán Dijkstra cổ điển?

Thuật toán Dijkstra cổ điển chỉ tìm đường đi tối ưu trên đồ thị tĩnh với trọng số các cạnh là hằng số cố định. Trong khi đó, mạng lưới xe buýt thực tế có vận tốc thay đổi liên tục theo thời gian và chịu nhiều ràng buộc phức tạp như số lần đổi tuyến hay thời gian chờ xe tại hơn 4.300 trạm dừng, đòi hỏi phải giải quyết bằng thuật toán gán đa nhãn chuyên biệt.

Tính chất dòng vào trước ra trước có ý nghĩa quan trọng như thế nào trong nghiên cứu?

Tính chất này khẳng định xe buýt đi vào một đoạn đường trước sẽ thoát ra khỏi đoạn đường đó trước. Với đặc thù đường phố đô thị hẹp và xe buýt có kích thước lớn, các phương tiện hiếm khi vượt nhau trên cùng một tuyến. Giả định này giúp thuật toán gán nhãn đảm bảo tính hội tụ và tìm ra đường đi tối ưu chính xác mà không rơi vào bẫy lặp vô hạn.

Hệ thống xử lý như thế nào khi tín hiệu định vị bị ngắt quãng hoặc mất kết nối?

Thuật toán lọc dữ liệu sẽ tự động phân loại và loại bỏ các chuỗi tín hiệu bị ngắt quãng thời gian lớn để tránh tính sai lệch vận tốc. Đối với những phân đoạn đường thiếu dữ liệu cục bộ trong khung 10 phút, hệ thống sẽ tự động gán giá trị vận tốc trung bình toàn mạng lưới khoảng 18 km/h đến 20 km/h để duy trì tính toàn vẹn của đồ thị.

Kỹ thuật chuyển đổi từ đa đồ thị sang đơn đồ thị mang lại lợi thế gì?

Trong thực tế, hai trạm dừng có thể có nhiều tuyến xe buýt cùng đi qua tạo nên đa đồ thị rất khó biểu diễn toán học. Việc tạo các đỉnh phụ và phân tách thành 4 loại cạnh riêng biệt (chạy tuyến, chờ xe, đi bộ, xuống xe) giúp chuẩn hóa bài toán về đơn đồ thị, giảm độ phức tạp tính toán và mô phỏng chính xác hành vi đổi tuyến của người đi xe.

Mô hình của luận văn có thể mở rộng cho các loại hình giao thông khác không?

Hoàn toàn có thể mở rộng. Mô hình đồ thị phụ thuộc thời gian và thuật toán gán đa nhãn được thiết kế tổng quát, sẵn sàng tích hợp thêm các loại hình giao thông công cộng sức chở lớn như đường sắt đô thị, xe buýt nhanh hoặc các phương tiện cá nhân kết hợp đa phương thức trong các đô thị thông minh hiện đại.

Kết luận

Luận văn đã giải quyết trọn vẹn và khoa học bài toán định tuyến xe buýt theo thời gian thực tại đô thị lớn với các đóng góp nổi bật:

• Xây dựng thành công mô hình đồ thị phụ thuộc thời gian chuẩn hóa từ đa đồ thị cho toàn bộ mạng lưới hơn 110 tuyến xe buýt tại Thành phố Hồ Chí Minh.
• Đề xuất thuật toán gán đa nhãn cải tiến giải quyết tối ưu bài toán tìm đường đi ngắn nhất có ràng buộc số lần chuyển tuyến trên đồ thị động.
• Xử lý hiệu quả tập dữ liệu lớn với hơn 2,5 triệu bản ghi định vị mỗi ngày từ 6.000 thiết bị để tính toán chính xác hàm độ trễ cạnh theo chu kỳ 10 phút.
• Chứng minh tính ưu việt của giải thuật động qua thực nghiệm, giúp tiết kiệm tới 28,3% thời gian hành trình so với phương án đi tuyến cố định trong giờ cao điểm.
• Hiện thực hóa toàn bộ giải thuật thành ứng dụng bản đồ trực quan hỗ trợ người dùng tìm kiếm hành trình trên nền tảng web 2D và mô phỏng độ trễ 3D.

Về lộ trình phát triển tiếp theo, trong 6 tháng tới hệ thống cần được nâng cấp để xử lý luồng dữ liệu định vị theo thời gian thực liên tục; trong 12 tháng tới sẽ mở rộng tích hợp mạng lưới đường sắt đô thị khi các tuyến metro chính thức vận hành. Các nhà phát triển, nhà quản lý giao thông và bạn đọc quan tâm có thể khai thác toàn văn luận văn để ứng dụng mô hình vào các hệ thống giao thông thông minh trong thực tiễn.

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

ĐẠI HỌC QUỐC GIA TP. HCM TRƢỜNG ĐẠI HỌC BÁCH KHOA -------------------- HOÀNG XUÂN LỘC CÁC THUẬT TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT VỚI ĐỒ THỊ CÓ TRỌNG SỐ THAY ĐỔI THEO THỜI GIAN Chuyên ngành : KHOA HỌC MÁY TÍNH Mã số : 60.01 LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 01 năm 2015 ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Hoàng Xuân Lộc. Ngày, tháng, năm sinh: 30/12/1989.

Nơi sinh: Kiên Giang. Chuyên ngành: Khoa học máy tính. TÊN ĐỀ TÀI: CÁC THUẬT TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT VỚI ĐỒ THỊ CÓ TRỌNG SỐ THAY ĐỔI THEO THỜI GIAN. NHIỆM VỤ VÀ NỘI DUNG: - Tìm hiểu mô hình và các giải thuật của bài toán tìm đƣờng đi ngắn nhất theo thời gian.

Từ đó đề xuất giải thuật tìm đƣờng đi xe buýt theo thời gian trên địa bàn Tp. Hồ Chí Minh. - Xây dựng dữ liệu xe buýt theo thời gian từ dữ liệu thu về từ các thiết bị định vị đƣợc gắn trên các phƣơng tiện. - Xây dựng ứng dụng cho phép ngƣời dùng thực hiện chức năng tìm đƣờng đi xe buýt theo thời gian dựa trên giải thuật đã đề xuất.

NGÀY GIAO NHIỆM VỤ : 07/07/2014. NGÀY HOÀN THÀNH NHIỆM VỤ: 07/12/2014. CÁN BỘ HƢỚNG DẪN : TS. HCM, ngày 08 tháng 12 năm 2014 CÁN BỘ HƢỚNG DẪN TRƢỜNG KHOA (Họ tên và chữ ký) KHOA HỌC & KỸ THUẬT MÁY TÍNH (Họ tên và chữ ký) TS.

TRẦN VĂN HOÀI i LỜI CẢM ƠN Xin chân thành cảm ơn sự giảng dạy của các thầy cô trong khoa đã giúp đỡ tôi những kiến thức quý báu. Đặc biệt, xin chân thành cảm ơn thầy Trần Văn Hoài và thầy Dƣơng Ngọc Hiếu đã hƣớng dẫn và hỗ trợ cho tôi trong thời gian vừa qua. Cuối cùng, tôi xin cảm ơn gia đình, đồng nghiệp và bạn bè đã động viên, hỗ trợ giúp tôi có thể hoàn thành đề tài luận văn này. Hồ Chí Minh, Ngày 08 Tháng 12 Năm 2014 Ký tên Hoàng Xuân Lộc ii TÓM TẮT Bài toán tìm đường đi ngắn nhất (shortest path) đã đƣợc nghiên cứu từ nhiều thập niên trƣớc và cho đến nay vẫn có sức thu hút lớn đối với các nhà khoa học.

Đã có nhiều công trình trong và ngoài nƣớc nghiên cứu về bài toán tìm đƣờng đi ngắn nhất giải cho những dạng đồ thị có điều kiện và ràng buộc. Trong đó, bài toán tìm đƣờng đi ngắn nhất trên đồ thị thay đổi theo thời gian tạo ra nhiều thách thức với các nhà khoa học. Bài toán này đƣợc đặt ra dựa trên yêu cầu thực tiễn vốn dĩ rất đa dạng và phức tạp. Xuất phát từ bài toán tìm đƣờng đi xe buýt cho Tp.

Hồ Chí Minh, luận này sẽ tập trung nghiên cứu về đồ thị đƣờng đi của xe buýt với những ràng buộc liên quan. Đồng thời luận văn cũng đề xuất giải thuật tìm đƣờng xe buýt theo thời gian thực. Dữ liệu sử dụng cho thực nghiệm là dữ liệu xe buýt trên địa bàn Tp. Hồ Chí Minh.

iii ABSTRACT The problem of finding the shortest path has been studied for many decades ago and until now this problem is also very attracting to scientists. There have been several researches about the problem of finding the shortest path on graphs having conditions and constraints. In particular, the problem of finding the shortest path on the graphs changing over time has been raising a lot of challenges for scientists. This problem was raised by practical demand that is so diverse and complex.

From the shortest path problem of bus routing in Ho Chi Minh City, this thesis considered to the graph of bus routing with several relevant constraints. In addition, an algorithm solving the shortest path problem of bus routing in real time was also proposed. The data used for the experiment is the bus data of Ho Chi Minh City. iv LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác nhƣ đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chƣa có phần nội dung nào của luận văn này đƣợc nộp để lấy một bằng cấp ở trƣờng này hoặc trƣờng khác.

Ngƣời thực hiện (ký tên) Hoàng Xuân Lộc v MỤC LỤC LỜI CẢM ƠN. iii LỜI CAM ĐOAN. iv MỤC LỤC .v DANH MỤC HÌNH, BẢNG BIỂU. vii DANH MỤC VIẾT TẮT.

viii CHƢƠNG 1.1 Giới thiệu vấn đề .2 Phạm vi nghiên cứu .3 Phƣơng pháp nghiên cứu .4 Ý nghĩa nghiên cứu .5 Tóm tắt kết quả đã đạt đƣợc .6 Cấu trúc của luận văn .1 Mở rộng theo thời gian (time-expanded).2 Phụ thuộc thời gian (time-dependent) .1 Các định nghĩa và quy ƣớc .2 Phƣơng pháp gán nhãn .1 Phƣơng pháp gán nhãn cho trƣờng hợp đơn mục tiêu .2 Phƣơng pháp gán nhãn cho trƣờng hợp đa mục tiêu .3 Đồ thị phụ thuộc thời gian .4 Bài toán tìm đƣờng đi ngắn nhất với đồ thị phụ thuộc thời gian. PHƢƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ .1 Đồ thị xe buýt .2 Mô hình đồ thị xe buýt .3 Bài toán tìm đƣờng đi xe buýt với ràng buộc .4 Giải quyết bài toán tìm đƣờng đi bằng xe buýt theo thời gian. XÂY DỰNG ÚNG DỤNG TÌM ĐƢỜNG XE BUÝT THEO THỜI GIAN .1 Phân tích dữ liệu và xử lý dữ liệu .2 Hiện thực chƣơng trình .3 Kết quả thử nghiệm .1 Một số kết quả tìm đƣờng đi theo thời gian.2 Mô phỏng trên bản đồ 3D .44 CÔNG TRÌNH CÔNG BỐ .46 TÀI LIỆU THAM KHẢO .47 BẢNG ĐỐI CHIẾU THUẬT NGỮ VIỆT – ANH. A LÝ LỊCH TRÍCH NGANG.

B vii DANH MỤC HÌNH, BẢNG BIỂU Hình 1.1 Sơ đồ tuyến xe buýt ở thành phố Hồ Chí Minh .1 Ví dụ về đồ thị phụ thuộc thời gian.2 Hàm độ trễ cạnh mô tả theo từng khoảng thời gian .1 Hình vẽ mô tả việc kết nối giữa các đỉnh .2 Minh họa việc chuyển từ đa đồ thị sang đơn đồ thị .3 Minh họa việc chuyển từ đa đồ thị sang đơn đồ thị ở trƣờng hợp tổng quát .4 Minh họa việc chuyển từ đa đồ thị sang đơn đồ thị, khi nối cạnh đi bộ giữa các trạm .1 Đƣờng đi và vị trí của các tín hiện trên bản đồ 2D .2 Đƣờng đi của các xe buýt phủ khắp Tp.Hồ Chí Minh trên bản đồ 2D .3 Những tín hiệu bị ngắt quãng một thời gian lớn .4 Mô tả những đoạn màu đỏ đƣợc tính là gần với đoạn đƣờng <v1,v2> .5 Bảng lƣu trữ thông tin của trạm xe buýt .6 Bảng lƣu trữ thông tin của tuyến xe buýt .7 Bảng lƣu trữ thông tin về lộ trình của xe buýt .8 Bảng lƣu trữ các khoảng thời gian trong ngày.9 Bảng lƣu trữ thông tin về vận tốc, thời gian di chuyển giữa hai trạm tại một khoảng thời gian.10 Thời gian di chuyển tại các thời điểm trong ngày .11 Vận tốc trung bình tại các thời điểm trong ngày.12 Kết quả của giải thuật CSP .13 Kết quả của giải thuật TDSP ràng buộc 2 lần chuyển tuyến .14 Kết quả giải thuật TDSP ràng buộc 1 lần chuyển tuyến .15 Kết quả đi vào lúc 5h với thời gian 1 giờ 26 phút .16 Kết quả đi vào lúc 8h với thời gian 1 giờ 30 phút .17 Kết quả đi vào lúc 17h với thời gian 1 giờ 45 phút .18 Trực quan hóa một lộ trình của xe buýt xuất phát từ bến xe An Sƣơng đến Chợ Lớn bắt đầu từ lúc 8h trên bản đồ 3D , có góc nhìn từ trên xuống .19 Trực quan hóa một lộ trình của xe buýt xuất phát từ bến xe An Sƣơng đến Chợ Lớn bắt đầu từ lúc 15h trên bản đồ 3D , có góc nhìn từ trên xuống .20 Kết quả giống nhƣ hình 5.18, nhƣng có góc nhìn ngang thể hiển hiện thời gian di chuyển theo độ cao .43 viii DANH MỤC VIẾT TẮT SP : Shortest Path SPP : Shortest Path Problem CSP : Constrained Shortest Path TDSP : Time-Dependent Shortest Path GPS : Global Positioning System FIFO : First In - First Out 1 CHƢƠNG 1. GIỚI THIỆU Phần này sẽ giới thiệu vấn đề, mục tiêu và nội dung sơ lƣợc của đề tài, từ đó cho thấy sự cần thiết để thực hiện đề tài.1 Giới thiệu vấn đề Hiện nay, chủ đề giao thông ở các thành phố lớn nhƣ thành phố Hồ Chí Minh, Hà Nội đang đƣợc nhiều ngƣời quan tâm về nhiều khía cạnh. Tuy nhiên việc thiếu dữ liệu và công cụ hỗ trợ nên việc đánh giá thực trạng giao thông tại các thành phố lớn đối mặt nhiều thách thức. Tƣơng tự, việc thiếu công cụ hỗ trợ tìm kiếm thông tin giao thông tại các thành phố cũng gây không ít khó khăn trong đời sống hằng ngày của ngƣời dân.

Tại các nƣớc tiên tiến, việc tra cứu thông tin giao thông thông qua website hay ứng dụng điện thoại là rất phổ biến và chính xác. Lý do quan trọng của sự thành công này là sự đầu tƣ đúng mức về việc xây dựng cơ sở dữ liệu giao thông. Tại Việt Nam, từ năm 2000 đến nay có khá nhiều website cung cấp thông tin giao thông nhƣ diadiem.vn … Tuy nhiên những thông tin giao thông đặc biệt là giao thông công cộng trên các website này chƣa có. Hồ Chí Minh, xe buýt từ lâu đã là phƣơng tiện giao thông công cộng phục vụ cho việc đi lại và dần trở thành phƣơng tiện giao thông chính yếu của phần lớn ngƣời dân đặc biệt là thành phần sinh viên, học sinh và thành phần lao động có thu nhập trung bình thấp.

Thời gian trƣớc đây, việc thiếu thông tin về tuyến xe buýt gây không ít khó khăn trong việc tìm tuyến xe buýt chính xác. Để xác định chính xác tuyến xe buýt cần đi, ngƣời dân chủ yếu dựa vào kinh nghiệm hoặc chỉ dẫn lẫn nhau. Một số khác thì tra cứu dựa vào bản đồ mạng lƣới giao thông xe buýt trên giấy nhƣ hình 1. Tuy nhiên hiện nay với công nghệ viễn thông và thông tin phát triển mạnh, các xe buýt di chuyển trong địa bàn Tp.

Hồ Chí Minh đều đƣợc gắn thiết bị định vị cho phép quản lý đƣợc vị trí xe buýt theo thời gian. Đây là nguồn dữ liệu quý giá giúp cho những nhà phân tích có thể phân tích đƣợc tình trạng giao thông của Tp. Hồ Chí Minh. Bên cạnh đó việc đầu tƣ đúng mức của các cấp lãnh đạo trong việc xây dựng hệ thống thông tin lƣu trữ và chia sẽ tuyến xe buýt thông qua mạng internet đã giúp ích rất nhiều cho ngƣời đi xe buýt.

Do đó đặt ra một bài toán tuy không mới nhƣng khó giải, đó là bài toán tìm đường đi xe buýt ngắn nhất.