CN104951848A - Real-time car-pooling matching method - Google Patents
Real-time car-pooling matching method Download PDFInfo
- Publication number
- CN104951848A CN104951848A CN201510315033.XA CN201510315033A CN104951848A CN 104951848 A CN104951848 A CN 104951848A CN 201510315033 A CN201510315033 A CN 201510315033A CN 104951848 A CN104951848 A CN 104951848A
- Authority
- CN
- China
- Prior art keywords
- driver
- passenger
- share
- car
- expense
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
Disclosed is a real-time car-pooling matching method. The method includes the following steps: 1, modelling a real-time car-pooling scene; 2, performing real-time car-pooling matching, wherein the step 2 includes: 21, screening strategies based on maximum passenger waiting time of Euclidean distance; 22, screening strategies based on maximum car-pooling cost of Euclidean distance; 23, performing progressive Return screening; 24, performing progressive Pickup screening.
Description
Technical field
The invention belongs to position-based service (LBS, Location Based Service) Mobile solution field, to go on a journey the problems such as difficulty mainly for the increase sharply a series of traffic congestions, the people that cause of current city vehicle, a kind of dynamic share-car matching process is in real time proposed, can will be ready that the passenger carrying out share-car is mated with driver automatically, and then slow down above-mentioned traffic problems with the form of share-car.
Background technology
Share-car is as the effective means solving urban transport problems, and have mode flexible, governmental input cost is few, reduces empty wagons rate, reduces environmental pollution, shares the advantages such as travel cost.In recent years, along with the relieving gradually in the universal of smart mobile phone and location Based service (LBS) and relevant policies, share-car problem obtains industry member with its good prospect, the consistent concern of academia and investors.
In industry member, most of Carpooling system using forestland is: user selects the role of share-car, and the relevant information of input share-car is as starting point, terminal, time and expense etc.System has several disposal route afterwards: (1) waits for other user's manual pairings and phone contact confirms, does like this very inconvenient share-car both sides.(2) with call a taxi software class seemingly, the most contiguous driver of the K near Systematic selection passenger starting point, and the driver nearest from passenger is returned to passenger.The driver's possibility terminal found like this is far from passenger's terminal, causes share-car costly; (3) system only selects driver and the passenger of coincidence route.Greatly reduce the successful probability of share-car so undoubtedly; (4) system allows driver to specify the on-board and off-board place of passenger, and therefore passenger may need walking before getting on the bus or after getting off, such share-car mode underaction in actual applications.
In academia, the problem of share-car starts from the phone dial-a-cab (Dial-a-ride Service) of developed country, phone chauffeur is the service hotline subscription services needing people's (being generally the elderly or disabled person) of service to dial government, drives to visit according to the when and where of each service personnel that arrange work in dispatching center.In recent years, researchist mainly pays close attention to the dynamic matching method design of driver and passenger, but existing main flow matching process is mostly predicted based on the large-scale position of driver's wheelpath data to driver or carried out pre-service calculating to maximum shortest path consuming time in share-car matching process.These methods can ensure real-time high-efficiency, but the mode of prediction makes matching process accuracy in practice effectively to be ensured, and need to consume a large amount of space storage resources to the pre-service of shortest path.
Summary of the invention
The present invention will overcome the above-mentioned shortcoming of prior art, proposes a kind of dynamic share-car matching process in real time.The method final purpose is according to share-car demand during passenger real, matches the candidate driver's set meeting it and require efficiently.
The inventive method 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, this step to share-car expense Modling model, will define share-car problem, 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 the distance of passenger from passenger's starting point to passenger's terminal (the present invention, 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,r)
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, r) (formula 1)
The modeling of step 1-2 share-car matching process
In the share-car scene that the present invention is suitable for, 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_ArrTimewith maximum share-car expense r
max_Priceshare-car retrains; Driver has the position constraint of Origin And Destination.Therefore, share-car matching process is defined as follows by this method:
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, such as, d
1in 15 minutes, receive passenger, and involved share-car expense is 20 yuan, d
2the stand-by period and the share-car expense that are supplied to same passenger are 17 minutes and 25 yuan respectively, so, it is considered herein that d
2alternatively driver recommends passenger to such driver is nonsensical.Therefore matching technique of the present invention is in the middle of matching process, has also carried out corresponding skyline filtration treatment 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 of the present invention, 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, the present invention devises a series of beta pruning step, reduces shortest path number of computations as much as possible, and then improves 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_ArrTimethe 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_Pricedriver.
Use Euclidean distance to replace Pickup and Return in the middle of share-car expense Price (d, r) (i.e. formula 1), 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_Priceif 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 2-4
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_Pricethen 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.
Advantage of the present invention is:
1) share-car process Auto-matching.Only need the share-car constraint condition such as time, expense according to passenger and driver both sides, can gather for passenger finds out alternative driver on automated intelligent ground.Compare current share-car technology, the inventive method passes to without the need to the ditch carrying out manual mode and determines whether coupling.
2) share-car matching efficiency is high, can complete in real time.A large amount of shortest paths potential in share-car matching process calculate and are filtered by a series of technology of prunning branches in the present invention, and then can find out the driver meeting passenger's time and cost constraint in a short period of time.
Accompanying drawing explanation
Fig. 1 is the procedure chart of step 2 of the present invention and step 3
Fig. 2 is the gradual Return screening process figure of step 4 of the present invention
Fig. 3 is the gradual Pickup screening process figure of step 4 of the present invention
Fig. 4 is Euclidean distance Sample Filter
Fig. 5 is driver's match information table
Fig. 6 is Euclidean expense Sample Filter
Fig. 7 is gradual Return Sample Filter figure
Fig. 8 is gradual Pickup Sample Filter figure
Embodiment
With reference to accompanying drawing:
Fig. 1 represents the step 2 of this share-car matching process and the procedure chart of step 3.After the relevant information of known share-car driver and passenger, first calculate the maximum latency of passenger; Then with the starting point of passenger for the center of circle, using Euclidean distance corresponding to the maximum latency of passenger as radius, do a range query, the driver within the scope of this joined in match information table; Then to all drivers in match information table, formula 2 is used to calculate its share-car expense; Finally delete and allly exceed passenger's maximum share-car expense restriction driver.
Fig. 2 is the gradual Return screening process figure of step 4 of the present invention.First the driver that have passed two steps above in match information table is sorted by increasing progressively according to the value of EuclideanPickup-DriverTrip, then iterative computation in the following manner, until all drivers were investigated: with passenger's terminal for starting point, the k nearest neighbor algorithm of increment type is used to find the driver that in current table, Return value is minimum, calculate the expense of this driver by formula 3, and compare with the maximum share-car expense of passenger.If be greater than passenger's share-car expense, delete all drivers below this driver and this driver.
Fig. 3 is the gradual Pickup screening process figure of step 4 of the present invention.To above have passed in matching list driver in steps first sort by increasing progressively according to the value of Return-DriverTrip, and the maximum share-car expense that threshold values MAX is passenger is set.Then iterative computation in the following manner, until match information table is empty: first with the starting point of passenger for starting point, the k nearest neighbor algorithm of increment type is used to find the driver that in current table, Pickup value is minimum, compare with passenger maximum latency MAX_Pickup by this Pickup value, if be greater than MAX_Pickup, then remaining all drivers in delete list, stop coupling immediately, return candidate driver's set; If be less than this value, then calculate share-car expense by formula 1, and compare with MAX.If share-car expense is greater than MAX, then this driver is deleted from table, and delete all drivers below this driver; If be less than MAX, then MAX value is upgraded the share-car expense of driver for this reason, and this driver is joined candidate driver's set, finally from match information table, delete this driver.
Fig. 4-Fig. 8 shows a complete share-car coupling example.
Fig. 4 illustrates an example according to Euclidean distance screening driver.Suppose that passenger r (white point represents) arrives its terminal after requiring 35 minutes, and from then on the distance of the origin-to-destination of passenger needs to walk 20 minutes, the maximum latency that therefore can calculate this passenger is 15 minutes (within 35 minutes, deducting 20 minutes).So with the starting point of passenger for the center of circle, with the Euclidean distance corresponding to 15 minutes for radius does a range query, can see that driver's (stain represents) of the passenger's starting point that can arrive in the very nick of time has: d
1, d
2, d
3.。。d
6。
Fig. 5 is match information table.At figure
4driver d selected in Euclidean distance screening step
1, d
2, d
3.。。D
6will be packed in matching list.In table, the DriverTrip field of driver directly can be copied by the corresponding field during driver shows.
Fig. 6 is the example according to Euclidean expense screening driver.For all drivers in match information table, itself EuclideanPickup and EuclideanReturn of calculating is inserted in table, then calculates its Euclidean share-car expense EuclideanPrice according to formula 2.The r of passenger in this example
max_time=15, r
max_price=30, RiderTrip=12; The EuclideanPickup of driver, EuclideanReturn and DriverTrip are respectively as shown in Table.Driver d
6because of Euclidean share-car expense (7.3+12*2+9.1-8)=32.4>30, will can not meet the share-car expense restriction of passenger and be deleted by from matching list.
Fig. 7 is the example that gradual Return screens driver.Driver remaining in match information table is sorted from small to large according to the value of EuclideanPickup-DriverTrip, is followed successively by d
1, d
4, d
2, d
3, d
5.Then with passenger's terminal for starting point, use the k nearest neighbor algorithm of increment type, find the driver d of terminal and passenger's terminal in current matching information table (namely actual Return is minimum) recently
3and obtain its Return value 9.9.Then d
3share-car expense according to formula 3 calculates: (9.9+2*12+5.8-9.6)=30.1>30.D
3because the share-car expense restriction that can not meet passenger is excluded.And be positioned at d in matching list
3under driver d
5also be excluded.Now only be left driver d in matching list
1, d
4and d
2, its return value is respectively 14,7.5 and 8.3, all meets passenger's share-car expense restriction.
Fig. 8 is the example that gradual Pickup screens driver.First driver remaining in matching list is sorted according to Return-DriverTrip, be followed successively by d
4, d
2, d
1.And the value arranging MAX is the maximum share-car expense 30 of passenger.Then with the starting point of passenger for starting point, use the k nearest neighbor algorithm of increment type, find the driver d of starting point and passenger's starting point in matching list (namely Pickup value is minimum) recently
1, and obtain its Pickup value 6.5.Then d
1share-car expense according to cost formula 1 calculates: (6.5+12*2+14-13.4)=31.1>MAX=30, has exceeded expense restriction, therefore d
1d is positioned at in table
1following driver is by deleted.Now also be left driver d
4and d
2.
And then make to find next driver d
2, and to obtain its Pickup value be 7, share-car expense is (7+12*2+8.3-10)=29.3<MAX, therefore by driver d
2join alternative driver set, the value upgrading MAX is 29.3, and by d
2delete from match information table.
In like manner find next driver d again
4, obtaining its Pickup value is 8.2, and share-car expense is (8.2+12*2+7.5-10)=29.7>MAX, so d
4be excluded, because d
4do not meet skyline principle (d
4on passenger waiting time Pickup and share-car expense Price, be all greater than d simultaneously
2).
So far, all drivers have been investigated, and this matching process terminates, and return candidate driver and gather.
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_ArrTimewith maximum share-car expense r
max_Priceshare-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_ArrTimethe 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_Pricedriver;
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_Priceif 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_Pricethen 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.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510315033.XA CN104951848A (en) | 2015-06-10 | 2015-06-10 | Real-time car-pooling matching method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510315033.XA CN104951848A (en) | 2015-06-10 | 2015-06-10 | Real-time car-pooling matching method |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN104951848A true CN104951848A (en) | 2015-09-30 |
Family
ID=54166487
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201510315033.XA Pending CN104951848A (en) | 2015-06-10 | 2015-06-10 | Real-time car-pooling matching method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN104951848A (en) |
Cited By (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107101643A (en) * | 2017-04-10 | 2017-08-29 | 浙江工业大学 | Car pooling matching method |
| CN107798403A (en) * | 2016-09-07 | 2018-03-13 | 北京嘀嘀无限科技发展有限公司 | A kind of share-car order processing method, server, terminal device and system |
| CN108268965A (en) * | 2017-01-03 | 2018-07-10 | 北京嘀嘀无限科技发展有限公司 | For resource allocation, for the vehicles scheduling method and its device |
| CN108549959A (en) * | 2018-04-11 | 2018-09-18 | 车巴达（苏州）网络科技有限公司 | Automatic send a car method and device, computer readable storage medium, terminal |
| CN109791672A (en) * | 2017-08-16 | 2019-05-21 | 北京嘀嘀无限科技发展有限公司 | A kind of system and method for handling the request of share-car simultaneously |
| CN111178724A (en) * | 2019-12-23 | 2020-05-19 | 华南理工大学 | Carpooling scheduling method based on evolution algorithm |
| CN107103383B (en) * | 2017-03-28 | 2020-07-14 | 大连理工大学 | Dynamic taxi sharing scheduling method based on taxi-taking hotspot |
| CN111523702A (en) * | 2020-03-30 | 2020-08-11 | 深圳大学 | Optimization method, system, server and storage medium for taxi-boarding points of network appointment taxi |
| CN111739329A (en) * | 2020-05-29 | 2020-10-02 | 腾讯科技（深圳）有限公司 | Travel route generation method, travel route generation device, storage medium, and server |
| CN112766868A (en) * | 2021-03-12 | 2021-05-07 | 天天惠民(北京)智能物流科技有限公司 | Logistics vehicle distribution order matching method and device and computer equipment |
Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101216913A (en) * | 2008-01-11 | 2008-07-09 | 北京工业大学 | Multistage screening method of carpool dynamic matching |
| US8140256B1 (en) * | 2006-08-16 | 2012-03-20 | University Of South Florida | Dynamic ride matching system |
| CN103778588A (en) * | 2014-02-18 | 2014-05-07 | 钟磊 | Hitching car sharing method |
| US8909475B2 (en) * | 2013-03-08 | 2014-12-09 | Zzzoom, LLC | Generating transport routes using public and private modes |
| CN104217249A (en) * | 2014-07-02 | 2014-12-17 | 浙江工业大学 | Dynamic car sharing and matching method based on time and cost constraints |
| CN104318324A (en) * | 2014-10-13 | 2015-01-28 | 南京大学 | Taxi GPS (Global Positioning System) record based airport bus station and path planning method |
| CN104408910A (en) * | 2014-11-24 | 2015-03-11 | 无锡清华信息科学与技术国家实验室物联网技术中心 | Taxi-sharing scheduling method beneficial to multiple parties |
-
2015
- 2015-06-10 CN CN201510315033.XA patent/CN104951848A/en active Pending
Patent Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8140256B1 (en) * | 2006-08-16 | 2012-03-20 | University Of South Florida | Dynamic ride matching system |
| CN101216913A (en) * | 2008-01-11 | 2008-07-09 | 北京工业大学 | Multistage screening method of carpool dynamic matching |
| US8909475B2 (en) * | 2013-03-08 | 2014-12-09 | Zzzoom, LLC | Generating transport routes using public and private modes |
| CN103778588A (en) * | 2014-02-18 | 2014-05-07 | 钟磊 | Hitching car sharing method |
| CN104217249A (en) * | 2014-07-02 | 2014-12-17 | 浙江工业大学 | Dynamic car sharing and matching method based on time and cost constraints |
| CN104318324A (en) * | 2014-10-13 | 2015-01-28 | 南京大学 | Taxi GPS (Global Positioning System) record based airport bus station and path planning method |
| CN104408910A (en) * | 2014-11-24 | 2015-03-11 | 无锡清华信息科学与技术国家实验室物联网技术中心 | Taxi-sharing scheduling method beneficial to multiple parties |
Cited By (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107798403A (en) * | 2016-09-07 | 2018-03-13 | 北京嘀嘀无限科技发展有限公司 | A kind of share-car order processing method, server, terminal device and system |
| CN108268965A (en) * | 2017-01-03 | 2018-07-10 | 北京嘀嘀无限科技发展有限公司 | For resource allocation, for the vehicles scheduling method and its device |
| CN107103383B (en) * | 2017-03-28 | 2020-07-14 | 大连理工大学 | Dynamic taxi sharing scheduling method based on taxi-taking hotspot |
| CN107101643B (en) * | 2017-04-10 | 2019-10-29 | 浙江工业大学 | Car pooling matching method |
| CN107101643A (en) * | 2017-04-10 | 2017-08-29 | 浙江工业大学 | Car pooling matching method |
| CN109791672A (en) * | 2017-08-16 | 2019-05-21 | 北京嘀嘀无限科技发展有限公司 | A kind of system and method for handling the request of share-car simultaneously |
| CN108549959A (en) * | 2018-04-11 | 2018-09-18 | 车巴达（苏州）网络科技有限公司 | Automatic send a car method and device, computer readable storage medium, terminal |
| CN111178724A (en) * | 2019-12-23 | 2020-05-19 | 华南理工大学 | Carpooling scheduling method based on evolution algorithm |
| CN111523702A (en) * | 2020-03-30 | 2020-08-11 | 深圳大学 | Optimization method, system, server and storage medium for taxi-boarding points of network appointment taxi |
| CN111523702B (en) * | 2020-03-30 | 2023-01-13 | 深圳大学 | Optimization method, system, server and storage medium for taxi-boarding points of network appointment taxi |
| CN111739329A (en) * | 2020-05-29 | 2020-10-02 | 腾讯科技（深圳）有限公司 | Travel route generation method, travel route generation device, storage medium, and server |
| CN111739329B (en) * | 2020-05-29 | 2021-11-02 | 腾讯科技（深圳）有限公司 | Travel route generation method, travel route generation device, storage medium, and server |
| CN112766868A (en) * | 2021-03-12 | 2021-05-07 | 天天惠民(北京)智能物流科技有限公司 | Logistics vehicle distribution order matching method and device and computer equipment |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN104951848A (en) | Real-time car-pooling matching method | |
| CN104217249B (en) | A kind of dynamic share-car matching process based on time Yu expense restriction | |
| CN111366160B (en) | Path planning method, path planning device and terminal equipment | |
| DE102013202059B4 (en) | CHARGER INFRASTRUCTURE FOR ELECTRIC VEHICLES (EVs) WITH OPTIMUM LOCATION SELECTION FOR CHARGING STATIONS | |
| CN104464274B (en) | Rideshare is called a taxi method and server | |
| CN107101643B (en) | Car pooling matching method | |
| CN103134505B (en) | Path planning system and method thereof | |
| US10157242B2 (en) | Charger arrangement planning supporting apparatus, charger arrangement planning supporting method, and program | |
| DE102019100796A1 (en) | METHOD AND DEVICE FOR ROUTE PLANNING INCLUDING LOADING NEEDS | |
| CN109460936A (en) | A kind of public transit vehicle smart shift scheduling method, intelligent terminal and storage medium | |
| CN106908065A (en) | The double-deck path construction method and system of vehicle boarded unmanned plane | |
| CN103308062A (en) | Route planning and matching system and method as well as device and terminal of system | |
| CN106991727A (en) | A kind of method and system of highway intercommunication charging | |
| CN106097060A (en) | A kind of university students is left unused Cycle Hire software screening method system and its implementation | |
| CN111325436A (en) | Network appointment vehicle co-operation passenger matching method and system, storage medium and server | |
| CN105989177A (en) | Bus information inquiring method and bus information inquiring apparatus | |
| CN110379198A (en) | A kind of city intelligent stopping guide system and its parking guide method | |
| CN107167151A (en) | Bus routes method to set up, route planning method and device | |
| WO2021227416A1 (en) | Electric vehicle energy management method, electric vehicle energy management apparatus and server | |
| CN117294577A (en) | Method and system for quickly recovering information physical collaboration of elastic power distribution network | |
| CN109523827A (en) | Underground parking lot parking system | |
| CN112669604B (en) | Urban traffic scheduling method and device | |
| CN114036411A (en) | Route planning method, device, equipment and medium | |
| CN116307580A (en) | Method and device for scheduling capacity, electronic equipment and storage medium | |
| CN113222248B (en) | Automatic taxi-driving charging pile selection method |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WD01 | Invention patent application deemed withdrawn after publication | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20150930 |