Optimization with ruin recreate

Details Optimization with ruin recreate Optimization with ruin recreate

1999-10-01

2002-07-09

Hoff, Marc S. (Department: 2863)

Data processing: measuring, calibrating, or testing

Measurement system

Statistical measurement

C705S007380

Reexamination Certificate

active

06418398

ABSTRACT:

1
. BACKGROUND OF THE INVENTION
1.1 Field of the Invention
The present invention relates to an automatic method of computerized optimization of a technical system like for instance routing systems such as a transportation routing system or a communication network or a supply chain system.
1.2 Description and Disadvantages of Prior Art
State of the art comprises a rich set of classical improvement heuristics of optimization approaches of technical systems. For comparison reasons the different approaches are often applied to published problem instances which are already extensively studied in the literature as the famous Traveling Salesman Problem which was often considered in the literature. For instance G. Reinelt, TSPLIB95, University of Heidelberg, Germany, 1995 and M. Grotschel, O. Holland, Math. Prog. 1991, 51, 141 published such an extensively studied set of traveling salesman problems. Also the problem set of M. Solomon, Operations Research, 1987, 35, 254 could be mentioned at this place.
Optimization of many technical systems can be stated as optimization of a routing system. Due to their importance routing systems have been subject of extensive studies. With respect to the technical problem of transportation routing the following state of the art work could be mentioned:
S. R. Thangiah, I. H. Osman, T. Sun, Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows, working paper, 1994), UKC/OR94/4; J.-Y. Potvin, S. Begio, 1994, A Genetic Approach to the Vehicle Routing Problem with Time Windows, Publication CRT-953, Centre de recherche sur les transports, Universite de Montreal; P. M. Thompson, H. Psaraftis, 1989, Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems, Operations Research 41, 935-946; J.-Y. Potvin, T. Kervahut, B.-L. Garcia, J.-M. Rousseau, 1993, A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows, Publication CRT-855, Centre de recherche sur les transports, Universite de Montreal; W.-C. Chiang, R. Russell, 1993, Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows, working paper, Department of Quantitative Methods, University of Tulsa, Tulsa, OK 74104; Y. Rochat, E. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, Vol 1, No 1, 1995, 147-67.
With respect to the applied methods the following important approaches can be distinguished within the state of the art:
1.2.1 Simulated Annealing and its Relatives
Simulated Annealing as outlined for example in N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller, J. Chem. Phys. 1953, 21, 1087., S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi, Science, 1983, 220, 671, S. Kirkpatrick, G. Toulouse, J. Physique, 1985, 46, 1277., Threshold Accepting as outlined for example in G. Dueck, T. Scheuer, J. Comp. Phys., 1990, 90, 161, the Great Deluge Algorithm as outlined for example in G. Dueck, J. Comp. Phys., 1993, 104, 86, G. Dueck, T. Scheuer, H.-M. Wallmeier, Spektrum der Wissenschaft, March 1993, Record-to-Record Travel technique as outlined for example in G. Dueck, J. Comp. Phys., 1993, 104, 86, and related Monte Carlo-type optimization algorithms as outlined for example in K. Binder, D. W. Heermann, Monte Carlo Simulation in Statistical Physics, Springer, N.Y., 1992, T. J. P. Penna, Phys. Rev. E, 1995, 51, R
1
-R
3
apply ideas of statistical physics and applied mathematics to find near-to-optimum solutions for combinatorial optimization problems. These are all iterative exchange algorithms. They start with an initial configuration and proceed by small exchanges in the actual or current solution to get a tentative new solution. The tentative new solution is evaluated, i.e. its objective function, e.g. its total cost, is computed. The algorithmic decision rule is applied. It is decided if the tentative new solution is kept as the current solution, in case of acceptance the new solution is taken as the new current solution.
1.2.1.1 Decision Rules
The different algorithms work with this same structure, but they use different decision rules for acceptance/rejection. The Random Walk (RW) accepts every new solution. The Greedy Algorithm (GRE) accepts every solution which is not worse than the current solution. Simulated Annealing procedures accept every better solution and, with a certain probability, also solutions being worse than the current solution. Threshold Accepting (TA) algorithms accept every solution which is not much worse than the current solution, where “not much” is defined by a threshold. The Great Deluge Algorithm rejects every solution below a required quality level (the “waterline”). This is in principle a Darwian approach. Instead of “Only the Fittest Will Survive” the deluge principal works with “Only the Worst Will Die
1.2.1.2 Mutations
Of course, the definition of an exchange in a current solution depends on the optimization problem. Let us look, for instance, at the Traveling Salesman Problem. In order to modify the current solution to get a new tentative chosen solution, different types of Local Search mutations are commonly applied. An Exchange exchanges two nodes in the tour. The Lin-2-Opt approach cuts two connections in the tour and reconstructs a new tour by insertion of two new connections. A Node Insertion Move (NIM, or Lin-2.5-opt outlined for instance in E. Aarts, J. K. Lenstra, Local Search in Combinatorial Optimization, John Wiley & Sons, Chichester, 1997) removes a node from the tour and reinserts it at the best position. Moreover, Lin-3-Opt, Lin-4-Opt and Lin-5-Opt etc., outlined for instance in S. Lin, Bell System Techn. J., 1965}, 44, 2245, S. Lin, B. W. Kernighan, Oper. Res., 1973, 21, 498, are sometimes applied, cutting three, four, and five connections and choosing one of 4, 25, and 208 etc. possibilities to recreate the new tour, respectively.
1.2.2 Set Based Algorithms
Simulated Annealing and related techniques have in common that a new configuration is generated based on the actual one. No information about former configurations is used. Genetic Algorithms and Evolution Strategies both use a large set, of configurations as individua of a .population. Tabu Search saves information about former configurations in its Tabu List and therefore also depends on a set of configurations.
1.2.2.1 Genetic Algorithms and Evolution Strategies
Genetic Algorithms mostly use different kinds of crossover operators generating children from parent configurations, while Evolution Strategies concentrate on mutations altering a member of the population. With both techniques new configurations are produced; various implementations of these algorithms-only differ in the type of the used mutations and in the choice which configurations are allowed to reproduce or to mix with each other or forced to commit suicide.
1.2.2.2 Tabu Search
Tabu Search, outlined for instance in G. Reinelt, The Traveling Salesman, Springer, Heidelberg, 1994, is a memory based search strategy to guide the system being optimized away from parts of the solution space which were already explored. This can be achieved either by forbidding solutions already visited or structures some former solutions had in common, which are stored in a Tabu List. This list is updated after each mutation according to some proposed rules, which have to guarantee that the optimization run never reaches a solution again which was already visited before, that the Tabu List Size does not diverge, and that a good solution can be achieved.
1.2.3 Problems within Prior Art
For the basic well-known problems in combinatorial optimization these algorithms turned out to be successful for the construction of near-to-optimum solutions. Dealing with complex problems, however, we encountered in severe difficulties using these classical algorithms. If we considered steel mill schedules, airline schedules, wide area networks, or very complex tour planning tasks, we faced troubles.
Complex problems often can be seen as “discontinuous”: If

Affiliated with

Also associated with

Rating

Optimization with ruin recreate does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimization with ruin recreate, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization with ruin recreate will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2897628