OPTIMAL MULTI-RENDEZVOUS POINT PATH SEARCHING METHOD AND DEVICE BASED ON A* STRATEGY

摘要

An optimal multi-rendezvous point path searching method and device based on an A* strategy, wherein the method comprises: obtaining preset path searching information comprising a graph G = (V, E, W), a point set U, α, a starting point s, and a destination point t; and executing the following steps: (1) using a universal-set path algorithm to calculate C(x, y, U), wherein x, y ∈ U; (2) if α ≤ 1/3, returning α × min_{x∈U, y∈U}(dist(s, x) + C(x, y, U) + dist(y, t)); (3) determining a shortest path P' from s to t; (4) calculating α × c(P') + (1 - α)x∑_x∈U(min_x∈VP'dist(x, v)) and assigning a value to best; (5) initializing a queue Q and a set D, and adding initial states ((s, s, ∅), 0, lb((s, s, ∅), t, U, 0, D) and ((t, t, ∅), 0, lb((t, t, ∅), s, U, 0, D) to the queue Q, wherein lb() is an operation for calculating lower bounds, and a result lb is a priority sequence of the queue Q; (6) if the queue Q is not null, finding an optimal solution by means of a cyclic operation. The method and the device can resolve technical difficulties in real-time ridesharing applications more effectively, and greatly improve efficiency and practicability.