Computing method for ridesharing paths, computing apparatus and recording medium using the same

• US 10,012,513 B2
• Filed: 08/16/2016
• Issued: 07/03/2018
• Est. Priority Date: 04/28/2016
• Status: Active Grant

• Current Assignee: National Tsing Hua University
• Original Assignee: National Tsing Hua University
• Inventors: Lee, Che-Rung, Hsu, Oscar Li Jen
• Primary Examiner(s): Trivedi, Atul
• Application Number:
  US15/238,556
• Publication Number:
  US 20170314947A1
• Time in Patent Office: 686 Days
• Field of Search: 701533
• CPC Class Codes: G01C 21/3438 Rendez-vous, i.e. searching a destination where several users can meet, and the routes to this destination for these users; Ride sharing, i.e. searching a route such that at least two users can share a vehicle for at least part of the route
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement

Abstract

A computing method for ridesharing paths, a computing apparatus and a recording medium using the same are provided. This invention finds the ridesharing paths out from the target trajectory which have ridesharing relationship with a plurality of candidate trajectories. People on the ridesharing paths can share a ride on a part of or whole target trajectory. In the computing method, a trajectory is transformed into a sequence of blocks. After target trajectory and a plurality of the candidate trajectories are transformed, it is determined whether each of the blocks of the candidate trajectories overlaps with at least one of the blocks of the target trajectory. Then, ridesharing paths are calculated according the screened candidate trajectories. This method is many-to-one method which compares a plurality of the candidate trajectories to one target trajectory at one time.

Claims

1. A computing apparatus for finding ridesharing paths in a target trajectory, comprising:

a storage, recording a plurality of first points of the target trajectory and a plurality of second points of a plurality of candidate trajectories; and

a processor, coupled to the storage, and configured to;

determine a sequence of first blocks for the target trajectory according to a plurality of first points of the target trajectory, and sequentially classify each of the first points into only one of the first blocks, wherein each first block has a same predetermined size;

determine a sequence of second blocks for each candidate trajectory according to a plurality of second points of each candidate trajectory, and sequentially classify each of the second points into only one of the second blocks, wherein each second block has the same predetermined size;

select at least one of the second blocks which overlaps with at least one of the first blocks, and obtain the second points classified in the selected at least one second blocks;

calculate the ridesharing paths in the target trajectory according to the obtained second points classified in the selected at least one second block; and

display the calculated ridesharing paths on a display of the computing apparatus.

2. The computing apparatus as claimed in claim 1, wherein the processor classifies the ith first point of the target trajectory into the jth first block of the target trajectory, and determines whether a longitude range or a latitude range of the first points in the jth first block is larger than a spatial parameter, or a time range of the first points is larger than a temporal parameter, wherein if the longitude range or the latitude range of the first points in the jth first block is larger than the spatial parameter, or the time range of the first points is larger than the temporal parameter, the processor reclassifies the ith first point into the (j+1)th first block of the target trajectory, wherein i is a positive integer incremented from 1 to a total number of the first points of the target trajectory, and j is a positive integer incremented from 1 to a total number of the first blocks of the target trajectory,

wherein the processor classifies the pth second point of each candidate trajectory into the qth second block of each candidate trajectory, and determines whether a longitude range or a latitude range of the second points in the qth second block is larger than the spatial parameter, or a time range of the second points is larger than the temporal parameter, wherein if the longitude range or the latitude range of the second points in the qth second block is larger than the spatial parameter, or the time range of the second points is larger than the temporal parameter, the processor reclassifies the pth second point into the (q+1)th second block of the candidate trajectory, wherein p is a positive integer incremented from 1 to a total number of the second points of each candidate trajectory, and q is a positive integer incremented from 1 to a total number of the second blocks of each candidate trajectory.

3. The computing apparatus as claimed in claim 2, wherein the processor takes the kth first point in the jth first block as a spatial reference point, and calculates the longitude range and the latitude range of the first points in the jth first block according to the spatial reference point, wherein the kth first point is a point first classified into the jth first block, and k is a positive integer between 1 and the total number of the first points of the target trajectory,

wherein the processor takes the rth second point in the qth second block as a spatial reference point, and calculates the longitude range and the latitude range of the second points in the qth second block according to the spatial reference point, wherein the rth second point is a point first classified into the qth second block, and r is a positive integer between 1 and the total number of the second points of each candidate trajectory.

4. The computing apparatus as claimed in claim 3, wherein the processor determines a direction of the jth first block according to a connection line between the kth first point and the mth first point in the jth first block, wherein m is a positive integer between k+1 and the total number of the first points of the target trajectory,

wherein the processor determines a direction of the qth second block according to a connection line between the rth second point and the sth second point in the qth second block, wherein s is a positive integer between r+1 and the total number of the second points of each candidate trajectory.

5. The computing apparatus as claimed in claim 2, wherein the processor finds out a maximum time and a minimum time of the first points in the jth first block to calculate the time range of the jth first block,

wherein the processor finds out a maximum time and a minimum time of the second points in the qth second block to calculate the time range of the qth second block.

6. The computing apparatus as claimed in claim 1, wherein the processor sequentially compares a difference between a center of each of the second blocks of the candidate trajectories and a center of each of the first blocks of the target trajectory with a spatial parameter and a temporal parameter, wherein the processor also compares an included angle between a direction of each of the second blocks of the candidate trajectories and a direction of each of the first blocks of the target trajectory with an included angle parameter, so as to determine whether each of the second blocks of the candidate trajectories overlaps with at least one of the first blocks of the target trajectory.

7. The computing apparatus as claimed in claim 6, wherein the processor records the second blocks of the candidate trajectories determined to be overlapped with the at least one first block of the target trajectory in a matrix according to each of the at least one first block of the target trajectory, and the processor is further configured to:

screen the at least one of the candidate trajectories according to the matrix.

8. The computing apparatus as claimed in claim 7, wherein the processor calculates a total compliance number of the second blocks of the candidate trajectories determined to be overlapped with the at least one first block of the target trajectory and recorded in the matrix, and screens the at least one of the candidate trajectories according to the total compliance number.

9. The computing apparatus as claimed in claim 1, wherein the processor restores the second points classified in the selected second blocks which overlaps with at least one of the first blocks, and calculates the ridesharing paths according to the restored second points.

10. The computing apparatus as claimed in claim 1, wherein the processor forms a three-dimensional object in a spatiotemporal coordinate system according to each of the first blocks of the target trajectory and each of the second blocks of the candidate trajectories, wherein all of the first blocks and the second blocks are in the same size defined by the spatial parameter and the temporal parameter.

11. A computing method for finding ridesharing paths in a target trajectory, adapted to a computing apparatus for comparing a plurality of candidate trajectories with the target trajectory, the computing method comprising:

determining a sequence of first blocks for the target trajectory according to a plurality of first points of the target trajectory, and sequentially classifying each of the first points into only one of the first blocks, wherein each first block has a same predetermined size;

determining a sequence of second blocks for each candidate trajectory according to a plurality of second points of each candidate trajectory, and sequentially classifying each of the second points into only one of the second blocks, wherein each second block has the same predetermined size;

selecting at least one of the second blocks which overlaps with at least one of the first blocks, and obtaining the second points classified in the selected at least one second blocks;

calculating the ridesharing paths in the target trajectory according to the obtained second points classified in the selected at least one second block; and

displaying the calculated ridesharing paths on a display of the computing apparatus.

12. The computing method as claimed in claim 11, wherein the step of sequentially classifying each of the first points into only one of the first blocks comprises:

classifying the ith first point of the target trajectory into the jth first block of the target trajectory; and

determining whether a longitude range or a latitude range of the first points in the jth first block is larger than a spatial parameter, or a time range of the first points is larger than a temporal parameter, so as to determine whether to reclassify the ith first point into the (j+1)th first block, wherein i is a positive integer incremented from 1 to a total number of the first points of the target trajectory, and j is a positive integer incremented from 1 to a total number of the first blocks of the target trajectory, wherein the step of sequentially classifying each of the second points into only one of the second blocks comprises;

classifying the pth second point of each candidate trajectory into the qth second block of each candidate trajectory; and

determining whether a longitude range or a latitude range of the second points in the qth second block is larger than the spatial parameter, or a time range of the second points is larger than the temporal parameter, so as to determine whether to reclassify the pth second point into the (q+1)th second block, wherein p is a positive integer incremented from 1 to a total number of the second points of the candidate trajectory, and q is a positive integer incremented from 1 to a total number of the second blocks of the candidate trajectory.

13. The computing method as claimed in claim 12, wherein the step of determining the sequence of first blocks for the target trajectory according to the first points of the target trajectory comprises:

forming a three-dimensional object in a spatiotemporal coordinate system according to each of the first blocks of the target trajectory, wherein the size of the first blocks was defined by the spatial parameter and the temporal parameter;

taking the kth first point of the target trajectory classified into the jth first block as a spatial reference point, wherein the kth first point is a point first classified into the jth first block, and k is a positive integer between 1 and the total number of the first points of the target trajectory; and

calculating a plurality of ranges of the first points in the jth first block according to the spatial reference point and the first points in the jth first block, wherein the ranges of the first points in the jth first block comprises the longitude range, the latitude range and the time range of the first points in the jth first block, wherein the step of determining the sequence of second blocks for each candidate trajectory according to the second points of each candidate trajectory comprises;

forming a three-dimensional object in a spatiotemporal coordinate system according to each of the second blocks of each candidate trajectory, wherein the size of the second blocks was defined by the spatial parameter and the temporal parameter;

taking the rth second point of each candidate trajectory classified into the qth second block as a spatial reference point, wherein the rth second point is a point first classified into the qth second block, and r is a positive integer between 1 and the total number of the second points of each candidate trajectory; and

calculating a plurality of ranges of the second points in the qth second block according to the spatial reference point and the second points in the qth second block, wherein the ranges of the second points in the qth second block comprises the longitude range, the latitude range and the time range of the second points in the qth second block.

14. The computing method as claimed in claim 13, wherein after the step of calculating the ranges of the first points in the jth first block according to the spatial reference point in the jth first block, the computing method further comprises:

determining a direction of the jth first block according to a connection line between the kth first point and the mth first point classified into the jth first block, wherein m is a positive integer between k+1 and the total number of the first points of the target trajectory, wherein after the step of calculating the ranges of the second points in the qth second block according to the spatial reference point in the qth second block, the computing method further comprises;

determining a direction of the qth second block according to a connection line between the rth second point and the sth second point classified into the qth second block, wherein s is a positive integer between r+1 and the total number of the second points of each candidate trajectory.

15. The computing method as claimed in claim 12, wherein the step of determining the sequence of first blocks for the target trajectory according to the first points of the target trajectory comprises:

finding out a maximum time and a minimum time of all the first points in the jth first block to calculate the time range of the first points in the jth first block, wherein the step of determining the sequence of second blocks for each candidate trajectory according to the second points of each candidate trajectory comprises;

finding out a maximum time and a minimum time of all the second points in the qth second block to calculate the time range of the second points in the qth second block.

16. The computing method as claimed in claim 11, wherein the step of selecting the at least one of the second blocks which overlaps with the at least one of the first blocks, and obtaining the second points classified in the selected at least one second blocks comprises:

sequentially comparing a difference between a center of each of the second blocks of the candidate trajectories and a center of each of the first blocks of the target trajectory with a spatial parameter and a temporal parameter; and

sequentially comparing an included angle between a direction of each of the second blocks of the candidate trajectories and a direction of each of the first blocks of the target trajectory with an included angle parameter, so as to determine whether each of the second blocks of the candidate trajectories overlaps with at least one of the first blocks of the target trajectory.

17. The computing method as claimed in claim 16, wherein after determining whether each of the second blocks of the candidate trajectories overlaps with at least one of the first blocks of the target trajectory, the computing method further comprises:

recording the second blocks of the candidate trajectories determined to be overlapped with the at least one first block of the target trajectory in a matrix according to each of the at least one first blocks of the target trajectory; and

screening the at least one of the candidate trajectories according to the matrix.

18. The computing method as claimed in claim 17, wherein the step of screening the at least one of the candidate trajectories according to the matrix comprises:

calculating a total compliance number of the second blocks of the candidate trajectories determined to be overlapped with the at least one first block of the target trajectory and recorded in the matrix; and

screening the at least one of the candidate trajectories according to the total compliance number.

19. The computing method as claimed in claim 11, wherein the step of calculating the ridesharing paths in the target trajectory according to the obtained second points classified in the selected at least one second block comprises:

restoring the second points classified in the selected second blocks which overlaps with at least one of the first blocks; and

calculating the ridesharing paths according to the restored second points.

20. A non-transitory computer-readable recording medium, recording a program, a target trajectory and a plurality of candidate trajectories, and being located to a computing apparatus to execute following steps:

determining a sequence of first blocks for the target trajectory according to a plurality of first points of the target trajectory, and sequentially classifying each of the first points into only one of the first blocks, wherein each first block has a same predetermined size;

determining a sequence of second blocks for each candidate trajectory according to a plurality of second points of each candidate trajectory, and sequentially classifying each of the second points into only one of the second blocks, wherein each second block has the same predetermined size;

selecting at least one of the second blocks which overlaps with at least one of the first blocks, and obtaining the second points classified in the selected at least one second blocks;

calculating ridesharing paths in the target trajectory according to the obtained second points classified in the selected at least one second block; and

displaying the calculated ridesharing paths on a display of the computing apparatus.