System and method for optimization of on-demand microtransit

Patent metadata

Field	Value
Publication number	US-10991063-B2
Application number	US-201615250706-A
Country	US
Kind code	B2
Filing date	Aug 29, 2016
Priority date	Aug 29, 2016
Publication date	Apr 27, 2021
Grant date	Apr 27, 2021

Abstract

A system and method for optimization of on-demand microtransit is provided. A list of possible stops of one or more vehicles is maintained. A plurality of requests for transportation are received, each of the requests associated with at least one traveler. Travelers to be transported by one of the vehicles are selected. A set of a minimal number of the stops is selected, the set comprising at least one stop that is within a predefined walking distance of the origin location of each of the selected travelers and at least one stop within the predefined walking distance of the destination location of each of the selected travelers. Potential routes are identified for the vehicle that include the stops in the set. The potential routes are evaluated using a plurality of constraints and one of the routes is selected for fulfilling the requests of the selected travelers.

First claim

What is claimed is:

1. A method for optimization of on-demand microtransit, comprising:
maintaining a list of possible stops of one or more self-driving vehicles;
receiving a plurality of requests for transportation, each of the requests associated with at least one traveler and comprising an origin location, a desired destination location, an earliest permitted departure time from the origin location and a latest permitted arrival time to the destination;
selecting multiple ones of the requests for fulfillment, comprising:
grouping the requests into a plurality of clusters based on the origin location and the destination location in each of the clusters;
sorting the clusters based on their size;
setting a threshold number that is a multiple of a capacity of one of the self-driving vehicles; and
selecting the requests from the clusters based on the size of the clusters up to the travelers associated with the selected requests equaling the threshold number, wherein the requests are selected from the clusters in an order of decreasing size of the clusters and all of the requests from a larger one of the clusters are selected prior to selecting the requests from a smaller one of the clusters;

selecting a set of a minimal number of the stops, the set comprising at least one stop that is within a predefined walking distance of the origin location of each of the selected travelers and at least one stop within the predefined walking distance of the destination location of each of the selected travelers;
identifying potential routes for the self-driving vehicles that include the stops in the set, comprising:
clustering the stops in the set within the walking distance of the origin locations and identifying a centroid of the origin stops cluster;
clustering the stops in the set within the walking distance of the destination locations and identifying a centroid of the destination stops cluster;
sorting the stops in the set within the walking distance of the origin locations in order of decreasing distance to the destination stops centroid;
sorting the stops in the set within the walking distance of the destination locations in order of increasing distance to the origin stops centroid; and
enumerating all of the potential routes that follow the sorted orders of the stops;

evaluating as a mixed integer linear problem possible assignments of at least some of the travelers associated with the selected requests to be transported by one or more of the self-driving vehicles along at least one of the enumerated routes, comprising:
determining a total travel time by the one or more self-driving vehicles associated with each of the possible assignments based on at least one of one or more of the earliest permitted departure times and one or more of the latest permitted arrival times;
determining a total number of the travelers whose requests would be fulfilled by each of the possible assignments;
determining a total walking time of the at least some travelers associated with each of the possible assignments; and
using the total travel time associated with each of the possible assignments, the total number of travelers associated with each of the possible assignments, and the total walking time associated with each of the possible assignment to select one of the possible assignments; and

causing one or more of the self-driving vehicles associated with the selected assignment to automatically follow the at least one route associated with the selected assignment via a wireless transceiver comprised in the one or more self-driving vehicles, wherein the steps are performed by a suitably-programmed computer.

2. A method according to claim 1 , wherein the grouping is performed using k means clustering, further comprising:
performing an clustering of the requests using a value of k;
calculating a distortion of the initial clustering;
increasing the value of k and repeating the clustering using the increased value of k;
calculating a distortion for the initial clustering and calculating a difference between the initial clustering distortion and the repeated clustering distortion based on the comparison; and
comparing the difference to a threshold and upon the difference meeting the threshold, further increasing the value of k and further repeating the clustering using the further increased value of k.

3. A method according to claim 1 , wherein the total travel time associated with each of the possible assignments, the total number of travelers associated with each of the possible assignments, and the total walking time associated with each of the possible assignments are weighed differently during the evaluation.

4. A method according to claim 1 , further comprising:
evaluating whether the possible assignments satisfy a plurality of constraints,
wherein the selected assignment satisfies all of the constraints.

5. A method according to claim 1 , wherein each of the possible stops is a public transportation stop.

6. A method according to claim 1 , further comprising:
calculating a walking distance between the origin location of each of the selected travelers to each of the stops in the set; and
directing each of the selected travelers to the stop in the set that is within a minimal walking distance from that traveler's origin location.

7. A system for optimization of on-demand microtransit, comprising:
a processor configured to execute code and configured to:
maintain a list of possible stops of one or more self-driving vehicles;
receive a plurality of requests for transportation, each of the requests associated with at least one traveler and comprising an origin location, a desired destination location, an earliest permitted departure time from the origin location and a latest permitted arrival time to the destination;
select multiple ones of the requests for fulfillment, further comprising:
group the requests into a plurality of clusters based on the origin location and the destination location in each of the clusters;
sort the clusters based on their size;
set a threshold number that is a multiple of a capacity of one of the self-driving vehicles; and
select the requests from the clusters based on the size of the clusters up to the travelers associated with the selected requests equaling the threshold number, wherein the requests are selected from the clusters in an order of decreasing size of the clusters and all of the requests from a larger one of the clusters are selected prior to selecting the requests from a smaller one of the clusters;

select a set of a minimal number of the stops, the set comprising at least one stop that is within a predefined walking distance of the origin location of each of the selected travelers and at least one stop within the predefined walking distance of the destination location of each of the selected travelers;
identify potential routes for the self-driving vehicles that include the stops in the set, comprising:
cluster the stops in the set within the walking distance of the origin locations and identify a centroid of the origin stops cluster;
cluster the stops in the set within the walking distance of the destination locations and identify a centroid of the destination stops cluster;
sort the stops in the set within the walking distance of the origin locations in order of decreasing distance to the destination stops centroid;
sort the stops in the set within the walking distance of the destination locations in order of increasing distance to the origin stops centroid; and
enumerate all of the potential routes that follow the sorted orders of the stops;

evaluate as a mixed integer linear problem possible assignments of at least some of the travelers associated with the selected requests to be transported by

Assignees

• Conduent Business Services Llc

Inventors

• Klenk Matthew E
• Fritz Christian
• Yang Rong

Classifications

• G06Q10/06311

  Scheduling, planning or task assignment for a person or group · CPC title

• G06Q10/047

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G08G1/202

  Dispatching vehicles on the basis of a location, e.g. taxi dispatching · CPC title

• G01C21/3438

  Rendezvous; Ride sharing · CPC title

• G07B15/02

  taking into account a variable factor such as distance or time, e.g. for passenger transport, parking systems or car rental systems (G07B15/06 takes precedence; taximeters G07B13/00; parking meters per se G07F17/24) · CPC title