System and method for constraint-based reduction of a solution space for vehicle routing

• US 8,386,397 B1
• Filed: 06/30/2010
• Issued: 02/26/2013
• Est. Priority Date: 12/21/2009
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Desai, Pradeep, Agarwal, Richa, Wan, Lin, Zhang, Jingqiao, Balasubramanian, Karthik, Bhaskaran, Michael Mahesh, Lakshman, Girish S., Onetto, Marc A.
• Primary Examiner(s): FLYNN, KEVIN H
• Application Number:
  US12/827,907
• Time in Patent Office: 972 Days
• Field of Search: 705/330, 705/338
• US Class Current: 705/330
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/083 Shipping

Abstract

Various embodiments of a system and method for constraint-based reduction of a solution space for vehicle routing are described. Embodiments may include a system configured to identify sets of redundant routes within a solution space. For each given set of redundant routes, the system may utilize one or more constraints associated with conveying shipments on routes of the given set in order to eliminate one or more routes of that set from consideration. For each of multiple routes of the given set that have not been eliminated from consideration, the system may determine a respective cost associated with utilizing that route. The system may also, in response to determining that the cost associated with a particular route that has not been eliminated from consideration is less than the cost associated with other routes that have not been eliminated from consideration, add the particular route to a reduced solution space.

Claims

1. A method for generating a reduced solution space based on a given solution space that includes routes for conveying a collection of shipments, wherein the method comprises:

performing, by one or more computing devices;

identifying multiple sets of redundant routes within the given solution space, wherein each route of a given set of redundant routes includes a different permutation of a common set of locations, wherein each permutation indicates a different order in which a particular combination of locations are to be traversed by a vehicle for conveying shipments;

for each given set of at least some of the multiple sets of redundant routes;

utilizing one or more constraints associated with conveying shipments on routes of the given set to eliminate one or more routes of the given set from consideration;

for each of multiple routes of the given set that have not been eliminated from consideration, determining a respective cost associated with utilizing the route; and

in response to determining that the cost associated with a particular route of the given set that has not been eliminated from consideration is less than the cost associated with each of one or more other routes of the given set that have not been eliminated from consideration, adding the particular route of the given set to the reduced solution space without adding the other routes of the given set to the reduced solution space;

analyzing the reduced solution space to select a particular subset of one or more routes for conveying the collection of shipments, wherein the reduced solution space comprises a plurality of routes from the given solution space including one route from each given set of the at least some of the multiple sets of redundant routes.

2. The method of claim 1, wherein the particular subset of routes includes all locations at which shipments of the collection of shipments are located.

3. The method of claim 2, wherein said analyzing the reduced solution space to select a particular subset comprises solving a set cover problem, wherein routes of the reduced solution space are sets of the set cover problem and locations of shipments are the elements to be covered in the set cover problem.

4. The method of claim 2, wherein said analyzing the reduced solution space to select a particular subset comprises:

identifying multiple subsets of routes from the reduced solution space, wherein each subset of routes includes all locations at which shipments of the collection of shipments are located; and

selecting said particular subset from the multiple subsets in response to determining that the particular subset meets one or more specified objectives.

5. The method of claim 4, wherein said one or more specified objectives include an objective associated with at least one of:

route cost, route length, or route travel time.

6. The method of claim 2, wherein the method comprises, for one or more routes of the particular subset of routes, generating one or more respective shipment carrier requests, wherein each shipment carrier request specifies that a respective shipment carrier is requested to pickup one or more shipments along a respective route.

7. The method of claim 1, wherein said one or more constraints comprise one or more of:

a constraint that specifies a maximum quantity of stops permitted on a route;

a constraint that specifies a maximum distance permitted between subsequent stops in a route;

a constraint that specifies a maximum total distance permitted in a route;

a constraint that specifies pickup windows for locations of a route must be compatible based on one or more of;

the travel time between each location and the distance between each location;

a constraint that specifies shipments consolidated on the route are not to exceed a maximum vehicle load;

or

a constraint that specifies a cost associated with conveying multiple groups of shipments together on the same route be less than the sum of costs associated with conveying each group of shipments separately on individual routes.

8. The method of claim 7, wherein one or more of said constraints are specified by a contractual agreement between a vendor and a merchant.

9. The method of claim 1, wherein the method comprises identifying a route that includes only one shipment source location and one shipment destination location and adding that route to the reduced solution space.

10. A system for generating a reduced solution space based on a given solution space that includes routes for conveying a collection of shipments, the system comprising:

a memory; and

one or more processors coupled to the memory, wherein the memory comprises program instructions executable by the one or more processors to;

identify multiple sets of redundant routes within the given solution space, wherein each route of a given set of redundant routes includes a different permutation of a common set of locations, wherein each permutation indicates a different order in which a particular combination of locations are to be traversed by a vehicle for conveying shipments;

for each given set of at least some of the multiple sets of redundant routes;

utilize one or more constraints associated with conveying shipments on routes of the given set to eliminate one or more routes of the given set from consideration;

for each of multiple routes of the given set that have not been eliminated from consideration, determine a respective cost associated with utilizing the route; and

in response to determining that the cost associated with a particular route of the given set from the given set that has not been eliminated from consideration is less than the cost associated with each of one or more other routes of the given set that have not been eliminated from consideration, add the particular route of the given set to the reduced solution space without adding the other routes of the given set to the reduced solution space;

analyze the reduced solution space to select a particular subset of one or more routes for conveying the collection of shipments, wherein the reduced solution space comprises a plurality of routes from the given solution space including one route from each given set of the at least some of the multiple sets of redundant routes.

11. The system of claim 10, wherein the particular subset of routes includes all locations at which shipments of the collection of shipments are located.

12. The system of claim 11, wherein to analyze the reduced solution space to select a particular subset the program instructions are configured to solve a set cover problem, wherein routes of the reduced solution space are sets of the set cover problem and locations of shipments are the elements to be covered in the set cover problem.

13. The system of claim 11, wherein to analyze the reduced solution space to select a particular subset the program instructions are configured to:

identify multiple subsets of routes from the reduced solution space, wherein each subset of routes includes all locations at which shipments of the collection of shipments are located; and

select said particular subset from the multiple subsets in response to determining that the particular subset meets one or more specified objectives.

14. The system of claim 13, wherein said one or more specified objectives include an objective associated with at least one of:

route cost, route length, or route travel time.

15. The system of claim 11, wherein the program instructions are configured to, for one or more routes of the particular subset of routes, generate one or more respective shipment carrier requests, wherein each shipment carrier request specifies that a respective shipment carrier is requested to pickup one or more shipments along a respective route.

16. The system of claim 10, wherein said one or more constraints comprise one or more of:

a constraint that specifies a maximum quantity of stops permitted on a route;

a constraint that specifies a maximum distance permitted between subsequent stops in a route;

a constraint that specifies a maximum total distance permitted in a route;

a constraint that specifies pickup windows for locations of a route must be compatible based on one or more of;

the travel time between each location and the distance between each location;

a constraint that specifies shipments consolidated on the route are not to exceed a maximum vehicle load;

or

a constraint that specifies a cost associated with conveying multiple groups of shipments together on the same route be less than the sum of costs associated with conveying each group of shipments separately on individual routes.

17. The system of claim 16, wherein one or more of said constraints are specified by a contractual agreement between a vendor and a merchant.

18. The system of claim 10, wherein the program instructions are configured to identify a route that includes only one shipment source location and one shipment destination location and add that route to the reduced solution space.

19. A non-transitory computer-readable storage medium for generating a reduced solution space based on a given solution space that includes routes for conveying a collection of shipments, the medium storing program instructions computer-executable on a computer system to:

identify multiple sets of redundant routes within the given solution space, wherein each route of a given set of redundant routes includes a different permutation of a common set of locations, wherein each permutation indicates a different order in which a particular combination of locations are to be traversed by a vehicle for conveying shipments;

for each given set of at least some of the multiple sets of redundant routes;

utilize one or more constraints associated with conveying shipments on routes of the given set to eliminate one or more routes of the given set from consideration;

for each of multiple routes of the given set that have not been eliminated from consideration, determine a respective cost associated with utilizing the route; and

in response to determining that the cost associated with a particular route of the given set that has not been eliminated from consideration is less than the cost associated with each of one or more other routes of the given set that have not been eliminated from consideration, add the particular route of the given set to the reduced solution space without adding the other routes of the given set to the reduced solution space;

analyze the reduced solution space to select a particular subset of one or more routes for conveying the collection of shipments, wherein the reduced solution space comprises a plurality of routes from the given solution space including one route from each given set of the at least some of the multiple sets of redundant routes.

20. The computer-readable storage medium of claim 19, wherein the reduced solution space such that the particular subset of routes includes all locations at which shipments of the collection of shipments are located.

21. The computer-readable storage medium of claim 20, wherein to analyze the reduced solution space to select a particular subset the program instructions are configured to solve a set cover problem, wherein routes of the reduced solution space are sets of the set cover problem and locations of shipments are the elements to be covered in the set cover problem.

22. The computer-readable storage medium of claim 20, wherein to analyze the reduced solution space to select a particular subset the program instructions are configured to:

identify multiple subsets of routes from the reduced solution space, wherein each subset of routes includes all locations at which shipments of the collection of shipments are located; and

select said particular subset from the multiple subsets in response to determining that the particular subset meets one or more specified objectives.

23. The computer-readable storage medium of claim 22, wherein said one or more specified objectives include an objective associated with at least one of:

route cost, route length, or route travel time.

24. The computer-readable storage medium of claim 20, wherein the program instructions are configured to, for one or more routes of the particular subset of routes, generate one or more respective shipment carrier requests, wherein each shipment carrier request specifies that a respective shipment carrier is requested to pickup one or more shipments along a respective route.

25. The computer-readable storage medium of claim 19, wherein said one or more constraints comprise one or more of:

a constraint that specifies a maximum quantity of stops permitted on a route;

a constraint that specifies a maximum distance permitted between subsequent stops in a route;

a constraint that specifies a maximum total distance permitted in a route;

a constraint that specifies pickup windows for locations of a route must be compatible based on one or more of;

the travel time between each location and the distance between each location;

a constraint that specifies shipments consolidated on the route are not to exceed a maximum vehicle load;

or

a constraint that specifies a cost associated with conveying multiple groups of shipments together on the same route be less than the sum of costs associated with conveying each group of shipments separately on individual routes.

26. The computer-readable storage medium of claim 25, wherein one or more of said constraints are specified by a contractual agreement between a vendor and a merchant.

27. The computer-readable storage medium of claim 19, wherein the program instructions are configured to identify a route that includes only one shipment source location and one shipment destination location and add that route to the reduced solution space.