CN104951848A - Real-time car-pooling matching method - Google Patents

Abstract

A real-time carpool matching method, comprising the steps of: step 1 real-time carpool scene modeling; step 2, real-time carpool matching, step 2 includes: step 21 passenger maximum waiting time screening strategy based on Euclidean distance; step 22 based on Euclidean distance Maximum carpool cost screening strategy; Step 23 progressive Return screening; Step 24 progressive Pickup screening.

Description

A real-time carpool matching method

technical field

The invention belongs to the mobile application field of location-based service (LBS, Location Based Service), and mainly aims at a series of traffic jams caused by the surge of urban vehicles, people's travel difficulties, etc., and proposes a real-time dynamic carpooling matching method, which can automatically Match passengers who are willing to carpool with drivers, and then alleviate the above traffic problems in the form of carpooling.

Background technique

As an effective means to solve urban traffic problems, carpooling has the advantages of flexible methods, low government investment costs, reduced empty car rates, reduced environmental pollution, and shared travel costs. In recent years, with the popularization of smartphones and location-based services (LBS) and the gradual liberalization of related policies, carpooling has attracted unanimous attention from industry, academia and investors with its promising prospects.

In the industry, most of the carpooling systems are used in the following mode: the user selects the carpooling role, and enters carpooling related information such as starting point, destination, time and cost. Afterwards, the system has several processing methods: (1) Waiting for other users to manually pair and call for confirmation, which is very inconvenient for both carpooling parties. (2) Similar to taxi-hailing software, the system selects the K closest drivers near the passenger's starting point, and returns the driver closest to the passenger to the passenger. The driver found in this way may have a very far end point from the passenger end point, resulting in high carpooling costs; (3) the system only selects drivers and passengers with overlapping routes. This undoubtedly greatly reduces the probability of successful carpooling; (4) the system allows the driver to specify the pick-up and drop-off locations of passengers, so passengers may need to walk before getting on or after getting off the car. Such a carpooling method is not flexible enough in practical applications.

In academia, the problem of carpooling began with the Dial-a-ride Service in developed countries. Dial-a-ride Service is when people who need services (usually the elderly or disabled) call the government's service hotline to make an appointment. The dispatch center arranges staff to drive to the door according to the time and place of each service. In recent years, researchers have mainly focused on the design of dynamic matching methods for drivers and passengers. However, most of the existing mainstream matching methods are based on large-scale driver trajectory data to predict the driver's location or to predict the shortest time-consuming match in the carpooling process. path for preprocessing calculations. These methods can guarantee real-time efficiency, but the prediction method makes the accuracy of the matching method in practice unable to be effectively guaranteed, and the preprocessing of the shortest path needs to consume a large amount of space and storage resources.

Contents of the invention

The present invention overcomes the above-mentioned shortcomings of the prior art, and proposes a real-time dynamic carpooling matching method. The ultimate goal of this method is to efficiently match a set of candidate drivers that meet passengers' real-time carpooling needs.

The inventive method comprises the steps:

Step 1 Real-time carpooling scene modeling

In the actual carpooling scenario, both the passenger and the driver have a starting point and an ending point. In addition, the passenger also has requirements for the latest arrival time at the destination and the maximum carpooling fee. In order to realize carpool matching, this step will establish a model for carpooling fees, define the carpooling problem, and design the data structure in the process of carpooling matching.

Step 1-1 Carpool Fee Modeling

In the process of carpooling, driver d first needs to drive from his starting point to passenger r’s starting point, then drive the passenger from passenger r’s starting point to his destination point, and finally return from passenger r’s end point to his own destination point. After the carpooling is over, the passenger r needs to pay a certain carpooling fee to the driver as a reward.

According to the above carpooling process, the carpooling fee in this method is defined as follows:

Price(d,r)=RiderTrip(r)+Detour(d,r)

Wherein Price (d, r) represents the cost of carpooling; RiderTrip (r) represents the distance that the driver and the passenger walk together after the carpooling, that is, the distance that the driver carries the passenger from the passenger's starting point to the passenger's terminal point (distance, cost and time in the present invention are all related to The distance is proportional, so it can be transformed into each other); Detour(d,r) represents the distance that the driver takes more than the original route, that is, the detour distance, and its calculation method is as follows:

Detour(d,r)=Pickup(d,r)+RiderTrip(r)+Return(d,r)–DriverTrip(d,r)

Among them, Pickup(d,r) is the distance between the driver’s starting point and the passenger’s starting point, that is, the driver’s fare when picking up the passenger; Return(d,r) represents the distance between the driver’s destination and the passenger’s The cost of returning when the passenger is finished; DriverTrip(d,r) refers to the driver's original distance without picking up the passenger.

Based on the above relationship, the following formula for calculating the cost of carpooling can be further obtained:

Price(d,r)＝Pickup(d,r)+2*RiderTrip(r)+Return(d,r)–DriverTrip(d,r) (Formula 1)

Step 1-2 Modeling of carpool matching process

In the carpooling scene to which the present invention is applicable, passengers and drivers have their own carpooling constraints. Among them, the passenger has the carpooling constraints of the starting point and the ending point, and the carpooling constraints of the latest arrival time r _{max_ArrTime} and the maximum carpooling fee r _{max_Price} ; the driver has the location constraints of the starting point and the ending point. Therefore, this method defines the carpool matching process as follows:

Definition 1. Given a set of drivers D and a passenger r, carpool matching aims to find a subset D’ in D, and for any driver d in D’, the following constraints need to be met:

Time constraints: Pickup(d,r)+RiderTrip(r)<r _{max_ArrTime}

Cost constraint: Price(d,r)<r _{max_Price}

·Skyline constraint: Each driver in D' has a skyline relationship between Pickup(d,r) and Price(d,r).

The Skyline constraint means that there is a skyline relationship between the drivers in the set D' on the two attributes of passenger arrival time and carpooling cost, that is, any driver will not be greater than the driver in another set in terms of waiting time and carpooling cost at the same time . Otherwise, it is meaningless to choose this driver. For example, d1 picks up the passenger within ₁₅ minutes, and the carpooling fee involved is 20 yuan, and the waiting time and carpooling fee provided by _d2 to the same passenger are 17 minutes and 25 yuan respectively , then, the present invention considers that it is meaningless to recommend a driver like d ₂ to a passenger as a candidate driver. Therefore, during the matching process, the matching technology of the present invention also performs corresponding skyline filtering processing for this type of drivers.

Step 1-3 carpooling data structure design

In order to facilitate subsequent carpool matching calculations, record candidate drivers and the matching process, it is necessary to design relevant carpool data structures. That is, the following two tables:

Driver Information Table (Driver Table): There are four fields in this table, which are used to record the relevant information of the driver. Including: 1) The driver's unique ID; 2) The driver's current location CurrentLocation; 3) The driver's destination location Destination; 4) The driver's distance from the current location to the destination DriverTrip.

Matching Table: This table has a total of 6 fields, which are used as the basis for carpool matching records and calculations. Including: 1) The driver's unique ID; 2) The shortest actual path Pickup between the driver's starting point and the passenger's starting point, which can be converted into the passenger's actual waiting time; (3) Euclidean Pickup between the driver's starting point and the passenger's starting point; 4 ) the shortest actual path Return between the driver's destination and the passenger's destination; 5) the Euclidean Return between the driver's destination and the passenger's destination; 6) the shortest path DriverTrip between the driver's starting point and the destination, that is, the first 4 fields. Step 2, real-time carpool matching;

In the application scene of the present invention, there will be a large number of drivers and passengers participating in each carpooling matching process, there are a large number of shortest paths between drivers and passengers to be calculated, and these calculations are very time-consuming, which seriously affects the real-time carpooling scene. application. For this reason, the present invention designs a series of pruning steps to reduce the number of calculations of the shortest path as much as possible, thereby improving the efficiency of carpool matching.

Step 2-1 Passenger maximum waiting time screening strategy based on Euclidean distance

The core idea of this step is to use the latest arrival time of passengers as a constraint condition, and convert this condition into Euclidean distance to filter drivers.

●Time constraint transformation: the time for passengers to reach their destination is the sum of the waiting time Pickup and the time RiderTrip corresponding to the journey from the origin to the destination. Since the passenger RiderTrip is a fixed value, the passenger's maximum waiting time Max_Pickup can be obtained by subtracting the passenger's latest arrival time r _{max_ArrTime} from the time corresponding to the passenger's RiderTrip. Namely: Max_Pickup = r _{max_ArrTime} - Pickup. Therefore, the latest arrival time of passengers is converted into the maximum waiting time, that is, the driver's Pickup value cannot exceed Max_Pickup.

● Euclidean range query and screening: In order to exclude drivers who cannot arrive at their starting point within the passenger's maximum waiting time Max_Pickup, the screening method of Euclidean range query can be used. First convert the time Max_Pickup into the corresponding Euclidean distance (multiply Max_Pickup by the current average vehicle speed of the road network), then use the current starting point of the passenger as the center of the circle, and use the Euclidean distance corresponding to Max_Pickup as the radius to make a circular range query ( Range Query). All drivers who are not within this circular range will be excluded because they cannot reach the passenger's starting point in time under the condition of the shortest distance (Euclidean Pickup).

Step 2-2 Screening strategy for maximum carpooling cost based on Euclidean distance

Drivers who pass the Euclidean distance screening in the previous step will be added to the matching information table and further screened using the passenger's maximum carpooling fee constraint, excluding the required carpooling fee under the Euclidean distance exceeding the passenger's maximum carpooling fee r _{max_Price} driver.

Replace the Pickup and Return in the carpooling fee Price(d,r) (that is, formula 1) with the Euclidean distance to get the Euclidean carpooling fee formula:

EuclideanPrice(d,r)=EuclideanPickup(d,r)+2*RiderTrip(r)+

EuclideanReturn–DriverTrip(d) (Formula 2)

Because the actual distance of the road network is greater than the Euclidean distance, if the driver’s ideal carpooling price EuclideanPrice(d,r) calculated by using formula 2 is greater than r _{max_Price} , then according to the transitivity of the inequality, the actual cost Price(d ,r) will also be greater than r _{max_Price} . Therefore, these drivers do not meet the passenger's maximum carpooling fee conditions and will be excluded.

So far, step 1 and step 2 have not produced any shortest path distance calculation, and only a simple Euclidean distance calculation can filter out some drivers.

Next, for the drivers screened through the above two steps, the matching table will be reordered, and the driver's Return and Pickup will be searched and screened gradually, and finally the candidate driver will be selected for passengers according to the skyline principle.

Step 2-3 Progressive Return Screening

For each driver in the matching record table, first sort by increasing the value of EuclideanPickup-DriverTrip, and then iteratively select drivers from the matching table for judgment and screening, until all drivers in the matching table are calculated or to be excluded. The iterative process is as follows:

a) Taking the passenger's destination as the starting point, use the incremental K Nearest Neighbor algorithm (Incremental K Nearest Neighbor) to find the driver whose Return value in the current matching record table is the smallest, that is, the destination in the actual road network is closest to the passenger's destination.

b) Use this real Return value to replace the Euclidean Return value in the cost formula of EuclideanPrice(d,r) (Formula 2) to get a new cost formula:

Semi-EuclideanPricePrice(d,r)=EuclideanPickup(d,r)+2*RiderTrip(r)+

Return(d,r)–DriverTrip(d) (Formula 3)

c) Determine whether the price calculated according to formula 3 exceeds the passenger's maximum carpooling price r _{max_Price} , and if it exceeds the cost constraint, delete the driver d from the matching information table. Because the fee required by the driver d to provide carpooling services is greater than the maximum carpooling fee that passengers can provide. At the same time, delete all drivers below driver d in the matching table, because the Euclidean Pickup-DriverTrip and Return values of these drivers below are both greater than d, and the carpooling fee must also be greater than d.

d) Go to the next iteration process.

Step 2-4 Progressive Pickup Screening

For all drivers in the matching information table that have passed the progressive Return screening, first set a threshold MAX, initialize its value as the passenger cost constraint r _{max_Price} , and then sort in increasing order by the value of Return-DriverTrip, and then iteratively start from the matching The drivers are selected from the table for judgment and screening, and finally the drivers who meet the skyline conditions are added to the candidate driver set until all the drivers are processed. The iterative process is as follows:

e) Taking the starting point of the passenger as the starting point, use the incremental K Nearest Neighbor algorithm (Incremental K Nearest Neighbor) to find the driver d whose Pickup value is the smallest in the current matching record table, that is, the starting point in the actual road network is closest to the passenger’s starting point.

f) Use this real Pickup value to compare it with the maximum passenger waiting time Max_Pickup. If it is greater than the maximum passenger waiting time, it means that d cannot meet the passenger's time constraints. Obviously, the pickups of the remaining drivers in the table will be greater than d, so Delete driver d and all remaining drivers in the table. This matching is over, and the set of candidate drivers is returned.

g) If the real Pickup is less than the passenger's maximum waiting time, the carpooling fee in Formula 1 is calculated based on the Pickup value and the real Return value obtained by driver d in the Return screening stage, and this fee will also be the actual fee provided by driver d. If the fee exceeds MAX, driver d and all drivers below him will be deleted because the skyline fee principle is not met.

h) If the actual carpooling cost of the driver is less than MAX, add the driver to the candidate driver set, update the value of MAX to the carpooling cost of the driver, and delete the driver from the matching information table. The value of MAX is updated because all matching drivers that are eventually returned require a skyline relationship. Compared with the previous candidate driver, the new candidate driver has a larger Pickup than the previous driver, so the carpool fee charged by him should be smaller than that of the previous candidate driver in order to be a candidate driver.

i) Go to the next iteration process.

The advantages of the present invention are:

1) Carpooling process is automatically matched. It only needs to automatically and intelligently find out a set of alternative drivers for passengers based on carpooling constraints such as time and cost of both passengers and drivers. Compared with the current carpooling technology, the method of the present invention does not require manual communication to determine whether to match.

2) Carpool matching is efficient and can be completed in real time. A large number of potential shortest path calculations in the carpool matching process are filtered by a series of pruning techniques in the present invention, so that drivers who meet the passenger time and cost constraints can be found in a very short time.

Description of drawings

Fig. 1 is the process chart of step 2 and step 3 of the present invention

Fig. 2 is the progressive Return screening process figure of step 4 of the present invention

Fig. 3 is the progressive Pickup screening process diagram of step 4 of the present invention

Figure 4 is an example of Euclidean distance screening

Figure 5 is the driver matching information table

Figure 6 is an example of Euclidean fee screening

Figure 7 is an example of progressive Return screening

Figure 8 is an example of progressive Pickup screening

Detailed ways

Refer to attached picture:

Fig. 1 shows the process diagram of step 2 and step 3 of the carpool matching method. After knowing the relevant information of carpool drivers and passengers, first calculate the maximum waiting time of passengers; then use the starting point of passengers as the center of the circle, and use the Euclidean distance corresponding to the maximum waiting time of passengers as the radius to do a range query. The drivers within the range are added to the matching information table; then, for all drivers in the matching information table, the carpooling fee is calculated using formula 2; finally, all drivers exceeding the passenger's maximum carpooling fee constraint are deleted.

Fig. 2 is a diagram of the progressive Return screening process in Step 4 of the present invention. For the drivers who have passed the above two steps in the matching information table, they are firstly sorted in ascending order according to the value of EuclideanPickup-DriverTrip, and then iteratively calculated in the following way until all drivers have been examined: starting from the passenger terminal, using incremental The K-Nearest Neighbor Algorithm finds the driver with the smallest Return value in the current table, calculates the driver's cost according to formula 3, and compares it with the passenger's maximum carpooling cost. If it is greater than the passenger's carpooling fee, delete the driver and all drivers under the driver.

Fig. 3 is a progressive Pickup screening process diagram of Step 4 of the present invention. The drivers who have passed all the above steps in the matching table are first sorted in ascending order according to the value of Return-DriverTrip, and the threshold MAX is set as the passenger's maximum carpooling fee. Then iteratively calculate in the following way until the matching information table is empty: First, use the incremental K-nearest neighbor algorithm to find the driver with the smallest Pickup value in the current table, using the passenger’s starting point as the starting point, and use this Pickup value and the passenger’s maximum waiting time MAX_Pickup Compare, if it is greater than MAX_Pickup, delete all the remaining drivers in the table, terminate the matching immediately, and return the set of candidate drivers; if it is less than this value, calculate the carpooling fee according to formula 1, and compare it with MAX. If the carpooling fee is greater than MAX, delete this driver from the table, and delete all drivers below this driver; if it is less than MAX, update the MAX value to the carpooling fee of this driver, and add this driver to the candidate driver set, Finally delete this driver from the matching information table.

Figures 4-8 show a complete carpool matching example.

Figure 4 shows an example of filtering drivers based on Euclidean distance. Assume that passenger r (indicated by the white dot) requires 35 minutes to arrive at its destination, and it takes 20 minutes to travel from the passenger's starting point to the destination, so it can be calculated that the passenger's maximum waiting time is 15 minutes (35 minutes minus 20 minutes ). Then take the starting point of the passenger as the center of the circle, and use the Euclidean distance corresponding to 15 minutes as the radius to make a range query, and you can see that the drivers (indicated by black dots) who can arrive at the starting point of the passenger in time are: d ₁ , d ₂ , d ₃ . . . d ₆ .

Figure 5 is the matching information table. The drivers d ₁ , d ₂ , and d ₃ selected in the Euclidean distance screening step in FIG. 4 . . . d ₆ will be filled in the matching table. The DriverTrip field of the driver in the table can be directly copied from the corresponding field in the driver table.

Figure 6 is an example of screening drivers based on Euclid fees. For all drivers in the matching information table, their EuclideanPickup and EuclideanReturn will be calculated and filled in the table, and then their EuclideanPrice will be calculated according to formula 2. In this example, the passenger's r _{max_time} = 15, r _{max_price} = 30, RiderTrip = 12; the driver's EuclideanPickup, EuclideanReturn and DriverTrip are shown in the table respectively. Driver d ₆ will be deleted from the matching table because the Euclid carpooling fee (7.3+12*2+9.1-8)=32.4>30 cannot satisfy the passenger's carpooling fee constraint.

Figure 7 is an example of progressive Return screening drivers. For the remaining drivers in the matching information table, they are sorted according to the value of EuclideanPickup-DriverTrip from small to large, in order of d ₁ , d ₄ , d ₂ , d ₃ , and d ₅ . Then take the passenger’s destination as the starting point and use the incremental K-nearest neighbor algorithm to find the driver d ₃ whose destination is closest to the passenger’s destination in the current matching information table (that is, the actual Return is the smallest) and obtain its Return value of 9.9. Then d ₃ is the carpooling fee calculated according to formula 3: (9.9+2*12+5.8-9.6)=30.1>30. d ₃ is excluded because it cannot satisfy the passenger's carpool cost constraint. And the driver _d5 below _d3 in the matching table is also excluded. At this time, only drivers d ₁ , d ₄ and d ₂ are left in the matching table, and their return values are 14, 7.5 and 8.3 respectively, all of which meet the passenger carpooling cost constraints.

Figure 8 is an example of progressive pickup screening drivers. Firstly, the remaining drivers in the matching table are sorted according to Return-DriverTrip, which are d ₄ , d ₂ , and d ₁ in turn. And set the value of MAX as the passenger's maximum carpooling fee of 30. Then, using the passenger’s starting point as the starting point, use the incremental K-nearest neighbor algorithm to find the driver d ₁ whose starting point is closest to the passenger’s starting point in the matching table (that is, the minimum Pickup value), and obtain its Pickup value of 6.5. Then d ₁ calculates the carpooling cost according to the cost formula 1: (6.5+12*2+14-13.4)=31.1>MAX=30, which exceeds the cost constraint, so d ₁ and drivers below d ₁ in the table are all Will be deleted. At this point the drivers d ₄ and d ₂ remain.

Then find the next driver d ₂ , and get its Pickup value of 7, the carpooling fee is (7+12*2+8.3-10)=29.3<MAX, so add driver d ₂ to the candidate driver set, update The value of MAX is 29.3 and _d2 is removed from the matching information table.

Similarly, find the next driver d ₄ , get its Pickup value of 8.2, and the carpooling fee is (8.2+12*2+7.5-10)=29.7>MAX, so d ₄ is excluded because d ₄ does not satisfy the skyline principle ( d ₄ is greater than d ₂ in both passenger waiting time Pickup and carpooling price Price.

So far, all drivers have been inspected, the matching process is over, and the set of candidate drivers can be returned.

Claims (1)

1. a real time pooling vehicle matching process, comprises the steps:

Step 1 real time pooling vehicle scene modeling;

In actual share-car scene, passenger and driver all have starting point and terminal, and in addition, passenger also has the requirement arriving destination time and maximum share-car expense at the latest; In order to realize share-car coupling, to share-car expense Modling model, share-car problem will be defined, and designs the data structure in share-car matching process;

Step 1-1 share-car Cost Modeling;

In share-car process, first driver d needs the starting point of arriving in passenger r from the starting point of oneself, then from the starting point of passenger r, passenger is loaded onto its terminal, finally gets back to the terminal of oneself from the terminal of passenger r; After share-car terminates, passenger r needs to pay certain share-car expense to driver in reward;

According to above-mentioned share-car process, the share-car expense in this method is defined as follows:

Price(d,r)＝RiderTrip(r)+Detour(d,r)

Wherein Price (d, r) represents share-car expense; The distance that after RiderTrip (r) represents share-car, driver and passenger walk jointly, namely driver carries passenger from passenger's starting point to the distance of passenger's terminal, and distance, expense and time are all directly proportional to distance, therefore can transform mutually; Detour (d, r) represents the distance that driver walks relative to its original route more, and namely detour distance, and its account form is as follows:

Detour(d,r)＝Pickup(d,r)+RiderTrip(r)+Return(d,r)–DriverTrip(d)

Wherein, Pickup (d, r) is the distance between driver's starting point and passenger's starting point, and namely driver goes expense when meeting passenger; Return (d, r) represents the path distance between driver destination and the destination of the passenger, i.e. the expense that returned when having sent passenger of driver; DriverTrip (d, r) refers to driver's oneself original distance when not picking passenger;

Based on above-mentioned relation, the following formula calculating share-car expense can be obtained further:

Price (d, r)=Pickup (d, r)+2*RiderTrip (r)+Return (d, r) – DriverTrip (d) (formula 1)

The modeling of step 1-2 share-car matching process;

In share-car scene, passenger and driver have its respective share-car constraint condition; Wherein passenger has the share-car of starting point, terminal to retrain, and at the latest time of arrival r _{max_ArrTime}with maximum share-car expense r _{max_Price}share-car retrains; Driver has the position constraint of Origin And Destination; Therefore, share-car matching process is defined as follows:

Define 1. given drivers and gather a D and passenger r, share-car coupling is intended to find a subclass D ' in D, and for any one the driver d in D ', demand fulfillment retrains as follows:

Time-constrain: Pickup (d, r)+RiderTrip (r) <r _{max_ArrTime}

Expense restriction: Price (d, r) <r _{max_Price}

Skyline retrains: each driver in D ' is skyline relation on Pickup (d, r) with Price (d, r);

Skyline constraint refers to that between driver in set D ' and driver be skyline relation on passenger's time of arrival and share-car expense two attributes, namely any one driver can not be greater than on stand-by period and share-car expense simultaneously another gather in driver; Otherwise select this driver then there is no practical significance; Therefore, in the middle of matching process, also corresponding skyline filtration treatment has been carried out to the driver of this class;

Step 1-3 share-car Data Structure Design;

For the ease of follow-up share-car matching primitives, record alternative driver and matching process, need the share-car data structure that design is relevant; I.e. following two forms:

Driver information table (Driver Table): this table has four fields, for recording the relevant information of driver; Comprise: 1) driver's unique ID; 2) driver current location CurrentLocation; 3) the destination locations Destination of driver; 4) driver needs the distance DriverTrip of process from current location to destination;

Matched record table (Matching Table): this table has 6 fields, as the foundation of share-car matched record and calculating; Comprise: 1) driver's unique ID; 2) the shortest Actual path Pickup between driver's starting point and passenger's starting point, this value can convert and be expressed as the actual stand-by period of passenger; (3) the Euclidean distance EuclideanPickup between driver's starting point and passenger's starting point; 4) the shortest Actual path Return between driver destination and the destination of the passenger; 5) the Euclidean distance EuclideanReturn between driver destination and the destination of the passenger; 6) the shortest path DriverTrip between the starting point of driver and destination, the 4th field namely in Driver Table;

Step 2, real time pooling vehicle mates;

In use scenes, have a large amount of drivers and passenger participates in, in each share-car matching process, have the shortest path between a large amount of drivers and passenger to need to calculate, and these calculating are very consuming time, had a strong impact on the application of real time pooling vehicle scene; For this reason, devise a series of beta pruning step, reduce shortest path number of computations as much as possible, and then improve the efficiency of share-car coupling;

Step 2-1 is based on passenger's maximum latency screening strategy of Euclidean distance;

The core thinking of this step uses the time of arrival at the latest of passenger as constraint condition, this condition is converted into Euclidean distance and screens driver;

● time-constrain transforms: the time RiderTrip sum that the distance that the time that passenger arrives its destination is its stand-by period Pickup with it from starting point to destination is corresponding; Because passenger RiderTrip is definite value, therefore by r time of arrival at the latest of passenger _{max_ArrTime}the time corresponding with the RiderTrip of passenger subtracts each other the maximum latency Max_Pickup that can obtain passenger; That is: Max_Pickup=r _{max_ArrTime}– Pickup; Therefore be converted into maximum latency the time of arrival at the latest of passenger, namely the Pickup value of driver can not more than Max_Pickup;

● Euclidean range query screens: in order to the driver that can not arrive in its starting point in passenger maximum latency Max_Pickup gets rid of, can adopt the screening mode of Euclidean range query; First time Max_Pickup is converted into corresponding Euclidean distance (being multiplied by current road network average speed with Max_Pickup), then with the current starting point of passenger for the center of circle, with Euclidean distance corresponding to Max_Pickup for radius does a circular range query (Range Query); All drivers not in this circular scope will be excluded, and reason is that they also cannot arrive in the very nick of time passenger's starting point under the condition of bee-line (Euclidean distance EuclideanPickup);

Step 2-2 is based on the maximum share-car expense screening strategy of Euclidean distance;

To the driver that have passed the screening of previous step Euclidean distance, will be added in match information table, and utilize the maximum share-car expense restriction of passenger to screen further, get rid of share-car expense needed under Euclidean distance and exceed the maximum share-car expense r of passenger _{max_Price}driver;

Use Euclidean distance to replace the Pickup (d, r) in the middle of share-car expense Price (d, r) (i.e. formula 1) and Return (d, r), obtain Euclidean share-car cost formula:

EuclideanPrice(d,r)＝EuclideanPickup(d,r)+2*RiderTrip(r)+

EuclideanReturn – DriverTrip (d) (formula 2)

Because road network actual range is greater than Euclidean distance, if so the desirable share-car expense EuclideanPrice (d, r) that driver uses formula 2 to calculate is greater than r _{max_Price}, then according to the transitivity of inequality, the actual cost Price (d, r) drawn with formula 1 also will be greater than r _{max_Price}; Therefore this part driver does not meet the maximum share-car fee condition of passenger, will be excluded;

So far, step 1 and step 2 all do not produce any shortest path distance and calculate, and only utilize simple Euclidean distance to calculate and can filter out a part of driver;

Below, for the driver by two steps screenings above, will be reordered by matching list, the search gradual to driver Return and Pickup and screening are finally the driver that passenger selects candidate according to the principle of skyline;

The gradual Return screening of step 2-3;

For every driver in matched record table, first sorted by increasing progressively by the value of EuclideanPickup-DriverTrip, then from matching list, pick out driver iteratively carry out judging and screening, until all drivers all in matching list are by calculated or be excluded; Iterative process is as follows:

A) with passenger's terminal for starting point, use the k nearest neighbor algorithm (Incremental K Nearest Neighbor) of increment type, find Return value in current matching record sheet minimum, the terminal namely in actual road network and the nearest driver of passenger's terminal;

B) use the EuclideanReturn value in this true Return value replacement EuclideanPrice (d, r) (formula 2) cost formula, obtain new cost formula:

Semi-EuclideanPricePrice(d,r)＝EuclideanPickup(d,r)+2*RiderTrip(r)+

Return (d, r) – DriverTrip (d) (formula 3)

C) judge whether the expense calculated according to formula 3 exceedes the maximum share-car expense r of passenger _{max_Price}if exceed this expense restriction, then this driver d is deleted from match information table; Because the maximum share-car expense that driver d provides the expense needed for Ride-share service to be greater than passenger can be provided; Delete all drivers in matching list below d driver, because EuclideanPickup-DriverTrip and the Return value of these drivers of below is all greater than d, share-car expense also must be greater than d simultaneously;

D) next iterative process is entered;

The gradual Pickup screening of step 24;

For drivers that have passed gradual Return and screen all in match information table, first arrange a threshold values MAX, its value of initialization is passenger's expense restriction r _{max_Price}then sorted by incremental order by the value of Return – DriverTrip, then from matching list, pick out driver iteratively carry out judging and screening, finally the driver meeting skyline condition is added alternative driver set, until all drivers are processed complete; Iterative process is as follows:

E) with passenger's starting point for starting point, use the k nearest neighbor algorithm (Incremental K Nearest Neighbor) of increment type, find Pickup value in current matching record sheet minimum, i.e. starting point and the nearest driver d of passenger's starting point in actual road network;

F) this true Pickup value is used, make comparisons with passenger maximum latency Max_Pickup, if be greater than passenger's maximum latency, then represent that d cannot meet the time constraint condition of passenger, the Pickup of driver remaining in obvious table will be greater than d, therefore all drivers remaining in driver d and table all be deleted; This mates end, returns candidate driver's set;

If g) true Pickup is less than the maximum latency of passenger, then the share-car expense of the true Return value computing formula 1 obtained at Return screening stage according to this Pickup value and driver d, this expense also will be the actual cost that driver d provides; If this expense has exceeded MAX, then because do not meet skyline cost principle, all drivers below driver d and its are all deleted;

If h) the actual share-car expense of this driver is less than MAX, then this driver is added alternative driver set, the share-car expense of the value then upgrading MAX driver for this reason, then this driver is deleted from match information table; The value upgrading MAX is because all coupling driver requests finally returned are skyline relations; And the relatively previous candidate driver of new candidate driver, because its Pickup is larger than previous driver, thus its share-car expense collected be less than a upper candidate driver could alternatively driver;

I) next iterative process is entered.