×

Determination and optimization of delivery routes

  • US 10,346,766 B1
  • Filed: 10/19/2012
  • Issued: 07/09/2019
  • Est. Priority Date: 10/19/2012
  • Status: Active Grant
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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×