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).

1. 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.