1. pgRouting คืออะไร ทำงานยังไง
pgRouting is a free, open-source project maintained by PostLBS, which provides core tools for Location Based Services (LBS) as Open Source Software (OSS). pgRouting adds routing and other network analysis functionality. A predecessor of pgRouting – pgDijkstra, written by Sylvain Pasche from Camptocamp, was later extended by Orkney and renamed to pgRouting. The project is now supported and maintained by Georepublic, iMaptools and a broad user community.
วัตถุ ประสงค์หลักของ pgRouting คือ จัดหาฟังก์ชั่นสำหรับการใช้งานใน PostgreSQL/PostGIS. เพื่อสร้างเครื่องมือในการคำนวนหาระยะทาง ซึ่งจะคล้าย ๆ กับ ชุดคำสั่งในโปรแกรมบางโปรแกรมเช่น คำสั่งการค้นหาระยะทางที่ใกล้ที่สุดในโปรแกรม ArcGIS หรือใน PostGIS และไม่เฉพาะในเรื่องของระยะทางบนถนนเท่านั้น แต่สามารถใช้ได้กับข้อมูลอะไรก็ได้ที่เกี่ยวกับ ระยะทาง การสิ้นเปลืองเวลา น้ำมัน เงิน เช่น เส้นทางเกี่ยวกับการเิดินเรือ และระบบเน็ตเวิร์คแม่ข่ายบนอินเตอร์เน็ต เป็นต้น
นอกจาก pgRouting สามารถคำนวนหาระยะทางที่สั้นที่สุด เร็วที่สุดแล้ว pgRouting ยังสามารถช่วยในการวางแผนการเดินทางในการจัดส่งสิ้นค้าหลาย ๆ ที่ในการเดินทางครั้งเดียวกัน เช่น จะไปส่งของให้ลูกค้าทั้งหมด 4 ที่ โดยเริ่มต้นเดินทางจากโรงงานผู้ผลิด ควรจะไปส่งของให้ลูกค้ารายใดก่อนหลัง ตามลำดับ เพื่อช่วยในการประหยัดเวลา และน้ำมัน เป็นต้น
ปัจจุบัน pgRouting ได้พัฒนามาเป็น version 2.0 จากเดิม 1.5 และมีฟังก์ชั่นต่างๆเพิ่มขึ้นมามากมาย ดังที่แสดงอยู่ข้างล่าง
- All Pairs Shortest Path, Johnson’s Algorithm [1]
- All Pairs Shortest Path, Floyd-Warshall Algorithm [1]
- Shortest Path A*
- Bi-directional Dijkstra Shortest Path [1]
- Bi-directional A* Shortest Path [1]
- Shortest Path Dijkstra
- Driving Distance
- K-Shortest Path, Multiple Alternative Paths [1]
- K-Dijkstra, One to Many Shortest Path [1]
- Traveling Sales Person
- Turn Restriction Shortest Path (TRSP) [1]
- Shortest Path Shooting Star [2
[1] ฟังก์ชั่นใหม่ที่เพิ่มขึ้นมาใน pgRouting 2.0.0
[2] ฟังก์ชั่นเก่าที่เลิกใช้แล้วใน pgRouting 2.0.0
ข้อดีของวิธีการหาเส้นทางจากระบบฐานข้อมูลคือ
- สามารถทำการแก้ไขข้อมูลและรายละเอียดข้อมูลได้หลายวิธี, เช่น QGIS” และ uDig ผ่านทาง JDBC, ODBC, หรือแก้ไขโดยตรงจากโปรแกรม Pl/pgSQL. อีกทั้งยังสามารถแก้ไขผ่านไม่ว่าจะทางคอมพิมเตอร์หรือโทรศัพท์ก็ได้
- Data changes can be reflected instantaneously through the routing engine. There is no need for precalculation.
ข้อมูลที่ถูกแก้ไขจะสามารถแสดงผลลัพธ์ใหม่ได้ทันทีผ่านโปรแกรมการเส้นทาง โดยไม่ต้องทำการคำนวนใหม่อีกครั้ง
- ตัวแปลค่าน้ำหนัก “cost” สามารถคำนวนผ่าน SQL และค่าเหล่านั้นสามารถเรียกมาคำนวนได้จากหลายๆตาราง หลายๆคอลัมในเวลาเดียวกัน
2. สร้างฐานข้อมูลและเพิ่ม pgRouting ฟังก์ชั่นเข้าไปในฐานข้อมูล
ตั้งแต่พัฒนาจาก pgRouting version 1.x มาเป็น 2.0 เราสามารถเพิ่มฟังก์ชั่นเข้าไปใน PostGIS Extension ได้ง่ายขึ้น แต่มีข้อกำหนดคือ ต้องใช้
- PostgreSQL 9.1 or สูงกว่า
- PostGIS 2.x installed as extension
หากลงโปรแกรม PostgreSQL/PostGIS ตาม Version ที่กำหนดแล้ว
ขั้นตอนต่อไปเริ่มจาก เปิดโปรแกรม pgAdmin 3: และใช้คำสั่งต่อไปนี้
# login as user "postgres"
psql -U postgres
# create routing database
CREATE DATABASE routing;
\c routing
# add PostGIS functions
CREATE EXTENSION postgis;
# add pgRouting core functions
CREATE EXTENSION pgrouting;
2.1 เอาข้อมูล Shapefile ใส่ในฐานข้อมูลที่ชื่อ routing
2.2 จากนั้นก็ Create a Network Topology
-- Add "source" and "target" column
ALTER TABLE road ADD COLUMN "source" integer;
ALTER TABLE road ADD COLUMN "target" integer;
-- Run topology function
pgr_createTopology('<table>', float tolerance, '<geometry column', '<gid>')
SELECT pgr_createTopology('road', 0.00001, 'the_geom', 'gid');
Note: ค่า float tolerance สามารถเปลี่ยนไปได้ขึ้นอยู่กับจำนวนความถี่ของโครงข่ายถนน ค่าพิกัดของข้อมูล หลังจาก created topology แล้ว สามารถเช็คค่าเพื่อตรวจสอบความถูกต้องได้จากคำสั่งSELECT * from road where source=target;
คำตอบที่ได้จะต้องเป็น 0 หรือ ไม่มีข้อมูล หากยังมีข้อมูลที่ซ้ำกันให้ทำการปรับค่า float tolerance ให้เล้กลงไปเรื่อยๆ จนกว่าข้อมูลจะไม่ซ้ำ
2.3 --Add indices เพื่อช่วยให้ทำการ query ข้อมูลได้เร็วขึ้น
CREATE INDEX source_idx ON road("source");
CREATE INDEX target_idx ON road("target");
3.ทดสอบการหาเส้นทางจากฟังก์ชั่นแรก Shortest Path Dijkstra
Dijkstra algorithm นั้นจะทำการ query จาก attributes (column)
source and
target ID,
id attribute and
cost (ระยะทาง หรือ column length)เท่านั้น. อีกทั้ง ยังสามารถกำหนดการคำนวนเส้นทางแบบ
directed (คิดในเรื่องของเส้นทางที่เป็น One way) and undirected (ไปได้ทุกเส้นทาง) ได้อีกด้วย. ขึ้นอยุ่กับว่าเราต้องกาำที่จะกำหนดค่า
reverse cost ให้กำข้อมูลถนนหรือไม่
3.1หากรายละเอียดข้อมูลถนนของเรายังไม่มี column ที่ชื่อ length ให้สร้างจากคำสั่งดังนี้
ALTER TABLE road ADD COLUMN lenght double precision;
UPDATE road SET length = ST_length(the_geom); --คำนวนระยะทางของถนนแต่ละเส้น
ในกรณีที่มีการใช้คำสั่งในการคำนวนในเรื่องของถนนที่เดินรถได้ทางเดียว (One way) จะต้องเพิ่ม column 'reverse_cost' เข้าไปและจะให้ค่าเริ่มต้นของ reverse_cost=length
ALTER TABLE road ADD COLUMN reverse_cost double precision;
UPDATE road SET reverse_cost = length;
ส่วนถนนเส้นไหนที่เป็นถนน One way นั้น ค่าของ reverse_cost จะใส่เป็น infinity หรือ 1,000,000
3.2 Query
--undirected
SELECT seq, id1 AS node, id2 AS edge, cost FROM pgr_dijkstra('
SELECT gid AS id,
source::integer,
target::integer,
length::double precision AS cost
FROM road',
105, 209, false, false);
--directed
SELECT seq, id1 AS node, id2 AS edge, cost FROM pgr_dijkstra('
SELECT gid AS id,
source::integer,
target::integer,
length::double precision AS cost,
reverse_cost::double precision AS reverse_cost,
FROM road',
105, 209, true, true);
ศึกษาเพิ่มเติมได้ที่ http://workshop.pgrouting.org/
undirected
directed
