Tài liệu ứng dụng bài toán luồng cực đại phục vụ mô hình tắc nghẽn giao thông tại thành phố hồ chí minh.

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC NÔNG LÂM THÀNH PHỐ HỒ CHÍ MINH ********** KHÓA LUẬN TỐT NGHIỆP ỨNG DỤNG BÀI TOÁN LUỒNG CỰC ĐẠI PHỤC VỤ MÔ HÌNH TẮC NGHẼN GIAO THÔNG TẠI THÀNH PHỐ HỒ CHÍ MINH Họ và tên sinh viên: DƯƠNG KHẢ LỢI Ngành: Hệ thống Thông tin Địa lý Niên khóa: 2013 – 2017 Tháng 06/2017 ỨNG DỤNG BÀI TOÁN LUỒNG CỰC ĐẠI PHỤC VỤ MÔ HÌNH TẮC NGHẼN GIAO THÔNG TẠI THÀNH PHỐ HỒ CHÍ MINH Tác giả DƯƠNG KHẢ LỢI Khóa luận được đệ trình để đáp ứng yêu cầu cấp bằng Kĩ sư ngành Hệ thống Thông tin Địa lý Giáo viên hướng dẫn: ThS. KHƯU MINH CẢNH Tháng 06 năm 2017 LỜI CẢM ƠN Trước hết, tôi xin gửi lời cảm ơn chân thành và sâu sắc đến Th.S Khưu Minh Cảnh và anh Lê Võ Hữu Trí, hiện đang công tác tại Sở Khoa học và Công nghệ thành phố Hồ Chí Minh, đã tận tình hướng dẫn, giúp đỡ tôi trong suốt quá trình thực hiện nghiên cứu đề tài khóa luận tốt nghiệp này. Tôi xin trân trọng cảm ơn Ban lãnh đạo Sở Khoa học và Công nghệ thành phố Hồ Chí Minh đã tạo điều kiện để tôi có thể thực tập, học hỏi thêm nhiều kỹ năng, kiến thức tại cơ quan. Tôi cũng xin gửi lời cảm ơn sâu sắc đến PGS.TS Nguyễn Kim Lợi, KS. Nguyễn Duy Liêm, các quý thầy cô Trường Đại học Nông lâm thành phố Hồ Chí Minh đã giảng dạy giúp tôi trau dồi những kiến thức quý báu trong suốt thời gian theo học tại trường bốn năm vừa qua. Cảm ơn tập thể lớp DH13GI và những người bạn đã đồng hành cùng tôi trong suốt quãng thời gian sinh viên, giúp đỡ, sẵn sàng chia sẻ cùng tôi trong học tập cũng như trong cuộc sống những lúc tôi gặp khó khăn. Cuối cùng, để có ngày hôm nay con xin gửi lời biết ơn sâu sắc nhất đến cha mẹ, những người đã sinh thành nên con, nuôi dạy, chăm sóc con thành người. Cảm ơn cha mẹ đã luôn động viên, ủng hộ và tạo những điều kiện tốt nhất để cho con yên tâm học tập. Dương Khả Lợi Chuyên ngành Hệ thống thông tin địa lý Khoa Môi trường và Tài nguyên Trường Đại học Nông Lâm TP. Hồ Chí Minh Email: [email protected] i TÓM TẮT Đề tài nghiên cứu “Ứng dụng bài toán luồng cực đại phục vụ mô hình tắc nghẽn giao thông tại Thành phố Hồ Chí Minh” đã được thực hiện trong khoảng thời gian từ tháng 03/2017 đến tháng 06/2017. Phương pháp tiếp cận của đề tài là sử dụng kết hợp các công cụ như ArcGIS, Visual Studio Code, PostgreSQL/ PostGIS, Java/ Apache Tomcat, ngôn ngữ lập trình Python áp dụng bài toán luồng cực đại để nghiên cứu phân tích về tính chất phân luồng của mạng lưới giao thông. Trong đó, công cụ ArcGIS có chức năng quản lý dữ liệu thuộc tính và dữ liệu không gian của đối tượng nghiên cứu giúp xử lý, biên tập dữ liệu đường giao thông, điểm tắc nghẽn giao thông tạo các lớp thông tin cần thiết để phục vụ đề tài nghiên cứu. PostgreSQL/ PostGIS dùng để đưa dữ liệu thuộc tính lên liên kết server phục vụ cho việc truy xuất dữ liệu. Visual Studio Code, Java/ Apache Tomcat cùng ngôn ngữ lập trình Python được dùng để lập trình thuật toán, tính toán tự động, nhanh chóng tiết kiệm thời gian và là công cụ để xây dựng mô hình Website tiện lợi hữu ích. Kết quả đạt được của đề tài nghiên cứu là: ­ Nghiên cứu lý thuyết đồ thị trong việc xây dựng mô hình kết nối mạng lưới giao thông. ­ Xây dựng được cơ sở dữ liệu GIS về đường phố và các điểm tắc nghẽn giao thông tại Thành phố Hồ Chí Minh. ­ Tiếp cận được thuật toán luồng cực đại của đồ thị, phương pháp tính toán và xây dựng mô hình đồ thị. ­ Xây dựng được mô hình Website ứng dụng bài toán đồ thị luồng cực đại. Với các kết quả đề tài đạt được, đề tài có thể áp dụng thực tế để giám sát giao thông, tính toán các đoạn đường tắc nghẽn trong thời gian ngắn và mang lại hiệu quả cao là cơ sở trong việc phân chia lại luồng giao thông giảm bớt khả năng tắc nghẽn giao thông tại các nút giao thông quan trọng. ii MỤC LỤC LỜI CẢM ƠN .................................................................................................................i TÓM TẮT ..................................................................................................................... ii MỤC LỤC .................................................................................................................... iii DANH MỤC BẢNG BIỂU ...........................................................................................v DANH MỤC HÌNH ẢNH ............................................................................................vi CHƯƠNG 1. MỞ ĐẦU .................................................................................................1 1.1. Tính cấp thiết của đề tài .........................................................................................1 1.2. Mục tiêu nghiên cứu ...............................................................................................2 1.2.1. Mục tiêu chung ................................................................................................2 1.2.2. Mục tiêu cụ thể ................................................................................................2 1.3. Đối tượng và phạm vi nghiên cứu .........................................................................2 CHƯƠNG 2. TỔNG QUAN TÀI LIỆU ......................................................................3 2.1. Khái quát về khu vực nghiên cứu .........................................................................3 2.1.1. Vị trí địa lý .......................................................................................................3 2.1.2. Tình trạng giao thông tại Thành phố Hồ Chí Minh ....................................5 2.2. Lý thuyết đồ thị .....................................................................................................10 2.2.1. Lịch sử hình thành ........................................................................................10 2.2.2. Ứng dụng của lý thuyết đồ thị ......................................................................11 2.2.3. Định nghĩa đồ thị ...........................................................................................11 2.2.4. Phân loại đồ thị ..............................................................................................12 2.3. Khả năng kết nối mạng lưới ................................................................................13 2.4. Mô hình về bài toán luồng trên mạng.................................................................21 2.4.1. Định nghĩa về mạng ......................................................................................21 2.4.2. Định nghĩa về luồng và luồng trên mạng ....................................................22 2.4.3. Bài toán luồng cực đại...................................................................................22 2.5. Tổng quan về xây dựng Website .........................................................................24 2.5.1. Hệ quản trị cơ sở dữ liệu PostgreSQL/ PostGIS ........................................24 2.5.2. Ngôn ngữ lập trình Python và Flask ...........................................................24 iii 2.5.3. Apache Tomcat ..............................................................................................24 2.5.4. Mã nguồn mở GeoServer..............................................................................25 2.6. Một số nghiên cứu liên quan................................................................................25 CHƯƠNG 3. DỮ LIỆU VÀ PHƯƠNG PHÁP NGHIÊN CỨU ..............................26 3.1. Dữ liệu thu thập ....................................................................................................26 3.2. Phương pháp nghiên cứu .....................................................................................27 3.2.1. Giai đoạn 1: Xây dựng cơ sở dữ liệu ...........................................................28 3.2.2. Giai đoạn 2: Lập đồ thị và tính khả năng kết nối đồ thị ...........................29 3.2.3. Giai đoạn 3: Xây dựng Website. Cài đặt thuật toán tìm luồng cực đại ...33 CHƯƠNG 4. KẾT QUẢ - THẢO LUẬN ..................................................................37 4.1. Xây dựng cơ sở dữ liệu .........................................................................................37 4.2. Xây dựng mô hình luồng cực đại ........................................................................43 4.3. Xây dựng tính toán luồng giao thông theo mô hình đồ thị ...............................44 4.4. Xây dựng Website .................................................................................................45 CHƯƠNG 5. KẾT LUẬN – KIẾN NGHỊ .................................................................53 5.1. Kết luận .................................................................................................................53 5.2. Kiến nghị ...............................................................................................................53 TÀI LIỆU THAM KHẢO...........................................................................................55 PHỤ LỤC .....................................................................................................................57 iv DANH MỤC BẢNG BIỂU Bảng 2.1. Mô tả phân loại dữ liệu đường TP HCM ........................................................ 9 Bảng 3.1. Mô tả dữ liệu thu thập ..................................................................................... 26 Bảng 3.2. Mô tả dữ liệu các nút giao thông quan trọng tại khu vực....................... ….30 Bảng 3.3. Mô tả các đoạn đường nối các nút giao thông quan trọng trong khu vực . 33 Bảng 4.1. Mô tả dữ liệu đường phố các điểm tắc nghẽn giao thông tại TPHCM ....... 39 v DANH MỤC HÌNH ẢNH Hình 2.1. Bản đồ ranh giới hành chính Thành phố Hồ Chí Minh ............................4 Hình 2.2. Bản đồ các điểm tắc nghẽn giao thông TP HCM .......................................8 Hình 2.3. Mô hình đồ thị .............................................................................................12 Hình 2.4. Phân loại đồ thị ...........................................................................................13 Hình 2.5. Khoảng cách Topologic ..............................................................................14 Hình 2. . ơ đồ kết nối ví dụ minh họa .....................................................................14 Hình 2. . ơ đồ mức độ kết nối của mô hình ví dụ...................................................21 Hình 2. . ơ đồ về mạng .............................................................................................22 Hình 3.1. ơ đồ phương pháp nghiên cứu .................................................................27 Hình 3.2. Dữ liệu thuộc tính của đường giao thông .................................................28 Hình 3.3. Tạo vùng đệm cho hapefile điểm .............................................................29 Hình 3.4. Cắt đường trong vùng đệm ........................................................................29 Hình 3.5. Bản đồ hướng đi của các nút giao thông quanh điểm kẹt xe tại một khu vực .................................................................................................................................30 Hình 3. . Ma trận kề kết nối các đỉnh .......................................................................32 Hình 3. . Mô hình đồ thị kết nối của các đỉnh tại một khu vực ..............................32 Hình 3. . Đưa dữ liệu liên kết lên Geoserver ............................................................34 Hình 3. . Chồng lớp bản đồ trên Geoserver .............................................................34 Hình 3.10. Giao diện thiết kế mô hình Website ........................................................35 Hình 4.1. Bản đồ ranh giới hành chính và bản đồ đường giao thông TP HCM ....37 Hình 4.2. Bản đồ các điểm kẹt xe TP HCM ..............................................................38 Hình 4.3. Đầu vào để thiết kế đỉnh .............................................................................43 Hình 4.4. Đầu vào thiết kế cạnh: ................................................................................43 Hình 4.5. Mô hình đồ thị sau khi đọc đầu vào J ON ...............................................44 Hình 4. . Mô hình sau khi đồ thị chạy thuật toán luồng cực đại ............................45 Hình 4. . Các lớp dữ liệu vùng TPHCM, đường giao thông và điểm kẹt xe khi kết nối lên Geoserver .........................................................................................................46 Hình 4. . Các lớp hapefile điểm nằm gần khu vực kẹt xe và đường liên kết các điểm đó khi kết nối hiển thị lên Geoserver ...............................................................46 vi Hình 4. . Chồng lớp các lớp hapefile thành bản đồ hoàn chỉnh trên Geoserver 47 Hình 4.10. Bảng thuộc tính khi kết nối PostGis ........................................................48 Hình 4.11. Giao diện web khi đưa lên erver Localhost..........................................49 Hình 4.12. Công cụ tương tác với bản đồ ..................................................................49 Hình 4.13. Thành phần thông tin dữ liệu trên giao diện web..................................50 Hình 4.14. Kết quả tự động nhập đầu vào ................................................................50 Hình 4.15. Website hoàn chỉnh khi chạy thuật toán ................................................52 vii CHƯƠNG 1. MỞ ĐẦU 1.1. Tính cấp thiết của đề tài Trong những năm qua, tắc nghẽn giao thông đã trở thành vấn đề được nhiều người quan tâm trên toàn thế giới, kể cả các quốc gia phát triển cũng như các quốc gia đang phát triển. Hệ lụy của tắc nghẽn giao thông ảnh hưởng tiêu cực đến nhiều khía cạnh của đời sống xã hội như: làm mất thời gian đi lại, tiêu hao nhiều nhiên liệu, tăng lượng khí thải và tiếng ồn, làm giảm chất lượng môi trường sống, kìm hãm sự phát triển của kinh tế đô thị. Theo báo cáo gần đây của Tạp chí giao thông: "Tình hình tắc nghẽn giao thông tại thành phố Hồ Chí Minh ngày càng trở nên phức tạp, nhiều cuộc họp đã được diễn ra nhằm đề xuất các giải pháp tối ưu để hạn chế nhưng vẫn không giải quyết được tình trạng tắc nghẽn giao thông. Cho đến nay, nhiều nghị định, văn bản được ban hành triển khai thực hiện vẫn chưa mang lại hiệu quả cao". Tại Việt Nam, tình trạng tắc nghẽn giao thông ở các đô thị lớn như Hà Nội và thành phố Hồ Chí Minh nhìn chung đang ở mức rất đáng báo động. "Thành phố Hồ Chí Minh là thành phố lớn nhất Việt Nam, đồng thời cũng là thành phố đang trên đà phát triển, là trung tâm văn hóa, giáo dục, khoa học, công nghệ quan trọng nhất cả nước và là một trong những đầu mối giao thông quan trọng điều phối kinh tế với các nơi ở các địa phương trong nước và nước ngoài. Tuy nhiên, với quá trình đô thị hóa diễn ra mạnh mẽ cùng với số lượng dân nhập cư từ các tỉnh lẻ và các nước khác tăng cao qua mỗi năm làm gia tăng số lượng các phương tiện giao thông trên toàn địa bàn thành phố gây ra nhiều bất cập trong mạng lưới giao thông". Bên cạnh đó, sự quản lý kém của các cấp chính quyền cùng với ý thức người tham gia giao thông chưa tốt đã làm cho mạng lưới giao thông của thành phố Hồ Chí Minh ngày càng trở nên tồi tệ, các tuyến đường quan trọng luôn bị đặt trong tình trạng quá tải, không thể lưu thông trong giờ cao điểm gây ảnh hưởng rất nhiều đến đời sống và công việc hàng ngày của người dân nơi đây. Có thể nói rằng: "Mạng lưới giao thông đô thị được ví như mạch máu của cơ thể con người, nếu mạch máu tắc nghẽn đồng nghĩa với việc cơ thể sẽ bị chết đi". Làm thế nào để tháo gỡ được vấn đề tắc nghẽn giao thông trên địa bàn thành phố Hồ Chí Minh là một bài toán khó của các cấp chính quyền và của toàn xã hội. Ngày nay, sự phát triển của khoa 1 học công nghệ đã phát minh, tìm ra nhiều công cụ, phần mềm để phục vụ tiện lợi hơn trong cuộc sống cũng như trong công việc. Một trong những công cụ được phát triển mạnh những năm gần đây là GIS (Geographic Information System- Hệ thống thông tin địa lý), GIS được ứng dụng với nhiều ngành khoa học- công nghệ khác, đặc biệt là đối với các vấn đề về dữ liệu không gian đô thị. GIS ứng dụng rộng rãi và phổ biến trong nhiều lĩnh vực dùng để phân tích, thống kê dữ liệu một cách hiệu quả và chính xác nhất. Cùng với sự phát triển những ứng dụng mới kết hợp với GIS, bài toán luồng cực đại trong mạng là một bài toán tối ưu nghiên cứu và ứng dụng lý thuyết đồ thị có thể dự đoán các luồng giao thông dựa trên cơ sở bản đồ số, dữ liệu không gian điều phối các luồng với sự hỗ trợ từ phần mềm GIS bao gồm các thông tin đã lưu trữ trong cơ sở dữ liệu và các công cụ cần thiết để có thể tính toán giải quyết tình trạng tắc nghẽn giao thông hiện tại. Xuất phát từ các lý do trên, đề tài “Ứng dụng bài toán luồng cực đại phục vụ mô hình tắc nghẽn giao thông tại thành phố Hồ Chí Minh” được thực hiện nhằm hỗ trợ việc phân tích hiện trạng và tính toán sự phân luồng của các điểm kẹt xe để sớm có biện pháp giảm thiểu tình trạng này một cách hợp lý nhất. 1.2. Mục tiêu nghiên cứu 1.2.1. Mục tiêu chung Ứng dụng bài toán luồng cực đại phục vụ mô hình tắc nghẽn giao thông tại thành phố Hồ Chí Minh. 1.2.2. Mục tiêu cụ thể Xây dựng bản đồ mạng lưới đường giao thông thành phố Hồ Chí Minh. Xây dựng dữ liệu mạng lưới các điểm tắc nghẽn giao thông trên địa bàn thành phố Hồ Chí Minh. Xây dựng mô hình đồ thị kết nối theo bài toán luồng cực đại thành phố Hồ Chí Minh. Xây dựng tính toán luồng giao thông cực đại theo mô hình đồ thị. Xây dựng mô hình Website ứng dụng phù hợp. 1.3. Đối tượng và phạm vi nghiên cứu Đề tài tập trung nghiên cứu trong phạm vi sau: - Đối tượng nghiên cứu đề tài là vấn đề tắc nghẽn giao thông. Phạm vi nghiên cứu: phạm vi nghiên cứu đề tài giới hạn trong địa bàn Thành phố Hồ Chí Minh. 2 CHƯƠNG 2. TỔNG QUAN TÀI LIỆU 2.1. Khái quát về khu vực nghiên cứu 2.1.1. Vị trí địa lý Thành phố Hồ Chí Minh nằm trong tọa độ địa lý khoảng 10º10’ - 10º38’ vĩ độ bắc và 106º22’ - 106º54’ kinh độ đông. Ranh giới địa lý thành phố Hồ Chí Minh giáp 6 tỉnh bao gồm: - Phía Bắc giáp tỉnh Bình Dương. - Phía Tây Bắc giáp tỉnh Tây Ninh. - Phía Đông và Đông Bắc giáp tỉnh Đồng Nai. - Phía Đông Nam giáp tỉnh Bà Rịa - Vũng Tàu. - Phía Tây và Tây Nam giáp tỉnh Long An và Tiền Giang. Theo số liệu đến năm 2015 của Tổng cục thống kê, TPHCM có tổng diện tích 2.095,5 km², với dân số 8.136,3 nghìn người. Mật độ dân số 3.888 người/ km². 3 Hình 2.1. Bản đồ ranh giới hành chính Thành phố Hồ Chí Minh 4 Số lượng người lao động từ độ tuổi 15 trở lên: 4.251,4 nghìn người. Thống kê của Sở Giao thông vận tải TPHCM ghi nhận được: "Đến tháng 3/2017, toàn thành phố có 7.976.845 phương tiện.Trong đó, có 637.323 ô tô, và gần 7,34 triệu xe gắn máy chiếm 92% tổng số xe. Ngoài ra, ước tính lượng xe máy và ô tô ngoài tỉnh hàng ngày ra vào TPHCM để làm ăn sinh sống và học tập không dưới 1 triệu phương tiện các loại". Theo ông Nguyễn Ngọc Tường, Phó ban Chuyên trách Ban An toàn giao thông TPHCM: "Từ đầu năm 2016 đến nay mỗi ngày bình quân TPHCM có hơn 1.000 xe gắn máy đăng ký mới, 180 xe có khi tới 250 xe ô tô đăng ký mới". Mức độ gia tăng về phương tiện đi lại ngày một lớn khiến TPHCM phải đối mặt với nhiều áp lực, đặc biệt là tắc nghẽn giao thông. Số liệu mới nhất của Sở Giao thông vận tải: "Tổng chiều dài đường bộ trong Thành phố Hồ Chí Minh là 3.670 km với 3.800 tuyến đường (không kể các tuyến đường khu vực nông thôn), phần lớn các tuyến đường đều hẹp, chỉ có khoảng 14% số đường có mặt đường rộng trên 12 m để có thể vận chuyển hành khách bằng xe buýt thuận lợi, 51% số đường có lòng đường rộng từ 7-12m, 35% so đường còn lại có lòng đường rộng dưới 7m". 2.1.2. Tình trạng giao thông tại Thành phố Hồ Chí Minh Dân số ngày càng tăng nhanh một cách chóng mặt, nhu cầu xây dựng nhà ở, công trình tăng theo chiếm phần lớn diện tích khu vực TPHCM. Bên cạnh đó, tốc độ xây dựng và phát triển cầu đường mới để phục vụ cho việc lưu thông không theo kịp sự gia tăng về dân số và số lượng phương tiện giao thông, việc phát triển vận tải công cộng còn chậm chạp và chưa có sự chuyển biên đột phá. Chính vì vậy, tình trạng ùn tắc giao thông tại TPHCM đang tăng lên đáng kể. Tình hình quản lý giao thông trên địa bàn ngày càng phức tạp do sự phát triển của các phương tiện xe cơ giới hiện đang không thể kiểm soát cùng với sự phát triển kinh tế và gia tăng dân số, đặc biệt sự gia tăng đột biến lượng xe gắn máy hai bánh và xe ô tô cá nhân là một trong những nguyên nhân gây nên tình trạng ùn tắc giao thông. Ngoài ra, nội thành TPHCM cũng tập trung số lượng rất lớn các trường học, bệnh viện, các cơ quan Nhà nước Trung ương và địa phương. Những học sinh, sinh viên, các bậc phụ huynh đưa đón con cùng với những người làm việc trong các cơ quan công sở đều đi vào giờ quy định giống nhau, hướng vào trung tâm thành phố nên tình trạng lưu thông ở các trục đường chính trở nên quá tải, nhất là vào giờ cao điểm buổi sáng và buổi chiều tan làm. Tính đến thời gian hiện tại, Sở GTVT TPHCM thống kê được trên địa bàn TPHCM đã phát sinh thêm rất nhiều điểm ùn tắc giao thông, nâng tổng số điểm ùn tắc giao thông của thành phố lên đến con số 37 điểm. Các điểm ùn tắc giao thông tập trung tại các khu vực như sân bay Tân Sơn Nhất, cảng Cát Lái, khu vực trung tâm, các tuyến đường kết nối từ ngoại ô vào nội đô thành phố. Đường xá trở nên quá tải đặc biệt là vào các giờ cao điểm, phương tiện xe máy và ô tô ngày càng nhiều khiến cho vận tốc lưu thông ngày 5 càng giảm, việc đi lại di chuyển trở nên khó khăn mất thời gian gây nhiều bất lợi cho cuộc sống. Thống kê danh sách các điểm ùn tắc giao thông tính đến hiện tại: - Khu vực Tôn Đức Thắng - Nguyễn Hữu Cảnh - Nguyễn Bỉnh Khiêm, Quận 1. - Giao lộ Nguyễn Văn Cừ - Trần Hưng Đạo, Quận 1 và Quận 5. Khu vực Lý Tự Trọng – Pasteur - Nam Kỳ Khởi Nghĩa - Lê Thánh Tôn (Xung quanh UBND TP), Quận 1. - Ngã sáu Công trường Dân Chủ, Quận 3 và Quận 10. - Đường Nguyễn Tất Thành, Quận 4. - Khu vực sư Vạn Hạnh - Thành Thái - 3 tháng 2, Quận 10. - Đường Trường Chinh (đoạn từ Âu Cơ đến Tân Kỳ Tân Quý), Quận Tân Bình. - Vòng xoay Lăng Cha Cả, Quận Tân Bình. - Giao lộ Cộng Hòa - Hoàng Hoa Thám, Quận Tân Bình. - Giao lộ Phan Thúc Duyện - Trần Quốc Hoàn, Quận Tân Bình. Vòng xoay Phạm Văn Đồng - Nguyễn Thái Sơn - Bạch Đằng - Hoàng Minh Giám - Nguyễn Kiệm, Quận Gò Vấp. - Đường Hoàng Minh Giám, Quận Phú Nhuận và Quận Gò Vấp. - Nút giao An Phú, Quận 2. - Đường Nguyễn Thị Định (từ vòng xoay Mỹ Thủy đến cảng Cát Lái), Quận 2. - Nút giao Mỹ Thủy, Quận 2. - Khu vực xa lộ Hà Nội - Thảo Điển - Quốc Hương, Quận 2. - Giao lộ Nguyễn Hữu Thọ - Nguyễn Văn Linh, Quận 7. - Giao lộ Huỳnh Tấn Phát - Lưu Trọng Lư, Quận 7. - Ngã tư Tây Hòa, Quận 9 và Quận Thủ Đức. - Ngã tư Thủ Đức, Quận 9 và Quận Thủ Đức. - Ngã tư An Sương, Quận 12 và Quận HoocMôn. - Quốc Lộ 50 (Cầu Ông Thìn), huyện Bình Chánh. - Giao lộ quốc lộ 50 - Nguyễn Văn Linh, Huyện Bình Chánh. 6 - Giao lộ Lê Văn Việt - Đình Phong Phú, Quận 9. - Đường Lã Xuân Oai (từ cầu Tăng Long đến đường Lò Lu), Quận 9. - Giao lộ Tô Ngọc Vân - TX25, Quận 12. - Ngã tư Bốn Xã, Quận Bình Tân và Quận Tân Phú. - Ngã sáu Gò Vấp, Quận Gò Vấp. - Giao lộ Phan Văn Trị - Phạm Văn Đồng, Quận Gò Vấp và Quận Bình Thạnh. - Giao lộ Lê Quang Định - Phạm Văn Đồng, Quận Gò Vấp. Đường Phan Văn Trị (đoạn từ Cầu Hang Trong đến đường Phạm Văn Đồng), Quận Gò Vấp và Quận Bình Thạnh. - Giao lộ Nguyễn Oanh - Phan Văn Trị, Quận Gò Vấp. - Giao lộ Quang Trung - Lê Văn Thọ, Quận Gò Vấp. - Giao lộ Đinh Bộ Lĩnh - Bạch Đằng, Quận Bình Thạnh. Đường Xô Viết Nghệ Tĩnh (từ Bạch Đằng đến Ngã 5 Đài Liệt Sỹ), Quận Bình Thạnh. - Giao lộ Vĩnh Lộc - Nguyễn Thị Tú - Quách Điêu, Huyện Bình Chánh. - Đường Quang Trung khu vực chợ HoocMôn, Huyện HoocMôn. 7 Hình 2.2. Bản đồ các điểm tắc nghẽn giao thông TP HCM Bên cạnh đó, mạng lưới xe buýt của thành phố sau hơn 14 năm hình thành và phát triển, tính đến nay Thành phố đang duy trì khoảng 136 tuyến xe buýt. Lượng hành khách đạt khoảng 324 triệu lượt, chiếm hơn 57,3% tổng lượng hành khách sử dụng các phương tiện vận tải hành khách công cộng. Nhưng tình hình ùn tắc giao thông diễn biến phức tạp đã khiến cho lộ trình các tuyến xe buýt không được đảm bảo, thời gian giữa các chuyến kéo dài quá lâu, tốc độ di chuyển chậm, thời gian hành trình kéo dài không đáp ứng được nhu cầu đi lại của người dân. Nhiều tuyến xe buýt hoạt động tùy tiện, phân bố không đều, có nơi có nhu cầu nhưng hoàn toàn không có mạng lưới xe buýt hoạt động, không thuận tiện cho người dân. Điều này dẫn đến người dân lựa chọn phương tiện cá nhân để đi lại phù hợp tiện lợi hơn, làm cho mức độ người dân sử dụng phương tiện xe buýt đang rơi vào tình trạng giảm rất nhiều so với những năm trước đây. Theo Tiến sỹ Nguyễn Bách Phúc - Chủ tịch Hội Tư vấn Khoa học Công nghệ và Quản lý (HASCON) phân tích tính toán cụ thể: Một chiếc xe gắn máy bình quân rộng 0,7 m, dài 2 m, khi chạy trên đường phải có khoảng cách an toàn tối thiểu với xe bên cạnh là 0,5 m, khoảng cách với xe phía trước là 2m. Như vậy, diện tích 1 xe gắn máy chiếm dụng mặt đường khi lưu hành là (0,7 m + 0,5 m x 2) x (2 m + 2 m) = 6,8 m2. 8 Dựa theo hệ thống phân loại đường phố trong OpenStreet Map, dữ liệu đường phố của toàn Thành phố Hồ Chí Minh được thống kê qua bảng 2.1 bao gồm 24 loại. Bảng 2.1. Mô tả phân loại dữ liệu đường TP HCM STT LOẠI ĐƯỜNG MÔ TẢ Footway Đường đi bộ, dành riêng cho người đi bộ. 2 Primary Đường tỉnh hoặc đường đô thị chính (bao gồm làn xe máy của các đại lộ). "Đường đô thị chính" là những đường chạy xuyên suốt cả một (hoặc vài) tỉnh/thành phố, tạo nên trục giao thông chính cho tỉnh/thành phố đó. 3 Path Đường mòn. 4 Primary_link Đường dẫn vào/ra đường tỉnh hoặc đường đô thị chính. Residential Đường đô thị nhỏ, cục bộ (trong phường, khu phố). Các con ngõ rộng hoặc đường trong khu đô thị, chung cư... mà ô tô có thể đi vừa. 6 Secondary Đường đô thị phụ hoặc đường huyện (cấp quận huyện). Ở mức đô thị, loại đường này góp phần làm giảm lưu lượng giao thông ở các tuyến chính lớn hơn. 7 Secondary_link Đường dẫn vào/ra đường huyện hoặc đường đô thị phụ. 8 Service Đường chuyên dụng và những ngõ ngách (kiệt, hẻm) trong đô thị. Đường chuyên dụng là những đường dùng riêng cho một tổ chức hay cá nhân, hay lối đi trong các khuôn viên. 9 Tertiary Đường xã và đường đô thị tương đương (cấp phường và liên phường). 10 Trunk Quốc lộ hoặc xa lộ. Quốc lộ là những đường quốc lộ nối thủ đô, các đô thị trực thuộc Trung ương và nhiều tỉnh thành khác. Xa lộ là những đường phố có quy mô lớn giữ vị trí quan trọng trong hệ thống giao thông đô thị. Xa lộ thường khá hiện đại và được thiết kế để tải lưu lượng giao thông cao. 11 Construction Đường đang thi công. 1 5 9 Cycleway Đường dành riêng cho xe đạp. Living_street Phố sinh hoạt, đường nội bộ trong khu dân cư, các loại xe bị hạn chế tốc độ tối đa (thường dưới 20 km/h). 14 Motorway Đường cao tốc, tức đường dành riêng cho xe cơ giới, có dải phân cách chia đường cho xe chạy hai chiều riêng biệt; không giao nhau cùng mức với một hoặc các đường khác; giới hạn cả tốc độ lớn nhất lẫn tốc độ nhỏ nhất. 15 Motorway_link Đường dẫn vào/ra đường cao tốc. 16 Pedestrian Phố đi bộ, thường dùng để mua sắm và ăn uống. 17 Proposed Đường dự kiến 18 Road Đường chưa xác định rõ ràng (ví dụ chỉ mới vẽ theo ảnh vệ tinh). 19 Steps Đường bậc thang. 20 Tertiary_link Đường dẫn vào/ra đường xã hoặc phố. 21 Track Đường dành cho xe đạp được tách ra khỏi làn đường cho xe ô tô. 22 Trunk_link Đường dẫn vào/ra quốc lộ trọng yếu, xa lộ. 23 Unclassified Đường không được phân loại.Chúng thường là đường vô danh và không được chỉ rõ là ngõ hay phố cũng như không có bất cứ chỉ dẫn, bảng tên hay số hiệu nào. Thường là những đường nhỏ trong xóm, ấp. 24 Platform Thềm ga, sân ga (xe lửa); bậc lên xuống (xe buýt). 12 13 2.2. Lý thuyết đồ thị 2.2.1. Lịch sử hình thành Lý thuyết đồ thị nảy sinh từ nhu cầu giải quyết các vấn đề thực tiễn và có liên quan chặt chẽ với nhiều ngành khác nhau. Lý thuyết đồ thị là một lĩnh vực đã có từ lâu và có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế kỷ XVIII bởi nhà toán học lỗi lạc người Thụy Sỹ Leonhard Euler. Chính ông là người đã sử dụng lý thuyết đồ thị để giải bài toán nổi tiếng về cái cầu ở thành phố Konigsberg (năm 1736). 10 Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại. Đặc biệt trong khoảng thời gian vài mươi năm trở lại đây, cùng với sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của Tin học, lý thuyết đồ thị ngày càng được quan tâm nhiều hơn. 2.2.2. Ứng dụng của lý thuyết đồ thị Lý thuyết đồ thị không những có nhiều trong thực tế mà còn là công cụ đắc lực cho ngành công nghệ thông tin. Nó giúp mô tả một cách dễ dàng các bài toán phức tạp cụ thể, để từ đó mã hóa các bài toán đó vào máy tính. Ngoài ra, lý thuyết đồ thị được ứng dụng trong nhiều lĩnh vực quan trọng khác: ­ Nghiên cứu các phân tử trong hóa học và vật lý, nghiên cứu cấu trúc của các nguyên tử, phân tử. ­ Xác định tính liên thông của mạng máy tính. ­ Giải quyết các bài toán tối ưu, phân bố tần suất. ­ Tìm đường đi ngắn nhất trong mạng lưới giao thông. ­ Có thể áp dụng lý thuyết đồ thị cho mạng lưới đường bộ, cố gắng tìm ra một cách giảm tắc nghẽn giao thông. ­ Sử dụng trong các mạng lưới bay của các hãng hàng không để kết nối các thành phố theo cách hiệu quả nhất, di chuyển hầu hết hành khách với ít chuyến đi nhất. Đảm bảo máy bay ở đúng nơi đúng lúc và không bị rơi. Trên thực tế có nhiều bài toán liên quan tới một tập hợp các đối tượng và những mối liên hệ giữa chúng, đòi hỏi phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu đó là đồ thị. Đồ thị được sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. Cũng có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Có thể xác định hai máy tính trong mạng có thể trao đổi thông tin được với nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị cũng giải được các bài toán: tìm đường đi ngắn nhất giữa hai thành phố trong mạng giao thông, phân bố tần suất hay tìm luồng cực đại trong mạng lưới. 2.2.3. Định nghĩa đồ thị Đồ thị là một cấu trúc rời rạc bao gồm các tập hợp các đỉnh và tập hợp các cạnh nối các đỉnh đó. Đồ thị G= (V,E). Trong đó V: tập các đỉnh E: tập các cạnh 11