使用Neo4j实现路径规划_neo4j apoc 最短路径

安装Neo4j

这里采用Docker方式安装社区版Neo4j，其他安装方式参考官方安装文档。

先创建数据、插件和配置目录：

mkdir -p ~/database/neo4j/data ~/database/neo4j/plugins ~/database/neo4j/conf
1

官方提供的两个插件APOC和GDS均实现了Dijkstra（狄克斯特拉）和A*（AStar）路径规划算法。

下载插件：apoc-4.4.0.8-all（neo4j和apoc的版本适配表）、neo4j-graph-data-science-2.1.9

下载默认配置文件，在末尾添加配置：

dbms.memory.pagecache.size=512M

dbms.default_listen_address=0.0.0.0
dbms.directories.logs=/logs
dbms.tx_log.rotation.retention_policy=100M size

dbms.security.procedures.unrestricted=gds.*,apoc.*
dbms.security.procedures.allowlist=gds.*,apoc.*
apoc.import.file.use_neo4j_config=true
apoc.import.file.enabled=true
apoc.export.file.enabled=true
1
2
3
4
5
6
7
8
9
10
11

启动Neo4j容器：

docker run -d -p 7474:7474 -p 7687:7687 -v ~/database/neo4j/data:/data -v ~/database/neo4j/plugins:/plugins -v ~/database/neo4j/conf:/conf --name neo4j neo4j:4.4.10-community
1

打开Neo4j Browser：http://127.0.0.1:7474/browser/

验证插件是否安装成功：

RETURN apoc.version()
RETURN gds.version()
1
2

导入路网数据

假设已经有路网数据存储在MongoDB，现导入Neo4j。由于GDS中，用于指导搜索的启发式函数是半正弦公式，该公式根据经纬度计算球体上两点之间的距离，距离以海里计算。所以为了得到最佳算法效果，最好将节点的坐标系转换为WGS84地理坐标系，节点间距离单位转换为海里。

将路网封装成节点对对象列表，作为参数nodePar：

:param obj => ([{
		s:{lng:113.8050, lat:22.8064, index:0},
		e:{lng:113.8053, lat:22.8060, index:1},
		r:{distance:0.1}
	},{
		s:{lng:113.8050,lat:22.8067,index:2},
		e:{lng:113.8053, lat:22.8060, index:1},
		r:{distance:0.2}
	}])
1
2
3
4
5
6
7
8
9

同时传入poiId和floor等参数，执行以下Cypher：

unwind $nodePar as par 	#解压nodePar，对每一个元素执行后续操作，类似foreach
	merge (s:RoadNode {poiId:$poiId, floor:$floor, index:par.s.index}) 	#由于路网节点可能存在共用，所以使用merge来同时实现match或create
	on create 	# 创建时执行以下操作
	    set s += par.s 	#此时s节点已经创建，需要将其他属性附加到s节点上，同名属性被替换，值为null的属性被删除
	merge (e:RoadNode {poiId:$poiId, floor:$floor, index:par.e.index})
	on create
	    set e += par.e
	merge (s)-[r1:ROAD_ROUTE]->(e)-[r2:ROAD_ROUTE]->(s)	# 创建关系，由于路网是无向图，但neo4j只支持单向关系，所以需要创建两条单向关系来模拟双向关系
	on create
	    set r1 += par.r
	    set r2 += par.r 
1
2
3
4
5
6
7
8
9
10
11

如果只有经纬度（WGS84），也可以使用point.distance()方法计算距离，计算结果单位为米，需要再转换为海里：

unwind $nodePar as par
	merge (s:RoadNode {poiId:$poiId, floor:$floor, index:par.s.index})
	on create
	    set s += par.s
	merge (e:RoadNode {poiId:$poiId, floor:$floor, index:par.e.index})
	on create
	    set e += par.e
	with par, s, e, point.distance(point({longitude:par.s.lng, latitude:par.s.lat}), point({longitude:par.e.lng, latitude:par.e.lat})) / 1852 as distance	# 1海里=1852米
		merge (s)-[r1:ROAD_ROUTE]->(e)-[r2:ROAD_ROUTE]->(s)
		on create
		    set r1 += par.r, r1.distance = distance
		    set r2 += par.r, r2.distance = distance
1
2
3
4
5
6
7
8
9
10
11
12

路径规划

使用GDS的A*算法规划最短路径

创建投影

Graph algorithms run on a graph data model which is a projection of the Neo4j property graph data model. A graph projection can be seen as a materialized view over the stored graph, containing only analytically relevant, potentially aggregated, topological and property information. Graph projections are stored entirely in-memory using compressed data structures optimized for topology and property lookup operations.

算法使用投影图来提高性能，先创建名为projectName的原生投影图：

CALL gds.graph.project(
    $projectName,
    "RoadNode",
    "ROAD_ROUTE",
    {
        nodeProperties: ["lng", "lat"],
        relationshipProperties: "distance"
    }
)
1
2
3
4
5
6
7
8
9

原生投影通过读取 Neo4j 存储文件来提供最佳性能，投影图包括了所有指定标签的节点和边的对应属性，要筛选节点和边可以使用Cypher投影图：

CALL gds.graph.project.cypher(
	$projectName,
	'match (n:RoadNode {poiId:$poiId, floor:$floor}) return id(n) as id',
	'match (n:RoadNode {poiId:$poiId, floor:$floor})-[r:ROAD_ROUTE]->(m:RoadNode) return id(n) as source, id(m) as target',
	{
		parameters:{poiId:1, floor:1}
	}
)
1
2
3
4
5
6
7
8

实测，使用原生投影3824个节点、7762条边耗时39ms、占用内存9453KB，使用Cypher投影293个节点、588条边耗时55ms、占用内存296KB，所以使用原生投影图可以获得更高性能，即便它投影了更多的节点和边。

调用A*算法

直接执行以下Cypher：

MATCH (source:RoadNode {poiId:$poiId, floor:$floor, index: $sourceIndex}), 
	  (target:RoadNode {poiId:$poiId, floor:$floor, index: $targetIndex})
CALL gds.shortestPath.astar.stream($projectName, {
	sourceNode: source,
	targetNode: target,
	latitudeProperty: 'lat',
	longitudeProperty: 'lng',
	relationshipWeightProperty: 'distance'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
	index,
	totalCost,
	[node IN gds.util.asNodes(nodeIds) | [node.index, node.lng, node.lat]] AS nodes,
	costs
ORDER BY index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16