Methods and systems for on-demand dynamic vehicle routing

Patent metadata

Field	Value
Publication number	US-11238399-B2
Application number	US-201816036829-A
Country	US
Kind code	B2
Filing date	Jul 16, 2018
Priority date	Jul 17, 2017
Publication date	Feb 1, 2022
Grant date	Feb 1, 2022

Abstract

Methods and systems for on demand logistics management are disclosed. An on-demand logistics system includes an electronic hardware processor configured to receive an on-demand request, the request indicating an on-demand location for an on-demand transaction, determine locations of a plurality of vehicles on a plurality of delivery routes, determine whether the on-demand location is within a threshold distance of at least one of the plurality of delivery routes based on the vehicle locations and assign the on-demand transaction to a vehicle based on the determination.

First claim

What is claimed is:

1. An on-demand logistics system, comprising:
a network interface circuit configured to receive a first electronic communication from a customer, the first electronic communication including an on-demand request for pick up and/or delivery of an item; and
an electronic hardware processor, configured to:
identify, in the on-demand request, a location for the requested item pick up and/or delivery;
identify, within a geographic area, a plurality of routes, each of the plurality of routes comprising a plurality of stops and having a corresponding vehicle traveling the route when the on-demand request is received;
determine, from the plurality of routes, a subset of stops which are within a threshold distance of the location for the requested item pick up and/or delivery and which are still pending for the current day;
determine a stop from the subset of stops which has the minimum distance from the location for the requested item pick up and/or delivery;
determine a route from the plurality of routes that includes the determined stop;
assign the requested item pick up and/or delivery to the vehicle corresponding to the determined route based on a determination that (1) addition of the location as an additional stop to the determined route does not violate time constraints associated with the determined route and the on-demand request and (2) addition of the location as the additional stop to the determined route does not exceed a defined maximum deviation distance for the vehicle traveling the determined route; and
generate a second electronic communication to the assigned vehicle, the second electronic communication comprising a command that designates the assigned vehicle to travel to the location,
wherein the network interface circuit is further configured to transmit the second electronic communication to the assigned vehicle.

2. The system of claim 1 , wherein the request identifies the item for delivery to the location, and wherein the electronic hardware processor is configured to identify the plurality of routes based on the item for delivery to the location.

3. The system of claim 2 , wherein identifying the plurality of routes comprises identifying, and including in the plurality of routes, those routes that have the corresponding vehicles which include the item in a vehicle inventory and that have at least one stop within a threshold distance of the location.

4. The system of claim 1 , wherein the electronic hardware processor is further configured to receive location updates for the corresponding vehicle for each of the plurality of routes and to determine locations of the corresponding vehicle for each of the plurality of routes at least partially based on the location updates, and to determine whether a stop is still pending for the current day based on the determined location of the vehicle and a list of stops for each of the plurality of routes stored in a route database.

5. The system of claim 1 , wherein the command instructs the assigned vehicle to perform the requested item pick up and/or delivery.

6. The system of claim 5 , wherein the vehicle is an autonomous vehicle, and the command updates a route in an on-board vehicle control computer of the vehicle.

7. The system of claim 1 , wherein the electronic hardware processor is further configured to select the determined route based on a determination that the determined route is a route that requires a minimum amount of distance deviation to fulfill the on-demand request, and wherein the requested item pick up and/or delivery is assigned to the vehicle corresponding to the determined route.

8. The system of claim 7 , wherein the electronic hardware processor is configured to determine the route requiring the minimum amount of deviation by:
determining, for each of the plurality of routes, the minimum route deviation distance required to fulfill the on-demand request;
determining operators for the plurality of routes;
determining the maximum deviation distance allowed for operators of the vehicles; and
determining which of the plurality of routes has the smallest minimum deviation distance which also does not exceed its operator's maximum deviation distance.

9. The system of claim 7 , wherein the electronic hardware processor is further configured to determine whether the requested item pick up and/or delivery will be fulfilled within geographic and vehicle constraints.

10. A method comprising:
receiving a first electronic communication from a customer, the first electronic communication including an on-demand request for pick up and/or delivery of an item;
identifying, in the on-demand request, a location for the requested item pick up and/or delivery;
identifying, within a geographic area, a plurality of delivery routes, each of the plurality of delivery routes comprising a plurality of stops and having a corresponding vehicle traveling the delivery route when the on-demand request is received;
determining, from the plurality of delivery routes, a subset of stops which are within a threshold distance of the location for the requested item pick up and/or delivery and which have at least one remaining stop along their respective routes;
determining a stop from the subset of stops which has the minimum distance from the location for the requested item pick up and/or delivery;
determining a route from the plurality of routes that includes the determined stop;
assigning the requested item pick up and/or delivery to a vehicle corresponding to the determined route based on a determination that (1) addition of the location as an additional stop to the determined route does not violate time constraints associated with the determined route and the on-demand request and (2) addition of the location as the additional stop to the determined route does not exceed a defined maximum deviation distance for the vehicle traveling the determined route;
generating a second electronic communication to the assigned vehicle, the second electronic communication comprising a command that designates the assigned vehicle to travel to the location and
transmitting the second electronic communication to the assigned vehicle.

11. The method of claim 10 , wherein the request identifies the item for delivery to the location, and further comprising determining the determined route further based on vehicle inventory of the item on each of the plurality of routes.

12. A non-transitory computer readable medium comprising instructions that when executed cause an electronic hardware processor to perform a method of assigning an on-demand request to a vehicle on a delivery route, the method comprising:
receiving a first electronic communication from a customer, the first electronic communication including an on-demand request for pick up and/or delivery of an item, the request indicating a location for the requested item pick up and/or delivery;
determining, in a geographic area, a plurality of routes, each of the plurality of routes comprising a plurality of stops and having a corresponding vehicle traveling the route when the on-demand request is received;
determining, from the plurality of routes, a subset of stops which are within a threshold distance of the location for the requested item pick up and/or delivery and which are still pending for the current day;
determining a stop from the subset of stops which has the minimum distance from the location for the requested item pick up and/or delivery;
determining a route from the plurality of routes that includes the determined stop;
assigning the requested item pick up and/or delivery to the vehicle corresponding to the determined route based on a d

Assignees

• United States Postal Service

Inventors

• Dixon Robert E
• Luckay Ryan

Classifications

• G01C21/3415

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title

• G06Q10/06315

  Needs-based resource requirements planning or analysis · CPC title

• G06Q10/08355 Primary

  Routing methods · CPC title

• G06Q10/0834

  Choice of carriers · CPC title

• G01C21/343

  Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047) · CPC title