CN105788334A - Urban path finding method taking personal preferences of drivers into consideration - Google Patents

Abstract

The invention provides an urban path finding method taking personal preferences of drivers into consideration. The method comprises the following steps: collecting driving GPS data of a driver and map attribute data to get a specific path chosen by the driver in previous travels and the information of the path including the road grade, length and the number of passing intersections; defining a road section generalized cost containing a parameter Beta and a multinomial Logit model to get the probability that the driver chooses the path, and estimating the personal preference parameter Beta through maximum likelihood estimation; and finding a path in conformity with the driver's preference and with the lowest generalized cost by use of a Dijkstra shortest path algorithm according to the calibrated generalized road section cost. The method has the advantage that the usual theoretical experience value is not taken for the measured impedance of a road section, and a shortest path is offered to a driver on the premise of considering the personal preference of the driver according to historical driving paths and on the basis of redefining the road section generalized cost.

Description

Urban route searching method considering personal preference of driver

Technical Field

The invention relates to a method for searching a shortest path, in particular to a personalized urban path searching method considering personal preference of a driver.

Background

The rapid development and wide application of information science and technology drive the demand of the whole society for space information, and a geographic information system (GIS for short) is a technical system which is supported by computer hardware and software, takes a space database as a basis, applies the theories of system engineering and information science to scientifically manage and comprehensively analyze space data and provide information for planning, deciding, managing and researching.

Network analysis is one of the most important functions of the GIS, plays an important role in electronic navigation, traffic tourism and city planning, and the most basic and most critical problem in network analysis is the shortest path problem. The method is used as a basis for selecting the optimal problem in many fields and plays an important role in a traffic network analysis system. From the perspective of a network model, the shortest path analysis is to find a path with the minimum blocking strength between two nodes in a given network. The shortest path problem is always a research hotspot of subjects such as traffic engineering, geographic informatics and the like, and a new shortest path algorithm is continuously emerged and has various characteristics due to effective combination of classical graph theory and continuously developed and perfected computer data structures and algorithms. The shortest path analysis is commonly used in car navigation systems and various urban emergency systems, for example, during driving, a driving route in front of a vehicle is calculated in real time.

Disclosure of Invention

The technical problem is as follows: the invention provides an urban route searching method which can accord with personal preference and personalized route searching and considers personal preference of a driver.

The technical scheme is as follows: the invention discloses a city path searching method considering personal preference of a driver, which comprises the following steps:

1) acquiring travel history data of a driver, wherein the history data are specific paths selected by the driver in previous travel, road grades and lengths of the paths and the number of intersections passed by the driver;

2) the generalized cost V of the road section is calculated as follows and taken as the measured impedance:

$c_k^{rs}=V={\mathrm{\β}}_1{l}_{1}a+{\mathrm{\β}}_2{l}_{2}b+{\mathrm{\β}}_3{l}_{3}c+{\mathrm{\β}}_4*1$

where k is a selected path, r is a starting point, s is an end point,the measured impedance of a path k between a starting point r and an end point s; v is the generalized cost of the road section; a is whether the highway is available: 1 is taken on the expressway, and 0 is not taken on the expressway; b is whether the main road is: 1 is taken from the main road, and 0 is not taken from the main road; c is whether a branch is present: 1 is taken as the branch, and 0 is not taken as the branch; l₁Is the length of the highway section l₂Is the length l of trunk road segment₃Length of branch road section β₁Weighting factor for highway section, β₂Weighting factor for trunk road segment, β₃Weighting factor for the leg segment, β₄Is an intersection weight coefficient, wherein β₄1 is the influence of the number of the sections, namely the number of the intersections on the cost;

the β₁、β₂、β₃、β₄All are obtained as follows: solving the probability of selecting the path k based on a plurality of Logit models; based on historical data, respectively estimating a highway section weight coefficient, a main road section weight coefficient, a branch road section weight coefficient and an intersection weight coefficient by using a maximum likelihood estimation method;

3) and finding the path with the shortest generalized cost according with the preference of the driver by utilizing a Dijkstra shortest path algorithm.

Further, in the method of the present invention, in the step 2), the probability of selecting the path k is obtained as follows:

firstly, based on a logit model, the probability of selecting a path k between a starting point r and an end point s is solved according to the following formula

$p_k^{rs}=\frac{\exp (-{\mathrm{\θc}}_k^{rs}/\stackrel{\‾}{c})}{\underset{l\∈R_{rs}}{\Σ}\exp (-{\mathrm{\θc}}_l^{rs}/\stackrel{\‾}{c})}$

Wherein,as measured impedance of path k between origin r and destination s,is the average of all path impedances, theta is the switching parameter, R_rsIs the set of all paths between the starting point s and the destination point r, and l is a certain path in the path set;

the probability of selecting path k is then calculated according to:

$p_k^{rs}\left(\mathrm{\β}\right)=\frac{\exp \[-{\mathrm{\θc}}_k^{rs}\left(\mathrm{\β}\right)/\stackrel{\‾}{c}\left(\mathrm{\β}\right)\]}{\underset{l\∈R_{rs}}{\Σ}\exp \[-{\mathrm{\θc}}_l^{rs}\left(\mathrm{\β}\right)/\stackrel{\‾}{c}\left(\mathrm{\β}\right)\]}$

wherein β represents β₁、β₂、β₃Or β₄。

Further, in the method of the present invention, the highway section weight coefficient, the trunk section weight coefficient, the branch section weight coefficient, and the intersection weight coefficient are estimated in step 2) as follows:

the probability P (beta) of the path selection between the starting point r and the destination point s obtained from the historical data is:

P(β)＝n₁logp₁(β)+n₂logp₂(β)+...+n_nlogp_n(β)

wherein β represents β₁、β₂、β₃Or β₄，n₁Number of times path 1 is selected, p₁(β) probability, n, that Path 1 was selected₂Number of times path 2 is selected, p₂(β) probability, n, that Path 2 was selected_nNumber of times path n is selected, p_n(β) is path n quiltA probability of selection;

the estimate β is then estimated from the following set of log-likelihood equations₁、β₂、β₃、β₄：

$\frac{\∂P\left(\mathrm{\β}\right)}{\∂{\mathrm{\β}}_1}=0$

$\frac{\∂P\left(\mathrm{\β}\right)}{\∂{\mathrm{\β}}_2}=0$

$\frac{\∂P\left(\mathrm{\β}\right)}{\∂{\mathrm{\β}}_3}=0$

$\frac{\∂P\left(\mathrm{\β}\right)}{\∂{\mathrm{\β}}_4}=0$

Further, in the method of the present invention, the Dijkstra shortest path algorithm in step 3) includes the following steps:

step 0: and (5) initializing.

Step 1: the test is terminated.

Step 2: the T label is modified.

Step 3: the P index is determined.

Has the advantages that: compared with the prior art, the invention has the following advantages:

in the previous research, a road impedance function, namely a BPR function, is generally used for calibrating the generalized cost of a road, perhaps the road section is theoretically the shortest path, but in combination with the actual situation of a driver, an individual may have special requirements, and usually a path which is not the theoretical shortest path but is preferred by the individual is selected; the invention defines the generalized cost of the road section (the parameter beta in the cost is obtained by the method mentioned in the text, and the method considers the actual personal preference of the driver rather than the hypothesis of the existing theory), so that the provided shortest path is more humanized and personalized.

The method calibrates the generalized road section cost by collecting the driving GPS data and the map attribute data of the driver, estimates the generalized cost considering personal parameters by utilizing maximum likelihood estimation in combination with a plurality of Logit models, and obtains the shortest path by utilizing the Dijkstra shortest path algorithm on the basis of the generalized cost, so as to find the path which is in line with the preference of the driver and has the shortest generalized cost. The method has the advantages that the measured impedance of the road section is not taken as a common theoretical empirical value, and the shortest path is provided for the driver on the basis of redefining the generalized cost of the road section by considering the personal preference of the driver according to the historical driving path.

Drawings

FIG. 1 is a flow chart of the method of the present invention.

FIG. 2 is an exemplary graph with k between origin-destination points₁，k₂......k_nA strip path.

Detailed Description

The invention is further described with reference to the following examples and the accompanying drawings.

The invention provides a personalized city route searching method considering personal preference of a driver, which is realized by the following steps:

1) and obtaining the probability of selecting the path k by the Logit path selection model.

In the random flow assignment problem, each alternative path between the origin-destination points r and s is defined to have a satisfactory degree as utility, a traveler always selects the path with the maximum subjective judgment utility, and the utility value of the kth path can be represented as:

$U_k=-c_k^{rs}=-{\mathrm{\θc}}_k^{rs}+{\mathrm{\ϵ}}_k^{rs}---\left(1\right)$

in the formula of U_kThe utility of selecting a path k for origin-destination;is the measured impedance of the path; θ is a positive conversion parameter that converts a measured impedance to utility;representing random error terms made up of factors not observable by the path.

The Logit model is established on the basis of random error items, mutual independence and Gumbel distribution obeying, and the probability of solving and selecting the path k based on the Logit model is as follows:

$p_k^{rs}=\frac{\exp (-{\mathrm{\θc}}_k^{rs}/\stackrel{\‾}{c})}{\underset{l\∈R_{rs}}{\Σ}\exp (-{\mathrm{\θc}}_l^{rs}/\stackrel{\‾}{c})}---\left(2\right)$

in the formula,is the measured impedance of the path k,the transformation parameter theta is an average value of all path impedances and is dimensionless and only related to the number of the alternative paths, and the variation range of theta is quite stable through experiments, and is generally equal to 3.3

2) In the present invention, the measured impedance in the formula (2)Defined as the generalized cost V of the road segment:

$c_k^{rs}=V={\mathrm{\β}}_1{l}_{1}a+{\mathrm{\β}}_2{l}_{2}b+{\mathrm{\β}}_3{l}_{3}c+{\mathrm{\β}}_4*1---\left(3\right)$

then the measured impedanceThe parameter is a linear function of β.

In the formula, a is whether the highway is an expressway (the highway takes 1, and the highway does not take 0);

b is whether the main road is the main road (the main road is 1, and the main road is not 0);

c is whether the branch is taken (1 is taken for the branch, and 0 is not taken for the branch);

l₁、l₂、l₃respectively corresponding road section lengths;

β₄and 1 is the influence of the number of the sections, namely the number of the intersections, on the cost.

3) Substituting the redefined measured impedance, namely equation (3), into the Logit model equation (2) to select the probability of the path kIs a function of the unknown parameter β.

$p_k^{rs}\left(\mathrm{\β}\right)=\frac{\exp \[-{\mathrm{\θc}}_k^{rs}\left(\mathrm{\β}\right)/\stackrel{\‾}{c}\left(\mathrm{\β}\right)\]}{\underset{l\∈R_{rs}}{\Σ}\exp \[-{\mathrm{\θc}}_l^{rs}\left(\mathrm{\β}\right)/\stackrel{\‾}{c}\left(\mathrm{\β}\right)\]}---\left(4\right)$

4) Assume that the driver has historically selected a preferred path of k₁Then the probability of the driver selecting his selected route, i.e. selecting route k, is known from equation (4)₁The probability of (c) is:

$p_{k1}^{rs}\left(\mathrm{\β}\right)=\frac{\exp \[-{\mathrm{\θc}}_{k1}^{rs}\left(\mathrm{\β}\right)/\stackrel{\‾}{c}\left(\mathrm{\β}\right)\]}{\underset{l\∈R_{rs}}{\Σ}\exp \[-{\mathrm{\θc}}_{k_1}^{rs}\left(\mathrm{\β}\right)/\stackrel{\‾}{c}\left(\mathrm{\β}\right)\]}---\left(5\right)$

5) assume that the collected driving history data is 100 persons, where n₁Individual selection path k₁，n₂Individual selection path k₂.....n_nIndividual selection path k_nWherein k is₁，k2...k_nIs the set of all paths; the driver selects the route k₁Probability of (2)Is p (k)₁) The driver selects the route k₂Has a probability of p (k)₂) ... driver selects path k_nHas a probability of p (k)_n)

The probability P (β) that the sample occurs can be expressed as

P(β)＝p(k₁ ⁿ¹·k₂ ⁿ²…k_n ⁿⁿ)

Taking the logarithm, then

logp(k₁ ⁿ¹·k₂n2…k_n ⁿⁿ)＝logpⁿ¹(k₁)+logpⁿ²(k₂)+...+logpⁿⁿ(k_n)

P(β)＝n₁logp₁(β)+n₂logp₂(β)+...+n_nlogp_n(β)

The log-likelihood equation set is:

$\frac{\∂P\left(\mathrm{\β}\right)}{\∂{\mathrm{\β}}_1}=0---\left(6\right)$

$\frac{\∂P\left(\mathrm{\β}\right)}{\∂{\mathrm{\β}}_2}=0---\left(7\right)$

$\frac{\∂P\left(\mathrm{\β}\right)}{\∂{\mathrm{\β}}_3}=0---\left(8\right)$

$\frac{\∂P\left(\mathrm{\β}\right)}{\∂{\mathrm{\β}}_4}=0---\left(9\right)$

β estimated from the equations (6), (7), (8) and (9)₁、β₂、β₃、β₄。

6) And (3) according to the generalized cost V of the calibrated road section, namely the formula (3), utilizing the most common shortest path calculation exploration algorithm, namely Dijkstra algorithm.

The Dijkstra (Dijkstra) algorithm was proposed by the netherlands computer scientist dickstra in 1959. Is a typical shortest path algorithm for calculating the shortest path from one vertex to the rest of the vertices, and solves the shortest path problem in the directed graph. The method is mainly characterized in that the expansion is carried out layer by layer towards the outer part by taking the starting point as the center until the end point is reached. The Dijkstra algorithm can obtain the optimal solution of the shortest path.

The specific steps of the Dijkatra algorithm are as follows:

step 0: and (5) initializing. Let i equal 0, s₀＝{v_s}，P{v_s}＝0，λ(v_s) 0, toLet t (v) ∞, λ (v) ═ M, let index k of current check point equal to s;

step 1: the test is terminated. If s_iN, the algorithm terminates, at which time c (v)_s，v)＝P(v)，Otherwise, switching to step 2;

step 2: the T label is modified. For each of (v)_k，v_j) ∈ A andif T (v)_j)＞P(v_k)+t_kjThen modify node v_jReference numeral of (1), let T (v)_j)＝P(vk)+t_kj，λ(v_j) K is; otherwise, turning to Step 3;

step 3: the P index is determined. Order toIf T (v)_ji) If + ∞, then v_jiThe T-symbol of (b) is designated as P-symbol, i.e., P (v)_ji)＝T(v_ji) Simultaneously order S_i+1＝S_i∪{v_ji}，k＝j_iLet i be i +1 and proceed to Step1, otherwise, the algorithm terminates, this time for each node v ∈ S_iHaving c (v)_sV) P (v), for eachc(v_s，v)＝T(v)。

After the method is terminated, the method can be used for tracking from the initial node v in a reverse way through the lambda value_sAnd (4) finding the shortest path to any node v, namely finding the path which is in accordance with the preference of the driver and has the shortest generalized cost.

The above examples are only preferred embodiments of the present invention, it should be noted that: it will be apparent to those skilled in the art that various modifications and equivalents can be made without departing from the spirit of the invention, and it is intended that all such modifications and equivalents fall within the scope of the invention as defined in the claims.

Claims (4)

1. A city route finding method considering personal preference of a driver, comprising the steps of:

1) acquiring travel history data of a driver, wherein the history data are specific paths selected by the driver in previous travel, road grades and lengths of the paths and the number of intersections passed by the driver;

2) the generalized cost V of the road section is calculated as follows and taken as the measured impedance:

where k is a selected path, r is a starting point, s is an end point,the measured impedance of a path k between a starting point r and an end point s; v is the generalized cost of the road section; a is whether the highway is available: 1 is taken on the expressway, and 0 is not taken on the expressway; b is whether the main road is: 1 is taken from the main road, and 0 is not taken from the main road; c is whether a branch is present: 1 is taken as the branch, and 0 is not taken as the branch; l₁Is the length of the highway section l₂Is the length l of trunk road segment₃Length of branch road section β₁Weighting factor for highway section, β₂Weighting factor for trunk road segment, β₃Weighting factor for the leg segment, β₄Is an intersection weight coefficient, wherein β₄1 is the influence of the number of the sections, namely the number of the intersections on the cost;

the β₁、β₂、β₃、β₄All are obtained as follows: solving the probability of selecting the path k based on a plurality of Logit models; based on historical data, respectively estimating a highway section weight coefficient, a main road section weight coefficient, a branch road section weight coefficient and an intersection weight coefficient by using a maximum likelihood estimation method;

3) and finding the path with the shortest generalized cost according with the preference of the driver by utilizing a Dijkstra shortest path algorithm.

2. The city path finding method considering personal preference of driver as claimed in claim 1, wherein in the step 2), the probability of selecting the path k is obtained as follows:

firstly, based on a logit model, the probability of selecting a path k between a starting point r and an end point s is solved according to the following formula

Wherein,as measured impedance of path k between origin r and destination s,is the average of all path impedances, theta is the switching parameter, R_rsIs the set of all paths between the starting point s and the destination point r, and l is a certain path in the path set;

the probability of selecting path k is then calculated according to:

wherein β represents β₁、β₂、β₃Or β₄。

3. The urban path finding method considering the personal preference of the driver according to claim 1 or 2, wherein the highway section weight coefficient, the trunk section weight coefficient, the branch section weight coefficient, and the intersection weight coefficient are estimated in step 2) as follows:

the probability P (beta) of the path selection between the starting point r and the destination point s obtained from the historical data is:

P(β)＝n₁logp₁(β)+n₂logp₂(β)+...+n_nlogp_n(β)

wherein β represents β₁、β₂、β₃Or β₄，n₁Number of times path 1 is selected, p₁(β) probability, n, that Path 1 was selected₂Number of times path 2 is selected, p₂(β) probability, n, that Path 2 was selected_nNumber of times path n is selected, p_n(β) a probability of being selected for path n;

the estimate β is then estimated from the following set of log-likelihood equations₁、β₂、β₃、β₄：

。

4. The city path finding method considering personal preference of drivers as claimed in claim 1 or 2, wherein the Dijkstra shortest path algorithm in the step 3) comprises the steps of:

step 0: and (5) initializing.

Step 1: the test is terminated.

Step 2: the T label is modified.

Step 3: the P index is determined.