Đề tài Kết hợp chuẩn opengis và hệ quản trị cơ sở dữ liệu để giải quyết một số bài toán tối ưu trên mạng giao thông thành phố

KH OA C NT T – Đ H KH TN - 1 - TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM TRẮC NGỌC ĐĂNG - 0012029 BÙI THẾ TÀI - 0012086 Đề tài: KẾT HỢP CHUẨN OPENGIS VÀ HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU ĐỂ GIẢI QUYẾT MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN MẠNG GIAO THÔNG THÀNH PHỐ. LUẬN VĂN CỬ NHÂN TIN HỌC NIÊN KHOÁ 2000 - 2004 KH OA C NT T – Đ H KH TN - 2 - TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM TRẮC NGỌC ĐĂNG - 0012029 BÙI THẾ TÀI - 0012086 Đề tài: KẾT HỢP CHUẨN OPENGIS VÀ HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU ĐỂ GIẢI QUYẾT MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN MẠNG GIAO THÔNG THÀNH PHỐ. LUẬN VĂN CỬ NHÂN TIN HỌC GVHD : Th.Sĩ NGUYỄN MINH NAM NIÊN KHOÁ 2000 - 2004 KH OA C NT T – Đ H KH TN - 3 - Lời cảm ơn Chúng em xin chân thành cảm ơn toàn thể quý thầy cô khoa Công Nghệ Thông Tin trường Đại học Khoa học Tự nhiên TP.HCM đã tận tình giúp đỡ và truyền đạt những kiến thức quý báu cho chúng em trong suốt thời gian học tập tại trường. Đặt biệt, chúng em xin dành sự biết ơn trân trọng nhất gởi đến thầy Th.Sĩ NGUYỄN MINH NAM, là người đã trực tiếp hướng dẫn và động viên chúng em trong suốt thời gian thực hiện luận văn tốt nghiệp này. Cuối cùng, chúng tôi xin cám ơn tất cả các bạn học đã giúp chúng tôi giải quyết những vướng mắc nho nhỏ trong quá trình làm việc. Xin cảm ơn tất cả. -Trắc Ngọc Đăng – Bùi Thế Tài KH OA C NT T – Đ H KH TN - 4 - MỤC LỤC LỜI CẢM ƠN ...........................................................................................................1 LỜI MỞ ĐẦU...........................................................................................................2 CHƯƠNG 1: TỔNG QUAN VỀ GIS 1.1. Hệ thống thông tin địa lý là gì?..........................................................................4 1.2. Mô hình dữ liệu của hệ thống thông tin địa lý...................................................5 1.3. Các nguồn dữ liệu của hệ thống thông tin địa lý ...............................................6 1.4. Hiện trạng ứng dụng công nghệ GIS tại Việt Nam............................................7 1.5. Kết chương.........................................................................................................7 CHƯƠNG 2: GIỚI THIỆU OPENGIS 2.1. Các khái niệm.....................................................................................................9 2.2. Tổng quan về OpenGIS .....................................................................................9 2.3. OpenGIS Abstract Specification .....................................................................15 2.4. Feature Geometry.............................................................................................31 CHƯƠNG 3: GIẢI THUẬT LIN-KERNIGHAN CHO BÀI TOÁN TÌM CHU TRÌNH TỐI ƯU (TSP) 3.1. Giới thiệu chung...............................................................................................73 3.2. Bài toán TSP ....................................................................................................74 3.3. Thuật giải Lin-Kernighan nguyên thuỷ (1971)................................................77 3.4. Thuật giải Lin-Kernighan cải tiến (2002) ........................................................87 3.5. Các thủ thuật cải tiến thuật giải L-K trong quá trình cài đặt .........................108 3.6. Các cấu trúc dữ liệu quan trọng của thuật giải Lin-Kernighan......................110 3.7. Kết chương.....................................................................................................112 THUYẾT MINH CHƯƠNG TRÌNH THỬ NGHIỆM.........................................113 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN............................................................119 PHỤ LỤC..............................................................................................................121 A. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA 2 ĐIỂM .......................122 B. BÀI TOÁN XỬ LÝ ĐIỀU PHỐI CẤP THỜI (EMERGENCY).....................123 KH OA C NT T – Đ H KH TN - 5 - C. GIỚI THIỆU VỀ NÚT ẢO. .......................................................................................124 TÀI LIỆU THAM KHẢO ....................................................................................127 KH OA C NT T – Đ H KH TN - 6 - Lời mở đầu Trong cuộc sống hiện nay, khi xã hội phát triển, con người luôn bị đòi hỏi cao về thời gian. Do đó, yếu tố thời gian được xem là yếu tố quyết định trong mọi sinh hoạt hằng ngày. Điều này đã cho chúng ta thấy thời gian đã quý nay lại càng quý hơn. Thực tế đã cho chúng ta thấy, có những việc đòi hỏi rất nghiêm khắc về thời gian, mà nếu không đáp ứng được có thể sẽ có một hậu quả nghiêm trọng, ảnh hưởng đến tính mạng con người cho đến tiêu hao về của cải vật chất. Ví dụ như: các hoạt động phòng cháy chữa cháy, cảnh sát phản ứng nhanh 113, đề xuất một lộ trình thích hợp cho một lần phân phối sản phẩm từ công ty mẹ đến các đại lý, lập lịch cho một thiết bị vận hành...Nhưng làm sao để ta biết phải điều phối các hoạt động đó thế nào thì hợp lý nhất; làm sao ta có được một lộ trình tối ưu với rất nhiều điểm phải đến trong một khoảng thời gian tương đối ngắn mà ta không phải đợi dài cổ tính, toán suy nghĩ cho mệt óc. Đây rõ ràng là các vấn đề nan giải. Hiện nay, với sự phát triển vũ bão của khoa học công nghệ, đặc biệt là ngành Công Nghệ Thông Tin, thì người ta phần nào được hệ thống máy tính trợ giúp giải quyết những vấn đề trên. Với hệ thống GIS (hệ thống thông tin địa lý), cùng GPS (hệ thống định vị toàn cầu) thì các vấn đề điều phối xử lý cấp thời dường như có thể thực hiện một cách tốt đẹp. Xuất phát từ những yêu cầu trên, nhằm hạn chế mọi chi phí không đáng có, những khoảng thời gian quý báu sẽ không phải mất đi nhiều, chúng em đã thử nghiệm và áp dụng các chuẩn của OpenGIS (xu thế của ngày nay khi các ứng dụng về GIS hướng đến tính mở nhiều hơn) cùng các thuật giải, các phương pháp nhằm giải quyết tối ưu các bài toán trên mạng giao thông, cũng như là khả năng điều phối nhanh các lực lượng phòng cháy chữa cháy, cảnh sát 113, xe Taxi, v.v… KH OA C NT T – Đ H KH TN - 7 - CHƯƠNG 1 TỔNG QUAN VỀ GIS KH OA C NT T – Đ H KH TN - 8 - 1.1 Hệ thống thông tin điạ lý (GIS – Geographic Information System) là gì ? Hệ thống thông tin điạ lý (Geographical Information System – GIS) là sự kết hợp giữa công nghệ bản đồ số hoá với công nghệ quản trị cơ sở dữ liệu cho phép việc truy xuất, xử lý thống kê một khối lượng lớn thông tin khổng lồ, đa dạng nhanh chóng và rất trực quan ….. Công nghệ GIS với khả năng phân tích không gian một cách chính xác, nhanh chóng đã được ứng dụng trong rất nhiều ngành khác nhau phục vụ cho việc quản lý vĩ mô. Hệ thống thông tin điạ lý đóng vai trò như một kỹ thuật tổ hợp. Hệ thống thông tin điạ lý đã tiến hoá bởi sự liên kết một số các kỹ thuật tổ hợp rời rạc vào thành một tổng thể hơn là sự cộng các thành phần của chúng lại. Hình 1.1 : Hệ thống thông tin điạ lý với sự tích hợp các ngành khoa học khác nhau. Bản đồ CAD Ảnh Nội suy Viễn thám GIS Phân tích không KH OA C NT T – Đ H KH TN - 9 - 1.2 Mô hình dữ liệu của hệ thống thông tin điạ lý : 1.2.1 Dữ liệu điạ lý: Do sự tích hợp liên ngành nên hệ thống thông tin điạ lý làm việc với nhiều nguồn thông tin khác nhau như: bản đồ, ảnh hàng không, ảnh viễn thám... Hệ thống thông tin là một hệ thống thu thập, lưu trữ và điều hành các thông tin dưới dạng giấy, ảnh, số về các hiện tượng tự nhiên trong thế giới thực. Trong cơ sở dữ liệu được cấu thành từ thông tin, các thông tin thường không sử dụng được trực tiếp mà phải thông qua một hệ thống các công cụ truy xuất, tái tạo lại đối tượng thế giới thực mà người dùng quan tâm. Một đối tượng được lưu trữ trong cơ sở dữ liệu dưới dạng các thực thể hình học, người dùng sẽ dùng phải tái tạo lại đối tượng ấy thông qua các dữ liệu hình học này. Như vậy dữ liệu là rất đa dạng, chúng có mang tính không gian, thời gian, được gọi là dữ liệu địa lý. Định nghĩa: Dữ liệu địa lý là các dữ liệu số mô tả các đối tượng trong thế giới thực. Dữ liệu điạ lý được tổ chức thành hai nhóm thông tin chính, đó là: 1/ Nhóm thông tin về phân bố không gian. 2/ Nhóm thông tin về thuộc tính của đối tượng. 1.2.2 Mô hình bản đồ chồng xếp: Một trong những phương pháp chung nhất của tổ chức dữ liệu điạ lý là tổ chức theo bản đồ và các lớp thông tin. Mỗi lớp thông tin là một biểu diễn của dữ liệu theo một mục tiêu nhất định, do vậy nó thường là một hoặc một vài dạng của thông tin. Ví dụ để nghiên cứu nguồn tài nguyên thiên nhiên, điạ chất, các điều kiện vật lý lớp dưới đất, sử dụng đất, kênh rạnh……Người ta tách chúng thành các lớp. KH OA C NT T – Đ H KH TN - 10 - Đối với bài toán quy hoạch thành phố, các thông tin có thể là dữ liệu về đường phố, công trình công cộng, giao thông, phân vùng….Các thông tin này được lấy từ bản đồ, ảnh hàng không, ảnh vũ trụ và được chồng xếp lên nhau để được bản đồ tổng quát. Cách tổ chức theo lớp này là hợp lý nếu chúng ta đang làm việc với các đối tượng trải bề rộng. Tuy nhiên phương pháp này có thể không cần thiết nữa nếu chúng khác theo độ cao hay theo thời gian. Hình1.2: Mô hình dữ liệu vật lý. Mỗi lớp thông tin lại có mô hình cấu trúc chi tiết hơn. Về nguyên lý lớp thông tin là tập hợp các dữ liệu điạ lý về một khiá cạnh nào đó của đối tượng điạ lý thực tế. Do đó nó sẽ mang cấu trúc chung cho loại dữ liệu đó. Không giống như các dạng dữ liệu thông dụng khác, dữ liệu điạ lý phức tạp hơn, nó bao gồm các thông tin về điạ lý, các quan hệ topo và các thuộc tính phi không gian. Mọi dữ liệu điạ lý có thể được mô hình với ba thành phần khác nhau theo quan niệm topology – điểm, đường, vùng.Bất kì một đối tượng tự nhiên nào đều có thể được biểu diễn bằng một trong bao đối tượng này kèm theo chúng là những thông tin đặc thù riêng. Mô hình dữ liệu điạ lý bao gồm bốn thành phần sau: 1. Thành phần khoá. 2. Định vị. KH OA C NT T – Đ H KH TN - 11 - 3. Thành phần phi không gian. 4. Thành phần không gian. Khoá : là mã số duy nhất cho thực thể để phân biệt thực thể này với thực thể khác. Định vị: Chỉ ra vị trí của thực thể. Thành phần phi không gian: Là những thuộc tính riêng cho từng thực thể như tỷ lệ, khoảng, định danh …. Thành phần không gian : Các đối tượng tư nhiên bên ngoài được chuyển vào máy tính để quản lý theo hai cách sau : 1. Raster. 2. Vectơ. Mô hình vectơ : tường được biểu diễn duới dạng điểm, đường và vùng . Vị trí không gian của một thực thể được xác định bởi một hệ toạ độ thống nhất toàn cầu. Một thực thể được xác định bởi cặp toạ độ (X,Y) và các thuộc tính khác như : kiểu điểm, màu, hình dạng . Hình1.3: minh hoạ về các thực thể được thể hiện trên bản đồ Mô hình Raster : Dữ liệu Raster được phân biệt bằng đơn vị pixel, đó là hình ảnh đơn vị nhỏ nhất phản ánh đối tượng trong không gian. Cấu trúc dữ liệu ratser 2-D được xem như là một ma trận các ô lưới đặc trưng cho một ô vuông bề mặt đất. Độ phân giải của dữ liệu raster phụ thuộc vào kích thước của những ô lưới này. KH OA C NT T – Đ H KH TN - 12 - Hình 1.4 :minh hoạ dữ liệu raster, ta có một ma trận với các giá trị khác nhau. Trong đó nước có giá trị 1, rừng là 2 và đất nông nghiệp là 3 1.3 Thu thập các nguồn dữ liệu của GIS: Có nhiều kỹ thuật để thu thập thông tin cho các nguồn dữ liệu. Nó thường được thu thập từ việc đo đạc trực tiếp trên những vùng địa trắc khác nhau. Tuy nhiên, một số lớn dữ liệu liệu có thể được chuyển đổi từ bản đồ giấy sang hình thức lưu trữ của bản đồ điện tử. Có hai phương pháp thường được sử dụng đó là : Phương pháp quét (scanning): Đây là kỹ thuật thông dụng mà lại ít tốn kém, có thể được thực hiện trên các máy tính cá nhân hay của công ty. Máy quét sẽ lưu trữ lại các hình ảnh của bản đồ giấy dưới hình thức số và hiển thị chúng trở lại màn hình. Việc quét hình ảnh từ bản đồ giấy tương đối đơn giản và nhanh chóng, tuy nhiên phương pháp này lại không thể cung cấp thuộc tính của các đối tượng tự nhiên như điạ chỉ của một toà nhà hay ngày thành lập cuả một sân vận động nào đó. Dữ liệu có được từ những phương pháp này thường dưới dạng raster cho kích thước rất lớn. Phương pháp số hoá: Kỹ thuật này đòi hỏi phải cung cấp các thiết bị chuyên ngành. Bản đồ nguồn sẽ được trãi bề mặt ngang, một con trỏ sẽ xác định tọa độ các điểm tạo nên hình dạng bản đồ, sau quá trình số hoá, thuộc tính của các đối tượng mới được thêm vào. Phương pháp này đòi hỏi nhiều thời gian và nguồn dữ liệu có được từ kỹ thuật này dưới hình thức Vectơ. Phương pháp vectơ hoá : KH OA C NT T – Đ H KH TN - 13 - Một vài hệ thống máy tính chuyên nghiệp có thể chuyển đổi dữ liệu Raster sang dạng dữ liệu Vectơ. Phương pháp này cho tốc độ nhanh do tính tự động nhưng lại kém chính xác hơn so với việc số hoá thủ công. Các kỹ thuật trên đều dựa vào nguồn dữ liệu bản đồ giấy có sẵn. Trên thực tế, người ta còn dựa vào các ngành lĩnh vực khác như : viễn thám, GPS, phân tích ảnh … để thu thập nguồn dữ liệu cho GIS. 1.4 Hiện trạng ứng dụng công nghệ GIS tại Việt Nam : Hiện nay công nghệ thông tin phát triển rất mạnh mẽ, nhiều công nghệ tiên tiến trước đây chỉ có ở các nước phát triển thì hiện nay đã có mặt ở Việt Nam. Đối với sản phẩm công nghệ thông tin chuyên nghiệp như hệ thống thông tin điạ lý, tuy là các nhà cung cấp luôn cố gắng đưa ra các sản phẩm dễ dùng, tiện lợi nhưng thực tế vẫn có khoảng cách giữa các nhà chuyên môn và các sản phẩm công nghệ nói trên.. Ở Việt Nam hệ thống thông tin điạ lý ứng dụng chủ yếu cho các lĩnh vực số hoá. Sau giai đoạn số hoá người ta cần đến hệ thống thông tin điạ lý ở các chức năng phân tích khác để giải quyết cho những bài toán ứng dụng. Nhiều công ty nước ngoài đã xâm nhập vào thị trường Việt Nam trong lĩnh vực này. Tuy nhiên, giá các sản phẩm phần mềm của họ rất cao tạo một khoảng cách ngày càng xa cho việc ứng dụng GIS vào cuộc sống hằng ngày. 1.5. Kết luận: Công nghệ GIS với những lợi thế của nó đã mang lại phương pháp quản lý hiệu quả hơn, mọi sự vật, đối tượng, từ những thông tin không gian đến những thông tin phi không gian tất cả đều được quản lý một cách thống nhất trên cùng hệ thống. Mọi truy xuất đều thể hiện trực quan hơn trên bản đồ số thay cho những dòng văn bản đơn thuần. Chính vì thế GIS ngày một trở nên quen thuộc hơn cho người dùng, nó được ứng dụng trong nhiều lĩnh việc từ đơn giản đến phức tạp và chi phí đòi hỏi đầu tư ngày một thấp hơn. Có thề nói rằng GIS ngày một tự khả định tầm quan trọng, được các nước phát triển xem như một mũi nhọn trong lĩnh công nghệ thông tin và được đưa vào chương trình giảng dạy. KH OA C NT T – Đ H KH TN - 14 - CHƯƠNG 2 GIỚI THIỆU OPENGIS KH OA C NT T – Đ H KH TN - 15 - 2.1. CÁC KHÁI NIỆM: Dữ liệu địa lý “geodata” : Thông tin xác định vị trí địa lý và những nét tiêu biểu của các đặc tính tự nhiên hoặc nhân tạo và những ranh giới của Trái đất. Geodata đại diện những khái niệm trừu tượng của những thực thể thế giới thực, như những con đường, toà nhà, xe cộ, hồ nước, những khu rừng và các quốc gia; là dữ liệu miêu tả các hiện tượng một cách trực tiếp hay gián tiếp kết hợp với vị trí (cùng thời gian và hướng) liên quan đến bề mặt Trái đất , đã dươc thu thập dưới dạng số (kĩ thuật số) trên 30 năm nay. Xử lý thông tin địa lý “geoprocessing” : là bất kì việc tính toán dạng kĩ thuật số nào sử dụng geodata, lập mô hình, phiên dịch và sử dụng thông tin Trái Đất gồm hệ thống thông tin địa lý (GI), hệ thống thông tin đất đai (LIS), việc xử lý ảnh và tạo ảnh Trái đất, việc chứa geodata trong tất cả các loại cơ sở dữ liệu, những phương thức khảo sát dạng kĩ thuật số, sự định hướng, khí tượng học, địa chấn học,v v.. “Interoperable geoprocessing” chỉ khả năng của một hệ thống kĩ thuật số để : - Tùy thích trao đổi tất cả các loại thông tin không gian về Trái đất ,về các đối tượng và hiện tượng ở trên ,bên trên và dưới bề mặt Trái đất . - Chạy các phần mềm có khả năng thao tác các thông tin như vậy qua mạng một cách hợp tác. 2.2. TỔNG QUAN VỀ OPENGIS : 2.2.1. Làm quen với OpenGIS Specification : 2.2.1.1. Khái niệm: Đặc tả OpenGIS (OpenGIS Specification) , một đặc tả toàn diện của một bộ khung phần mềm cho các truy cập phân tán đến geodata và những tài nguyên geoprocessing . Đặc tả này cung cấp cho các nhà phát triển phần mềm trên thế giới một khuôn mẫu giao diện chung cặn kẽ để viết các phần mềm hoạt động chung với KH OA C NT T – Đ H KH TN - 16 - các phầm mềm dạng OpenGIS khác.Bộ khung OpenGIS (OpenGIS framework) gồm : - Một cách thức chung dạng số thể hiện Trái đất và các hiện tượng của nó trên cơ sở toán học và khái niệm. - Một mô hình chung để thực hiện những truy nhập, quản lý, thao tác, trình bày, và chia sẻ geodata giữa những cộng đồng thông tin . - Một bộ khung để sử dụng mô hình Open Geodata và mô hình dich vụ Open GIS để giải quyết vấn đề khả năng không hoạt đông kết hợp không chỉ về mặt kĩ thuật mà cả về mặt tổ chức. Các nhà phát triển xây dựng những hệ thống có giao diện thích ứng OpenGIS Specification sẽ tạo ra những phần mềm trung (middleware), phần mềm bộ phận (componentware) và những ứng dụng có thể kiểm soát một phạm vi rộng các kiểu geodata và các hàm geoprocessing. Người sử dụng các hệ thống này có thể chia sẻ một không gian dữ liệu tiềm năng rộng lớn qua mạng, dù dữ liệu được sản sinh vào các thời điểm khác nhau bởi các nhóm không liên quan sử dụng các hệ thống sản xuất khác nhau cho những mục đích khác nhau và thật sự có thể đang hiện hữu dưới sự điều khiển chính của hệ thống được sử dụng cho việc sản xuất của họ. Geodata kế thừa (Legacy geodata) được tổ chức trong các hệ thống có giao diện thích ứng OpenGIS Specification sẽ có thể được truy xuất bởi các phần mềm có giao diện thích ứng OpenGIS Specification khác . OpenGIS Specification cung cấp một bộ khung cho những người phát triển phần mềm để tạo ra phần mềm cho phép những người dùng của họ truy nhập và xử lý dữ liệu địa lý từ những nguồn đa dạng qua một giao diện tính toán chung bên trong một nền tảng công nghệ thông tin mở. 2.2.1.2. Ưu điểm: Người phát triển ứng dụng có thể dễ dàng và linh hoạt hơn để: • Viết phần mềm để truy cập geodata. • Viết phần mềm để truy cập những tài nguyên geoprocessing . KH OA C NT T – Đ H KH TN - 17 - • Sửa đổi những ứng dụng theo nhu cầu người dùng cụ thể, tích hợp phi không gian và không gian. • Chọn một môi trường phát triển. • Cung cấp những ứng dụng trên những nền tảng đa dạng. • Sử dụng lại mã geoprocessing Nhà quản lý thông tin linh hoạt hơn đối với: • Truy cập và / hoặc phân phối geodata • Cung cấp những khả năng geoprocessing tới những khách hàng • Tích hợp Dữ liệu địa lý và sự xử lý vào một kiến trúc tính toán liên hợp • Chọn những nền thích hợp - kiểu máy tính cá nhân, kiểu máy chủ, và kiểu nền tính toán phân tán ( CORBA, OLE / COM, DCE, ….) • Phù hợp với người dùng với những công cụ geoprocessing đúng (và được địng cỡ đúng) Những người dùng cuối là những người hưởng lợi tối ưu, nhận được: • Sự truy nhập thời gian thực tới một hệ thống vũ trụ thông tin địa lý lớn rộng hơn so với hệ thống vũ trụ thông tin địa lý có thể truy cập ngày nay. • Nhiều ứng dụng hơn ( với những middleware và tài liệu hỗn hợp) khai thác thông tin địa lý. • Những khả năng làm việc với những kiểu geodata và định dạng khác nhau bên trong một môi trường ứng dụng đơn và dòng công việc ( workflow ) liên tục , mà không quan tâm đến chi tiết của những kiểu và những định dạng này. 2.2.2. OpenGIS Specification định nghĩa : 2.2.2.1. Mô