US5897629A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for solving optimization problems and delivery planning system
Assignee: Fujitsu Ltd
•
Filing: 1996-12-31
•
Granted: 1999-04-27
•
Expires: 2016-12-31
Abstract
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.
Inventors
- 👤 Akio Shinagawa
- 👤 Hiroyuki Okada
- 👤 Ayumi Nakabayashi
- 👤 Kazumi Takada
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 17:11
CPC Classifications
G; G06; G06N; G06N3/00; G06N3/12; G06N3/126
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
124 words
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.
Claim 2
Dependent Claim
124 words
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.
Claim 3
Dependent Claim
37 words
A problem solver apparatus according to claim 1, wherein the chromosome includes sections respectively indicating the selection order of the non-stationary elements, the starting element of the stationary elements, and the scanning direction of the stationary elements.
Claim 4
Dependent Claim
37 words
A problem solver apparatus according to claim 1, wherein said searching strategy optimization means calculates fitness values of the candidate solutions found by said solution searching means and evaluates the individuals based on the fitness values calculated.
Claim 5
Dependent Claim
81 words
A problem solver apparatus according to claim 1, wherein a solution of the optimization problem is represented as an array of elements, said solution searching means constructs the candidate solution by incrementally adding a new element to the array of elements, and each time said solution searching means adds the new element to the array of elements, said solution searching means tries to find the array of elements that will exhibit better fitness to a predetermined objective condition under given constraints.
Claim 6
Dependent Claim
129 words
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.
Claim 7
Dependent Claim
129 words
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.
Claim 8
Dependent Claim
34 words
A delivery planning system according to claim 5, wherein said searching strategy optimization means optimizes the solution searching strategies so as to achieve reduction of delivery costs and/or better compliance to the given constraints.
Claim 9
Dependent Claim
66 words
A delivery planning system according to claim 5, wherein: the selection order designates in what order a subject carrier is selected from among the carriers; the initial destination determines to which destination the subject carrier should be allocated first; and the scanning direction designates a direction for successively selecting a target destination in order to examine feasibility of allocating the subject carrier to the target destination.
Claim 10
Dependent Claim
25 words
A delivery planning system according to claim 7, wherein the chromosome includes sections respectively indicating the selection order, the initial destinations, and the scanning direction.
Claim 11
Dependent Claim
49 words
A delivery planning system according to claim 5, wherein said searching strategy optimization means has a predefined fitness function to calculate fitness values of the proposed delivery plans found by said solution searching means and evaluating the individuals based on the fitness values calculated with the predefined fitness function.
Claim 12
Dependent Claim
23 words
A delivery planning system according to claim 5, wherein said solution searching means finds the proposed delivery plans using an Operations Research-based method.
Claim 13
Dependent Claim
27 words
A delivery planning system according to claim 5, wherein said solution searching means recognizes locations of the distribution center and the destinations in a polar coordinate system.
Claim 14
Dependent Claim
28 words
A delivery planning system according to claim 11, wherein said solution searching means recognizes the location of the distribution center as the origin of the polar coordinate system.
Claim 15
Dependent Claim
55 words
A delivery planning system according to claim 11, wherein said solution searching means recognizes one position out of the barycenter of the destinations, the barycenter of the destinations and the distribution center, the median of the destinations, and the median of the destinations and the distribution center, as the origin of the polar coordinate system.
Claim 16
Dependent Claim
27 words
A delivery planning system according to claim 5, wherein said solution searching means recognizes locations of the distribution center and the destinations in a Cartesian coordinate system.
Claim 17
Dependent Claim
28 words
A delivery planning system according to claim 14, wherein said solution searching means recognizes the location of the distribution center as the origin of the Cartesian coordinate system.
Claim 18
Dependent Claim
55 words
A delivery planning system according to claim 14, wherein said solution searching means recognizes one position out of the barycenter of the destinations, the barycenter of the destinations and the distribution center, the median of the destinations, and the median of the destinations and the distribution center, as the origin of the Cartesian coordinate system.
Claim 19
Dependent Claim
55 words
A delivery planning system according to claim 5, wherein said solution searching means selects a target destination from among the destinations and a subject carrier from among the plurality of carriers in accordance with the solution searching strategies, and assigns the target destination to the subject carrier as long as the given constraints are satisfied.
Claim 20
Dependent Claim
37 words
A delivery planning system according to claim 17, wherein said solution searching means selects the target destination from among the destinations excluding the destinations that have already been assigned to the carriers other than the subject carrier.
Claim 21
Dependent Claim
113 words
A delivery planning system according to claim 5, wherein said solution searching means takes the given constraints into consideration when finding the proposed delivery plans, and the given constraints include at least one of limitations of working hours of the distribution center, limitations of office hours of delivery acceptance desks at the destinations, limitations of access to the destinations, limitations of types of carriers that are allowed to enter to the destinations, limitations of load capacity of the carriers, availability of temperature control facility in the carriers, limitations of operating hours of the carriers, limitations of total mileage of the carriers, and limitations of the number of carriers available in the distribution center.
Claim 22
Dependent Claim
57 words
A delivery planning system according to claim 19, wherein the limitations of load capacity of the carriers, which are taken into consideration as part of the given constraints by said solution searching means, include at least one of maximum load weight of each carrier, maximum load volume of each carrier, and maximum load dimension of each carrier.
Claim 23
Dependent Claim
63 words
A delivery planning system according to claim 5, wherein said solution searching means selects a target destination from among the destinations and a subject carrier from among the plurality of carriers in accordance with the solution searching strategies, and assigns the target destination to the subject carrier in consideration of a time period during which the subject carrier stays at the target destination.
Claim 24
Dependent Claim
92 words
A delivery planning system according to claim 5, wherein said solution searching means selects a target destination from among the destinations and a subject carrier from among the carriers in accordance with the solution searching strategies, and constructs a delivery route by assigning the target destination to the subject carrier if the given constraints are satisfied, and said solution searching means, when assigning the target destination to the subject carrier, determines delivery order in such a way that a predefined evaluation function for evaluating the delivery route will indicate an optimal condition.
Claim 25
Dependent Claim
82 words
A delivery planning system according to claim 22, wherein said solution searching means, when assigning the target destination to the subject carrier, examines all connection paths interconnecting the destinations and the distribution center which are involved in the delivery route under construction, and said solution searching means determines the delivery order by choosing one of the plurality of connection paths as an appropriate place at which the target destination is inserted, so that the predefined evaluation function will indicate an optimal condition.
Claim 26
Dependent Claim
40 words
A delivery planning system according to claim 23, wherein said solution searching means, after constructing the delivery route, rearranges the delivery order within the delivery route in such a way that the predefined evaluation function will exhibit an optimal condition.
Claim 27
Dependent Claim
126 words
A delivery planning system according to claim 24, wherein the delivery route contains a plurality of connection paths including a connection path from the distribution center to an initial destination where the subject carrier is scheduled to visit first, connection paths between consecutive destinations where the subject carrier is scheduled to visit sequentially, and a connection path to the distribution center from a final destination where the subject carrier is scheduled to visit last, said solution searching means, when rearranging the delivery route, examines all the plurality of connection paths to find alternative delivery routes that satisfy the given constraints, and only when the alternative delivery routes are found, chooses one of the alternative delivery routes that exhibits a best value of the predefined evaluation function.
Claim 28
Dependent Claim
36 words
A delivery planning system according to claim 5, wherein the predetermined evaluation function for evaluating the delivery route includes at least one of total traveling time, total driving hours, total driving distance, and total fuel cost.
References Cited (Backward Citations)
US5343554A
Cited
US5136686A
Cited
US5319781A
Cited
US5222191A
Cited
JPH07219920A
Cited
JPH07230443A
Cited
US5581657A
Cited
US5541848A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-04-26 | 2002-10-26 | 2003-04-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-04-26 | 2006-10-26 | 2007-04-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-04-26 | 2010-10-26 | 2011-04-27 | $7700.00 | Window Closed / Lapsed |