Non-linear systems and methods for destination selection

Abstract

Apparatus and methods for machine-based planning. The apparatus may cluster a plurality of geographically different resources into a plurality of clusters of proximate resources. The apparatus may calculate a cost of transporting each resource to each of a plurality of destinations. The apparatus may map each cluster to one of the destinations to determine a sum of costs of transporting all of the resources to the destinations. The apparatus may assign to each of the plurality of destinations only resources: that are mapped to the destination; for which the destination has sufficient capacity to accommodate the resources; and whose assignment to the destination does not exclude from the destination, by filling the capacity, a different resource that is: mapped to the destination; and has a net cost that is higher than a net cost of the resource of the assignment.

1 . A method for machine-based dynamic assignment of resources, the method comprising, using a processor running computer-executable instructions:
 clustering a plurality of geographically different resources into a plurality of clusters of proximate resources;   calculating a cost of transporting each resource to each of a plurality of destinations and storing the costs in-machine-readable memory, referenced by resource and destination; and   mapping each cluster to one of the destinations, the mapping determining a total cost of transporting the plurality of resources to their respective destinations, wherein the mapping of a cluster comprises mapping all of the resources included in the cluster to the same destination;   ordering each resource in a cluster based on a set of shadow costs, each shadow cost comprising a cost of remapping a resource from the destination to which the cluster is mapped to a next-more-costly destination, the shadow costs based at least in part on the stored costs for transporting each resource to each of the plurality of destinations;   determining that a total number of resources in a first cluster mapped to a first destination exceeds a predetermined capacity of the first destination; and   based on the ordering, remapping a resource that exceeds the predetermined capacity from the first destination to a second destination.   
     
     
         2 . The method of  claim 1  wherein the total cost is a lowest cost of transporting the plurality of resources to their respective destinations. 
     
     
         3 . The method of  claim 1  wherein
 each destination has a redetermined capacity; and 
 the mapping is constrained to identify a set of destinations, the set having an aggregate capacity greater than or equal to the total number of resources. 
 
     
     
         4 - 5 . (canceled) 
     
     
         6 . The method of  claim 1  further comprising:
 storing in machine-readable memory:
 for a first of the resources a first resource record including, for each of the destinations, a first cost of remapping the first resource to a next more-costly destination; and, 
 for a second of the resources a second resource record including, for each of the destinations, a second cost of remapping the second resource to a next more-costly destination; 
 
 using the processor, identifying a destination, of the plurality of destinations, for which the first and second costs are equal; and 
 changing the second resource record by a predetermined amount so that the second cost is less than the first cost. 
 
     
     
         7 . The method of  claim 1  further comprising calculating for each cluster a sum of costs of transporting each resource in the cluster to the one of the destinations to which the cluster is mapped. 
     
     
         8 . The method of  claim 1  wherein a resource is not constrained to fall within a particular cluster. 
     
     
         9 . The method of  claim 1  wherein a total number of destinations to which clusters are mapped is constrained to be less than or equal to a number of destinations specified by a user. 
     
     
         10 - 12 . (canceled) 
     
     
         13 . The method of  claim 1  further comprising identifying a destination to which both a first of the clusters and a second of the clusters have been mapped. 
     
     
         14 . The method of  claim 13  further comprising, when the destination is a first of the destinations, remapping the second of the clusters from the first of the destinations to a second of the destinations only if the first of the destinations has a predetermined capacity that is exceeded by the combined resources of both the first of the clusters and the second of the clusters; wherein the second of the destinations is different from the first of the destinations. 
     
     
         15 . The method of  claim 14  wherein the remapping includes:
 evaluating for each resource in the second cluster a net cost of remapping the resource to each destination in the plurality of destinations, the net cost comprising an amount by which the cost of remapping the resource exceeds a cost of mapping the resource to the first destination; 
 summing, for each destination, the net costs; and 
 selecting as the second destination that destination having the lowest net cost. 
 
     
     
         16 . The method of  claim 15  further comprising, after the selecting, calculating for each cluster a sum of costs of transporting each resource in the cluster to the one of the destinations to which the cluster is mapped. 
     
     
         17 . The method of  claim 14  further comprising repeating the identifying and the remapping until all of the clusters are mapped to destinations, the destinations comprising a set of destinations having an aggregate capacity not exceeded by the total number of resources. 
     
     
         18 . The method of  claim 17  further comprising evaluating for each resource a net cost, for each of the destinations to which the resource is not mapped, of remapping the resource from that destination to which the resource is mapped to that destination to which the resource is not mapped, the net cost comprising the amount by which the cost of remapping the resource exceeds a cost of mapping the resource. 
     
     
         19 . The method of  claim 18  further comprising assigning to each of the plurality of destinations only resources:
 that are mapped to the destination; 
 for which a predetermined capacity of the destination is not exceeded by assignment of the resource; and 
 whose assignment to the destination does not exclude from the destination, by filling the destination, a different resource that is:
 mapped to the destination; and 
 has a net cost of remapping that is higher than the resource of the assignment. 
 
 
     
     
         20 . The method of  claim 19  further comprising, before the assigning:
 identifying in machine readable memory:
 a first resource record in which there is a first net cost; and 
 a second resource record in which there is a second net cost, the first and second net costs being equal; and 
 
 using the processor, changing the second resource record by a predetermined amount so that the second net cost is less than the first net cost. 
 
     
     
         21 . A system for machine-based dynamic assignment of resources, the system comprising:
 means for clustering a plurality of geographically different resources into a plurality of clusters of proximate resources;   means for calculating a cost of transporting each resource to each of a plurality of destinations and storing the costs in machine-readable memory, referenced by resource and destination;   means for mapping each cluster to one of the destinations, the mapping determining a total cost of transporting the plurality of resources to their respective destinations, wherein the mapping of a cluster comprises mapping all of the resources included in the cluster to the same destination;   means for ordering each resource in the cluster based on a set of shadow costs, each shadow cost comprising a cost of remapping a resource from the destination to which the cluster is mapped to a next-more-costly destination, the shadow costs based at least in art on the stored costs for transporting each resource to each of the plurality of destinations;   means for determining that assigning a resource in the cluster to the destination does not exclude from the destination by filling a predetermined capacity, a different resource that is mapped to the destination and has a higher shadow cost; and   means for assigning the resource to the destination.   
     
     
         22 . The system of  claim 21  wherein the total cost is a lowest cost of transporting all of the resources to the destinations. 
     
     
         23 . The system of  claim 21  wherein each destination has a predetermined capacity to hold a number of resources and the mapping is constrained to identify a set of destinations, the set having an aggregate capacity greater than or equal to the total number of resources. 
     
     
         24 - 25 . (canceled) 
     
     
         26 . The system of  claim 21  further comprising:
 means for providing:
 for a first of the resources, a first resource record including, for each of the destinations, a first shadow cost for the first resource; and, 
 for a second of the resources, a second resource record including, for each of the destinations, a second shadow cost for the second resource; 
 
 means for identifying a destination, of the plurality of destinations, for which the first and second shadow costs are equal; and 
 means for changing the second resource record so that the second shadow cost is less than the first shadow cost. 
 
     
     
         27 . The system of  claim 21  further comprising means for calculating for each cluster a sum of costs of transporting each resource in the cluster to the one of the destinations to which the cluster is mapped. 
     
     
         28 . The system of  claim 21  wherein a resource is not constrained to fall within a particular cluster. 
     
     
         29 . The system of  claim 21  wherein a total number of destinations to which clusters are mapped is constrained to be less than or equal to a number of destinations specified by a user. 
     
     
         30 - 32 . (canceled) 
     
     
         33 . The system of  claim 21  further comprising means for identifying a destination to which both a first of the clusters and a second of the clusters have been mapped. 
     
     
         34 . The system of  claim 33  further comprising means for remapping, when the destination is a first of the destinations, the second of the clusters from the first of the destinations to a second of the destinations if the first of the destinations has a capacity that is exceeded by the combined resources of both the first of the clusters and the second of the clusters; wherein the second of the destinations is different from the first of the destinations. 
     
     
         35 . The system of  claim 34  wherein the remapping includes:
 evaluating for each resource in the second cluster a net cost of remapping the resource to each destination in the plurality of destinations, the net cost comprising an amount by which the cost of remapping the resource exceeds a-cost of mapping the resource to the first destination; 
 summing, for each destination, the net costs; and 
 selecting as the second destination that destination having the lowest net cost. 
 
     
     
         36 . The system of  claim 35  further comprising means for calculating, after the selecting, for each cluster, a sum of costs of transporting each resource in the cluster to the one of the destinations to which the cluster is mapped. 
     
     
         37 . The system of  claim 34  further comprising means for repeating the identifying and the remapping until all of the clusters are mapped to destinations, the destinations comprising a set of destinations having an aggregate capacity not exceeded by the total number of resources. 
     
     
         38 . The system of  claim 37  further comprising means for evaluating for each resource a net cost, for each of the destinations to which the resource is not mapped, of remapping the resource from that destination to which the resource is mapped to that destination to which the resource is not mapped, the net cost comprising an amount by which the cost of remapping the resource exceeds a cost of the mapping the resource. 
     
     
         39 . The system of  claim 38  further comprising means for assigning to each of the plurality of destinations only resources:
 that are mapped to the destination; 
 for which a predetermined capacity of the destination is not exceeded by assignment of the resource; and 
 whose assignment to the destination does not exclude from the destination, by filling the destination, a different resource that is:
 mapped to the destination; and 
 has a net cost of remapping that is higher than the resource of the assignment. 
 
 
     
     
         40 . The system of  claim 39  further comprising:
 means for identifying, before the assigning:
 a first resource record in which there is a first net cost; and 
 a second resource record in which there is a second net cost, the first and second net costs being equal; and 
 
 means for changing the second resource record to lower the second net cost by a predetermined amount so that the second net cost is less than the first net cost.