ĐẠ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.
