Method for allocating trip sharing

• US 8,498,953 B2
• Filed: 03/30/2010
• Issued: 07/30/2013
• Est. Priority Date: 03/30/2010
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Lehmann, Jens, Sommer, David
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Sugent, James F
• Application Number:
  US12/750,407
• Publication Number:
  US 20110246404A1
• Time in Patent Office: 1,218 Days
• Field of Search: 706/21, 705/7.12
• US Class Current: 706/21
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 50/14 Travel agencies

Abstract

A method and system for allocating users as trip accompanies provides for: creating a first trip prediction algorithm, collecting input parameters, predicting by the first trip prediction algorithm using the collected input parameters as input, at least one first trip, executing a matching method, the matching method comparing attributes of the predicted at least one first trip with attributes of at least one second trip, and allocating the first and the second user to each other as trip accompanies in dependence of the matching score of the first and second potential trip data object.

Claims

1. A computer implemented method for allocating users as trip accompanies, the method comprising:

creating a first trip prediction algorithm, the first trip prediction algorithm being operable to predict future trips of a first user and being created by evaluating information on past trips of the first user, the information on past trips of the first user being stored in a first trip history, the first trip history comprising trip data objects representing past trips of the first user, each trip data object comprising at least the starting time, starting date, starting place and the destination of the past trip;

collecting, by a first processing device, input parameters, the input parameters comprising at least the current time and current date;

predicting, by the first trip prediction algorithm using the collected input parameters as input, at least one first trip;

for each predicted trip, calculating a prediction score, wherein the prediction score is calculated as a derivative value of an accuracy of the first trip prediction algorithm and a calculated probability value being indicative of a probability that the first user will indeed executed the predicted trip;

executing, by a trip sharing service, a matching method, the matching method comparing attributes of the predicted at least one first trip with attributes of at least one second trip, the at least one second trip belonging to a second user of the trip sharing service, the at least one first trip being represented by a first potential trip data object, the second trip being represented by a second potential trip data object, the matching resulting in the determination of a matching score for each pair of compared potential trip data objects;

allocating the first and the second user to each other as trip accompanies in dependence of the matching score of the first and second potential trip data object; and

dynamically assigning driver and passenger roles to the users having been allocated to each other as the trip accompanies for a planned trip, wherein the assignment of the driver and passenger roles to the users depend on distribution of the driver and passenger roles in specific geographic regions.

2. The computer implemented method according to claim 1, wherein the first trip prediction algorithm is implemented as a neural network.

3. The computer implemented method according to claim 2, wherein the neural network is implemented as feed-forward back-propagation network, the network being trained on the first history, wherein the step of predicting the at least one first trip is established by selecting the at least one first trip from a set of known trips, the set of known trips being selected from the group consisting of

trips derived from all trip data objects of the first history, and

trips derived from all trip data objects of the first history and trips having been derived from a calendar application implicitly or explicitly specifying planned trips of the first user.

4. The computer implemented method according to claim 1, wherein the first trip prediction algorithm is based on a statistical approach, the statistical approach comprising the steps of

assigning each input parameter an input parameter type;

assigning each input parameter type a weight;

calculating, for each collected input parameter and for each known trip a probability value, the probability value being indicative of the probability that the known trip will be executed by the first user in the future given said input parameter, the set of known trips being selected from the group consisting of

trips derived from all trip data objects of the first history, and

trips derived from all trip data objects of the first history and trips having been derived from a calendar application implicitly or explicitly specifying planned trips of the first user;

calculating a total probability value for all known trips by weighting each probability value calculated for an input parameter value according to the weight assigned to the type of said parameter; and

summing up the weighted probabilities for each known destination calculated for the collected input parameter values.

5. The computer implemented method according to claim 1, wherein during the execution of the matching method one role is assigned dynamically to each of the first user and the at least one second user, wherein one of both users is assigned a driver role and the other user is assigned a passenger role, the role assignment depending on the preferences specified by each user, the preferences comprising a scale value indicating the preference of a user to act as driver or as passenger.

6. The computer implemented method according to claim 1, further comprising:

creating a first trip series pattern recognition algorithm, the first trip series pattern recognition algorithm being operable to predict future trips series of the first user and having being created by evaluating information on past trips of the first user, the information on past trips of the first user being stored in the first trip history;

collecting, by the first processing device, trip series pattern recognition input parameters for the trip series pattern recognition algorithm, the trip series pattern recognition input parameters comprising at least the current time and current date;

predicting, by the first trip series pattern recognition algorithm using the collected trip series pattern recognition input parameters as input, at least one first trip series.

7. The computer implemented method according to claim 6, wherein the predicted at least one trip series comprises a predicted third trip, further comprising:

transforming the predicted third trip into a third potential trip data object;

comparing, by the matching method, the third and the at least one second potential trip data object;

determining, during execution of the matching method, a matching score of the predicted third potential trip data object and the at least one second potential trip data object;

increasing said matching score if the second predicted trip belongs to a second predicted trip series of a second user and if in addition at least one further pair of potential trip data objects reaches a matching score above a threshold value, the at least one further pair of potential trip data objects comprising one predicted trip from the first predicted trip series and one potential trip data object from the second predicted trip series, wherein said increasing of the matching score results in a preferential allocation of users as trip accompanies who have been predicted by the trip series pattern recognition algorithm to share multiple future trip plans.

8. The computer implemented method according to claim 1, wherein the prediction score is calculated as the calculated probability that the first user will chose the predicted destination given the input parameters.

9. The computer implemented method according to claim 1, wherein the step of creating a first trip prediction algorithm, collecting input parameters and predicting at least one first trip are executed on a client device being operable to submit service requests to a remote trip sharing server, the method further comprising the following steps which are executed before the execution of the matching method on the trip sharing server is initiated:

creating, for the at least one first predicted future trip, a trip sharing service request, the created service request comprising at least the starting time, starting date and starting location and the destination of the predicted at least one first trip;

submitting the created trip sharing service request to the trip sharing server;

receiving the created trip sharing service request by the trip sharing service;

creating, by the trip sharing service, the first potential trip data object, the first potential trip data object comprising the starting time, starting date, starting location and destination specified in the received service request;

wherein during the execution of the matching method the first potential trip data object is compared against a plurality of existing second potential trip data objects, each second potential trip data object representing an explicitly defined or predicted future trip of at least one second user.

10. The computer implemented method according to claim 9, wherein the client device is selected from the group consisting of:

a notebook, a netbook, a desktop computer, a mobile phone, a navigation device, and a smart phone.

11. The computer implemented method according to claim 1, wherein the step of creating a first trip prediction algorithm, collecting input parameters and predicting at least one first trip are executed on the trip sharing server being operable to receive service requests from trip sharing service clients, wherein the at least one predicted first trip is transformed into a first potential trip data object, the created first potential trip data object comprising at least the starting time and date, the starting location and the destination of the at least one first predicted trip, and wherein during the execution of the matching method the first potential trip data object is compared against a plurality of existing second potential trip data objects, each second potential trip data object representing an explicitly defined or predicted future trip of at least one second user.

12. The computer implemented method according to claim 11, wherein the first trip history of the first user is part of a global trip history, the global trip history comprising at least one second trip history of at least one second user, wherein at least a second trip prediction algorithm is derived from data contained in the at least one second trip history, and wherein the second potential trip data object is comprises at least the starting time, starting date, starting location and destination of a second predicted trip, the second predicted trip having been predicted by the second trip prediction algorithm.

13. The computer implemented method according to claim 11, further comprising the steps of

analyzing all trip data objects of the global history, thereby assigning trip data objects to a geographic region according to their starting place;

determining, for each geographic region, the fraction of drivers and passengers;

graphically representing the determined fractions of drivers and passengers in form of a map, wherein different driver fraction ranges in different geographic regions are displayed with different colors or by hachuring.

14. The computer implemented method according to claim 11, further comprising the steps of

analyzing all trip data objects of the global history, thereby determining a global set of location pairs, each location pair comprising a first and a second location, the first and second location of each location pair being derived from the starting point and destination of a trip data object;

determining, for a predefined or user-defined period of time and for each location pair of the global set of location pairs, the average number of trip data objects in the global trip history having the first location of the location pair as start location and the second location as destination, the determined number being a frequency value which indicates the probability to find a trip accompany for a trip having first location as starting location and second location as destination;

graphically representing the determined frequency values in form of a map, wherein different frequency ranges are displayed with different colors or by hachuring.

15. The computer implemented method according to claim 13, wherein the determined fraction of drivers and passengers for different geographic regions is used by the matching method to execute, when matching a first potential trip data object of a first user against a second potential trip data object of a second user a step, the step being selected from the group consisting of:

increasing a driver preference score value of the first user if the first potential trip data object has a starting place in a first geographic region wherein the driver fraction is lower than the driver fraction of the geographic region comprising the starting place of the second potential trip data object,

decreasing a driver preference score value of the first user if the first potential trip data object has a starting place in a first geographic region wherein the driver fraction is higher than the driver fraction of the geographic region comprising the starting place of the second potential trip data object, and

increasing the matching score of a pair of a first and a second potential trip data object, the first potential trip data object belonging to a first user and having a first geographic region as starting place, the second potential trip data object belonging to a second user and having a second geographic region as starting place, if the first user preferentially acts as driver, the second user preferentially acts as passenger, and the first geographic region has a higher driver fraction than the second geographic region,

thereby reducing the determined regional driver/passenger inequalities between different geographic regions.

16. The computer implemented method according to claim 9, wherein the comparison of the first potential trip data object with the at least one second potential trip data object is implemented as a comparison of multidimensional vectors, wherein a first multidimensional vector represents the first potential trip data object, a second multidimensional vector represents the second potential trip data object, the first and the second vector each comprise multiple dimensions, wherein each dimension has associated a weight, wherein each dimension represents an attribute of its represented potential trip data object, and wherein the comparison of the first and the second vector comprises a comparison of the angle of both vectors in a multi-dimensional space and wherein the weight of each dimension determines the impact of the corresponding dimension on the result of the comparison.

17. The computer implemented method according to claim 1, wherein the collected input parameters in addition comprise parameters being selected from the group consisting of data provided by external service or data providers, vehicle data, the current position of the processing device, and application data.

18. A data processing system comprising a server hosting a trip sharing service and at least a first client device of a first user, the server and the first client device being operable of communicating with one another, the first client device being capable to submit a first service request to the service, the server being capable to generate a result in response to the first service request and to return the result to the first client device,

the first client device comprising:

a processor;

an interface for connecting the client device to a network and for exchanging data with the server;

a computer readable non-transitory storage medium stored thereon instructions that when executed by the processor of the client device cause the processor to submit a service request to the trip sharing service, the service request comprising at least the starting time and date, the starting place and destination of a first predicted trip of the first user, the first predicted trip being predicted by a first trip prediction algorithm, the first trip prediction algorithm taking at least the current time and date determined by the clock as input for predicting the first trip, the first trip prediction algorithm having been created based on data of past trips of the first user being stored to a first trip history, wherein each past trip in the first trip history is represented as trip data object comprising at least the starting time, starting date, starting location and destination of the past trip;

the first trip prediction algorithm, for each trip, calculating a prediction score, wherein the prediction score is calculated as a derivative value of an accuracy of the first trip prediction algorithm and a calculated probability value being indicative of a probability that the first user will indeed executed the predicted trip;

wherein the server further comprising;

a processor;

a network interface for connecting the server to a network ant for exchanging data with at least one client;

a computer readable non-transitory storage medium stored thereon instructions that when executed by a processor of the server cause the processor to perform a trip sharing service,

wherein the trip sharing service in operation transforms the service request received from the first client device into a first potential trip data object, executes a matching method comparing attributes of the predicted first trip with attributes of at least one second trip, the at least one second trip belonging to a second user of the trip sharing service, the second trip being represented by a second potential trip data object, the matching resulting in the determination of a matching score for each pair of compared trips and in the assignment of the first and the second user to each other as trip accompanies, dynamically assigning driver and passenger roles to the user having been allocated to each other as the trip accompanies for a planned trip, wherein the assignment of the driver and passenger roles to the users depend on distribution of the driver and passenger roles in specific geographic regions.

19. The data processing system according to claim 18, wherein the non-transitory storage medium of the client further comprises instructions for executing a first trip series pattern recognition algorithm, the first trip series pattern recognition algorithm being operable to predict future trips series of the first user and having being created by evaluating information on past trips of the first user, the information on past trips of the first user being stored in the first trip history.

20. A computer-readable non-transitory storage medium stored thereon instructions that when executed by a processor cause the processor to perform a method for allocating users as trip accompanies, the method comprising:

creating a first trip prediction algorithm, the first trip prediction algorithm being operable to predict future trips of a first user and being created by evaluating information on past trips of the first user, the information on past trips of the first user being stored in a first trip history comprising trip data objects, each past trip being represented by a trip data object, each trip data object comprising at least the starting time, starting date, starting place and the destination of the past trip;

collecting, by a first processing device, input parameters for the trip prediction algorithm, the input parameters comprising at least the current time and date;

predicting, by the first trip prediction algorithm using the collected input parameters as input, at least one first trip;

for each predicted trip, calculating a prediction score, wherein the prediction score is calculated as a derivative value of an accuracy of the first trip prediction algorithm and a calculated probability value being indicative of a probability that the first user will indeed executes the predicted trip;

executing, by a trip sharing service, a matching method, the matching method comparing attributes of the predicted at least one first trip with attributes of at least one second trip, the at least one second trip belonging to a second user of the trip sharing service, the at least one first trip being represented by a first potential trip data object, the second trip being represented by a second potential trip data object, the matching resulting in the determination of a matching score for each pair of compared trips;

allocating the first and the second user to each other as trip accompanies; and

dynamically assigning driver and passenger roles to the users having been allocated to each other as the trip accompanies for a planned trip, wherein the assignment of the driver and passenger roles to the users depend on distribution of the driver and passenger roles in specific geographic regions.