INCREASING THROUGHPUT FOR CARPOOL ASSIGNMENT MATCHING
First Claim
Patent Images
1. A computer-implemented method comprising:
- setting a current location L of a carpool driver to a starting location of the carpool driver in an initial iteration of the method, wherein the current location L updates with a location change of the driver;
identifying, using a processing device, an eligible next location M for the carpool driver to drive;
identifying, using the processing device, a distance d from the current location L to the next location M;
calculating a plurality of distances from the next location M to all must-reach locations N to a final destination of the carpool driver;
identifying a maximum of the plurality of distances from the next location M to all must-reach locations N to a final destination of the carpool driver;
adding the identified maximum to the distance d to calculate a distance d′
;
calculating a travel time t from the distance d′
based on an optimistic approximation using the processing device;
adding an additional time for picking up and dropping off each passenger to the time t to calculate the time t′
;
excluding the location M as a potential stop for the driver in a travel route if the time t′
exceeds a maximum travel time of the driver;
selecting a next location M′ and
repeating the method until a final destination of the driver is reached to identify all travel routes and potential stops;
weighting each identified travel route by a number of passengers picked up and a shortest travel time t′
;
selecting a top weighted travel route; and
assigning the driver and passenger(s) in the top weighted travel route to a carpool.
2 Assignments
0 Petitions
Accused Products
Abstract
Distances between locations traveled by a carpool driver in a carpooling system may be initially estimated by calculating direct, straight line distances between each of the location points. Travel speeds may also be initially estimated using an expected maximum vehicle speed, which may a maximum speed limit. An estimated travel time may then be calculated from this data to initially designate passengers as eligible or ineligible for carpooling with a carpool driver.
49 Citations
18 Claims
-
1. A computer-implemented method comprising:
-
setting a current location L of a carpool driver to a starting location of the carpool driver in an initial iteration of the method, wherein the current location L updates with a location change of the driver; identifying, using a processing device, an eligible next location M for the carpool driver to drive; identifying, using the processing device, a distance d from the current location L to the next location M; calculating a plurality of distances from the next location M to all must-reach locations N to a final destination of the carpool driver; identifying a maximum of the plurality of distances from the next location M to all must-reach locations N to a final destination of the carpool driver; adding the identified maximum to the distance d to calculate a distance d′
;calculating a travel time t from the distance d′
based on an optimistic approximation using the processing device;adding an additional time for picking up and dropping off each passenger to the time t to calculate the time t′
;excluding the location M as a potential stop for the driver in a travel route if the time t′
exceeds a maximum travel time of the driver;selecting a next location M′ and
repeating the method until a final destination of the driver is reached to identify all travel routes and potential stops;weighting each identified travel route by a number of passengers picked up and a shortest travel time t′
;selecting a top weighted travel route; and assigning the driver and passenger(s) in the top weighted travel route to a carpool. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A non-transitory computer readable medium comprising a set of instructions stored in the medium that, when executed by a processing device, cause the processing device to:
-
set a current location L of a carpool driver to a starting location of the carpool driver in an initial iteration of the method, wherein the current location L updates with a location change of the driver; identify an eligible next location M for the carpool driver to drive; identify a distance d from the current location L to the next location M; calculate a plurality of distances from the next location M to all must-reach locations N to a final destination of the carpool driver; identify a maximum of the plurality of distances from the next location M to all must-reach locations N to a final destination of the carpool driver; add the identified maximum to the distance d to calculate a distance d′
;calculate a travel time t from the distance d′
based on an optimistic approximation using the processing device;add an additional time for picking up and dropping off each passenger to the time t to calculate the time t′
;exclude the location M as a potential stop for the driver in a travel route if the time t′
exceeds a maximum travel time of the driver;select a next location M′ and
repeating the method until a final destination of the driver is reached to identify all travel routes and potential stops;weight each identified travel route by a number of passengers picked up and a shortest travel time t′
;select a top weighted travel route; and assign the driver and passenger(s) in the top weighted travel route to a carpool. - View Dependent Claims (12, 13, 14)
-
-
15. A system comprising:
-
a memory device; a processing device; and a calculating arrangement, wherein; the processing device sets a current location L of a carpool driver to a starting location of the carpool driver in an initial iteration of the method wherein the current location L updates with a location change of the driver in the memory device, identifies an eligible next location M for the carpool driver to drive, identifies a distance d from the current location L to the next location M; the calculating arrangement calculates a plurality of distances from the next location M to all must-reach locations N to a final destination of the carpool driver, identifies a maximum of the plurality of distances from the next location M to all must-reach locations N to a final destination of the carpool driver, adds the identified maximum to the distance d to calculate a distance d′
, calculates a travel time t from the distance d′
based on an optimistic approximation using the processing device, adds an additional time for picking up and dropping off each passenger to the time t to calculate the time t′
, excludes the location M as a potential stop for the driver in a travel route if the time t′
exceeds a maximum travel time of the driver, selects a next location M′ and
repeating the method until a final destination of the driver is reached to identify all travel routes and potential stops, weights each identified travel route by a number of passengers picked up and a shortest travel time t′
, selects a top weighted travel route, and assigns the driver and passenger(s) in the top weighted travel route to a carpool. - View Dependent Claims (16, 17)
-
-
18. A computer-implemented method comprising:
-
setting a current location L of a potential route to a starting location of the potential route in an initial iteration of the method, wherein the current location L updates as the method progresses; identifying, using a processing device, an eligible next location M of the potential route; calculating, using the processing device, a shortest distance d from the current location L to the next location M and a longest straight line distance d′
from the next location M to all must-reach locations N to a final destination of the potential route;calculating a fastest time t to travel the distances d and d′
based on an optimistic approximation using the processing device;excluding the location M as a potential route for the driver if the time t exceeds a maximum travel time of the driver; selecting a next location M′ and
repeating the method until each location has been selected to check all potential routes;weighting each non-excluded potential route by a predetermined criterion; and selecting a top weighted route as a final route.
-
Specification