VNOSGIS-Open source GIS for Vietnamese

Wednesday, June 27, 2012

Sử dụng PAL trong các phần mềm GIS mã nguồn mở

Quách Đồng Thắng - Trung tâm Ứng dụng GIS TP.HCM

Tóm tắt

Gán nhãn tự động (Automatic Label Placement) là một trong những vấn đề khá quan trọng trong các ứng dụng GIS. Đối với các phần mềm thương mại, việc gán nhãn được giải quyết khá tốt (chưa kể việc sử dụng các công cụ hỗ trợ mạnh mẽ như Maplex cho ArcGIS, SmartLabel/EverName cho MapInfo). Trong khi đó, chức năng gán nhãn trong các phần mềm GIS mã nguồn mở còn nhiều hạn chế như bị trùng lắp, dễ gây nhầm lẫn, gây khó khăn cho người sử dụng. PAL (Automatic Label Placement) là một thư viện mã nguồn mở được phát triển bởi University of Applied Sciences, Western Switzerland (HES-SO). PAL được thiết kế cho việc gán nhãn động, đa lớp với thời gian chấp nhận được và chất lượng gán nhãn cao. Bài viết trình bày khả năng áp dụng gói thư viện PAL để nâng cao hiệu quả và chất lượng gán nhãn trong các phần mềm GIS mã nguồn mở thông dụng là gvSIG, Quantum GIS và MapWindow.

Từ khoá: gán nhãn tự động, PAL, JPAL,POPMUSIC, phần mềm GIS mã nguồn mở.

Abstract

Automatic Label Placement is an important problem in GIS applications. For commercial GIS software, this problem has been solved fairly well (Maplex for ArcGIS, SmartLabel/EverName for MapInfo). Meanwhile, Automatic Label Placement in open source GIS softwares is still a considerable problem. PAL is an open source library package developed by University of Applied Sciences, Western Switzerland (HES-SO). PAL is designed for dynamic, multi-layers labeling with acceptable execution time and high quality. This paper presents the ability of using PAL to enhance the effect and quality of automatic labeling placement in some popular open source GIS softwares such as gvSIG, QuantumGIS and MapWindow.

Key words: Automatic Label Placement, PAL, JPAL POPMUSIC, open source GIS

1. GIỚI THIỆU

Gán nhãn là một trong những vấn đề khá quan trọng trong ngành bản đồ học. Trước khi có bản đồ số, các quy tắc gán nhãn trên bản đồ nói chung đã được nhiều nhà nghiên cứu đề xuất nhằm đảm bảo tính dễ đọc, dễ nhận biết, ít gây nhầm lẫn và tính thẩm mỹ trong công tác thành lập và xuất bản bản đồ. Đối với bản đồ số, việc gán nhãn là một quá trình động và phức tạp vì nó phụ thuộc vào nhiều yếu tố như khung nhìn bản đồ, số lớp/ số đối tượng cần hiển thị nhãn, độ lớn trường dữ liệu mà nhãn thể hiện,…

Eduard Imhof (1895-1986), nhà bản đồ học nổi tiếng người Thuỵ Sĩ, trong quyển “Positioning Names on Maps” (1962/1975) đã nêu ra một số quy tắc căn bản trong việc gán nhãn cho bản đồ:

- Dễ đọc: các nhãn phải được đặt sao cho dễ đọc, dễ nhận biết và dễ phân biệt.

- Không nhập nhằng: dễ dàng nhận biết chính xác đối tượng mà nhãn thể hiện.

- Tránh chồng lắp: so với các nhãn khác và với các đối tượng đồ hoạ khác.

Ông đã nêu ra một số khuyến cáo khi gán nhãn cho các đối tượng dạng điểm, đường và vùng trong bản đồ:

Đối tượng dạng điểm

- Vị trí nhãn ở về phía trên bên phải thì ưa nhìn hơn so với phía dưới và bên trái.

- Vị trí nhãn càng gần điểm mà nó thể hiện càng tốt.

- Nhãn được bố trí nằm ngang.

Đối tượng dạng đường

- Nhãn càng gần đường mà nó thể hiện càng tốt.

- Nhãn phải bố trí theo hình dạng của đường.

- Nhãn càng có ít vị trí cong càng tốt.

- Đối với các đường dài, nhãn phải được lặp lại.

- Đối với các đường thẳng đứng: Nếu nhãn nằm về phía bên trái thì đọc từ dưới lên, ngược lại bên phải thì đọc từ trên xuống

Đối tượng dạng vùng

- Nhãn nên nằm bên trong và trải ra đủ lớn trên diện tích của vùng.

- Các đối tượng vùng nhỏ, các quy tắc gán nhãn tương tự quy tắc gán nhãn cho điểm.

Eduard Imhof đã liệt kê ra các trường hợp tốt/ xấu khi gán nhãn một cách trực quan cho các đối tượng điểm, đường và vùng. Các quy tắc gán nhãn của ông mặc dù thiên về kỹ thuật xuất bản cho bản đồ giấy nhưng đồng thời là một tham khảo rất có giá trị trong việc gán nhãn tự động cho bản đồ số. Bằng chứng là các quy tắc căn bản và các khuyến cáo của ông vẫn được tuân thủ khá tốt trong các công cụ gán nhãn tự động và được xem như các quy tắc tham khảo cho việc đánh giá chất lượng và tính thẩm mỹ của gán nhãn tự động trên bản đồ số.

2. GÓI THƯ VIỆN PAL

2.1 Giới thiệu chung

Đối với việc xây dựng một công cụ gán nhãn cho bản đồ số, có 3 vấn đề cần quan tâm:

- Tuân thủ các quy tắc căn bản trong việc gán nhãn bản đồ nói chung, đồng thời đáp ứng khả năng gán nhãn động trong bản đồ số.

- Nghiên cứu lựa chọn giải thuật gán nhãn sao cho thời gian thực thi ở mức chấp nhận được.

- Khả năng tuỳ biến của người dùng: trong việc lựa chọn vị trí hiển thị, xác định độ ưu tiên của lớp dữ liệu,…

PAL được phát triển bởi University of Applied Sciences, Western Switzerland (HES-SO), với sự hợp tác của 3 nhóm MIS-TIC, IICT-SYSIN và G2C:

- MIS-TIC: giải thuật tối ưu.

- IICT-SYSIN: hiện thực giải thuật thành gói thư viện PAL.

- G2C: chịu trách nhiệm về các quy tắc gán nhãn (dễ nhìn, không gây nhầm lẫn, tính thẩm mỹ,...).

2.2 Đặc điểm và chức năng

PAL được thiết kế cho gán nhãn đa lớp đồng thời, hỗ trợ các lớp dữ liệu như điểm, đường và vùng. Các yếu tố ảnh hưởng đến việc gán nhãn có thể tuỳ biến trong PAL:

- Giới hạn tỉ lệ hiển thị nhãn.

- Độ ưu tiên của lớp dữ liệu gán nhãn.

- Đối tượng được hiển thị nhãn có được xem là chướng ngại vật khi tính toán vị trí hiển thị nhãn hay không?

- Lớp dữ liệu có đang được hiển thị hay không?

- Lớp dữ liệu có được hiển thị nhãn hay không?

- Phương hướng hiển thị ưa thích (tự do, nằm ngang, nằm trên đường, ...).

2.3 Cách hoạt động của PAL

Quá trình gán nhãn gồm 2 giai đoạn chính: Xác định vị trí ứng viên và tối ưu hoá.

2.3.1 Xác định ứng viên

Xác định vị trí ứng viên trả về một tập các vị trí ứng viên cho mỗi đối tượng cần gán nhãn và một đồ thị thể hiện sự xung đột vị trí (conflict graph) giữa các ứng viên.

Xác định vị trí ứng viên gồm 2 bước chính: tạo ứng viên và lọc ứng viên. Tạo ứng viên tính toán danh sánh các đối tượng cần gán nhãn, danh sách các chướng ngại vật, tỉ lệ và độ lớn khung nhìn bản đồ và tính toán tương ứng với từng đối tượng gán nhãn là một số các vị trí ứng viên được tạo ra kèm với nó là một trọng số. Giai đoạn lọc ứng viên sẽ lọc ra một số các vị trí có trọng số thấp và ít trùng lắp với các đối tượng khác.

Đối với các đối tượng điểm: Có p vị trí ứng viên được tạo ra (p là tham số có thể = 4, hoặc 8, hoặc nhiều hơn tuỳ vào mô hình ứng viên). Vị trí tốt nhất là phía trên bên phải, vị trí tệ nhất là phía trái-bên dưới.

Đối tượng đường:

- Chọn các điểm a và b trên đường, ứng với mỗi đoạn

xác định được độ dài của nhãn.

- P_line: ứng viên được đặt ngay trên

- P_line_around: đặt 2 ứng viên cách một khoảng distlabel so với

- Tính toán tỉ lệ

xác định chất lượng ứng viên.

Đối tượng vùng: 4 cách chọn vị trí ứng viên

- P_POINT: Gán nhãn theo tâm của vùng.

- P_LINE: Gán nhãn theo vành đai của vùng.

- P_FREE: đặt nhãn nằm trong vùng, cho phép quay nhãn

- P_HORIZ: đặt nhãn nằm trong vùng, theo phương nằm ngang

Đầu tiên sẽ kiếm tra tính lồi của vùng. Đối với các đối tượng vùng lõm, vùng sẽ được chia thành các đa giác lồi, sau đó xác định các vị trí ứng viên cho các hình chữ nhật bao nhỏ nhất của từng đa giác lồi này.

2.3.2 Tối ưu hoá

Quá trình tối ưu hoá nhằm xác định vị trí cần hiển thị trong số các ứng viên (trên cơ sở tính toán chất lượng vị trí, độ ưu tiên của lớp dữ liệu, đồ thị xung đột vị trí,…) dựa trên các giải thuật sau:

- Giải thuật FALP (Fast Point-Feature Label Placement Algorithm).

- POPMUSIC (Partial Optimization Metaheuristic Under Special Intensification Conditions):

thuật toán meta-heuristic tối ưa hoá từng phần.

- 4 phương pháp tìm kiếm:

Pt: POPMUSIC + Tabu Search.
Ptc: POPMUSIC + Tabu Search + Chain Transformation.
Pc: POPMUSIC + tìm kiếm đệ quy + Chain Transformation.
c: tìm kiếm đệ quy + Chain Transformation.

3. SỬ DỤNG PAL TRONG MỘT SỐ PHẦN MỀM GIS MÃ NGUỒN MỞ

Đối với các phần mềm GIS mã nguồn mở như Quantum GIS, MapWindow và gvSIG, chức năng gán nhãn tự động còn một số hạn chế như sau:

- Hiện tượng “đám mây” khi zoom bản đồ ở tỉ lệ nhỏ.

- Hướng hiển thị của nhãn không được tính toán theo dáng điệu của đối tượng đường.

- Đối với các đối tượng dạng vùng là đa giác lõm, nhãn có thể nằm ngoài đa giác (do vị trí gán nhãn được chọn là tâm của đa giác), dễ gây nhầm lẫn cho người sử dụng.

- Khi di chuyển khung nhìn bản đồ dọc theo các đối tượng đường có kích thước dài hoặc các đối tượng vùng có kích thước lớn, các nhãn không được tính toán và vẽ lại vị trí trong khung nhìn hiện tại, gây khó khăn cho việc nhận biết nhãn.

- Trùng lắp vị trí khi có nhiều lớp dữ liệu được gán nhãn đồng thời trên bản đồ.

3.1 Sử dụng PAL trong Quantum GIS

Gói thư viện PAL được tích hợp vào QuantumGIS (http://www.qgis.org/) từ phiên bản 1.4, phục vụ cho việc gán nhãn tự động và cả việc thể hiện biểu đồ trên các đối tượng không gian. Hiện tại người dùng có thể sử dụng chức năng gán nhãn chuẩn của Quantum GIS hoặc sử dụng công cụ PAL. Hình sau thể hiện ưu điểm khi sử dụng PAL để gán nhãn trong Quantum GIS

Người dùng có thể tuỳ biến các tuỳ chọn gán nhãn như vị trí hiển thị ưa nhìn, độ ưu tiên của lớp đối tượng, khoảng tỉ lệ hiển thị nhãn, lựa chọn sử dụng phương pháp tìm kiếm,...

3.2 Sử dụng PAL trong MapWindow

Hiện tại chức năng gán nhãn trong MapWindow (http://www.mapwindow.org/) vẫn còn nhiểu hạn chế hạn chế như đã trình bày. Tuy nhiên, PAL đang được nhóm phát triển MapWindow xem xét lựa chọn sử dụng để nâng cao chất lượng gán nhãn trong các phiên bản sau của MapWindow (http://www.mapwindow.org/phorum/read.php?5,12798).

3.3 Sử dụng PAL gvSIG

gvSIG (http://www.gvsig.org/web/) được phát triển trên nền java, trong khi PAL là gói thư viện được viết bằng C++. Đối với các ứng dụng GIS nền java nói chung và gvSIG nói riêng, JNI (Java Native Interface) được dùng để gọi các dll của gói thư viện PAL. Do đó PAL trong các ứng dụng GIS nền java thường được gọi là JPAL (JPAL = JNI + PAL).

PAL được tích hợp trong gvSIG thông qua plugin extJPAL. Phần sau trình bày cách cài đặt, cấu hình extJPAL trong gvSIG

3.3.1 Cài đặt, cấu hình gvSIG chạy trong JRE 1.6.

extJPAL sử dụng một số các đối tượng đồ hoạ được hỗ trợ từ java 1.6. Do đó, để sử dụng extJPAL, gvSIG phải được cấu hình chạy trong môi trường JRE 1.6.

Đối với trường hợp cài dặt mới gvSIG, trình cài đặt mặc định dùng JRE 1.5. Do đó, trước khi cài đặt gvSIG chạy trên JRE 1.6, cần cài đặt theo trình tự như sau:

- JRE 1.6.x

- JAI 1.1.x for JRE

- JAI Image I/O 1.x for JRE

- gvSIG 1.1.x

Lưu ý:

- Khi cài đặt gvSIG, chọn “No” checking application requirement, sau đó chọn đường dẫn đến JRE vừa cài đặt.

- Trình cài đặt gvSIG sẽ copy một số DLL vào thư mục Java, trong đó có msvcr71.dll bị lỗi khi chép đè. Do đó cần đổi tên hoặc xoá msvcr71.dll trước khi cài đặt gvSIG.

Đối với trường hợp nâng cấp gvSIG: Nếu đã có phiên bản gvSIG chạy trên Java 1.5, chỉnh sửa jre_home trong file gvSIG.ini thành:

jre_home = C:\Program Files\Java\jre6

3.3.2 Cài đặt extJPAL trong gvSIG

- Download extJPAL-Window, giải nén trong thư mục cài đặt gvSIG, ví dụ: C:\Program Files\gvSIG_1.1_PAL.

- Chạy file deploy.bat, chọn “D”. Deploy.bat thực hiện các công việc sau:

copy jpal.dll vào gvSIG_1.1\lib.
copy libgeos-3-0-0.dll vào gvSIG_1.1\lib
copy thư mục ch.heigvd.jpal vào thư mục extensions của gvSIG.

- Sửa tên gvSIG_1.1_PAL\bin\gvSIG\extensiones\com.iver.cit.gvsig\lib\fmap.jar thành gvSIG_1.1_PAL\bin\gvSIG\extensiones\com.iver.cit.gvsig\lib\fmap.jar.old

- Copy ch.heigvd.jpal\lib\fmap.jar vào gvSIG_1.1_PAL \bin\gvSIG\extensiones\com.iver.cit.gvsig\lib\fmap.jar

- Copy gvSIG.bat trong gvSIG_1.1_PAL\ deployWindow vào gvSIG_1.1_PAL\bin\

- Sử dung gvSIG.bat để khởi động gvSIG (thay vì gvSIG.exe)

3. KẾT LUẬN

PAL là gói thư viện mã nguồn mở cho việc nâng cao hiệu quả và chất lượng gán nhãn tự động trong các ứng dụng GIS. Việc sử dụng PAL trong Quantum GIS và extJPAL trong gvSIG cho thấy khả năng tích hợp rất tốt của PAL vào các phần mềm GIS mã nguồn mở. Mặc dù tốc độ thực thi và khả năng tuỳ biến không thể so sánh với Maplex của ArcGIS, song PAL là một lựa chọn rất tốt cho cộng đồng GIS mã nguồn mở.

4. TÀI LIỆU THAM KHẢO

[1]. Olivier Ertz, Maxence Laurent, Daniel Rappo, Abson Sae-Tang1, Eric Taillard, 2008. PAL - A cartographic labelling library, Foos4G2008.

[2]. Eduard Imhof, 1975. Positioning Names on Maps. The American Cartographer, Vol.2, No.2, pp. 128 -144.

[3]. Steven Woudenberg, 2007. Label Placement.

[4]. http://i11www.iti.uni-karlsruhe.de/map-labeling/bibliography/.

[5] http://www.mapwindow.org/.

[6]. http://www.gvsig.org/web.

[7]. http://www.qgis.org/.

[8]. http://geosysin.iict.ch/trac/wiki/extJPAL/installationGuide.

Thursday, May 17, 2012

Sử dụng pgRouting phân tích mạng trong ứng dụng GIS

Quách Đồng Thắng

Trung tâm Ứng dụng GIS TP.HCM

TÓM TẮT: Phân tích mạng là lớp bài toán có nhiều ứng dụng trong thực tế. Phần lớn các phần mềm GIS thương mại hay mã nguồn mở đều hỗ trợ phân tích mạng như tìm đường đi ngắn nhất, bài toán người giao hàng,…Tuy nhiên, việc sử dụng các chức năng được đóng gói sẵn theo phần mềm cũng bộc lộ một số nhược điểm. Nhà phát triển ứng dụng hoàn toàn phụ thuộc vào cách vận hành của các gói này, hoặc nếu các chức năng được cung cấp dưới dạng mã nguồn mở thì cũng mất khá nhiều thời gian trong việc tìm hiểu, can thiệp mã nguồn để chỉnh sửa theo nhu cầu đặc thù của từng ứng dụng. Nếu không muốn phụ thuộc vào các nhà cung cấp thì nhà phát triển ứng dụng phải tự xây dựng các thuật toán cho riêng mình, điều này càng chiếm nhiều thời gian hơn đối với một ứng dụng GIS. Có một giải pháp dung hoà hai hướng này là cách tiếp cận phân tích mạng ở mức cơ sở dữ liệu (CSDL). Bài báo trình bày khả năng sử dụng gói PgRouting trong PostgreSQL/PostGIS để giải quyết một số bài toán phân tích mạng như tìm đường đi ngắn nhất, tính khoảng cách lái xe và bài toán người giao hàng.

Từ khóa: PgRouting, phân tích mạng, tìm đường đi ngắn nhất, bài toán người giao hàng, GIS.

1. GIỚI THIỆU

PgRouting (http://www.pgrouting.org/) cung cấp chức năng phân tích mạng ở mức CSDL sử dụng trong PostgreSQL/PostGIS. PgRouting lúc đầu mang tên pgDijkstra (được phát triển bởi Camptocamp) vì khởi đầu chỉ hỗ trợ chức năng tìm đường đi ngắn nhất bằng thuật toán Dijkstra. Sau đó PgRouting được mở rộng bởi Orkney, Nhật Bản và hiện đang được tiếp tục phát triển bởi Georepublic. PgRouting được phát hành với giấy phép mã nguồn mở GPLv2.

Các bài toán phân tích mạng có thể giải quyết với PgRouting:

Shortest Path Dijkstra: Tìm đường đi ngắn nhất bằng thuật toán Dijkstra.
Shortest Path A-Star: Tìm đường đi ngắn nhất cho tập dữ liệu lớn sử dụng heuristic.
Shortest Path Shooting-Star: Tìm đường đi ngắn nhất cho tập dữ liệu lớn sử dụng heuristic. Shooting-Star dựa trên các cạnh mạng (khác với Dijkstra và A-Star dựa trên các nút mạng) và hỗ trợ cho đường cấm quẹo.
Driving Distance calculation: Tính toán khoảng cách lái xe.
Traveling Salesman Problem (TSP): Bài toán người giao hàng.

Các thuận lợi khi giải quyết các bài toán phân tích mạng ở mức CSDL:

Dữ liệu mạng có thể được chỉnh sửa trực tiếp bằng SQL trong CSDL hoặc bởi nhiều phần mềm client khác nhau như gvSIG, Quantum GIS, uDig,… thông qua JDBC, ODBC.
Dữ liệu mạng nếu có thay đổi sẽ được cập nhật tức thì khi thực hiện các phép phân tích mạng mà không cần tính toán lại toàn mạng.
Trọng số các cạnh của mạng có thể được tính toán bằng SQL và giá trị có thể được tính toán dựa trên các trường dữ liệu hoặc các bảng khác trong CSDL.
Nhà phát triển ứng dụng có thể hiện thực các phép phân tích mạng ở mức CSDL mà không phụ thuộc giải pháp của nhà cung cấp phần mềm.
PgRouting áp dụng cho dữ liệu PostGIS (tuân thủ chuẩn OGC như Well Konwn Text – WKT, Well Known Binary - WKB), dễ dàng chuyển sang các định dạng khác.

Bài báo trình bày khả năng sử dụng gói PgRouting trong PostgreSQL/PostGIS để giải quyết một số phép phân tích mạng như bài toán tìm đường đi ngắn nhất (với các thuật toán Dijkstra, A-Star và Shooting-Star), tính khoảng cách lái xe (driving distance) và bài toán người giao hàng (traveling salesman problem).

2. THỬ NGHIỆM

2.1. Cài đặt PgRouting

PgRouting được cài đặt thử nghiệm với PotgreSQL 8.4 và PostGIS 1.5.

Sau khi download pgRouting tại http://www.pgrouting.org/download.html, chép các file trong thư mục Lib và Share/Contrib vào thư mục tương ứng cài đặt PostgreSQL. Thư mục Lib gồm 3 file dll: librouting.dll: tìm đường đi ngắn nhất, librouting_dd.dll: tính khoảng cách lái xe, librouting_tsp.dll: giải bài toán người giao hàng.

Đối với bài toán khoảng cách lái xe và bài toán người giao hàng không được tích hợp sẵn trong bản cài đặt mà cần download source code pgrouting, sau đó chép các file sql trong .../extra/driving_distance/sql và .../extra /tsp/sql vào Share/Contrib của PostgreSQL.

2.2. Chuẩn bị dữ liệu

Trong PgAdmin, tạo database có tên PgRouting với Template là template_postgis.

Sử dụng lớp giao thông line ở định dạng shapefile làm dữ liệu thử nghiệm. Dùng công cụ Shapefile to Postgis Importer (được cài đặt cùng với PostGIS 1.5) để load lớp giao thông vào trong CSDL PgRouting với tên table là routing.

Do đặc điểm của PgRouting, dữ liệu routing là lớp giao thông line đã được tiền xử lý để cắt các đường giao thông tại các giao điểm (có thể sử dụng công cụ Topology/ Planarize Lines trong ArcMap hoặc sử dụng các hàm PostGIS).

Thực thi các SQL file để định nghĩa các hàm hỗ trợ routing cho database PgRouting: routing_topology, routing_core_wrappers, routing_core, routing_tsp, routing_tsp_wrappers, routing_dd, routing_dd_wrappers (trong …/Share/Contrib).

Các thuật toán trong PgRouting thường gồm một core function và các wrapper functions. Wrapper functions thường thiết lập mặc định các tham số của core function để đơn giản khi sử dụng, và có thể bổ sung thêm các thông số như bounding box để giới hạn không gian tìm kiếm.

Tạo các cột source, target, và length cho table routing.

ALTER TABLE routing ADD COLUMN source integer;

ALTER TABLE routing ADD COLUMN target integer;

ALTER TABLE routing ADD COLUMN length double precision;

Tạo network topology cho table routing:

SELECT assign_vertex_id('routing', 0.001, 'the_geom', 'gid');

Kết quả là một đồ thị được tạo ra với các nút mạng được lưu trong bảng vertices_tmp, liên hệ giữa các cạnh với các nút mạng được định nghĩa trong source, target của table routing.

Tính toán trọng số của cạnh bằng chính độ dài thực tế của các cạnh.

UPDATE routing SET length = length(the_geom);

Tạo chỉ mục cho source, target và geometry column để tăng tốc độ tìm kiếm cho tập dữ liệu lớn.

CREATE INDEX source_idx ON routing(source);

CREATE INDEX target_idx ON routing(target);

CREATE INDEX geom_idx ON routing USING GIST(the_geom GIST_GEOMETRY_OPS);

2.3. Tìm đường đi ngắn nhất

Thử nghiệm các thuật toán tìm đường đi ngắn nhất mà pgRouting hỗ trợ bằng cách sử dụng trực tiếp các lệnh SQL trong PostgreSQL.

Dijkstra

Tìm đường đi ngắn nhất bằng thuật toán Dijkstra cần các thông số như source, target và trọng số length - chính là độ dài ứng với mỗi cạnh của mạng.

Tạo bảng shortest_path để chứa kết quả tìm đường đi ngắn nhất giữa 02 điểm bằng thuật toán dijkstra:

DROP TABLE IF EXISTS shortest_path;

CREATE TABLE shortest_path(gid int4) ;

SELECT AddGeometryColumn('shortest_path', 'the_geom', ' 32648', 'MULTILINESTRING', 2);

CREATE SEQUENCE shortest_path_gid_seq

INCREMENT 1

MINVALUE 1

MAXVALUE 9223372036854775807

START 1

CACHE 1;

ALTER TABLE shortest_path_gid_seq OWNER TO postgres;

ALTER TABLE shortest_path ALTER COLUMN gid SET DEFAULT nextval('shortest_path_gid_seq'::regclass);

Sử dụng core function shortest_path

shortest_path(sql text,

source_id integer,

target_id integer,

directed boolean,

has_reverse_cost boolean)

Source_id, target_id là các nút mạng; directed = true áp dụng cho đồ thị có hướng với reverse_cost là chi phí đi ngược lại từ target đến source. Giả sử reverse_cost được tính bằng chính độ dài thực tế của cạnh:

ALTER TABLE routing ADD COLUMN reverse_cost double precision;

UPDATE routing SET reverse_cost = length;

Áp dụng:

SELECT * FROM shortest_path('

SELECT gid as id,

source::integer,

target::integer,

length::double precision as cost

FROM routing',

52, 35, false, false);

Sử dụng wrapper function dijkstra_sp:

INSERT INTO shortest_path (the_geom) SELECT the_geom FROM dijkstra_sp('routing', 52, 35);

Có thể giới hạn không gian tìm kiếm trong một bounding box với wrapper function dijkstra_sp_delta, giúp tăng tốc độ tìm kiếm, đặc biệt đối với các tập dữ liệu lớn.

SELECT gid, AsText(the_geom) AS the_geom

FROM dijkstra_sp_delta('routing', 52, 35, 3000);

A-Star

A-Star bổ sung các thông tin địa lý vào source và target ứng với mỗi cạnh của mạng. Điều này cho phép ưu tiên tìm kiếm các cạnh gần với đích hơn.

ALTER TABLE routing ADD COLUMN x1 double precision;

ALTER TABLE routing ADD COLUMN y1 double precision;

ALTER TABLE routing ADD COLUMN x2 double precision;

ALTER TABLE routing ADD COLUMN y2 double precision;

UPDATE routing SET x1 = x(ST_startpoint(the_geom));

UPDATE routing SET y1 = y(ST_startpoint(the_geom));

UPDATE routing SET x2 = x(ST_endpoint(the_geom));

UPDATE routing SET y2 = y(ST_endpoint(the_geom));

Sử dụng core function:

shortest_path_astar(sql text,

source_id integer,

target_id integer,

directed boolean,

has_reverse_cost boolean)

Áp dụng:

SELECT * FROM shortest_path_astar('

SELECT gid as id,

source::integer,

target::integer,

length::double precision as cost,

x1, y1, x2, y2

FROM routing',

52, 35, false, false);

Sử dụng wrapper function với bounding box

SELECT gid, AsText(the_geom) AS the_geom

FROM astar_sp_delta('routing', 52,35, 3000);

Shooting-Star

Shooting-Star là thuật toán tìm kiếm cho các cạnh (edge based), khác với thuật toán tìm kiếm cho các nút (vertex based) như Dijkstra và A-Star.

Shooting-Star định nghĩa thêm 2 tham số:

ALTER TABLE routing ADD COLUMN to_cost double precision;

ALTER TABLE routing ADD COLUMN rule text;

Sử dụng core function:

shortest_path_shooting_star( sql text,

source_id integer,

target_id integer,

directed boolean,

has_reverse_cost boolean)

Trong đó source_id và target_id là các cạnh của mạng.

Áp dụng:

SELECT * FROM shortest_path_shooting_star('

SELECT gid as id,

source::integer,

target::integer,

length::double precision as cost,

x1, y1, x2, y2,

rule, to_cost

FROM routing’,

103, 35, false, false);

Sử dụng wrapper function với bounding box:

SELECT gid, AsText(the_geom) AS the_geom

FROM shootingstar_sp('routing', 103, 35, 3000, 'length', true, true);

Đối với đường một chiều:

Trong các hàm tìm kiếm Dijkstra, A-Star và Shooting-Star, tham số directed = true và has_reverse_cost = true áp dụng cho trường hợp đồ thị có hướng (đường một chiều). Cách định nghĩa đường một chiều trong PgRouting được thể hiện qua ví dụ sau:

Ví dụ: Tìm đường đi ngắn nhất không quan tâm đến yếu tố đường ngược chiều từ nút 93 đến nút 35 (directed = false và has_reverse_cost = false ).

SELECT * FROM shortest_path('

SELECT gid as id,

source::integer,

target::integer,

length::double precision as cost

FROM routing',

93, 35, false, false);

Kết quả:

Tìm đường đi ngắn nhất quan tâm đến yếu tố đường ngược chiều từ nút 93 đến nút 35 (directed = true và has_reverse_cost = true, với reverse_cost = length).

SELECT * FROM shortest_path('

SELECT gid as id,

source::integer,

target::integer,

length::double precision as cost,

reverse_cost::double precision as reverse_cost

FROM routing',

93, 35, true, true);

Kết quả tìm kiếm vẫn giống như trường hợp directed = false và has_reverse_cost = false. Đó là do reverse_cost = length: chi phí đi từ đỉnh source đến target và ngược lại là như nhau (hay nói cách khác đồ thị có hướng trong trường hợp này được xem như đồ thị vô hướng) .

Giải sử muốn cài đặt đường ngược chiều từ 93 đến 85, cần xem xét các bước tiếp theo:

Trước tiên khảo sát source, target của cạnh chứa đỉnh 93 và 85 (ở đây là cạnh 104):

select gid, source, target , length, reverse_cost from routing where gid = 104;

Kết quả:

Dễ thấy cạnh 104 có hướng từ 85 đến 93: đi từ nút 85 đến 93 có chi phí là length. Để cài đặt đường một chiều từ 93 đến 85, cần tăng reverse_cost cho cạnh 104

update routing set reverse_cost = 10000 where gid = 104;

Có thể hiểu là: để đi từ nút 93 đến 85 cần đánh đổi chi phí rất cao là 10000 (do đó cạnh 93_85 được xem như đường một chiều)

Lúc này thực hiện tìm kiếm với directed = true và has_reverse_cost = true, kết quả là lộ trình mới đã bỏ qua nút 85 do chi phí quá cao.

Đối với đường cấm quẹo:

Trong thực tế, có những đường cấm quẹo vào từ một số đường khác. Giải quyết vấn đề này bằng cách sử dụng Shooting–Star.

Shooting – Star định nghĩa thêm 2 tham số là rule và to_cost. Rule của một cạnh liệt kê danh sách các cạnh mà nếu đi từ đó phải mất chi phí là to_cost (thường được gán giá trị cao đối với đường cấm quẹo từ đường khác vào).

Kết quả của hàm tìm kiếm shooting-star từ cạnh 103 đến cạnh 35:

SELECT * FROM shortest_path_shooting_star('

SELECT gid as id,

source::integer,

target::integer,

length::double precision as cost,

x1, y1, x2, y2,

rule, to_cost

FROM routing’,

103, 35, false, false);

Lộ trình đi từ cạnh 103 đến cạnh 35 là: 103à 104à 94à 54à 26à 19à14à 35.

Kết quả lộ trình thể hiện trong gvSIG:

Giả sử từ đường 103 cấm quẹo vào đường 104, cập nhật bằng SQL như sau: Nếu đi từ đường 103 vào đường 104 thì tốn chi phí to_cost rất cao là 10000.

update routing set rule = 103, to_cost = 10000 where gid = 104

Sau đó chạy lại hàm shooting-star, kết quả tìm kiếm như sau:

Lộ trình mới bỏ qua cạnh 104 do chi phí quá cao: 103-> 182-> 196-> 230-> 233-> 237-> 241-> 244-> 245-> 30-> 14-> 35.

2.4. Mở rộng bài toán tìm đường đi ngắn nhất

Trong mạng giao thông thực tế, khái niệm tìm đường đi ngắn nhất có thể được hiểu theo nghĩa rộng hơn: “tìm đường đi với chi phí thấp nhất”. Chi phí ở đây có thể là quãng đường, thời gian lưu thông,… vì có trường hợp quãng đường ngắn nhưng thường hay kẹt xe, kéo theo làm tăng chi phí cho bài toán tìm đường. Để giải quyết vấn đề này, có thể thiết kế thêm bảng thể hiện mức độ kẹt xe ứng với mỗi con đường. Ví dụ, giá trị 1 được gán cho đường có mức độ kẹt xe cao nhất và giảm dần đối với đường thông thoáng hơn. Lúc này, kết quả của phép nhân chiều dài đường với mức độ kẹt xe được dùng để tính chi phí cho bài toán tìm đường đi với chi phí thấp nhất:

SELECT * FROM shortest_path_shooting_star(

'SELECT gid as id, traffic_id, source, target, length*t.cost as cost,

x1, y1, x2, y2, rule, to_cost, reverse_cost*t.cost as reverse_cost

FROM routing r, traffic t

WHERE traffic_id =r.id', 52, 35, true, true);

Cách giải quyết này hoàn toàn có thể mở rộng áp dụng tìm đường đi với chi phí thấp nhất trên cơ sở tính toán các thông số khác như độ rộng, vật liệu đường, cấp đường, mật độ giao thông lúc bình thường và vào giờ cao điểm, tìm đường theo từng loại phương tiện như đi bộ, xe máy, ô tô,…Hơn nữa, các chi phí này được tính toán trực tiếp bằng SQL và có tác động tức thì đến kết quả tìm kiếm mà không cần xây dựng cũng như tính toán lại cho toàn mạng.

2.5. Tính khoảng cách lái xe

Driving distance cho phép tính khoảng cách ngắn nhất từ 1 đỉnh đến các đỉnh khác trong bán kính nhất định.

Sử dụng core funtion:

driving_distance(

sql text,

source_id integer,

distance float8,

directed boolean,

has_reverse_cost boolean)

Áp dụng: tính khoảng cách từ nút 52 đến các nút khác trong phạm vi 1000m:

SELECT * FROM driving_distance('SELECT gid AS id,source,target,length::double precision AS cost FROM routing’,52,1000,false,false) order by cost;

Kết quả cho thấy trong bán kính 1000m có 10 nút có thể đi từ nút 52 với chi phí tương ứng là cost. Lưu ý ở đây edge_id là cạnh có điểm đầu là vertex_id chứ không phải là cạnh mà nút 52 phải đi qua để đến một vertex_id. Ví dụ: đi từ nút 52 đến nút 85 có khoảng cách là 476.5 m, và từ nút 85 có thể đi tiếp đến cạnh 113.

Để xác định đường đi cụ thể từ 52 đến 85, sử dụng hàm tìm đường đi ngắn nhất:

SELECT * FROM shortest_path('

SELECT gid as id,

source::integer,

target::integer,

length::double precision as cost

FROM routing',

52, 85, false, false);

Dễ thấy đường đi ngắn nhất từ 52 đến 85 là 52-> 93 -> 85, với tổng khoảng cách là 476.5 m, đúng với kết quả từ hàm driving_distance.

2.6 Bài toán người giao hàng

Sử dụng core funtion:

tsp(sql text,

ids varchar,

source_id integer)

Áp dụng:

SELECT * FROM tsp('SELECT distinct source AS source_id,x1::double precision AS

x,y1::double precision AS y FROM routing

WHERE source IN (1,2,3,4,5)', '1,2,3,4,5’, 2);

Nhận xét: Bài toán người giao hàng trong PgRouting hiện tại chỉ dừng lại ở mức thử nghiệm với các mạng đơn giản chứ chưa thể áp dụng tốt cho mạng giao thông thực tế.

2.7. Xây dựng ứng dụng tìm đường đi ngắn nhất sử dụng PgRouting

Triển khai ứng dụng tìm đường đi ngắn nhất trên WebGIS

Khi triển khai sử dụng PgRouting để giải quyết các bài toán phân tích mạng nói chung và tìm đường đi ngắn nhất nói riêng trong các ứng dụng GIS cần có những bước tiền xử lý.

Trên cơ sở thử nghiệm PgRouting trong ứng dụng tìm đường đi ngắn nhất trên WebGIS sử dụng Geoserver, Openlayers phía client, bài báo đưa ra một số khuyến cáo sau:

Dữ liệu routing là lớp giao thông line đã được cắt tại các giao điểm.

Các nút, cạnh tham gia vào mạng cần được đánh chỉ mục để tăng tốc độ tìm kiếm.
Ưu tiên sử dụng hàm tìm kiếm với bounding box để giới hạn không gian tìm kiếm. Bounding box có thể được tính toán dựa trên 2 điểm đầu và cuối do người dùng xác định trên bản đồ.

Thông thường, các điểm đầu và điểm cuối được xác định bởi người dùng không trùng khớp vị trí với điểm đầu hoặc cuối của một cạnh trong mạng (hay các nút trong mạng). Do đó, đối với thuật toán tìm đường dựa vào nút mạng (vertex-based) như Dijkstra, A-Star, cần tính toán khoảng cách từ điểm do người dùng chọn so với điểm đầu và cuối của cạnh gần nhất để quyết định nút nào được chọn để làm đầu vào tính toán. Đối với thuật toán tìm đường dựa vào cạnh mạng (edge-based) như Shooting-Star, chỉ cần chọn cạnh gần nhất làm đầu vào tính toán.

3. KẾT LUẬN

PgRouting là một giải pháp cho các nhà phát triển ứng dụng GIS, đặc biệt là các nhà phát triển sử dụng giải pháp mã nguồn mở giải quyết một số bài toán phân tích mạng ở mức CSDL như tìm đường đi ngắn nhất, tính khoảng cách lái xe, bài toán người giao hàng.

Bài toán tìm đường đi ngắn nhất với PgRouting có thể mở rộng thành bài toán “tìm đường đi với chi phí thấp nhất”, trong đó trọng số các cạnh của mạng được tính toán linh động thông qua các trường hoặc bảng khác trong CSDL mà không cần tính toán lại toàn mạng.

Một nhược điểm của PgRouting là các thuật toán tìm đường đi ngắn nhất chỉ sử dụng các điểm đầu – cuối được “bắt dính” tương ứng với điểm đầu – cuối của các cạnh trong mạng, hay nói cách khác là tại vị trí giao cắt giữa ít nhất 2 cạnh trong mạng. Đối với các cạnh dài và ít giao cắt thì điểm đầu – cuối làm đầu vào tính toán có thể cách xa vị trí người dùng mong muốn (chẳng hạn như vị trí nằm ở khoảng giữa của đường dài, ít giao cắt).

NETWORK ANALYSIS IN GIS APPLICATIONS USING PGROUTING

Quach Dong Thang

HoChiMinh City GIS Center

ABSTRACT: Network analysis is often used in GIS applications. Most commercial and open source GIS software support network analysis (shortest path, traveling salesman problem,…). However, using those functions at application level has some disadvantages. Developers completely depend on software suppliers. Even if those functions are open source, it is time-consuming to research and customize them to fit individual needs. There is a solution that developer can choose to fill this gap: network analysis at database level. This paper presents the ability of using PgRouting to perform network analysis in PosgreSQL/PostGIS for GIS developers.

Keywords: PgRouting, network analysis, shortest path, traveling salesman problem, GIS.

TÀI LIỆU THAM KHẢO

[1]. Claude Philipona (Camptocamp SA), Daniel Kastl (Orkney, Inc.), Web-based Routing: An Introduction to pgRouting with OpenLayers, FOSS4G 2007 – Victoria.

[2]. Daniel Kastl, Claude Philipona, Frédéric Junod, Anton Patrushev, Workshop- FOSS4G routing with pgRouting tools and OpenStreetMap road data, FOSS4G 2009- OSaKa, Japan.

[3]. Daniel Kastl, Frédéric Junod, Workshop - FOSS4G Routing with pgRouting tools, OpenStreetMap road data and GeoExt Manual, FOSS4G 2010- Barcalona, Spain.