Apparatus for solving optimization problems and delivery planning system
First Claim
1. A problem solver apparatus for solving an optimization problem whose possible solutions contain a plurality of stationary elements and non-stationary elements, said apparatus comprising:
- searching strategy optimization means for creating a population of individuals each of which has a chromosome specifying a solution searching strategy, and optimizing the solution searching strategies by using a genetic algorithm, wherein each of the solution searching strategies describes a selection order of the non-stationary elements, a starting element from which the stationary elements are scanned, and a scanning direction of the stationary elements;
solution searching means for finding candidate solutions in accordance with the solution searching strategies specified by the chromosomes of the individuals; and
solution output means for outputting the candidate solutions that meet a predetermined criterion.
1 Assignment
0 Petitions
Accused Products
Abstract
A problem solver apparatus for solving optimization problems, which finds better solutions at a higher speed by utilizing both genetic algorithms and OR-based techniques. When an optimization problem is given to the problem solver apparatus, a searching strategy optimization unit creates a population of individuals using a genetic algorithm. Each individual has a chromosome to indicate a solution searching strategy. Upon receipt of such a population, a solution searching unit searches for solutions according to the strategies respectively indicated by the chromosomes of the individuals, thus obtaining candidate solutions. This group of candidate solutions is returned to the searching strategy optimization unit. The searching strategy optimization unit calculates fitness values of respective candidate solutions in the received candidate group. The searching strategy optimization unit applies some genetic operators to the individuals, thereby producing a new generation population. The produced new generation population is directed to the solution searching unit to perform another search. The problem solver apparatus repeats the above procedure until the candidate solutions show some acceptable fitness values. Lastly, the fittest candidate solution is chosen as the final solution of the optimization problem.
-
Citations
26 Claims
-
1. A problem solver apparatus for solving an optimization problem whose possible solutions contain a plurality of stationary elements and non-stationary elements, said apparatus comprising:
-
searching strategy optimization means for creating a population of individuals each of which has a chromosome specifying a solution searching strategy, and optimizing the solution searching strategies by using a genetic algorithm, wherein each of the solution searching strategies describes a selection order of the non-stationary elements, a starting element from which the stationary elements are scanned, and a scanning direction of the stationary elements; solution searching means for finding candidate solutions in accordance with the solution searching strategies specified by the chromosomes of the individuals; and solution output means for outputting the candidate solutions that meet a predetermined criterion. - View Dependent Claims (2, 3, 4)
-
-
5. A delivery planning system for solving a delivery planning problem, where a plurality of carriers deliver packages from a distribution center to different destinations under given constraints, said system comprising.
searching strategy optimization means for creating a population of individuals each of which has a chromosome specifying a solution searching strategy, and optimizing the solution searching strategies by using a genetic algorithm, wherein each of the solution searching strategies describes a selection order of the carriers, an initial destination from which the destinations are scanned, and a scanning direction of the destinations; -
solution searching means for finding proposed delivery plans in accordance with the solution searching strategies specified by the chromosomes of the individuals; and solution output means for outputting the proposed delivery plans that meet a predetermined criterion. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
Specification