System and method for constraint-based reduction of a solution space for vehicle routing
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
36 Citations
27 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
-
Specification