IP Library Granted Patent US 11,263,561
Granted Patent B2
US 11,263,561 · App. 16/941,757 · Granted Mar 1, 2022

Systems and methods for managing dynamic transportation networks using simulated future scenarios

Inventor: Chinmoy Dutta (Mountain View, CA)
Assignee: Lyft, Inc.
G06Q10/047G01C21/3438G06Q10/067
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,263,561
App. No.
16/941,757
Granted
Mar 1, 2022
Kind
B2
Abstract

The disclosed computer-implemented method may include (i) receiving a first transport request and a second transport request, (ii) evaluating a fitness of matching the first and second transport requests to be fulfilled by a transport provider, based at least partly on a transportation overlap between the first and second transport requests, (iii) generating a simulated future transport request, (iv) evaluating a fitness of matching the first transport request with the simulated future transport request, based at least in part on a transportation overlap between the first transport request and the simulated future transport request, and (v) matching the first and second transport requests based at least in part on the fitness of matching the first and second transport requests and based at least in part on the fitness of matching the first transport request with the simulated future transport request. Various other methods, systems, and computer-readable media are disclosed.

Claims (72)

1. A computer-implemented method comprising:

receiving, by a dynamic transportation matching system, a first transport request and a second transport request;

evaluating, by the dynamic transportation matching system, a fitness of matching the first transport request with the second transport request to be fulfilled by a transport provider;

generating a simulated future transport request;

evaluating, by the dynamic transportation matching system, a fitness of matching the first transport request with the simulated future transport request; and

matching, by the dynamic transportation matching system, the first transport request with the second transport request upon determining that the fitness of matching the first transport request with the second transport request exceeds the fitness of matching the first transport request with the simulated future transport request.

2. The computer-implemented method of claim 1 , wherein matching, by the dynamic transportation matching system, the first transport request with the second transport request upon determining that the fitness of matching the first transport request with the second transport request exceeds the fitness of matching the first transport request with the simulated future transport request comprises performing a multi-stage stochastic optimization, wherein:

the first transport request and the second transport request are defined within an initial stage of the multi-stage stochastic optimization; and

the simulated future transport request is defined within a subsequent stage of the multi-stage stochastic optimization.

3. The computer-implemented method of claim 1 , wherein the simulated future transport request specifies:

an origin location;

a destination location; and

a request time.

4. The computer-implemented method of claim 1 , further comprising generating a simulated future scenario that comprises:

the simulated future transport request; and

at least one simulated transportation provider.

5. The computer-implemented method of claim 1 ,

further comprising generating a plurality of distinct simulated future scenarios, each distinct simulated future scenario within the plurality of distinct simulated future scenarios specifying a corresponding set of simulated future transport requests;

wherein matching, by the dynamic transportation matching system, the first transport request with the second transport request is further based at least in part on evaluating, in each of the plurality of distinct simulated future scenarios, potential matches between the first transport request and each simulated future transport requests within the corresponding set of simulated future transport requests.

6. The computer-implemented method of claim 5 , further comprising weighting each of the plurality of distinct simulated future scenarios according to a corresponding probability assigned to each of the plurality of distinct simulated future scenarios.

7. The computer-implemented method of claim 5 , wherein matching, by the dynamic transportation matching system, the first transport request with the second transport request is further based at least in part on evaluating, in each of the plurality of distinct simulated future scenarios, potential matches between pairs of simulated future transport requests within the corresponding set of simulated future transport requests.

8. The computer-implemented method of claim 1 , further comprising:

receiving, by the dynamic transportation matching system, a third transport request and a fourth transport request;

evaluating, by the dynamic transportation matching system, a fitness of matching the third transport request with the fourth transport request to be fulfilled by a transport provider;

generating an additional simulated future transport request;

evaluating, by the dynamic transportation matching system, a fitness of matching the third transport request with the additional simulated future transport request; and

declining to match, by the dynamic transportation matching system, the third transport request with the fourth transport request upon determining that the fitness of matching the third transport request with the fourth transport request is less than the fitness of matching the third transport request with the additional simulated future transport request.

9. The computer-implemented method of claim 1 , wherein:

the dynamic transportation matching system is configured to search for a match for the first transport request within a first window of time and to search for a match for the second transport request within a second window of time; and

the simulated future transport request is simulated to take place after the first window of time and after the second window of time.

10. The computer-implemented method of claim 1 , further comprising transmitting, by the dynamic transportation matching system and in response to matching the first transport request with the second transport request, transportation instructions to a transportation provider device specifying that a transportation provider:

pick up a first transportation requestor that originated the first transport request;

pick up a second transportation requestor that originated the second transport request;

transport the first transportation requestor and second transportation requestor together along a transportation overlap between the first transport requestor and the second transport requestor;

drop off the first transportation requestor; and

drop off the second transportation requestor.

11. A system comprising one or more physical processors and one or more memories coupled to one or more of the physical processors, the one or more memories comprising instructions operable when executed by the one or more physical processors to cause the system to perform operations comprising:

receiving, by a dynamic transportation matching system, a first transport request and a second transport request;

evaluating, by the dynamic transportation matching system, a fitness of matching the first transport request with the second transport request to be fulfilled by a transport provider;

generating a simulated future transport request;

evaluating, by the dynamic transportation matching system, a fitness of matching the first transport request with the simulated future transport request; and

matching, by the dynamic transportation matching system, the first transport request with the second transport request upon determining that the fitness of matching the first transport request with the second transport request exceeds the fitness of matching the first transport request with the simulated future transport request.

12. The system of claim 11 , wherein matching, by the dynamic transportation matching system, the first transport request with the second transport request upon determining that the fitness of matching the first transport request with the second transport request exceeds the fitness of matching the first transport request with the simulated future transport request comprises performing a multi-stage stochastic optimization, wherein:

the first transport request and the second transport request are defined within an initial stage of the multi-stage stochastic optimization; and

the simulated future transport request is defined within a subsequent stage of the multi-stage stochastic optimization.

13. The system of claim 11 , wherein the simulated future transport request specifies:

an origin location;

a destination location; and

a request time.

14. The system of claim 11 , wherein the operations further comprise generating a simulated future scenario that comprises:

the simulated future transport request; and

at least one simulated transportation provider.

15. The system of claim 11 ,

wherein the operations further comprise generating a plurality of distinct simulated future scenarios, each distinct simulated future scenario within the plurality of distinct simulated future scenarios specifying a corresponding set of simulated future transport requests;

wherein matching, by the dynamic transportation matching system, the first transport request with the second transport request is further based at least in part on evaluating, in each of the plurality of distinct simulated future scenarios, potential matches between the first transport request and each simulated future transport requests within the corresponding set of simulated future transport requests.

16. The system of claim 15 , wherein the operations further comprise weighting each of the plurality of distinct simulated future scenarios according to a corresponding probability assigned to each of the plurality of distinct simulated future scenarios.

17. The system of claim 15 , wherein the operations further comprise matching, by the dynamic transportation matching system, the first transport request with the second transport request is further based at least in part on evaluating, in each of the plurality of distinct simulated future scenarios, potential matches between pairs of simulated future transport requests within the corresponding set of simulated future transport requests.

18. The system of claim 11 , wherein the operations further comprise:

receiving, by a dynamic transportation matching system, a third transport request and a fourth transport request;

evaluating, by the dynamic transportation matching system, a fitness of matching the third transport request with the fourth transport request to be fulfilled by a transport provider;

generating an additional simulated future transport request;

evaluating, by the dynamic transportation matching system, a fitness of matching the third transport request with the additional simulated future transport request; and

declining to match, by the dynamic transportation matching system, the third transport request with the fourth transport request upon determining that the fitness of matching the third transport request with the fourth transport request is less than the fitness of matching the third transport request with the additional simulated future transport request.

19. The system of claim 11 , wherein:

the dynamic transportation matching system is configured to search for a match for the first transport request within a first window of time and to search for a match for the second transport request within a second window of time; and

the simulated future transport request is simulated to take place after the first window of time and after the second window of time.

20. A non-transitory computer-readable storage medium comprising computer-readable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

receive, by a dynamic transportation matching system, a first transport request and a second transport request;

evaluate, by the dynamic transportation matching system, a fitness of matching the first transport request with the second transport request to be fulfilled by a transport provider;

generate a simulated future transport request;

evaluate, by the dynamic transportation matching system, a fitness of matching the first transport request with the simulated future transport request; and

match, by the dynamic transportation matching system, the first transport request with the second transport request upon determining that the fitness of matching the first transport request with the second transport request exceeds the fitness of matching the first transport request with the simulated future transport request.

Assignments (2)
SECURITY INTEREST Recorded Nov 3, 2022
From: LYFT, INC.
To: JPMORGAN CHASE BANK, N.A., AS ADMINISTRATIVE AGENT
Reel/Frame 061880/0237 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jul 29, 2020
From: DUTTA, CHINMOY
To: LYFT, INC.
Reel/Frame 053339/0851 →
Continuity (2)
Continuation 16027250 · Jul 3, 2018
Related Publication 20200356912A1 · Nov 12, 2020