Systems, apparatuses, and methods of efficient route planning for e-commerce fulfillment

Patent metadata

Field	Value
Publication number	US-10565543-B1
Application number	US-201916290040-A
Country	US
Kind code	B1
Filing date	Mar 1, 2019
Priority date	Mar 1, 2019
Publication date	Feb 18, 2020
Grant date	Feb 18, 2020

Abstract

Methods, apparatuses, and systems of route planning for package pickup and delivery includes: receiving predetermined locations in a geographic region and data representing a predetermined route connecting the predetermined locations; determining unit areas in the geographic region based on sequential nearness of the predetermined locations along the predetermined route, the unit areas including a first unit area and a second unit area, and the unit areas being configured such that all locations in the first unit area are to be visited before visiting locations of the second unit area; generating delivery patterns for determining a route connecting at least one of the unit areas, each delivery pattern including at least one of the unit areas associated with a visiting sequence; when receiving task data including target locations to visit, determining a target route using the delivery patterns and the target data; and sending the target route to a mobile apparatus.

First claim

What is claimed is:

1. An apparatus of route planning for package pickup and delivery, comprising:
a memory storing instructions; and
at least one processor configured to execute the instructions to:
receive predetermined locations in a geographic region and data representing a predetermined route connecting the predetermined locations;
determine unit areas in the geographic region based on sequential nearness of the predetermined locations along the predetermined route, wherein the unit areas comprise a first unit area and a second unit area, and the unit areas are configured such that all locations in the first unit area are to be visited before visiting locations of the second unit area;
determine, for each of the unit areas, a vector representation of the unit area by applying a graph embedding technique to addresses of locations in the unit area;
determine training delivery patterns for unit areas covering the predetermined locations, wherein each training delivery pattern comprises at least one of the unit areas ordered in a visiting sequence;
determine a vector representation of each training delivery pattern by adding vector representations of the at least one of the unit areas in the training delivery pattern;
determine a score for each training delivery pattern by inputting the vector representation of each training delivery pattern into a first machine learning model, wherein the score indicates an efficiency level for visiting the at least one of the unit areas along the visiting sequence;
update parameters of the first machine learning model based on a determination that the visiting sequence is inconsistent with the predetermined route;
determine the first machine learning model for generating the delivery patterns based on a determination that the visiting sequences of all of the training delivery patterns are consistent with the predetermined route;
generate delivery patterns for determining a route connecting at least one of the unit areas, wherein each delivery pattern comprises at least one of the unit areas associated with a visiting sequence;
in response to receiving task data comprising target locations to visit, determine a target route for visiting the target locations using the delivery patterns and the target data; and
send the target route to a mobile apparatus.

2. The apparatus of claim 1 , wherein the at least one processor configured to execute the instructions to determine the unit areas in the geographic region based on the sequential nearness of the predetermined locations along the predetermined route is further configured to execute the instructions to:
receive deliverable locations in the geographic region;
determine a location vector for each of the deliverable locations using a second machine learning model, wherein a distance between two location vectors indicates sequential nearness of two locations corresponding to the two location vectors along a delivery route;
determine, for each of the deliverable locations, a feature vector comprising the location vector and location attributes of the deliverable location; and
determine the unit areas by grouping the deliverable locations based on distances between the feature vectors, wherein distances between feature vectors of deliverable locations grouped into a unit area are within a predetermined threshold value.

3. The apparatus of claim 2 , wherein the location attributes comprise at least one of a geographic coordinate, a number of a building, a name of an area, a name of a road, or a postal code.

4. The apparatus of claim 2 , wherein the second machine learning model comprises a neural network model, and the at least one processor is further configured to execute the instructions to:
determine location vectors for each of the predetermined locations, wherein an element of a location vector comprises an attribute of an address of each of the predetermined locations;
determine probability values for a current location of the predetermined locations by inputting a location vector of the current location into the neural network model, wherein each probability value corresponds to one of the predetermined locations and indicates a probability of the one of the predetermined location being visited immediately following the current location;
determine whether a subsequent location immediately following the current location along the predetermined route corresponds to the highest probability value;
update parameters of the neural network model based on a determination that the subsequent location does not correspond to the highest probability value; and
determine probability values for the subsequent location by inputting a location vector of the subsequent location into the neural network model based on a determination that the subsequent location corresponds to the highest probability value.

5. The apparatus of claim 4 , wherein the at least one processor is further configured to execute the instructions to:
determine the neural network model for determining the location vector for each of the deliverable locations based on a determination that a location following each of the predetermined locations along the predetermined route corresponds to the highest probability value in probability values determined by the neural network model for each of the predetermined locations.

6. The apparatus of claim 1 , wherein the first machine learning model comprises a neural network model, and the at least one processor configured to generate the delivery patterns is further configured to execute the instructions to:
determine candidate delivery patterns using the unit areas, wherein each candidate delivery pattern comprises at least one of the unit areas ordered in a visiting sequence;
determine a vector representation of each candidate delivery pattern by adding vector representations of the at least one of the unit areas in the candidate delivery pattern;
determine a score for each candidate delivery pattern by inputting the vector representation of each candidate delivery pattern into first machine learning model; and
generate the delivery patterns as the candidate delivery patterns having scores higher than a predetermined threshold value.

7. The apparatus of claim 1 , wherein the at least one processor is further configured to execute the instructions to:
receive the task data comprising the target locations to visit;
determine target unit areas as unit areas covering the target locations; and
determine the target route linking the target unit areas, wherein each target unit area is to be visited for once along the target route.

8. The apparatus of claim 7 , wherein the first machine learning model comprises a neural network model, and the at least one processor configured to determine the target route linking the target unit areas is further configured to execute the instructions to:
determine at least one set of feasible delivery patterns linking the target unit areas; and
determine the target route as a feasible delivery pattern having the shortest time for visiting all of the target unit areas.

9. A computer-implemented method of route planning for package pickup and delivery, comprising:
receiving predetermined locations in a geographic region and data representing a predetermined route connecting the predetermined locations;
determining, by at least one processor, unit areas in the geographic region based on sequential nearness of the predetermined locations along the predetermined route, wherein the unit areas comprise a first unit area and a second unit area, and the unit areas are configured such that all locations in the first unit area are to be visited before visiting locations of the second unit area;
determ

Assignees

• Coupang Corp

Inventors

• Mo Wenting
• Cen Yuanyuan

Classifications

• G01C21/343

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

• G06Q10/047 Primary

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

• G06Q10/08355 Primary

  Routing methods · CPC title

• G06N20/00

  Machine learning · CPC title

• G06N3/08

  Learning methods · CPC title