Ride-sharing with geo-fencing technique

For the undergraduate final year's project, me and my team designed and implemented a taxi ride-sharing algorithm that is targeted at urban areas. In this blog, I am going to describe algorithms that we used for this project and all these algorithms are open source in my GitHub (VroomAlgorithm). If you are willing to further study these algorithms and if you have any confusion, or if you have any suggestions of improvement, then feel free to contact me.

The major algorithms that we used in this ride-sharing system are as follows:

GEO-FENCING

For vehicle searching, we have used the geo-fencing technique. In this technique, we divide the geographical area into multiple smaller areas (based on the district, for example) called ‘Major Fence’. Then we further divide the regions within ‘Major Fence’ into smaller manageable regions called ‘Minor Fence’(for example, city). The size of the ‘Minor Fence’ is determined by the traffic and point of interest. So we convert the vehicle searching problem to a mathematical problem to find if a point lies within a polygon, using the Winding number algorithm. We check if the location of the driver lies within the ‘Minor Fence’ and thus perform the ride-matching. In the figure below, I have shown an example of geo-fences.

Geo-fences Example(showing some fences in different color polygon)

RIDE MATCHING

Ride matching is done with the help of geo-fencing. When a ride request is made in luxury mode(without sharing) or for a motorcycle, then at first, the ride request is forwarded only to the drivers who are available in the same fence. If no free driver is found inside the same fence, then the ride request is forwarded to the drivers in the neighboring fences. So, a single geofence data also contains some information about its 4 neighbors. For example:

name:"fence-name"
topLeftX:"topLeftX-coordinate"
topLeftY:"topLeftY-coordinate"
topRightX:"topRightX-coordinate"
topRightY:"topRightY-coordinate"
bottomLeftX:"bottomLeftX-coordinate"
bottomLeftY:"bottomLeftY-coordinate"
bottomRightX:"bottomRightX-coordinate"
bottomRightY:"bottomRightY-coordinate"
neighbors:{"left-neighbors","right-neighbors","bottom-neighbors","top-neighbors"}

RIDE SHARING

In this project, we used a progressive ride-sharing approach. Whenever a ride offer is created, the system generates the set of geo-fences whose sequence specifies the direction of the ride. The set of geo-fences is generated along the shortest route, between source and the destination, generated by Google Map API. To get the shortest route geo-fences N (the set of geo-fences composing of the route), the only departure and destination location is required. We apply the inverted index data structure on the mechanism of saving the ride’s node. Now whenever the ride request is generated, the system computes the geo-fences along the path of the pickup and drop-off location and checks the following three constraints:

• Does the ride pass through the pickup geo-fence?
• Does the sequence of geo-fence of the ride offer has the same direction as the sequence of geo-fence of the route between passenger’s pick-up and drop-off location?
• Does the vehicle that is offering the ride has enough empty seats?

The figures below show how inverse index data structure can be used for finding path and direction in terms of geo-fences, and how this can be used for shared ride matching.

Inverse Index Data Structure

Shared Ride Matching

Ride Matching and Fence Direction Update

PRE-DEFINED AVAILABILITY CHECK

A normal algorithm might not forward any ride request if the vehicle is full as per it's current situation. However, if we analyse it temporally, then it might be the case that the vehicle will have enough empty seat when it reaches the place(geo-fence) from which new ride request is created. Hece, it is nice to perform a pre-defined availability check.

Let us assume that the number of empty seats available “A” in the vehicle is less than the number of seats requested “R” in the shared ride. Also, suppose that the geo-fence path of the ride matches with the customer’s ride request’s geo-fence path. Now, as per the predefined availability check, we check that how many passengers will be inside the vehicle going through the pickup fence of the requested ride.

Let,

A = Available number of seats,

R = Requested number of seats,

Driver’s updated fence direction = {“N1”, “N2”, “N3”, “N4”...}

Requested ride’s fence direction = {“Nk”,“Nk+1”, “Nk+2”...}

if A <= R at the time of ride request{
 if (Total seat - the number of passengers inside the vehicle 
 who will pass through the geo-fence “Nk”) <= R{
  forward the ride request to the driver
 }
}

Pre-defined Availability Check.

FUTURE DIRECTION

It would be nice to analyze the applicability of this approach. Also in addition to the abovementioned algorithms, temporal analysis (e.g time-series analysis) might be done in the data that is collected every day so that drivers will know which place will have higher ride requests at a certain time of the day. Or even better, the system does so and suggests drivers where to go for more ride requests. If the system does so then the drivers will be evenly distributed in the geo-fences based on the number of potential passengers. However, it might not be as easy as I have said and it is still a topic of research.

REFERENCES

To come up with this algorithm, we took reference from the following papers for learning more about geo-fencing and managing ride sharing using the help of inverse index data structure.

• D. Suganthi, S. R. (2018). Vehicle Tracking with Geo Fencing on Android Platform. International Journal of Engineering Science and Computing, 16992-16995.
• S. Maximilian, S. H. (2016). A Matching Algorithm for Dynamic Ridesharing. Transportation Research Procedia 19, 272 – 285.

Comments

[Talank]

Sure. D. Suganthi, S. R. (2018) Vehicle Tracking with Geo Fencing on Android Platform. International Journal of Engineering Science and Computing, 16992-16995. explains a lot about geo-fencing.