Apparatus for solving optimization problems and delivery planning system

• US 5,897,629 A
• Filed: 12/31/1996
• Issued: 04/27/1999
• Est. Priority Date: 05/29/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Nakabayashi, Ayumi, Takada, Kazumi, Okada, Hiroyuki, Shinagawa, Akio
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/775,333
• Time in Patent Office: 847 Days
• Field of Search: 395/13, 706/13
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

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.

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.

2. 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.

3. 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.

4. 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.

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.

6. 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.

7. 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.

8. 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.

9. 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.

10. A delivery planning system according to claim 5, wherein said solution searching means finds the proposed delivery plans using an Operations Research-based method.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.