Gis và các bài toán giao thông

PHẦN 2 GIS VÀ CÁC BÀI TOÁN GIAO THÔNG chương 3 GIS VÀ CÁC BÀI TOÁN GIAO THÔNG 3.1 tổng quan về các bài toán giao thông 3.1.1 Giới thiệu Như đã mô tả ở phần trên, GIS có ứng dụng rất rộng rãi đặc biệt là trong các vấn đề về đô thị. Một trong những vấn đề đó là giải quyết một cách trực quan bài toán về giao thông. Bài toán giao thông là bài toán giải quyết và dự đoán các luồng giao thông, xử lý các sự cố phát sinh tức thời trên đường giao thông dựa vào cơ sở bản đồ số, điều phối các luồng để tránh tình trạng ách tắc. Có hai dạng điều phối là điều phối tĩnh và điều phối động. Điều phối tĩnh là các công việc đưc sắp xếp trước theo một thứ tự nào đó và thực hiện đúng theo trình tự đó. Việc điều phối này phải được nghiên cứu và sắp xếp trước bởi các chuyên gia giao thông. Với sự hỗ trợ của GIS cùng với các thông tin đã được lưu trữ trong cơ sở dữ liệu thì việc sắp xếp này sẽ trực quan hơn, nhanh hơn. Bài toán cho cách điều phối này là bài toán sắp xếp tuyến xe buýt với các tuyến và trạm đuợc xác định trước, sau đó được mô tả và hiện thực trên bản đồ số sử dụng công nghệ GIS. Điều phối động là sự sắp xếp các công việc theo một thứ tự phụ thuộc vào dữ liệu động được cập nhật tức thời vào thời điểm điều phối. Bài toán minh họa là bài toán điều phối xe taxi. Khi có yêu cầu từ khách hàng thì trung tâm điều phối phải xác định được xe nào gần khách hàng nhất và điều xe đó đến. Để giải quyết các bài toán này dựa trên công nghệ GIS và bản đồ số, các tác giả đã sử dụng kỹ thuật tạo node giả trên bản đồ, kỹ thuật này vừa không phá vỡ cấu trúc và hình dạng của bản đồ, vừa tạo sự dễ dàng trong việc quản lý các mô tả của bài toán cũng như cấu trúc node giả và node thật. Hình 3.1: GIS và giao thông 3.1.2 Bài toán xe buýt Theo thông tin từ các báo, đài, tuyến xe buýt ở nước ta nói chung và thành phố Hồ Chí Minh nói riêng vẫn còn rất thiếu, chưa đáp ứng được nhu cầu của người dân. Chính phủ cũng như chính quyền thành phố đang ra sức đầu tư phát triển các phương tiện vận chuyển công cộng, trong đó có xe buýt chiếm một vai trò quan trọng cho sự phát triển. Như đã giới thiệu ở phần trên, bài toán xe buýt là kiểu điều phối tĩnh. Phần mềm CityGuide sử dụng công nghệ GIS để cung cấp cho người sử dụng (hay người điều phối) một bản đồ số, người sử dụng sẽ có các thao tác rất trực quan trên giao diện đồ họa của bản đồ số này. Trong khuôn khổ đề tài này, tác giả cho phép người sử dụng thiết lập các trạm xe buýt cho từng tuyến đường đã được hoạch định trước. Chỉ bằng vài thao tác nhấn chuột, người sử dụng sẽ thấy được toàn bộ các trạm cho một tuyến xe buýt trên bản đồ. Theo ghi nhận của tác giả thì ở thành phố Hồ Chí Minh, các tuyến xe buýt được chia thành ba loại là: tuyến vòng, tuyến trung chuyển và tuyến đầu cuối. Tuyến vòng là tuyến có điểm xuất phát và điểm đến trùng nhau. Đây chính là một chu trình. Việc tìm kiếm lộ trình cho một tuyến vòng chính là giải quyết bài toán tìm chu trình. Tuyến trung chuyển là tuyến trung gian để vận chuyển hành khách giữa hai tuyến đường. Do đó, từ điểm xuất phát đến điểm dừng(hai điểm này không trùng nhau) yêu cầu phải vận chuyển với lộ trình có thời gian ngắn nhất và không dừng ở bất kỳ trạm trung gian nào. Đây là bài toán tìm đường đi ngắn nhất. Tuyến đầu cuối là tuyến vận chuyển hành khách từ điểm xuất phát, qua các trạm trung gian để đến điểm cuối. Đối với tuyến này thì các trạm trung gian hoàn toàn là do các chuyên gia giao thông nghiên cứu và sắp đặt. Đó có thể là một lộ trình bao quát rộng hoặc có thể là một lộ trình ngắn nhất. Trong khuôn khổ đề tài này, cụ thể là phần mềm ứng dụng CityGuide, các tác giả xem đây là một bài toán tìm đường đi ngắn nhất qua tất cả các trạm, để về đến điểm cuối. Ý tưởng tổ chức Tổ chức với giao diện đồ họa cho phép người sử dụng dùng chuột để thiết lập các trạm đầu, cuối, cũng như các trạm trung gian của tuyến xe buýt trên bản đồ số(sử dụng công nghệ nền là GIS). Như đã giới thiệu ở phần trước, bản đồ số được hình thành từ vô số các node và các edge. Do đó, nếu cũng sử dụng các thông tin này để lưu các trạm của tuyến thì sẽ làm cho việc quản lý ở mức cơ sở dữ liệu trở nên khó khăn, thậm chí có thể làm biến dạng cấu trúc và hình dạng của bản đồ số. Vấn đề đặt ra là làm sao lưu được các node đại diện cho các trạm mà cũng có tính chất gần như các node tạo nên bản đồ mà không phá hủy bản đồ. Giải pháp là xem các node đại diện đó là các node giả, được tổ chức dữ liệu riêng phù hợp với bản chất của nó. Vấn đề phát sinh tiếp theo là sử dụng cấu trúc dữ liệu nào để lưu trữ và truy xuất các node này tối ưu nhất. Câu trả lời là B+Tree(xem thêm ở phần phụ lục). Nhờ tất cả dữ liệu chỉ được lưu ở các node lá và các node lá này tạo thành một danh sách liên kết nên các thao tác lưu trữ và truy xuất trở nên rất linh hoạt và nhanh chóng. Do đó, việc quản lý các node giả(đồng thời cũng là các trạm trung gian) trở nên đơn giản hơn. Sau khi đã lưu được các node thì vấn đề còn lại chỉ là thực hiện bài toán như thế nào. Về mặt lý thuyết, muốn giải bài toán tìm chu trình hay tìm đường đi ngắn nhất trên đồ thị thì điều kiện đầu tiên là đồ thị đó phải là đồ thị liên thông. Còn trên thực tế mà cụ thể là trên bản đồ thì sự liên thông giữa các node chính là các edge, đại diện cho đường giao thông(do tính chất topology của hệ thống). Khi ngừơi sử dụng thiết lập các trạm trên bản đồ thì hệ thống sẽ lưu các trạm đó như các node giả trên bản đồ và thực hiện tính toán khoảng cách cũng như tìm kiếm sự liên thông giữa các node thông qua các edge. Từ đó, hệ thống sẽ tính toán và đưa ra được đường đi(hay chu trình)với các giải thuật phù hợp để đi qua các trạm với chi phí nhỏ nhất. Chẳng hạn như bài toán tìm chu trình áp dụng giải thuật GA(Genetic Algorithm), bài toán tìm đường đi ngắn nhất dùng giải thuật A* hay Dijkstra. Ngoài ra, bài toán xe buýt còn có khả năng để điều phối động trong trường hợp có chướng ngại vật bất ngờ trên đường giao thông chẳng hạn như khi đường bị tắc. Lúc này, người điều phối sẽ phải điều chỉnh lại lộ trình tức thời cho xe buýt. Hình 3.2 : Tổ chức tuyến xe buýt 3.1.3 Bài toán xe taxi Một dạng bài toán khác mà GIS có thể hỗ trợ là bài toán điều phối xe taxi. Việc điều phối xe taxi ở đây rất phụ thuộc vào cách quản lý và yếu tố con người. Ở khuôn khổ phần mềm này, hệ thống chỉ hỗ trợ việc xác định xe taxi gần khách hàng nhất. Đây là một bài toán động cả về nghĩa đen lẫn nghĩa bóng. Khi các xe taxi lưu thông trên đường, cũng dùng kỹ thuật node giả, ta xem các xe taxi là các node giả. Sự khác biệt ở đây chính là các node giả di động đây là nghĩa đen trong tính động của bài toán; nó thay đổi vị trí theo thời gian, lúc này dữ liệu về toạ độ, khoảng cách của các node giả được cập nhật liên tục. Nếu có yêu cầu từ khách hàng thì người điều phối phải lập tức xác định được vị trí của các xe taxi chưa có khách trên bản đồ , có nghĩa vào thời điểm có yêu cầu từ khách thì các xe taxi được xem là đang đứng yên tức thời. Từ các vị trí tức thời này hệ thống sẽ xác định xe taxi nào gần khách hàng nhất, tức là đường đi ngắn nhất từ các xe taxi đến nơi yêu cầu Ý tưởng tổ chức Đối với các node giả ta sử dụng cấu trúc B+Tree để lưu. Một B+Tree sẽ lưu tất cả các xe taxi, trong đó có một biến để theo dõi trạng thái của xe taxi. Nếu xe nào có trạng thái là 1 tức là đang có khách, và xe nào có trạng thái là 0 tức là xe hiện không có khách. Trong quá trình hoạt động nếu xe có sự thay đổi trạng thái từ có khách sang xe trống thì một node sẽ di chuyển từ trạng thái 1 sang trạng thái 0. Ngoài ra để đáp ứng tính động của hệ thống , mỗi khi xe taxi di chuyển thì vị trí tọa độ sẽ được cập nhập lại vào các node đại diện cho xe đó trong B+Tree. Cứ sau khoảng thời gian t nào đó hệ thống sẽ cập nhật lại vị trí tương đối của các xe trên bản đồ. Để làm được điều này, các hãng taxi cần trang bị một hệ thống phù hợp, trong khuôn khổ đề tài này, các tác giả không đề cập đến các trang thiết bị đó là những gì, hoạt động ra sao,… mà chỉ nêu ra phương án giải quyết, hỗ trợ việc tính khoảng cách của các xe taxi đối với khách hàng và hiển thị trên bản đồ. Hình 3.3 : Tổ chức điều phối xe Taxi Hai bài toán trên tiêu biểu cho việc điều phối giao thông trong thành phố, ngoài ra với một mô hình thích hợp cùng với sự hỗ trợ của GIS ta còn có thể giải quyết các bài toán thuộc vấn đề giao thông khác như : bài toán xe cứu hỏa , xe cứu thương,… Nói chung, tất cả các bài toán giao thông trên bản đồ điều là các bài toán trên đồ thị, mà mấu chốt của vấn đề chính là sự liên thông của đồ thị, nếu chúng ta giải quyết được hai bài toán tiêu biểu trên thì tất cả các bài toán trên đồ thị liên thông đều có thể giải quyết tốt trên nền GIS. Đây chính là phương pháp tìm đường đi trên bản đồ số(Sẽ được giới thiệu ở chương sau). Do đó, việc tổ chức được dữ liệu một cách hợp lý, và áp dụng chúng vào các giải thuật phù hợp trên đồ thị là khâu tư duy quan trọng nhất. 3.2 vấn đề tìm đường trên bản đồ số 3.2.1 Giới thiệu Trong một số ứng dụng có phát sinh vấn đề xác định đường đi tối ưu. Đó có thể là bất cứ loại nào từ tìm đường đi ngắn nhất cho đến xác định đường đi an toàn nhất cho robot du hành trên bề mặt sao hỏa. Trong khuôn khổ đề tài này, tác giả chỉ giới hạn phạm vi trong việc tìm đường đi trong không gian Euclid hai chiều. Cụ thể hơn , tác giả chỉ chú trọng đến việc tìm đường đi tối ưu cho các phương tiện giao thông di chuyển trên bản đồ. 3.2.1.1 Bản đồ số Những thông tin để vẽ bản đồ truyền thống được thể hiện trong một định dạng có thể cho máy tính truy cập được đưa dến những thử thách củng như những cơ hội mới. Một số lượng lớn thông tin thường xuyên được hiển thị thì đòi hỏi những kỹ thuật lưu trữ hiệu quả, trong khi việc trình diễn thì đòi hỏi các phương pháp chỉ số và lấy thông tin nhanh. Do đó cách lưu trữ chính yếu là CSDL. Trong vấn đề trình bày ở chương này , tác giả không đi vào giải quyết như thế nào. Xem thông tin chi tiết về vấn đề định dạng lưu trữ với CSDL ở chương giới thiệu về vpf. Việc kết hợp nhiều kiểu dữ liệu khác nhau thể hiện nhiều cơ hội mới cho việc chú tâm vào dữ liệu theo những cách không thể nhận biết được với các kỹ thuật truyền thông . Máy tính hỗ trợ về phân tích,xử lý, đánh giá và hiển thị các dữ liệu về địa lý đại diện cho nhiều lĩnh vực nghiên cứu chẳng hạn như: xử lý ảnh và hiển thị, trí tuệ nhân tạo, theo dõi môi trường, việc sử dụng đất, thiết kế CSDL v..v… Đề tài này là một ví dụ về những gì có thể làm được với những hỗ trợ của máy tính và một phần dữ liệu bản đồ số. 3.2.1.2 Dữ liệu quét Dữ liệu quét là một lưới hai chiều gồm các giá trị số đại diện cho một vài đại lượng có thể đo được, trong đó bề mặt dữ liệu không gian được chiếu trên một mặt phẳng lưới. Gái trị tại mỗi điểm lưới riêng biệt, được gọi là pixel, được dịch thành giá trị trung bình của vùng diện tích được chiếu trên mỗi điểm chiếu. Các công việc biên dịch khác có thể phụ thuộc vào nguồn dữ liệu(cảm biến, sự đồng bộ hoá hay bất cứ cái gì). Điều này cho phép dữ liệu địa lý (các bản đồ) luôn luôn được thể hiện như bản đồ truyền thống. 3.2.1.3 Dữ liệu hình học Dữ liệu hình học, còn được gọi là dữ liệu vector , bao gồm những danh sách của những điểm rời rạc và những giá trị kết hợp để phiên dịch thành hình dạng các đường thẳng , các đường cong hoặc những đối tượng hình học hữu dụng khác. 3.3 Sơ lược các phương pháp tìm đường Trong nhiều năm , đã co một dố cách tiếp cận khác nhau cho vấn đề tìm kiếm đường đi với những quy luật khác nhau phụ thuộc vào sự phát sinh tự nhiên các vấn đề. Sau đây là những giới thiệu sơ lược về những cách tiếp cận thông thường nhất . 3.3.1 Phương pháp giao đoạn thẳng Đây là phương pháp thường gặp cho các vấn đề khi dữ liệu bao gồm các đối tượng hình học, nghĩa là các chướng ngại vậthoàn toàn không thể vượt qua dược. Trong trường hợp này, đường đi ngắn nhất theo khoảng cách Euclid chính là đường đi ngắn nhất. Ý tưởng là: đầu tiên xây dựng một bao lồi cho tấc cả các đối tượng . Góc của những đa giác lồi định nghĩa thành một tập các đỉnh. Nối tất cả các đỉnh với cạnh . Sau đó làm các động tác lọc lại các cạnh này và cuối cùng tìm được đường đi ngắn nhất giữa hai điểm đầu và cuối theo các cạnh sử dụng giải thuật trên đồ thị chuẩn. Vấn đề chính của phương pháp này là bộ lọc hoạt động như thế nào. Mục đích của bộ lọc là loại bỏ bớt những đoạn thẳng không có khả năng thuộc vào đường đi ngắn nhất và do đó, giảm được đáng kể đường đi phải xét. 3.3.2 Phương pháp đồ thị có trọng số Mặc dù nó chia sẽ bản chất của việc tìm kiếm trên đồ thị cuối cùng với phương pháp giao đoạn thẳng, nhưng phương pháp này hoàn toàn khác, nếu như không nói là ngược lại, về cách tiếp cận để xây dựng đổ thị tìm kiếm. Ý tưởng cơ bản là chia không gian thành những vùng rời rạc, gọi là cell, và hạn chế sự di chuyển từ một cell cụ thể đến cell lân cận . Một cell “láng giềng” là cell chỉ có thể đến trực tiếp từ một cell cụ thể. Một đồ thị có hướng được xây dựng bằng cách xem những cell như là các đỉnh của đồ thị và có thể di chuyển sang cell lân cận trên các cạnh giữa đỉnh. Một hàm lượng giá được định nghĩa bằng việc gán trọng số cho mỗi cạnh theo các câu hỏi (như thời gian, độ dài, hay bất kỳ chức năng nào phù hợp với vấn đề). Việc phân chia không gian, định nghĩa vùng lân cận và hàm lượng giá cạnh, tất cả có thể khác nhau giữa các phương pháp khác nhau. Ngoài ra, còn một số phương pháp khác chẳng hạn như dùng hàm có hai biến để theo dõi sự phát triển của những đường cong có khoảng cách bằng nhau trên một mặt và từ đó đưa ra sơ đồ để tìm kiếm nhiều đường đi ngắn nhất trên nhiều mặt. Hoặc là định nghĩa một vài loại “trọng số mặt” và đi theo hướng có dốc. 3.4 phương pháp tìm kiếm Bây giờ, vấn đề chính là tìm kiếm đường đi có trọng số nhỏ nhất trong một đồ thị có hướng và có trọng số . Đôi khi nó còn được gọi là vấn đề đường đi ngắn nhất thay vì trọng số nhỏ nhất. 3.4.1 Phương pháp vét cạn Cách tiếp cận dễ dàng nhất là vét cạn, liệt kê tất cả các đường đi có thể và lựa chọn đường đi có trọng số nhỏ nhất. Bất kỳ phương pháp nào được sử dụng để xây dựng những đường đi như vậy đều có thể chứng minh được bằng cây quyết định. Bắt đầu bằng việc theo vết một cây quyết định xuống đến lá trong cây quyết định để phát sinh đường đi đầu tiên. Sau đó quay lui về điểm quyết định đầu tiên ở mức cao trên cây mà chưa được xem xét tất cả các quyết định có khả năng và tiếp tục đi xuống theo một nhánh mới để tạo đường đi mới. Cứ tiếp tục như thế thì cuối cùng cây được duyệt hết. Nói cách khác, bắt đầu ở đỉnh xuất phát, “quyết định” trên một trong các cạnh dẫn đến một đỉnh khác (mà chưa có trong đường đi), duyệt và quay lại cho đến khi đạt đến điểm đích. 3.4.2 Phương pháp lập trình tuyến tính Lập trình tuyến tính thường được sử dụng để giải quyết luồng trong mạng và vấn đề cấp phát tài nguyên. Có thể xem xét vấn đề đồ thị như một vấn đề lập trình tuyến tính , chẳng hạn như đưa về vấn đề luồng có trong số thấp hoặc một một vấn đề chia phần tương đương. Bên cạnh đó , còn nhiều phương pháp khác như Relaxation, Simulated anncoling, …. 3.5 GIẢI THUẬT 3.5.1 Giải thuật Dijkstra Mô tả: Tập dữ liệu vào gồm : một đồ thị G=(V, E) với V là tập các đỉnh và E là tập các cạnh của G điểm bắt đầu của đường cần tìm sỴV Trọng số của các cạnh phải là số không âm w(u,v) ³ 0 , "(u,v)ỴE. Giải thuật Dijkstra chia tập V là làm hai tập con R và Q, sao cho V = R È Q. Tập R chứa kết quả tìm đường của giải thuật, như vậy Q=V– R, khi một đỉnh được đưa từ Q sang R ta nói đỉnh đó bị loại (retired), người ta thường gọi Q là tập mở (Open) còn R là tập đóng (Closed). Với mỗi đỉnh ta sẽ lưu trữ khoảng cách ngắn nhất đã tính g[v], chúng ta không cần tìm chính xác giá trị nhỏ nhất vì tập các đỉnh sẽ làm điều này. Chúng ta cũng cần lưu trữ cạnh trước của mỗi đỉnh ed[v], đó là cạnh được thiết lập bởi đỉnh trước đó tới cạnh đang xét, thông tin này được sử dụng để quay lui(back tracking) khi đã đến đích. Giải thuật bằng mã giả : Dijkstra(G,w,s) R = Q = { } for all vỴV do g[v] = ¥ Q.Insert(v) while (Q ¹ { }) do u = Q.ExtractMin() R = R È {u} for vỴNeighbors{u} do if (g[v] > g[u] + w(u,v)) then Q.DecreaseKey(v, g[u] + w(u,v)) ed[v] = (u,v) Tập Q đựơc tổ chức dưới dạng là cấu trúc dữ liệu hàng đợi ưu tiên (priority queue: PQ) trong đó có hai thao tác cơ bản là: - Q .Insert(u) – chèn một phần tử vào Queue, - Q .ExtractMin() – là lấy phần tử vỴQ với g[v] là nhỏ nhất, - Q .DecreaseKey(v, a) – giảm g[v] xuống a, rồi cập nhật lại queue. Giải thuật Dijkstra xét lần lược các đỉnh trong trong tập Open bằng cách ước lượng khoảng cách ngắn nhất bằng trọng số các cạnh. Bởi vì các trọng số trên các cạch là luôn dương do đó chúng ta không thể mở rộng việc tìm kiếm sang các đỉnh khác do đó v sẽ được đưa vào tập Closed và loại nó trong tập Open.Tiếp đến chúng ta kiển tra xem có thể mở rộn dường đi ngắn nhất san các đỉnh kế cận của điển hiện hành được không bằng cách ước lượng chiều dài, nếu được ta cập nhật lại các cạnh tới tương ứng. Trong thực tế, người ta lại chia nhỏ Q thành U và PQ, U là tập chứa tất cả các đỉnh của đồ thị ngoại trừ s , còn PQ đóng vai trò như Q ở trên. Các cạnh được đưa từ U sang PQ khi được thăm lần đầu tiên, bằng cách đặt thêm cờ để nhận biết xem đỉnh đó đã được thăm chưa (đã có trong U) và như vậy ta không đưa nó vào U nữa. Hình 3