×

INCREASING THROUGHPUT FOR CARPOOL ASSIGNMENT MATCHING

  • US 20130158861A1
  • Filed: 12/19/2011
  • Published: 06/20/2013
  • Est. Priority Date: 12/19/2011
  • Status: Active Grant
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.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×