Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
2005-06-07
2005-06-07
Knight, Anthony (Department: 2121)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
Reexamination Certificate
active
06904421
ABSTRACT:
Solving a Traveling Salesman Problem (TSP) by selecting a set of locations to visit, selecting a starting point and an ending point from the set of locations, applying a search method to the set of locations, and providing a route as a solution to the TSP, where the search method is a combinatoric approach to a genetic search and the search method simultaneously minimizes distance and time. The route starts and ends in different locations and completes in polynomial time, such as O(n+k), where k is a constant. The solution to the TSP has many applications, including finding distribution chains to satisfy customer demand for an Internet enterprise.
REFERENCES:
patent: 5155845 (1992-10-01), Beal et al.
patent: 5489419 (1996-02-01), Diep et al.
patent: 5586219 (1996-12-01), Yufik
patent: 5623404 (1997-04-01), Collins et al.
patent: 5737728 (1998-04-01), Sisley et al.
patent: 5848402 (1998-12-01), Pao et al.
patent: 6052678 (2000-04-01), Itoh et al.
patent: 6182008 (2001-01-01), Nikiel et al.
patent: 6363368 (2002-03-01), Shinagawa
patent: 6418398 (2002-07-01), Dueck et al.
patent: 2001/0011258 (2001-08-01), Shinagawa
Augmenting Genetic Algorithms with Memory to Solve Traveling Salesman Problems, Sushil J. Louis, Gong Li, Dept. of Computer Science University of Nevada, (1997).
Eshelman, L.J., “The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination”,In: Foundations of Genetic Algorithms, San Mateo, CA: Morgan Kaufmann Publishers, G.J.E. Rawlins, ed., pp. 265-283, (1991).
Fogel, D.B., “An Evolutionary Approach to the Traveling Salesman Problem”,Biological Cybernetics, 60(2) , pp. 139-144, (1988).
Grefenstette, J., et al., “Genetic Algorithms for the Traveling Salesman Problem”,Proceedings of an International Conference on Genetic Algorithms and their Applications, pp. 160-168, (Jul. 1985).
Kalantari, B., et al., “An algorithm for the traveling salesman problem with pickup and delivery customers”,European Journal of Operational Research, 22(3), pp. 377-386, (1985).
Mitchell, M., “Genetic Algorithms: An Overview”,In: Introduction to Genetic Algorithms, Chapter 1, Cambridge, Mass: The MIT Press, M. Mitchell, ed., pp. 1-34, (1996).
Yip, P.P., et al., “A New Approach to the Traveling Salesman Problem”,Proceedings of the International Joint Conference on Neural Networks, vol. 3 of2, Nagoya Congress Center, Japan, pp. 1569-1572, (Oct. 1993).
Fredrick Kris T.
Holmes Michael B.
Honeywell International , Inc.
Knight Anthony
LandOfFree
Methods for solving the traveling salesman problem does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for solving the traveling salesman problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for solving the traveling salesman problem will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3509178