Optimizing solutions using local virtual forces

• US 20070022061A1
• Filed: 11/23/2005
• Published: 01/25/2007
• Est. Priority Date: 07/20/2005
• Status: Abandoned Application

• Current Assignee: BBN Technologies Corporation (Rtx Corporation)
• Original Assignee: BBNT Solutions LLC (Rtx Corporation)
• Inventors: Ramanathan, Subramanian, Brinn, Marshall, Helsinger, Aaron
• Application Number:
  US11/287,576
• Publication Number:
  US 20070022061A1
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

Described are methods and apparatus, including computer program products, for optimizing solutions using local attractive and/or repulsive virtual forces. In one aspect, a first virtual force is defined that is associated with an attractive characteristic and has a weighting parameter. A second virtual force is defined that is associated with a repulsive characteristic and has a weighting parameter. A detected virtual force is received that includes the first virtual force, the second virtual force, or a combination thereof. At an element associated with receiving the detected virtual force, a path is selected from a plurality of available paths based on the detected virtual force.

Claims

1. An optimization method using virtual forces, the method comprising:

receiving a detected virtual force comprising a first virtual force, a second virtual force, or a combination thereof, the first virtual force being associated with an attractive characteristic and a first weighting parameter, the second virtual force being associated with a repulsive characteristic and a second weighting parameter; and

selecting, at an element associated with receiving the detected virtual force, a path from a plurality of available paths based on the detected virtual force.

2. The method of claim 1, wherein selecting comprises determining a direction in which to travel.

3. The method of claim 1, wherein selecting is associated with logistics planning.

5. The method of claim 1, wherein the first virtual force, the second virtual force, or any combination thereof represent a reactive characteristic.

6. The method of claim 1, wherein the first virtual force is based on a state associated with an element generating the first virtual force, the second virtual force is based on a state associated with an element generating the second virtual force, or any combination thereof.

7. The method of claim 6, wherein the state is associated with a quantity of an item.

8. The method of claim 1, wherein the first virtual force, the second virtual force, or any combination thereof represent an anticipatory characteristic.

9. The method of claim 1, further comprising generating the second virtual force based on a location of an element generating the second virtual force.

10. The method of claim 1, further comprising generating the second virtual force based on a first element associated with supplying an item such that other similar elements capable of also being associated with supplying the item are repulsed from a location of the first element.

11. The method of claim 1, wherein the first virtual force, the second virtual force, or any combination thereof represent an auxiliary characteristic.

12. The method of claim 11, wherein the auxiliary characteristic comprises an oscillation avoidance force, a random perturbation force, an inertia force, or any combination thereof.

13. The method of claim 1, wherein the path is associated with a transportation network.

14. The method of claim 13, further comprising representing the transportation network employing nodes and links.

15. The method of claim 14, wherein selecting further comprises selecting the path based on distances along the links, redundancy through the network, speeds on which links can be traveled, or any combination thereof.

16. The method of claim 14, wherein the links comprise roads, waterways, air routes, or any combination thereof.

17. The method of claim 1, wherein receiving further comprises receiving a signal representing the detected virtual force.

18. The method of claim 17, further comprising determining a distance between the element associated with receiving the detected virtual force and an element transmitting the virtual force based on a strength of the signal.

19. The method of claim 17, wherein the signal comprises location information, the method further comprising determining a distance between the element associated with receiving the detected virtual force and an element transmitting the virtual force based on the location information.

20. The method of claim 19, wherein the location information is based on a GPS signal.

21. The method of claim 1, wherein the first virtual force, the second virtual force, or any combination thereof is based on a force function.

22. The method of claim 21, wherein the force function comprises a maximum distance parameter.

23. The method of claim 21, wherein the force function comprises a traversability parameter.

24. The method of claim 21, wherein the force function comprises a gradient of local pressures.

25. The method of claim 21, further comprising determining a value associated with the force function employing a genetic algorithm.

26. The method of claim 1, further comprising determining the first weighting parameter, the second weighting parameter, or any combination thereof employing a genetic algorithm.

27. The method of claim 26 wherein determining further comprises employing, by the genetic algorithm, an environment in which the plurality of available paths is based.

28. The method of claim 1, wherein receiving further comprises receiving the detected virtual force based on a distance from a source of the detected virtual force.

29. The method of claim 28, wherein the distance is based on one or more of the available paths.

4. The method of claim 4, wherein receiving further comprises receiving the detected virtual force by a deliverer of an item, the method further comprising:

associating a supplier of the item, a consumer of the item, or any combination thereof with the first virtual force; and

associating another deliverer of the item with the second virtual force.

30. A system for optimizing solutions using local virtual forces, the system comprising:

a means for receiving a detected virtual force comprising a first virtual force, a second virtual force, or a combination thereof, the first virtual force being associated with an attractive characteristic and a first weighting parameter, the second virtual force being associated with a repulsive characteristic and a second weighting parameter; and

a means for selecting, at an element associated with receiving the detected virtual force, a path from a plurality of available paths based on the detected virtual force.

31. A computer program product, tangibly embodied in an information carrier, for optimizing solutions using local virtual forces, the computer program product including instructions being operable to cause data processing apparatus to:

receive a detected virtual force comprising a first virtual force, a second virtual force, or a combination thereof, the first virtual force being associated with an attractive characteristic and a first weighting parameter, the second virtual force being associated with a repulsive characteristic and a second weighting parameter; and

select, at an element associated with receiving the detected virtual force, a path from a plurality of available paths based on the detected virtual force.