Patent ID: 8768614

Claim:
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 travel time t to calculate a total 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 one (t″) of the total times t′ associated with the identified travel route; selecting a top weighted travel route; and assigning the driver and passenger(s) in the top weighted travel route to a carpool.