Determination and optimization of delivery routes
First Claim
Patent Images
1. A system for determining an optimal delivery route, comprising:
- at least one computing device; and
program instructions executable in the at least one computing device that, when executed, cause the at least one computing device to perform a method comprising;
identifying a plurality of geocoordinates for at least one of a plurality of locations;
generating a plurality of candidate routes by applying a convex hull to an outermost subset of the geocoordinates and psuedorandomly inserting an innermost subset of the geocoordinates into segments of the convex hull while minimizing a change in travel cost for the segments, the convex hull being a smallest possible convex polygon encompassing the geocoordinates as coalesced;
applying a genetic optimization to the plurality of candidate routes until a termination condition has been satisfied by;
identifying a plurality of street segments for at least one of the candidate routes based at least in part on the geocoordinates and digital map data;
for the at least one of the candidate routes, coalescing at least two different ones of the geocoordinates located on a same one of the street segments into a single geocoordinate;
determining a fitness level for individual ones of the candidate routes;
retaining at least one of the candidate routes based at least in part on the fitness level determined for the individual ones of the candidate routes; and
replacing a first portion of the candidate routes having the fitness level lower than a second portion of the candidate routes with a mutated one of the candidate routes; and
identifying the optimal delivery route as one of the candidate routes based at least in part on a corresponding fitness level.
1 Assignment
0 Petitions
Accused Products
Abstract
Disclosed are various embodiments for determining and plotting delivery routes in a computing device. A set of solutions to the traveling salesman problem may be determined by applying a convex hull to determine a set of initial solutions. Computational complexity may be reduced by decreasing the dimensions of the initial solutions. The set of initial solutions may be further optimized by applying genetic optimization to determine the most efficient solutions.
14 Citations
22 Claims
-
1. A system for determining an optimal delivery route, comprising:
-
at least one computing device; and program instructions executable in the at least one computing device that, when executed, cause the at least one computing device to perform a method comprising; identifying a plurality of geocoordinates for at least one of a plurality of locations; generating a plurality of candidate routes by applying a convex hull to an outermost subset of the geocoordinates and psuedorandomly inserting an innermost subset of the geocoordinates into segments of the convex hull while minimizing a change in travel cost for the segments, the convex hull being a smallest possible convex polygon encompassing the geocoordinates as coalesced; applying a genetic optimization to the plurality of candidate routes until a termination condition has been satisfied by; identifying a plurality of street segments for at least one of the candidate routes based at least in part on the geocoordinates and digital map data; for the at least one of the candidate routes, coalescing at least two different ones of the geocoordinates located on a same one of the street segments into a single geocoordinate; determining a fitness level for individual ones of the candidate routes; retaining at least one of the candidate routes based at least in part on the fitness level determined for the individual ones of the candidate routes; and replacing a first portion of the candidate routes having the fitness level lower than a second portion of the candidate routes with a mutated one of the candidate routes; and identifying the optimal delivery route as one of the candidate routes based at least in part on a corresponding fitness level. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A non-transitory computer-readable medium for programmatically optimizing a delivery route using a non-deterministic polynomial-time (NP) complete computation embodying program instructions executable in at least one computing device that, when executed, cause the at least one computing device to perform a method comprising:
-
determining a plurality of geocoordinates for a corresponding plurality of delivery locations identified from a plurality of orders of items originated over a network, wherein the delivery locations are bundled according to a geographic area; generating a plurality of candidate routes by applying a convex hull to an outermost subset of the geocoordinates and pseudorandomly inserting an innermost subset of the geocoordinates into segments of the convex hull while minimizing a change in travel cost for the segments, the convex hull being a smallest possible convex polygon encompassing the geocoordinates; applying a genetic optimization to the candidate routes until a termination condition has been satisfied by performing a plurality of iterations of; identifying a plurality of street segments for at least one of the candidate routes based at least in part on the geocoordinates and digital map data; for the at least one of the candidate routes, coalescing at least two different ones of the geocoordinates located on a same one of the street segments into a single geocoordinate; determining a fitness level for individual ones of the candidate routes as a function of an estimated route travel time or an estimated route distance identified for a corresponding one of the candidate routes; inserting individual ones of an innermost subset of the geocoordinates into segments in the candidate routes based at least in part on the fitness level; retaining at least a portion of the candidate routes based at least in part on the fitness level, the portion of the candidate routes retained having a higher fitness level than a non-retained one of the candidate routes; mating at least two of the candidate routes as retained based at least in part on the fitness level determined for the at least two of the candidate routes to create additional ones of the candidate routes for inclusion in a new generation of candidate routes; and replacing a first portion of the new generation of candidate routes having a second fitness level lower than a second portion of the new generation of candidate routes with at least one newly generated candidate route, the at least one newly generated candidate route comprising a mutated one of the additional ones of the candidate routes; identifying the optimal delivery route as one of the new generation of candidate routes based at least in part on a corresponding fitness level; and generating a user interface for display on a client device, wherein the user interface comprises the optimal delivery route and a map for performing a delivery of items at individual ones of the delivery locations in accordance with the optimal delivery route. - View Dependent Claims (10, 11, 12, 13, 14)
-
-
15. A method for determining an optimal delivery route using a non-deterministic polynomial-time (NP) complete computation, comprising:
-
determining, via at least one computing device, a plurality of geocoordinates, individual ones of the geocoordinates corresponding to at least one of a plurality of delivery locations; generating a plurality of candidate routes by applying, via the at least one computing device, a convex hull to an outermost subset of the geocoordinates and pseudorandomly inserting an innermost subset of the geocoordinates into segments of the convex hull while minimizing a change in travel cost for the segments, the convex hull being a smallest possible convex polygon encompassing the geocoordinates; applying, via the at least one computing device, a genetic optimization to the plurality of candidate routes until a termination condition has been satisfied by; identifying a plurality of street segments for at least one of the candidate routes based at least in part on the geocoordinates and digital map data; for the at least one of the candidate routes, coalescing at least two different ones of the geocoordinates located on a same one of the street segments into a single geocoordinate; determining a fitness level for individual ones of the candidate routes; mating at least two of the candidate routes based at least in part on the fitness level of the at least two of the candidate routes to create a plurality of additional candidate routes; and replacing a first portion of the candidate routes having a lower fitness level than a second portion of the candidate routes with a mutated one of the candidate routes; and identifying, via the at least one computing device, an optimal delivery route from at least one of the candidate routes or the additional candidate routes based at least in part on the fitness level. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22)
-
Specification