Validation of routes in automatic route design

Patent metadata

Field	Value
Publication number	US-2020242554-A1
Application number	US-202016777459-A
Country	US
Kind code	A1
Filing date	Jan 30, 2020
Priority date	Jan 30, 2019
Publication date	Jul 30, 2020
Grant date	—

Abstract

A system including one or more processors and one or more non-transitory computer-readable media storing computing instructions configured to run on the one or more processors and perform certain acts. The acts can include obtaining a sequence of stops and service time windows for the stops. The acts also can include generating a sequence of driver states that satisfies the sequence of the stops. The acts further can include determining, for each pair of respective sequential driver states from the sequence of driver states, whether to generate a respective recommendation to add a respective additional driver state within the respective sequential driver states in order to satisfy a set of rules. The acts additionally can include updating the sequence of driver states based on the respective recommendations, such that the sequence of driver states is feasible in view of the service time windows and the set of rules. The acts further can include outputting the sequence of driver states. Other embodiments are described.

First claim

What is claimed is:

1 . A system comprising:
one or more processors; and one or more non-transitory computer-readable media storing computing instructions configured to run on the one or more processors and perform:
obtaining a sequence of stops and service time windows for the stops;
generating a sequence of driver states that satisfies the sequence of the stops;
determining, for each pair of respective sequential driver states from the sequence of driver states, whether to generate a respective recommendation to add a respective additional driver state within the respective sequential driver states in order to satisfy a set of rules;
updating the sequence of driver states based on the respective recommendations, such that the sequence of driver states is feasible in view of the service time windows and the set of rules; and
outputting the sequence of driver states.

2 . The system of claim 1 , wherein updating the sequence of driver states based on the respective recommendations further comprises:
for each of the respective recommendations, determining whether the respective additional driver state can be added at a specified time, and if not, whether to replace the respective additional driver state with a different respective additional driver state.

3 . The system of claim 1 , wherein outputting the sequence of driver states further comprises:
outputting a respective start time and a respective end time for each driver state of the sequence of driver state.

4 . The system of claim 1 , wherein the set of rules comprises one or more duration rules and one or more cumulative rules.

5 . The system of claim 4 , wherein each of the one or more duration rules comprises a respective rule identifier, a respective minimum duration, a respective maximum duration, and a respective applied driver state type.

6 . The system of claim 5 , wherein determining whether to generate the respective recommendation to add the respective additional driver state within the respective sequential driver states in order to satisfy the set of rules further comprises:
applying a respective duration rule of the one or more duration rules by:
iterating through the sequence of driver states to determine a cumulative duration for the respective applied driver state type until a respective driver state of the driver sequence of driver states is not within the respective applied driver state type; and
validating the respective duration rule when the cumulative duration is between the respective minimum duration and the respective maximum duration.

7 . The system of claim 4 , wherein each of the one or more duration rules comprises a respective rule identifier, a respective minimum duration, a respective maximum duration, a respective applied driver state type, and a respective stop driver state type.

8 . The system of claim 7 , wherein determining whether to generate the respective recommendation to add the respective additional driver state within the respective sequential driver states in order to satisfy the set of rules further comprises:
applying a respective cumulative rule of the one or more cumulative rules by:
iterating through the sequence of driver states to determine a cumulative duration for the respective applied driver state type until a respective driver state of the driver sequence of driver states is within the respective applied stop driver type; and
validating the respective duration rule when the cumulative duration is between the respective minimum duration and the respective maximum duration.

9 . The system of claim 1 , wherein driver state types that apply to the set of rules are defined hierarchically based on hours of service rules.

10 . The system of claim 1 , wherein the respective additional driver state comprises one of a break state, a layover state, or a wait state.

11 . A method being implemented via execution of computing instructions configured to run at one or more processors and stored at one or more non-transitory computer-readable media, the method comprising:
obtaining a sequence of stops and service time windows for the stops; generating a sequence of driver states that satisfies the sequence of the stops; determining, for each pair of respective sequential driver states from the sequence of driver states, whether to generate a respective recommendation to add a respective additional driver state within the respective sequential driver states in order to satisfy a set of rules; updating the sequence of driver states based on the respective recommendations, such that the sequence of driver states is feasible in view of the service time windows and the set of rules; and outputting the sequence of driver states.

12 . The method of claim 11 , wherein updating the sequence of driver states based on the respective recommendations further comprises:
for each of the respective recommendations, determining whether the respective additional driver state can be added at a specified time, and if not, whether to replace the respective additional driver state with a different respective additional driver state.

13 . The method of claim 11 , wherein outputting the sequence of driver states further comprises:
outputting a respective start time and a respective end time for each driver state of the sequence of driver state.

14 . The method of claim 11 , wherein the set of rules comprises one or more duration rules and one or more cumulative rules.

15 . The method of claim 14 , wherein each of the one or more duration rules comprises a respective rule identifier, a respective minimum duration, a respective maximum duration, and a respective applied driver state type.

16 . The method of claim 15 , wherein determining whether to generate the respective recommendation to add the respective additional driver state within the respective sequential driver states in order to satisfy the set of rules further comprises:
applying a respective duration rule of the one or more duration rules by:
iterating through the sequence of driver states to determine a cumulative duration for the respective applied driver state type until a respective driver state of the driver sequence of driver states is not within the respective applied driver state type; and
validating the respective duration rule when the cumulative duration is between the respective minimum duration and the respective maximum duration.

17 . The method of claim 14 , wherein each of the one or more duration rules comprises a respective rule identifier, a respective minimum duration, a respective maximum duration, a respective applied driver state type, and a respective stop driver state type.

18 . The method of claim 17 , wherein determining whether to generate the respective recommendation to add the respective additional driver state within the respective sequential driver states in order to satisfy the set of rules further comprises:
applying a respective cumulative rule of the one or more cumulative rules by:
iterating through the sequence of driver states to determine a cumulative duration for the respective applied driver state type until a respective driver state of the driver sequence of driver states is within the respective applied stop driver type; and
validating the respective duration rule when the cumulative duration is between the respective minimum duration and the respective maximum duration.

19 . The method of claim 11 , wherein driver state types that apply to the set of rules are defined hierarchicall

Assignees

• Walmart Apollo Llc

Inventors

• Huang Jing
• Liu Minghui
• Fu Mingang

Classifications

• G01C21/343

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

• G01C21/3484

  Personalized, e.g. from learned user behaviour or user-defined profiles · CPC title

• G06Q10/08355 Primary

  Routing methods · CPC title

• G06F16/29

  Geographical information databases · CPC title