CN109521449B - A method for selecting cruise destination based on taxi GPS track - Google Patents

Abstract

The invention discloses a method for selecting a cruising destination based on a taxi GPS track. The method specifically comprises the five steps of step 1, determining cruise areas in different time periods, step 2, carrying out grid division on a cruise range, step 3, determining alternative cruise destination grids, step 4, calculating the attractive force of each alternative cruise destination grid, and step 5, pushing the alternative cruise destination grids to a taxi. The method disclosed by the invention is based on taxi GPS track data, the cruising area is gridded, the attraction of the alternative cruising destination grid to the taxi is calculated according to the number of historical passenger carrying points, the land utilization intensity and the shortest travel time, and the alternative cruising destination grid is pushed to the taxi according to the sequence of the attraction from large to small. The method can assist the taxi to select the cruising destination, improve the passenger carrying success rate, and reduce the idle cruising mileage, the fuel consumption, the environmental pollution and the traffic jam caused by the idle cruising.

Description

A Method of Selecting Cruise Destination Based on Taxi GPS Trajectory

technical field

The invention relates to the field of navigation algorithm development, in particular to a method for recommending no-load cruising destinations for taxi drivers.

Background technique

Taxi GPS data can cover urban road network traffic in an all-round way, which can not only reflect the historical passenger experience and rules of taxis, but also reflect the demand characteristics and travel rules of passengers. Therefore, by analyzing the massive GPS data of taxis, we can discover the deep information hidden in the data. With the help of data mining technology, we can analyze the information contained in the data and the historical passenger experience of taxis, which can help taxis to be faster and more efficient. looking for passengers.

If a method for recommending no-load cruising destinations for taxi drivers is developed, and the optimal cruising destinations are calculated for taxis based on the distribution of taxi historical passenger points, it can assist taxis in selecting cruising destinations and improve passenger capacity. The success rate can reduce the invalid driving caused by the cruising process and the resulting fuel consumption, environmental pollution and traffic congestion.

In previous studies, some scholars have analyzed the cruising behavior of taxis based on taxi GPS data. Effects of cruise point selection behavior. Some scholars study the demand law of taxi passengers. For example, patent 201410068245.8 studies the taxi empty navigation system and method based on the expected value of the taxi. None of these research results deal with how to calculate and recommend cruising destinations for taxis during cruising. Based on the above background, it can be seen that there is an urgent need to design a method for recommending unloaded cruising destinations for taxi drivers by using the historical passenger information of taxis, so as to help taxi drivers find passengers more quickly and efficiently, and solve the problem of passive waiting for taxi drivers. And the problem of blind inefficient cruising. After searching, there is no relevant report at home and abroad on the algorithm that recommends cruising destinations for taxis in the process of cruising with no load.

SUMMARY OF THE INVENTION

1. A method for selecting a cruising destination based on taxi GPS track, characterized in that, comprising the steps:

Step 1 Determine the cruising area for different time periods

Divide 24 hours a day into 12 time periods, each time period is 2 hours, collect the road network traffic volume of any working day in the city for 24 hours, set the time period with the largest traffic volume as the peak time period, and set the time period for other periods as As the flat peak period, the maximum acceptable cruising radius R of taxis during peak hours is set to 3km, and the maximum acceptable cruising radius R of taxis during flat peak hours is set to 5km. The circular area where R is 3km is defined as the cruising area of the taxi during peak hours; the circular area with the current cruising starting point O of the taxi as the center and a radius R of 5 km is defined as the cruising area of the taxi during the peak hours;

Step 2 Mesh the cruise area

Step 2.1 Calculate the mesh side length

Divide the cruising area into square grids, first calculate the sum of the passenger points of all taxis in the cruising area the day before, denoted as Q, then calculate the area of the cruising area A=πR ² , and calculate the area of each grid S= 2A/Q, finally calculate the side length of each grid

Step 2.2 Rasterize the cruise area

Take the latitude line passing through the current cruising starting point O as the benchmark, translate it upwards by L/2 to draw a parallel line, and then translate this parallel line upwards by L to draw a parallel line, and on this basis, sequentially translate upwards by k*L to draw a parallel line, k= 1, 2, 3, 4, ... until the line is tangent to or separated from the cruising area; similarly, using the latitude line passing through the current cruising starting point O as a reference, translate it downward by L/2 to draw a parallel line, Then translate the parallel line downward by L to draw a parallel line, and on this basis, sequentially translate downward by k*L to draw a parallel line, k=1, 2, 3, 4,... until the line is tangent or intersecting with the cruise area stop when leaving;

Based on the meridian passing through the current cruise starting point O, move it to the left by L/2 to draw a parallel line, then move the parallel line to the left by L to draw a parallel line, and then move to the left by k*L to draw a parallel line , k=1,2,3,4,..., until the line is tangent to or separated from the cruising area; similarly, take the meridian passing through the current cruising starting point O as a reference, and translate it to the right by L/2 draw Parallel line, then translate the parallel line to the right by L and draw a parallel line, on this basis, translate to the right by k*L to draw a parallel line, k=1,2,3,4,... until the line is in line with the cruise area Stop when tangent or separated;

A square grid is formed by each latitude and longitude, and the grid crossed by the boundary of the cruise area is screened. If the center point of a grid is located in the cruise area, the grid is counted in the cruise area. On the contrary, if a certain If the center point of the grid is outside the cruising area, the grid is not included in the cruising area;

Step 3 Identify Alternate Cruise Destination Grid

Record the sum of passenger loading points of all taxis in each grid in the cruising area as Q _n , n is the grid label, n=1, 2, 3, 4,..., N, N is the grid in the cruising area The total number of grids, the grids are sorted in descending order according to the value of Q _n , and the first 10 grids are used as grids of alternative cruising destinations, which are recorded as D _i , i=1,2,3,...,10 ;

Step 4 Calculate the attractiveness of each alternative cruise destination grid

Calculate the shortest travel time from the current cruising starting point O to each alternative cruising destination grid D _i according to the shortest path calculation method, denoted as t _i ;

The sum of the number of passenger points of all taxis in the previous day in each alternative cruising destination grid is recorded as Q'_i;

Apply formula 1 to calculate the land use intensity of each candidate cruising destination grid, where P _i is the population in the grid;

M _i =P _i /S Formula 1

Calculate the attractiveness of each alternative cruising destination grid as:

F _i ＝Q′ _i · M _i /t _i Formula 1

Step 5 Push the grid of alternative cruising destinations to the taxi

On the system interface, the grids of alternative cruising destinations are pushed to taxi drivers in order of F _i from large to small.

Compared with the prior art, the beneficial effects of the present invention are:

A method for selecting a cruising destination based on a taxi GPS track according to the present invention, by analyzing the taxi GPS track data, obtains the distribution of historical passenger loading points, then grids the cruising area, and based on the historical passenger loading points The number of points, land use intensity and the shortest travel time from the current location to the alternative destination calculate the attractiveness of all alternative destination grids to taxis, and the final attraction is sorted from large to small as taxis Perform alternate cruise destination grid push. This method can assist taxis to select cruising destinations, improve the success rate of passenger loading, reduce the mileage of unloaded cruising, and the fuel consumption, environmental pollution and traffic congestion caused by unloaded cruising.

Description of drawings

Fig. 1 is the general flowchart of the method for selecting cruise destination based on taxi GPS track of the present invention;

Fig. 2 is a schematic diagram of grid division of the cruising area of the present invention;

Fig. 3 is a schematic diagram of distribution of passenger points according to an embodiment of the present invention;

Fig. 4 is a schematic diagram of an interface for pushing a grid of alternative cruising destinations according to an embodiment of the present invention.

Detailed ways

1. GPS track point data format

Table 1 shows an example of the data format of the taxi track point data obtained by the taxi-mounted GPS device.

Table 1 Example of GPS track point data format

serial number date number plate record moment Longitude (E) Latitude (N) vehicle status … … … … … … … 241 2017/12/20 Guangdong B8UG39 7:32:30 113.888894 22.562061 0 242 2017/12/20 Guangdong B945Z0 7:32:35 113.992741 22.583639 0 243 2017/12/20 Guangdong B945Z0 7:32:40 113.992741 22.583639 1 244 2017/12/20 Guangdong B8UG39 7:32:45 113.992741 22.583639 1 245 2017/12/20 Guangdong B0721D 7:32:50 113.927474 22.684084 0 246 2017/12/20 Guangdong B372Z7 7:32:55 114.150457 22.657699 0 247 2017/12/20 Guangdong B8UG39 7:33:00 114.140772 22.610005 0 248 2017/12/20 Guangdong BA5Y24 7:33:05 114.043187 22.520746 0 249 2017/12/20 Guangdong B214G9 7:33:10 114.107526 22.535423 1 250 2017/12/20 Guangdong B945Z0 7:33:15 113.921162 22.532657 1 … … … … … …

2. Calculation method and steps

Referring to Fig. 1, the method for selecting the cruising destination based on the taxi GPS trajectory described in the patent of the present invention consists of the following five steps:

Step 1 Determine the cruising area for different time periods

Divide a day into 12 time periods according to the traffic volume, determine the peak hours and the peak hours according to the traffic volume of the road network, and set the cruising areas during the peak hours and the peak hours respectively.

Step 2 Mesh the cruise area

Step 2.1 Calculate the mesh side length

Calculate the side length L of the square grid according to the sum of the passenger loading points of all taxis in the cruising area and the area of the cruising area on the previous day.

Step 2.2 Rasterize the cruise area

According to the side length L of the square grid calculated in step 2.1, based on the longitude and latitude passing through the current cruising starting point O, translate L/2 in the four directions of up, down, left, and right to draw a parallel line, and then continue to translate the parallel line outward L draws parallel lines, and on this basis, translates k*L to draw parallel lines in four directions up, down, left, and right, k=1, 2, 3, 4, ..., until the line is tangent to or separated from the cruise area and stops.

A square grid is formed by each latitude and longitude, and the grid crossed by the boundary of the cruise area is screened. If the center point of a grid is located in the cruise area, the grid is counted in the cruise area. On the contrary, if a certain If the center point of the grid is outside the cruising area, the grid is not included in the cruising area, as shown in the shaded area in Figure 2.

Step 3 Identify Alternate Cruise Destination Grid

Based on the taxi GPS trajectory data set, data preprocessing is performed, and valid fields such as license plate number, date, recording time, longitude, latitude, and vehicle status are retained. An example of the GPS trajectory point data format is shown in Table 1. According to the vehicle state data, it can be seen that the trajectory data when the vehicle state changes from empty (ie vehicle state=0) to passenger (ie vehicle state=1) is the data of a passenger loading point of the taxi.

Record the sum of passenger loading points of all taxis in each grid in the cruising area as Q _n , n is the grid label, n=1, 2, 3, 4,..., N, N is the grid in the cruising area The total number of grids, the grids are sorted in descending order of the value of Q _n , and the first 10 grids are used as candidate cruise destination grids, which are recorded as D _i , i=1, 2, 3,...10.

Step 4 Calculate the attractiveness of each alternative cruise destination grid

Calculate the shortest travel time from the current cruising starting point O to each alternative cruising destination grid D _i according to the shortest path calculation method, denoted as t _i ;

Record the sum of the loading points of all taxis in the previous day in each alternative cruising destination grid as Q'_i;

Apply formula 1 to calculate the land use intensity M _i of the grid of alternative cruise destinations;

Apply formula 2 to calculate the attraction F _i of each candidate cruise destination grid.

Step 5 Push the grid of alternative cruising destinations to the taxi

On the system interface, the grids of alternative cruising destinations are pushed to taxi drivers in descending order of F _i .

Three, the embodiment

An embodiment of a method for selecting a cruising destination based on the taxi GPS trajectory described in the patent of the present invention provides the implementation process and inspection results, but the scope of protection of the present invention is not limited to the following embodiments.

Collect GPS track point data of all taxis in Shenzhen on December 20-21, 2017, process the data, and retain valid fields such as license plate number, date, recording time, longitude, latitude, and vehicle status. According to the statistics of the traffic flow data of the Shenzhen road network, the peak hours are 6:00-8:00. Taking a taxi in Shenzhen as an example, the starting point O of a certain cruise during the peak hours of 6:00-8:00 on December 21, 2017 is Shennan Keyuan Overpass (22.539865°E, 113.945515°N). As shown in Figure 3, according to the data processing, the trajectory distribution of passenger loading points of all taxis in Shenzhen on December 20, 2017 is obtained, and the passenger loading points in the circular cruising area with O as the center and radius R of 3 km are calculated during peak hours The sum Q=6538. At the same time, the area A of the cruising area is known to be πR ² , and the side length L of each grid is calculated to be 0.093km.

Based on the longitude and latitude passing through the current cruising starting point O, the grid is divided with the side length L=0.093km, and the grids crossed by the boundary of the cruising area are screened. Calculate the sum of all taxi passenger points in each grid in the cruising area on December 20, 2017, denoted as Q _n , n is the grid label, n=1,2,3,4,...,N, N is cruising The total number of grids in the area, the grids are sorted according to the value of Q _n from large to small, and the first 10 grids are used as candidate cruise destination grids, which are recorded as D _i , i=1,2,3 ,...10.

According to the calculated top 10 candidate cruise destination grids as shown in Fig. 3, the land use intensity of each candidate cruise destination grid is obtained by applying formula 1, and combined with the calculated current cruise starting point O to each standby Select the shortest travel time of the cruising destination grid, and apply formula 2 to calculate the attractiveness of each alternative cruising destination grid. The calculation results are shown in Table 2. On the system interface, push the grid of alternative cruising destinations to taxi drivers in order of attractiveness from large to small. The push interface is shown in Figure 4.

Table 2 Attractiveness of Alternative Cruise Destination Grid

Claims (1)

1. A method for selecting a cruising destination based on taxi GPS track, characterized in that, comprising the steps: Step 1 Determine the cruising area in different time periods Divide 24 hours a day into 12 time periods, each time period is 2 hours, collect the road network traffic volume of any working day in the city for 24 hours, set the time period with the largest traffic volume as the peak time period, and set the time period for other periods as As the flat peak period, the maximum acceptable cruising radius R of taxis during peak hours is set to 3km, and the maximum acceptable cruising radius R of taxis during flat peak hours is set to 5km. The circular area where R is 3km is defined as the cruising area of the taxi during peak hours; the circular area with the current cruising starting point O of the taxi as the center and a radius R of 5 km is defined as the cruising area of the taxi during the peak hours; Step 2 Carry out grid division for the cruise area Step 2.1 Calculate the grid side length Divide the cruising area into square grids, first calculate the sum of the passenger points of all taxis in the cruising area the day before, denoted as Q, then calculate the area of the cruising area A=πR ² , and calculate the area of each grid S= 2A/Q, finally calculate the side length of each grid

Step 2.2 Rasterize the cruise area Take the latitude line passing through the current cruising starting point O as the benchmark, translate it upwards by L/2 to draw a parallel line, and then translate this parallel line upwards by L to draw a parallel line, and on this basis, sequentially translate upwards by k*L to draw a parallel line, k= 1, 2, 3, 4, ... until the line is tangent to or separated from the cruising area; similarly, using the latitude line passing through the current cruising starting point O as a reference, translate it downward by L/2 to draw a parallel line, Then translate the parallel line downward by L to draw a parallel line, and on this basis, sequentially translate downward by k*L to draw a parallel line, k=1, 2, 3, 4, ... until the line is tangent or intersecting with the cruise area stop when leaving; Based on the meridian passing through the current cruise starting point O, move it to the left by L/2 to draw a parallel line, then move the parallel line to the left by L to draw a parallel line, and then move to the left by k*L to draw a parallel line , k=1,2,3,4,..., until the line is tangent to or separated from the cruising area; similarly, take the meridian passing through the current cruising starting point O as a reference, and translate it to the right by L/2 draw Parallel line, then translate the parallel line to the right by L and draw a parallel line, on this basis, translate to the right by k*L to draw a parallel line, k=1,2,3,4,... until the line is in line with the cruise area Stop when tangent or separated; A square grid is formed by each latitude and longitude, and the grids crossed by the boundary of the cruise area are screened. If the center point of a grid is located in the cruise area, the grid is counted in the cruise area. On the contrary, if a certain If the center point of the grid is outside the cruising area, the grid is not included in the cruising area; Step 3 Determine the Alternative Cruise Destination Grid Record the sum of passenger loading points of all taxis in each grid in the cruising area as Q _n , n is the grid label, n=1, 2, 3, 4,..., N, N is the grid in the cruising area The total number of grids, the grids are sorted in descending order according to the value of Q _n , and the first 10 grids are used as grids of alternative cruising destinations, which are recorded as D _i , i=1,2,3,...,10 ; Step 4 Calculate the attractiveness of each alternative cruising destination grid Calculate the shortest travel time from the current cruising starting point O to each alternative cruising destination grid D _i according to the shortest path calculation method, denoted as t _i ; The sum of the number of passenger points of all taxis in the previous day in each alternative cruising destination grid is recorded as Q'_i; Apply formula 1 to calculate the land use intensity of each candidate cruising destination grid, where P _i is the population in the grid; M _i =P _i /S Formula 1 Calculate the attractiveness of each alternative cruising destination grid as: F _i ＝Q' _i ·M _i /t _i Formula 2 Step 5 Push the alternate cruising destination grid to the taxi On the system interface, the grids of alternative cruising destinations are pushed to taxi drivers in order of F _i from large to small.

Images