JPH1055349A

JPH1055349A - Mathematical planning computer, distribution planning system, medium recording mathematical planning program, and medium recording distribution planning program

Info

Publication number: JPH1055349A
Application number: JP12052597A
Authority: JP
Inventors: Akio Shinagawa; 明雄品川; Hiroyuki Okada; 浩之岡田; Ayumi Nakabayashi; 歩中林; Kazusane Takada; 和実高田
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1996-05-29
Filing date: 1997-05-12
Publication date: 1998-02-24
Anticipated expiration: 2017-05-12
Also published as: JP3535342B2

Abstract

(57)【要約】【課題】良好な解を高速に探索することができるよう
にする。【解決手段】この数理計画計算装置に数理計画問題が
入力されると、解探索方針最適化手段１が遺伝的アルゴ
リズムを用いて、解探索方針を示す染色体を有する個体
３ａ〜３ｃを生成する。これらの個体で個体群３が形成
され、この個体群３は、解探索手段２に渡される。解探
索手段２は、個体群３内の各個体３ａ〜３ｃの染色体で
示された解探索方針に従って数理計画問題の解を探索
し、解候補４ａ〜４ｃを作成する。そして、解候補４ａ
〜４ｃを解候補群４として、解探索方針最適化手段１に
渡す。解探索方針最適化手段１は、解候補群４の各解候
補４ａ〜４ｃの適応度値を求める。次の世代の解候補を
探索する必要がなければ、適応度値の最も良い解候補
を、この数理計画問題の解とする。 (57) [Summary] [PROBLEMS] To enable a high-speed search for a good solution. SOLUTION: When a mathematical programming problem is input to the mathematical programming calculation device, a solution search policy optimizing means 1 generates individuals 3a to 3c having chromosomes indicating the solution search policy using a genetic algorithm. These individuals form an individual group 3, which is passed to the solution search means 2. The solution search means 2 searches the solution of the mathematical programming problem according to the solution search policy indicated by the chromosome of each of the individuals 3a to 3c in the individual group 3, and creates solution candidates 4a to 4c. And the solution candidate 4a
4c as a solution candidate group 4 to the solution search policy optimizing means 1. The solution search policy optimizing means 1 obtains fitness values of the solution candidates 4 a to 4 c of the solution candidate group 4. If it is not necessary to search for a solution candidate of the next generation, a solution candidate having the best fitness value is set as a solution of this mathematical programming problem.

Description

DETAILED DESCRIPTION OF THE INVENTION

【０００１】[0001]

【発明の属する技術分野】本発明は数理計画問題を解く
ための数理計画計算装置、配送計画問題を解くための配
送計画システム、コンピュータによって数理計画問題の
解を求めるための数理計画プログラムを記録した媒体、
及びコンピュータによって配送計画問題の解を求めるた
めの配送計画プログラムを記録した媒体に関し、特に遺
伝的アルゴリズム（ＧＡ）を用いて最適解を探索する数
理計画計算装置、遺伝的アルゴリズムを用いて最適な配
送計画を探索する配送計画システム、遺伝的アルゴリズ
ムを用いて最適解を探索する数理計画プログラムを記録
した媒体、及び遺伝的アルゴリズムを用いて最適解を探
索する配送計画プログラムを記録した媒体に関する。BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention records a mathematical planning computer for solving a mathematical programming problem, a delivery planning system for solving a delivery planning problem, and a mathematical programming program for obtaining a solution of the mathematical programming problem by a computer. Medium,
And a medium on which a distribution planning program for finding a solution to a distribution planning problem by a computer is recorded, and in particular, a mathematical programming calculation device for searching for an optimal solution using a genetic algorithm (GA), and an optimal distribution using a genetic algorithm The present invention relates to a delivery planning system for searching for a plan, a medium on which a mathematical planning program for searching for an optimal solution using a genetic algorithm is recorded, and a medium on which a delivery planning program for searching for an optimal solution using a genetic algorithm is recorded.

【０００２】[0002]

【従来の技術】数理計画問題（最適化問題）とは、一般
に、１ないし複数の変数とこれらの変数によって定義さ
れる目的関数（評価関数）とが与えられ、所定の制約条
件の下でこの目的関数の値を最大あるいは最小とする変
数の組（最適解）を求める問題である。この数理計画問
題は、ジェットエンジンの設計やネットワークの設計等
の様々な分野に利用されている。そこで、数理計画問題
の解の探索手法は、従来より様々なものが考えられてい
る。2. Description of the Related Art In general, a mathematical programming problem (optimization problem) is provided with one or more variables and an objective function (evaluation function) defined by these variables. This is a problem of finding a set of variables (optimal solution) that maximizes or minimizes the value of the objective function. This mathematical programming problem is used in various fields such as jet engine design and network design. Therefore, various methods for searching for a solution to the mathematical programming problem have been conventionally considered.

【０００３】従来より広く用いられている数理計画問題
の解の探索手法として、オペレーションズ・リサーチ
（ＯＲ）に含まれる幾つかの解法がある。ＯＲ的手法に
含まれる解法として、例えば、目的関数が線形で表され
る線形計画の解法があり、この解法は古くから研究され
ている。これらの古典的な解法の一部は、山登り法と呼
ばれ、可能解（条件の全てを満たした変数の組）の変数
の値をすこしずつ変化させながら、目的関数の値を最適
解に近づけるものである（但し、可能解の集合内に閉じ
た変化は、山登り法の一部においては必須ではない）。As a method of searching for a solution of a mathematical programming problem that has been widely used in the past, there are several solutions included in Operations Research (OR). As a solution included in the OR method, for example, there is a solution to a linear program in which an objective function is expressed in a linear manner, and this solution has been studied for a long time. Some of these classical solutions are called hill-climbing methods, in which the value of the objective function approaches the optimal solution while gradually changing the values of the variables of the possible solutions (sets of variables that satisfy all of the conditions). (Although closed changes within the set of possible solutions are not essential in some hill-climbing methods).

【０００４】ところが、問題によっては、山登り法のよ
うな手法では最適解（厳密には、ある程度の許容範囲に
ある許容解）を得ることができない場合がある。即ち、
周辺（一部または全ての変数の値をすこしだけ変化させ
た場合）と比べれば一番良い値の可能解が得られても、
離れた位置（変数の値を大幅に変化させた場合）にはも
っと良い値の可能解が存在することがある。従って、一
般的な山登り法では、離れた位置に最適解が存在してい
ても、その解を導き出すことができない。However, depending on the problem, there is a case where an optimum solution (strictly, an allowable solution within a certain allowable range) cannot be obtained by a method such as a hill-climbing method. That is,
Even if the best possible solution is obtained compared with the surroundings (when some or all of the values of the variables are slightly changed),
There may be better value possible solutions at distant locations (if the value of the variable is significantly changed). Therefore, in a general hill-climbing method, even if an optimal solution exists at a distant position, the solution cannot be derived.

【０００５】そこで、上記の問題を取り除くため、遺伝
的アルゴリズム（ＧＡ）という解探索手法を用いるとが
考え出された。遺伝的アルゴリズムとは、生物の遺伝の
機構を模倣して、それを工学的に応用した技術である。Therefore, in order to eliminate the above problem, it has been devised to use a solution search technique called a genetic algorithm (GA). A genetic algorithm is a technology that imitates the genetic mechanism of an organism and applies it engineeringly.

【０００６】生物の進化の過程では、既存の個体（親）
から新たな個体（子）が生まれる際に、個体の持つ染色
体同士の交叉、染色体上の遺伝子の突然変異などが起こ
り、既存の個体とは異なる性質の個体が生まれる。そし
て、環境に適応しない個体は淘汰され、環境に適応した
個体のみが生き延びて新たな子孫を作ることができる。
これにより、環境により適応した個体の集団が生き延び
る。In the process of evolution of an organism, existing individuals (parents)
When a new individual (child) is born from, crossover between chromosomes of the individual and mutation of a gene on the chromosome occur, and an individual having characteristics different from those of the existing individual is generated. Then, individuals that do not adapt to the environment are eliminated, and only individuals that adapt to the environment can survive and create new offspring.
This allows the population of individuals more adapted to the environment to survive.

【０００７】このような生物の進化を数理計画問題に当
てはめたものが、遺伝的アルゴリズムによる解探索手法
である。遺伝的アルゴリズムでは、解候補を個体に見立
て、解候補に含まれる変数を、個体の持つ染色体上の遺
伝子として取り扱う。そして、数理計画問題の目的関数
が環境であり、目的関数の値が各個体の環境への適応性
を表す。なお、遺伝的アルゴリズムでは、目的関数を最
適にするものほど大きい値を取るような適応度関数を定
義し、適応度関数の値（適応度値）を用いて各個体の環
境への適応性を判断し、適応度関数の値が小さい解候補
ほど淘汰されるように制御する。即ち、後述する選択操
作において、適応度関数の値が小さい解候補ほど、より
選択されないように制御する。[0007] A solution search method using a genetic algorithm applies such an evolution of an organism to a mathematical programming problem. In the genetic algorithm, a solution candidate is regarded as an individual, and a variable included in the solution candidate is treated as a gene on a chromosome of the individual. The objective function of the mathematical programming problem is the environment, and the value of the objective function represents the adaptability of each individual to the environment. In the genetic algorithm, a fitness function that takes a larger value as the objective function is optimized is defined, and the fitness of each individual to the environment is determined using the value of the fitness function (fitness value). Judgment is performed, and control is performed so that solution candidates with smaller fitness function values are eliminated. That is, in a selection operation described later, control is performed so that a solution candidate with a smaller value of the fitness function is not more selected.

【０００８】以上のような定義に基づき、個体に見立て
た複数の解候補に対して、選択(selection) ／自己複製
(reproduction)、交叉(crossover) 、突然変異(mutatio
n)の操作を繰り返し行う。以下に、遺伝的アルゴリズム
の最適解探索の手順を、簡単に説明する。Based on the above definition, selection / self-replication is performed for a plurality of solution candidates considered as individuals.
(reproduction), crossover, mutation (mutatio)
Repeat step n). The procedure for searching for an optimal solution of a genetic algorithm will be briefly described below.

【０００９】先ず、複数の個体を生成する。これらの個
体の集団を第１世代と呼ぶ。そして、選択の操作を行
う。選択では、第１世代の各個体の染色体（遺伝子の一
次元ストリング）から適応度値を求め、その中から適応
度の高い個体をより高い確率で選択する。選択された個
体の中から、個体対を作る。この個体対が、次世代の親
になる。First, a plurality of individuals are generated. The population of these individuals is called the first generation. Then, a selection operation is performed. In the selection, a fitness value is obtained from a chromosome (one-dimensional string of a gene) of each individual of the first generation, and an individual having a higher fitness is selected from the fitness value with a higher probability. From the selected individuals, create an individual pair. This individual pair becomes the parent of the next generation.

【００１０】次に、交叉の操作を行う。交叉では、個体
対のそれぞれの個体の持つ染色体の一部を丁度互いに入
れ換えたような染色体を持つ、新たな個体を生成する。
このようにして生成された個体は、双方の親の性質をあ
る程度ずつ引き継いでいる。Next, a crossover operation is performed. In the crossover, a new individual having a chromosome in which a part of the chromosome of each individual of the individual pair is replaced with each other is generated.
The individuals generated in this way inherit the properties of both parents to some extent.

【００１１】さらに、突然変異の操作を行う。突然変異
では、交叉によって生成された個体の染色体の一部の遺
伝子を、ランダムに選ばれた別の値に置き換える。この
突然変異によって、親の持っていない遺伝子を有する個
体が生まれる。このようにして生成された複数の個体
（集団）が第２世代の集団となる。Further, a mutation operation is performed. Mutation replaces some genes on the chromosome of an individual created by crossover with another value that is randomly selected. This mutation results in individuals having genes that the parent does not have. The plurality of individuals (populations) generated in this manner become a second generation population.

【００１２】以後、選択、交叉、突然変異を繰り返し、
世代を重ねていく。その結果、適応度の低い個体は淘汰
され、適応度の高い個体の集団が形成される。しかも、
交叉や突然変異があることにより解空間の中を大域的
に、且つ確率的に探索でき、山登り法のように最適解に
対しかなり劣る解に収束する現象を防止することができ
る。Thereafter, selection, crossover and mutation are repeated,
Repeat generations. As a result, individuals with low fitness are eliminated, and a group of individuals with high fitness is formed. Moreover,
Due to the crossover and mutation, the solution space can be searched globally and stochastically, and a phenomenon such as the hill-climbing method that converges to a solution that is considerably inferior to the optimal solution can be prevented.

【００１３】[0013]

【発明が解決しようとする課題】しかし、遺伝的アルゴ
リズムは解空間の中を大局的に探索できる反面、その実
行には膨大な量の計算が必要であり、実際の問題を解く
には時間がかかりすぎるという問題点があった。However, while a genetic algorithm can search globally in a solution space, its execution requires an enormous amount of calculation, and it takes time to solve an actual problem. There was a problem that it took too much.

【００１４】例えば、荷物の配送問題において、配送コ
スト、制約条件満足度等の観点から遺伝的アルゴリズム
により最適解を探索する場合を考える。この場合、制約
条件には、配送センタの業務時間、配送先の受け付け時
間等、様々な制約条件がある。これらの全ての制約条件
を考慮した場合、解の探索空間が広大となる。このよう
に広大な探索空間を遺伝的アルゴリズムで探索した場
合、現在の計算機では、実用可能な時間内で許容解を得
ることはできない。For example, consider a case in which an optimal solution is searched by a genetic algorithm from the viewpoint of delivery cost, satisfaction of constraint conditions, and the like in a package delivery problem. In this case, the constraint conditions include various constraint conditions such as the business hours of the distribution center and the reception time of the delivery destination. When all these constraints are considered, the search space for the solution is vast. When such a vast search space is searched by a genetic algorithm, a current computer cannot obtain an allowable solution within a practical time.

【００１５】本発明はこのような点に鑑みてなされたも
のであり、良好な解を高速に探索することができる数理
計画計算装置を提供することを目的とする。また、本発
明の他の目的は、良好な結果の配送計画を高速に探索す
ることができる配送計画システムを提供することであ
る。SUMMARY OF THE INVENTION The present invention has been made in view of the above circumstances, and has as its object to provide a mathematical programming calculation apparatus capable of searching for a good solution at high speed. It is another object of the present invention to provide a delivery planning system capable of quickly searching for a delivery plan with good results.

【００１６】また、本発明の他の目的は、コンピュータ
に良好な解を高速に探索させることができる数理計画プ
ログラムを記録した媒体を提供することである。また、
本発明の別の目的は、コンピュータに良好な結果の配送
計画を高速に探索させることができる配送計画プログラ
ムを記録した媒体を提供することである。It is another object of the present invention to provide a medium on which a mathematical programming program which allows a computer to search for a good solution at a high speed is recorded. Also,
Another object of the present invention is to provide a medium recording a delivery plan program that allows a computer to quickly search for a delivery plan with good results.

【００１７】[0017]

【課題を解決するための手段】本発明では上記課題を解
決するために、数理計画問題の解を求める数理計画計算
装置において、遺伝的アルゴリズムを用いて解の探索方
針を指定する個体を生成し、解の探索方針を最適化する
解探索方針最適化手段と、前記個体の染色体で示された
解探索方針に従って、解候補を探索する解探索手段と、
を有することを特徴とする数理計画計算装置が提供され
る。According to the present invention, in order to solve the above-mentioned problems, in a mathematical programming calculation apparatus for finding a solution to a mathematical programming problem, an individual designating a solution search policy using a genetic algorithm is generated. A solution search policy optimizing means for optimizing a solution search policy, and a solution search means for searching for a solution candidate according to the solution search policy indicated by the chromosome of the individual;
And a mathematical programming calculation device characterized by having:

【００１８】この数理計画計算装置によれば、遺伝的ア
ルゴリズムによって解探索方針が示され、その探索方針
に従って解候補を探索するため、遺伝的アルゴリズムに
よる解空間の中の大局的（大域的）な探索と同時に、詳
細な解候補の探索は高速に行うことができる。According to this mathematical programming calculation device, a solution search policy is indicated by a genetic algorithm, and a solution candidate is searched according to the search policy. Therefore, a global (global) solution in a solution space by the genetic algorithm is obtained. At the same time as the search, the search for detailed solution candidates can be performed at high speed.

【００１９】また、配送計画問題の解を求める配送計画
システムにおいて、遺伝的アルゴリズムを用いて解探索
方針を指定する個体を生成し、解探索方針を最適化する
解探索方針最適化手段と、前記個体の染色体で示された
解探索方針に従って、配送計画案を探索する解探索手段
と、を有することを特徴とする配送計画システムが提供
される。Further, in a delivery planning system for finding a solution to a delivery planning problem, a solution search policy optimizing means for generating an individual designating a solution search policy using a genetic algorithm and optimizing the solution search policy, And a solution search means for searching for a delivery plan in accordance with a solution search policy indicated by the chromosome of the individual.

【００２０】この配送計画システムによれば、遺伝的ア
ルゴリズムによって解探索方針が示され、その探索方針
に従って配送計画案が作成されるため、遺伝的アルゴリ
ズムによる解空間の中の大局的な探索と同時に、詳細な
配送計画案の作成は高速に行うことができる。According to this delivery planning system, a solution search policy is indicated by a genetic algorithm, and a delivery plan is created in accordance with the search policy. The creation of a detailed delivery plan can be performed at high speed.

【００２１】また、コンピュータによって数理計画問題
の解を求めるための数理計画プログラムを記録した媒体
において、遺伝的アルゴリズムを用いて解の探索方針を
指定する個体を生成し、解の探索方針を最適化する解探
索方針最適化手段、前記個体の染色体で示された解探索
方針に従って、解候補を探索する解探索手段、としてコ
ンピュータを機能させるための数理計画プログラムを記
録した媒体が提供される。Further, on a medium recording a mathematical programming program for finding a solution to a mathematical programming problem by a computer, an individual specifying a solution search policy is generated using a genetic algorithm, and the solution search policy is optimized. A medium for recording a mathematical programming for causing a computer to function as a solution search policy optimizing means to perform, and a solution search means to search for a solution candidate according to the solution search policy indicated by the chromosome of the individual.

【００２２】この媒体に記録された数理計画プログラム
をコンピュータに実行させれば、遺伝的アルゴリズムを
用いて解の探索方針を指定する個体を生成し、解の探索
方針を最適化する解探索方針最適化手段と、個体の染色
体で示された解探索方針に従って、解候補を探索する解
探索手段とが、コンピュータによって実現される。When the computer executes the mathematical programming recorded on the medium, an individual designating a solution search policy is generated using a genetic algorithm, and a solution search policy optimization for optimizing the solution search policy is performed. The computerizing means realizes a solution search means for searching for a solution candidate according to a solution search policy indicated by a chromosome of an individual.

【００２３】また、コンピュータによって配送計画問題
の解を求めるための配送計画プログラムを記録した媒体
において、遺伝的アルゴリズムを用いて解探索方針を指
定する個体を生成し、解探索方針を最適化する解探索方
針最適化手段、前記個体の染色体で示された解探索方針
に従って、配送計画案を探索する解探索手段、としてコ
ンピュータを機能させるための配送計画プログラムを記
録した媒体が提供される。[0023] Also, in a medium recording a delivery plan program for finding a solution of a delivery plan problem by a computer, an individual designating a solution search policy is generated using a genetic algorithm, and a solution for optimizing the solution search policy is generated. A medium recording a distribution plan program for causing a computer to function as search policy optimizing means and solution search means for searching for a distribution plan in accordance with the solution search policy indicated by the chromosome of the individual is provided.

【００２４】この媒体に記録された配送計画プログラム
をコンピュータに実行させれば、遺伝的アルゴリズムを
用いて解探索方針を指定する個体を生成し、解探索方針
を最適化する解探索方針最適化手段と、個体の染色体で
示された解探索方針に従って、配送計画案を探索する解
探索手段とが、コンピュータによって実現される。When the computer executes the delivery plan program recorded on this medium, an individual designating a solution search policy is generated using a genetic algorithm, and a solution search policy optimizing means for optimizing the solution search policy. And a solution search means for searching for a delivery plan in accordance with a solution search policy indicated by the chromosome of the individual are realized by a computer.

【００２５】[0025]

【発明の実施の形態】以下、本発明の実施の形態を図面
に基づいて説明する。図１は本発明の数理計画計算装置
の原理構成図である。この数理計画計算装置に数理計画
問題が入力されると、解探索方針最適化手段１が遺伝的
アルゴリズムを用いて、解探索方針を示す染色体を有す
る個体３ａ〜３ｃを生成する。これらの個体で個体群３
が形成され、この個体群３は、解探索手段２に渡され
る。Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a diagram showing the principle configuration of a mathematical programming calculation apparatus according to the present invention. When a mathematical programming problem is input to the mathematical programming calculation device, the solution search policy optimizing means 1 uses a genetic algorithm to generate individuals 3a to 3c having chromosomes indicating the solution search policy. Population 3 in these individuals
Is formed, and this individual group 3 is passed to the solution search means 2.

【００２６】解探索手段２は、個体群３内の各個体３ａ
〜３ｃの染色体で示された解探索方針に従って数理計画
問題の解を探索し、解候補４ａ〜４ｃを作成する。この
とき、解候補４ａは個体３ａに基づき、解候補４ｂは個
体３ｂに基づき、解候補４ｃは個体３ｃに基づき、それ
ぞれ独立に作成される。そして、解候補４ａ〜４ｃを解
候補群４として、解探索方針最適化手段１に渡す。The solution search means 2 is provided for each individual 3a in the individual group 3.
The solution of the mathematical programming problem is searched according to the solution search policy indicated by the chromosomes No. to No. 3c, and solution candidates 4a to 4c are created. At this time, the solution candidate 4a is created independently based on the individual 3a, the solution candidate 4b is created based on the individual 3b, and the solution candidate 4c is created independently based on the individual 3c. Then, the solution candidates 4 a to 4 c are passed to the solution search policy optimizing means 1 as a solution candidate group 4.

【００２７】解探索方針最適化手段１は、解候補群４の
各解候補４ａ〜４ｃの適応度値を求める。そして、さら
に次の世代の解候補を探索する必要があれば、適応度値
を用いて個体３ａ〜３ｃの選択、交叉、及び突然変異の
処理を施し、次の世代の個体群を作成し、解探索手段２
に渡す。一方、次の世代の解候補を探索する必要がなけ
れば、適応度値の最も良い解候補を、この数理計画問題
の解とする。なお、殆どの場合、この解は厳密な意味の
最適解ではなく、予め定められた許容範囲内にある比較
的良好な許容解である。The solution search policy optimizing means 1 obtains fitness values of the solution candidates 4a to 4c of the solution candidate group 4. Then, if it is necessary to search for a solution candidate of the next generation, selection, crossover, and mutation of the individuals 3a to 3c are performed using the fitness values, and a population of the next generation is created. Solution search means 2
Pass to. On the other hand, if it is not necessary to search for a solution candidate of the next generation, a solution candidate having the best fitness value is set as a solution of the mathematical programming problem. In most cases, this solution is not an optimal solution in a strict sense, but a relatively good allowable solution within a predetermined allowable range.

【００２８】このように、解を探索するための探索方針
を遺伝的アルゴリズムで最適化し、その方針に従って別
の高速な手法で解を探索することにより、全ての解探索
を遺伝的アルゴリズムで行う場合よりも、高速に処理す
ることができる。しかも、解探索方針が遺伝的アルゴリ
ズムで指定されるため、広大な解空間の中を大局的に探
索できる。As described above, when a search policy for searching for a solution is optimized by a genetic algorithm and a solution is searched for by another high-speed technique according to the policy, all solution searches are performed by a genetic algorithm. Processing can be performed at a higher speed than in the case. Moreover, since the solution search policy is specified by the genetic algorithm, it is possible to search globally in the vast solution space.

【００２９】なお、上記の解探索方針最適化手段１と解
探索手段２とは、所定のプログラムをコンピュータに実
行させることにより、実現することができる。その場
合、これらの手段を実現するためのプログラムは、コン
ピュータで読み取り可能な記録媒体（半導体メモリや磁
気記録媒体等）に格納しておく。The solution search policy optimizing means 1 and the solution search means 2 can be realized by causing a computer to execute a predetermined program. In this case, a program for implementing these means is stored in a computer-readable recording medium (such as a semiconductor memory or a magnetic recording medium).

【００３０】以上のような数理計画計算装置は、様々な
数理計画問題の解探索に利用することができる。その一
つに、配送計画問題がある。以下に、上記の数理計画計
算装置を適用した配送計画システムについて説明する。The above-described mathematical programming calculation apparatus can be used for searching for solutions to various mathematical programming problems. One of them is a delivery planning problem. Hereinafter, a delivery planning system to which the above mathematical plan calculation device is applied will be described.

【００３１】図２は配送システム全体の概略構成を示す
ブロック図である。この配送システムは、配送計画シミ
ュレータ１０を中心に構成されている。この配送計画シ
ミュレータ１０は、遺伝的アルゴリズムとＯＲ的手法と
を用いて配送計画の計算を行う。FIG. 2 is a block diagram showing a schematic configuration of the entire delivery system. This delivery system mainly includes a delivery plan simulator 10. This delivery plan simulator 10 calculates a delivery plan using a genetic algorithm and an OR-like technique.

【００３２】配送計画の計算を行う際には、配送計画シ
ミュレータ１０に対して、シミュレーション条件２１、
地図情報２２、配送先／配送車情報２３、及び出荷デー
タ２４が入力される。シミュレーション条件２１は、制
約条件、適応度関数、及び遺伝的アルゴリズムを用いる
際に第何世代まで計算するか等の計算条件である。地図
情報２２には、配送先の位置情報、配送先内所要時間情
報、及び道路情報等が含まれる。配送先／配送車情報２
３には、配送先の店着指定時刻、納品時間、停車車種制
限等が含まれる。出荷データ２４は、配送すべき荷物の
出荷伝票のデータである。この出荷データ２４は、品物
の在庫や、注文の受け付け等を管理している基幹システ
ムから送られてくる。When calculating a delivery plan, a simulation condition 21,
Map information 22, delivery destination / delivery vehicle information 23, and shipping data 24 are input. The simulation condition 21 is a calculation condition such as a constraint condition, a fitness function, and the number of generations to be calculated when a genetic algorithm is used. The map information 22 includes location information of the delivery destination, required time information within the delivery destination, road information, and the like. Delivery destination / delivery car information 2
3 includes a store arrival designated time of a delivery destination, a delivery time, a stop type restriction, and the like. The shipping data 24 is data of a shipping slip of the package to be delivered. The shipment data 24 is sent from a backbone system that manages inventory of goods, acceptance of orders, and the like.

【００３３】必要な情報を受け取った配送計画シミュレ
ータ１０は、配送計画を計算する。算出された配送計画
は、ルート表示部２５とタイムチャート表示部２６に送
られる。ルート表示部２５は、表示装置上に地図ウィン
ドウを開き、そのウィンドウの中に周辺の地図を表示
し、更に、その地図上に各配送ルートを表示する。The delivery plan simulator 10 having received the necessary information calculates a delivery plan. The calculated delivery plan is sent to the route display unit 25 and the time chart display unit 26. The route display unit 25 opens a map window on the display device, displays a map of the surroundings in the window, and displays each delivery route on the map.

【００３４】タイムチャート表示部２６は、地図ウィン
ドウとは別のタイムチャートウィンドウを開く。そのタ
イムチャートウィンドウには、各配送ルートに於ける時
間経過に伴う配送車両の状態の変化がタイムチャートで
表示される。The time chart display section 26 opens a time chart window different from the map window. In the time chart window, a change in the state of the delivery vehicle over time in each delivery route is displayed in a time chart.

【００３５】図３は配送計画シミュレータの内部構成を
示すブロック図である。配送計画シミュレータ１０内に
は、遺伝的アルゴリズムにより、検討すべき配送車の配
送先への割当順序等の解探索方針を最適化する配送車割
当順序検討部１１と、指定された探索方針に従ってＯＲ
的手法により配送計画案を作成する配送計画作成部１２
とが設けられている。FIG. 3 is a block diagram showing the internal configuration of the delivery planning simulator. In the delivery planning simulator 10, a delivery vehicle assignment order examination unit 11 that optimizes a solution search policy such as an assignment order of delivery vehicles to be delivered to delivery destinations by a genetic algorithm and an OR in accordance with the designated search policy.
Delivery plan creation unit 12 that creates a delivery plan draft by a dynamic method
Are provided.

【００３６】配送車割当順序検討部１１は、遺伝的アル
ゴルズムによる処理機能を有しており、解探索方針を染
色体で示す個体に対して、選択、交叉、及び突然変異の
操作を繰り返し行う。これにより、個体群の子孫を順次
生成する。解探索方針としては、検討の対象とする配送
車の配送先への割当順序、最初の配送車の検討を行う際
に、初めに検討対象とすべき配送先の指定、及び配送先
の検討を順次行う際の配送先の選択方向指定である。The delivery vehicle allocation order examining unit 11 has a processing function based on a genetic algorithm, and repeatedly performs selection, crossover, and mutation operations on individuals whose solution search policy is indicated by chromosomes. Thereby, the descendants of the population are sequentially generated. As a solution search policy, the order of allocation of delivery vehicles to be examined to delivery destinations, when examining the first delivery vehicle, first specify the delivery destination to be considered, and consider the delivery destination This is the designation of the selection direction of the delivery destination when performing the order.

【００３７】配送車割当順序検討部１１が選択を行う際
には、その世代の個体群を配送計画作成部１２に渡し、
各個体に対応して作成された配送計画案を配送計画作成
部１２から受け取る。この配送計画案から適応度値を計
算し、適応度値に基づいて選択を行い、次世代を生成す
るための個体対を作る。また、処理の終了条件を満たし
た場合には、その世代の中で適応度値の値の大きい配送
計画案を解とする。When the delivery vehicle allocation order examination unit 11 makes a selection, the individuals of that generation are passed to the delivery plan creation unit 12,
A delivery plan created for each individual is received from the delivery plan creation unit 12. A fitness value is calculated from the delivery plan, and selection is made based on the fitness value, thereby forming an individual pair for generating the next generation. When the processing termination condition is satisfied, a delivery plan with a large fitness value in that generation is determined as a solution.

【００３８】配送計画作成部１２は、配送経路立案部１
２ａと配送経路修正部１２ｂとを有している。配送経路
立案部１２ａは、配送車割当順序検討部１１から送られ
たある世代の個体群を受け取ると、個体の染色体に示さ
れている順番で検討対象の配送車を選択する。そして、
検討対象の配送車について、配送先を割り当てる仮配送
経路を作成する。配送経路修正部１２ｂは、仮配送経路
を受け取り、各配送車が配送すべき配送先の配送順の入
替えを行い、時間が最短になるような配送順を見つけ
る。修正が加えられた配送経路が、新配送経路となる。
同様にして、全ての配送車に対する新配送経路を確定
し、配送計画案が作成される。そして、各個体に対応し
て作成した配送計画案を配送車割当順序検討部１１に送
る。The delivery plan creation unit 12 is provided with a delivery route planning unit 1
2a and a delivery route correction unit 12b. Upon receiving the population of a certain generation sent from the delivery vehicle allocation order examination unit 11, the delivery route planning unit 12a selects a delivery vehicle to be examined in the order indicated on the chromosome of the individual. And
A provisional delivery route to which a delivery destination is assigned is created for the delivery vehicle under consideration. The delivery route correction unit 12b receives the temporary delivery route, changes the delivery order of the delivery destination to which each delivery vehicle should deliver, and finds the delivery order that minimizes the time. The modified delivery route becomes the new delivery route.
Similarly, new delivery routes for all delivery vehicles are determined, and a delivery plan is created. Then, the delivery plan draft created for each individual is sent to the delivery vehicle allocation order reviewing unit 11.

【００３９】なお、上記の配送車割当順序検討部１１と
配送計画作成部１２とは、所定のプログラムをコンピュ
ータに実行させることにより、実現することができる。
その場合、これらの機能を実現するためのプログラム
は、コンピュータで読み取り可能な記録媒体（半導体メ
モリや磁気記録媒体等）に格納しておく。It should be noted that the above-described delivery vehicle allocation order study section 11 and delivery plan creation section 12 can be realized by causing a computer to execute a predetermined program.
In this case, programs for implementing these functions are stored in a computer-readable recording medium (such as a semiconductor memory or a magnetic recording medium).

【００４０】以上のような配送計画システムにより、遺
伝的アルゴルズムとＯＲ的手法とを組み合わせて、最適
解を探索する。以下に、配送問題の具体例を用いて、上
記の配送計画システムの処理手順を説明する。With the above-described delivery planning system, an optimal solution is searched for by combining the genetic algorithm and the OR method. Hereinafter, the processing procedure of the delivery planning system will be described using a specific example of the delivery problem.

【００４１】図４は配送問題の配送先と配送センタとを
示す図である。この例では、配送センタ３１から各配送
先３２へ荷物を配送する際に必要となる車両数を最小に
することを目的とする。この空間は、配送センタ３１を
原点とする極座標で認識される。そして、検討対象とす
る配送先を選択するための線３４を定義する。この線３
４と原線３３との角度θを増大させるか（反時計回
り）、減少させるか（時計回り）を指定することによ
り、配送先検討方向が指定される。FIG. 4 is a diagram showing a delivery destination and a delivery center in the delivery problem. The purpose of this example is to minimize the number of vehicles required when delivering packages from the delivery center 31 to each delivery destination 32. This space is recognized in polar coordinates with the delivery center 31 as the origin. Then, a line 34 for selecting a delivery destination to be considered is defined. This line 3
By specifying whether to increase (counterclockwise) or decrease (clockwise) the angle θ between 4 and the original line 33, the delivery destination study direction is specified.

【００４２】制約条件としては、「配送センタの業務時
間制約」、「配送先の受け付け時間制約」、「配送先へ
の侵入制約（道路事情による侵入可否）」、「配送先の
受け付け配送車種類制約（配送先Ａ社には、Ａ社の社名
入りの配送車しか使用することができない場合等）」、
「配送車の容量制約」、「配送車の積載温度制約」、
「配送車の稼働時間制約」、「配送車の走行距離制
約」、「配送車台数制約」がある。なお、「配送車の容
量制約」には、「配送車積載重量制約」、「配送車積載
体積制約」、「配送車積載寸法制約」が含まれる。As the constraint conditions, there are "delivery center operation time constraint", "delivery destination reception time restriction", "delivery destination intrusion restriction (possibility of intrusion due to road conditions)", "delivery destination reception vehicle type". Restrictions (for example, a delivery company A can use only a delivery vehicle with the company name of company A) "
"Delivery vehicle capacity constraints", "Delivery vehicle loading temperature constraints",
There are "operation time constraints of delivery vehicles", "restrictions of travel distance of delivery vehicles", and "restrictions of the number of delivery vehicles". Note that the "capacity of delivery vehicle capacity" includes "delivery vehicle loading weight constraint", "delivery vehicle loading volume restriction", and "delivery vehicle loading dimension restriction".

【００４３】この例では、配送コストの低減を目的とし
て最適化する。配送コストを左右する要素には、使用配
送車数、配送時間（人件費に影響する）、配送車走行距
離（燃料費に影響する）などがある。ここでは、特に使
用配送車数の削減を主たる目的とし、合わせて配送車積
載重量総和の削減も副次的目的として、最適化を行う。
１台の配送車両の１年間の維持費は高額であり、配送セ
ンタに必要な配送車両の数を減らせれば、コストの削減
の効果が非常に大きいためである。In this example, optimization is performed for the purpose of reducing the delivery cost. Factors that affect the delivery cost include the number of delivery vehicles used, delivery time (affects labor costs), and mileage of delivery vehicles (affects fuel costs). Here, optimization is performed with the main purpose of reducing the number of delivery vehicles in use, and also as a secondary purpose of reducing the total weight of the delivery vehicles.
This is because the maintenance cost of one delivery vehicle for one year is high, and if the number of delivery vehicles required for the delivery center can be reduced, the effect of cost reduction is very large.

【００４４】そこで、ｋ番目の個体の示す探索方針で作
成された配送計画案の適応度関数ｆ _kは、Thus, the search policy indicated by the k-th individual is
Fitness function f of the generated delivery plan _kIs

【００４５】[0045]

【数１】ｆ_k＝１／（ａ×配送車数＋ｂ×配送車積載重
量総和＋ｃ×配送車不足）とする。ここで、ａ，ｂ，ｃは、予め設定された定数で
ある。配送車不足は、配送車が不足する場合は「１」、
そうでない場合は「０」である。この適応度関数を最大
にする解を求めれば、必要な配送車数及び配送車積載重
量総和を最小にすることができる。なお、ｃの値は、ａ
やｂよりも十分大きな値とする。ｃの値を大きな値とす
ることにより、配送車が不足するような解しか生成され
ない個体は、淘汰される可能性が大きくなる。It is assumed that f _k = 1 / (a × the number of delivery vehicles + b × the total weight of the delivery vehicles loaded + c × the shortage of delivery vehicles). Here, a, b, and c are constants set in advance. Delivery car shortage is "1" when delivery car shortage,
Otherwise, it is "0". If a solution that maximizes the fitness function is obtained, the required number of delivery vehicles and the total weight of the delivery vehicles can be minimized. The value of c is a
And a value sufficiently larger than b. By setting the value of c to a large value, an individual who can generate only a solution that runs short of delivery vehicles has a high possibility of being eliminated.

【００４６】選択確率は、The selection probability is

【００４７】[0047]

【数２】選択確率＝ｆ_k ⁿ／Σ（ｆ_k ⁿ）とする。ここで、適応度関数ｆ_kをｎ乗したのは、この
ｎの値を変えることにより、個体の選択確率を容易に調
整することができるようにするためである。即ち、ｎの
値を大きくすれば、適応度値の大きな個体が選択される
可能性が大きくなり、ｎの値を小さくすれば、適応度値
の小さな個体であっても選択される可能性が大きくな
る。[Number 2] as the selection probability _{^{= f k n / Σ (f}} k n). Here, the fitness function f _k is raised to the n-th power so that the selection probability of the individual can be easily adjusted by changing the value of n. That is, when the value of n is increased, the possibility that an individual having a large fitness value is selected increases. When the value of n is decreased, the possibility that an individual having a small fitness value is selected is increased. growing.

【００４８】また、交叉には２点交叉を用い、突然変異
は２遺伝子の交換とする。そして、個体の有する染色体
は、「配送車割当順」、「割当開始位置」、「検討方
向」を指定する部分染色体で構成する。In addition, two-point crossover is used for crossover, and mutation is exchange of two genes. The chromosome possessed by the individual is composed of partial chromosomes that specify “order of delivery vehicle allocation”, “allocation start position”, and “review direction”.

【００４９】図５は染色体の構成を示す図である。この
染色体５０は、６個の遺伝子を有している。染色体５０
は３つの部分染色体から構成されており、遺伝子５１、
遺伝子５２、及び遺伝子５３〜５６がそれぞれ１つの部
分染色体を形成している。FIG. 5 is a diagram showing the structure of a chromosome. This chromosome 50 has six genes. Chromosome 50
Is composed of three partial chromosomes, gene 51,
The gene 52 and the genes 53 to 56 each form one partial chromosome.

【００５０】遺伝子５１は、「＋」あるいは「−」のい
ずれかの値が設定される。遺伝子５１が「＋」の時は、
配送センタを原点とした極座標の、角度θが増大する方
向に配送先の検討を行うことを示す。遺伝子５１が
「−」の時は、配送センタを原点とした極座標の角度θ
が減少する方向に配送先の検討を行うことを示す。For the gene 51, a value of either "+" or "-" is set. When gene 51 is "+",
This indicates that the delivery destination is examined in the direction in which the angle θ of the polar coordinates with the delivery center as the origin increases. When the gene 51 is “−”, the angle θ of the polar coordinates with the origin at the delivery center
Indicates that the delivery destination should be considered in the direction in which the number decreases.

【００５１】遺伝子５２は、配送先の番号が設定され
る。１番目に検討を行う配送車は、この遺伝子５２に設
定された番号の配送先から検討を開始する。遺伝子５３
〜５６は、配送先割当の検討を行う配送車の順番を指定
している。遺伝子５３→遺伝子５４→遺伝子５５→遺伝
子５６の順で、その遺伝子の示す配送車の配送先割当を
検討する。For the gene 52, a delivery destination number is set. The delivery vehicle to be examined first starts examination from the delivery destination of the number set in the gene 52. Gene 53
Nos. To 56 designate the order of delivery vehicles for which delivery destination allocation is to be considered. The delivery destination allocation of the delivery vehicle indicated by the gene is examined in the order of gene 53 → gene 54 → gene 55 → gene 56.

【００５２】このように、染色体５０は、空間内に固定
されていない要素種（遺伝子５３〜５６）と所定の空間
内に固定されて存在する要素種（遺伝子５１，５２）と
から成り立っている。As described above, the chromosome 50 is composed of element types (genes 53 to 56) not fixed in the space and element types (genes 51 and 52) fixed and existing in the predetermined space. .

【００５３】このような染色体に対して交叉と突然変異
とを行う際には、まず、染色体を３つの部分染色体に分
割する。そして、親となる２つの染色体の部分染色体ど
うしを互いに入れ換えることにより、２点交叉を行う。
交叉を行った後に、突然変異を行う。遺伝子５１と遺伝
子５２と（それぞれの遺伝子１つが、１つの部分染色体
である）に対する突然変異は、一定の確率で遺伝子の値
を別の値に変更することである。遺伝子５３〜５６（４
つの遺伝子で１つの部分染色体を構成している）に対す
る突然変異は、一定の確率で２つの遺伝子の値を互いに
他方の値に置き換えることである。In performing such crossover and mutation on such a chromosome, first, the chromosome is divided into three partial chromosomes. Then, two-point crossover is performed by exchanging the partial chromosomes of the two parent chromosomes.
After crossover, mutation is performed. Mutation to the gene 51 and the gene 52 (one of each gene is one partial chromosome) is to change the value of the gene to another value with a certain probability. Genes 53 to 56 (4
Mutation to one gene constitutes one partial chromosome) is to replace the values of two genes with each other with a certain probability.

【００５４】以上のような情報が配送計画シミュレータ
１０（図２に示す）に入力された後、配送計画の最適解
の探索が開始される。最適解の探索は、配送車割当順序
検討部１１が中心になって処理する。After the above information is input to the delivery plan simulator 10 (shown in FIG. 2), the search for the optimal solution of the delivery plan is started. The search for the optimum solution is performed mainly by the delivery vehicle allocation order examination unit 11.

【００５５】図６は配送車割当順序検討部の処置手順を
示すフローチャートである。〔Ｓ１〕集団の初期化として、第１世代を構成する個体
の集団を生成する。この第１世代の各個体は、例えばラ
ンダムに遺伝子を組み合わせることによって作成する。〔Ｓ２〕生成された集団の各個体から、所定の判断基準
に基づき個体対を選択する。この処理の詳細は、図７に
おいて説明する。〔Ｓ３〕ステップＳ２によって選択された個体対の各個
体の染色体を２点交叉によって交叉させ、新たな染色体
を生成する。〔Ｓ４〕ステップＳ３で生成された各染色体の中の２つ
の遺伝子の値を互いに他方の値に換えることにより、突
然変異を行う。このステップで生成された染色体を有す
る個体が、次の世代の個体群となる。〔Ｓ５〕処理が終了か否かを判断する。判断基準として
は、例えば、ある一定の世代に達していれば処理を終了
する。処理を終了するための基準を満たしていなけれ
ば、ステップＳ２に進み、次の世代による解の探索を行
う。処理を終了すると判断した場合には、現在の世代で
得られた配送計画案の中で、適応度値が最も良いものを
許容解とする。FIG. 6 is a flow chart showing the procedure of the treatment performed by the delivery vehicle allocation order examination section. [S1] As a group initialization, a group of individuals constituting the first generation is generated. Each individual of the first generation is created by, for example, randomly combining genes. [S2] An individual pair is selected from each individual in the generated population based on a predetermined criterion. Details of this processing will be described with reference to FIG. [S3] The chromosomes of each individual of the individual pair selected in step S2 are crossed by two-point crossover to generate a new chromosome. [S4] Mutation is performed by replacing the values of the two genes in each chromosome generated in step S3 with each other. The individual having the chromosome generated in this step is the next generation of individuals. [S5] It is determined whether the process is completed. As a criterion, for example, the process is terminated if a certain generation has been reached. If the criterion for terminating the process is not satisfied, the process proceeds to step S2, and a search for a solution by the next generation is performed. If it is determined that the processing is to be ended, the one with the best fitness value among the delivery plans obtained in the current generation is determined as an allowable solution.

【００５６】図７は選択処理の手順を示すフローチャー
トである。〔Ｓ１１〕集団を配送計画作成部１２に渡し、配送計画
作成部１２から、ＯＲ的手法により作成された配送計画
案を受け取る。〔Ｓ１２〕受け取った配送計画案の適応度値を計算す
る。〔Ｓ１３〕適応度値を判断基準として、個体対を選択す
る。FIG. 7 is a flowchart showing the procedure of the selection process. [S11] The group is passed to the delivery plan creation unit 12, and the delivery plan draft created by the OR method is received from the delivery plan creation unit 12. [S12] The fitness value of the received delivery plan is calculated. [S13] An individual pair is selected using the fitness value as a criterion.

【００５７】図８は、図７のステップＳ１１において配
送車割当順序検討部が配送計画作成部１２に与える個体
及びその染色体と、配送計画作成部１２から受け取る配
送計画案の組の例を示す図である。配送計画案４１〜４
３は、配送経路作成部１２から送られてくる。配送計画
案４１〜４３から適応度値を求めることにより、染色体
５０，５０ａ，５０ｂを評価することができる。FIG. 8 is a diagram showing an example of a set of individuals and their chromosomes provided by the delivery vehicle assignment order examination unit to the delivery plan creation unit 12 in step S11 of FIG. 7 and a delivery plan draft received from the delivery plan creation unit 12. It is. Delivery plan 41-4
3 is sent from the delivery route creation unit 12. The chromosomes 50, 50a, and 50b can be evaluated by calculating the fitness values from the delivery plans 41 to 43.

【００５８】図９は配送計画案の内容を示す図である。
これは染色体５０の示す探索条件に従って作成された配
送計画案である。このように、各配送車６１〜６４がど
の配送先をどの順番で巡回するのかを示す情報が含まれ
ている。FIG. 9 is a diagram showing the contents of the delivery plan.
This is a delivery plan draft created according to the search condition indicated by the chromosome 50. As described above, the information indicating which delivery destination the delivery vehicles 61 to 64 visit in which order is included.

【００５９】以上が、配送車割当順序検討部１１の処置
手順である。次に、配送計画作成部１２の処理手順を説
明する。図１０は配送計画作成部の処置手順を示すフロ
ーチャートである。なお、以下のフローチャートの説明
において特に示さない限り、配送経路立案部１２ａが処
理を行う。〔Ｓ２１〕ｉの初期値として「１」を設定する。〔Ｓ２２〕検討対象配送車として、ｉ番目の遺伝子を選
択する。この場合のｉ番目とは、染色体の配送車割当順
序を示す遺伝子を左側から数えた場合の順番である。図
５に示した染色体５０では、遺伝子５３が１番目であ
り、以降、遺伝子５４、遺伝子５５、遺伝子５６の順で
ある。〔Ｓ２３〕検討対象配送車の積荷の検討を行う。この処
理の詳細は、図１１において説明する。〔Ｓ２４〕予め設定されている「ｉｍａｘ」（運行可能
な配送車の数）とｉを比較し、等しければ処理を終了す
る。ｉｍａｘに達していなければ、次のステップＳ２５
に進む。即ち、ｉｍａｘに達した時点で、全ての車両に
ついて検討されたことになる。〔Ｓ２５〕ｉの値を１だけカウントアップし、ステップ
Ｓ２２に進む。これにより、ｉの値がｉｍａｘに達する
まで処理が繰り返される。The above is the procedure of the delivery vehicle allocation order examination unit 11. Next, a processing procedure of the delivery plan creation unit 12 will be described. FIG. 10 is a flowchart showing the procedure of the process performed by the delivery plan creation unit. Unless otherwise indicated in the following description of the flowchart, the delivery route planning unit 12a performs the processing. [S21] "1" is set as the initial value of i. [S22] The ith gene is selected as the delivery vehicle to be examined. In this case, the i-th order is the order in which genes indicating the order of chromosome delivery vehicle allocation are counted from the left side. In the chromosome 50 shown in FIG. 5, the gene 53 is the first, and thereafter, the gene 54, the gene 55, and the gene 56 are in the order. [S23] The cargo of the delivery vehicle to be examined is examined. Details of this processing will be described with reference to FIG. [S24] The preset imax (the number of operable delivery vehicles) is compared with i, and if they are equal, the process ends. If imax has not been reached, the next step S25
Proceed to. That is, when imax is reached, all vehicles have been examined. [S25] The value of i is incremented by one, and the process proceeds to step S22. Thus, the process is repeated until the value of i reaches imax.

【００６０】図１１は検討対象の配送車の積荷の検討処
理（図１０のステップＳ２３）の詳細を示すフローチャ
ートである。〔Ｓ３１〕ｊの初期値として「１」を設定する。〔Ｓ３２〕検討対象配送先として、ｊ番目の配送先を選
択する。ここで、ｊ番目の配送先とは、このフローチャ
ートの処理が開始された時点で、いずれの配送車にも振
り分けられていない配送先に付けた番号である。FIG. 11 is a flowchart showing the details of the process of examining the load of the delivery vehicle to be examined (step S23 in FIG. 10). [S31] "1" is set as the initial value of j. [S32] The j-th delivery destination is selected as the study destination delivery destination. Here, the j-th delivery destination is a number assigned to a delivery destination that has not been allocated to any delivery vehicle when the processing of this flowchart is started.

【００６１】配送先への番号付けは、例えば次のように
行う。最初の配送車の積荷の検討を行う場合には、検討
開始配送先（図５の遺伝子５２で指定された配送先）を
基準として指定された検討方向（図５の遺伝子５１で指
定された検討方向）に検索し、検出された順に番号を付
ける。２台目以降の配送車の積荷の検討を行う場合に
は、極座標における原線３３から検討開始配送先への角
度θ（図４を参照）を若干増加させた位置を基準として
指定された検討方向に検索し、検出された順に番号を付
ける。The delivery destination is numbered, for example, as follows. In the case of examining the load of the first delivery vehicle, the examination direction (the examination designated by the gene 51 in FIG. 5) designated based on the examination start delivery destination (the delivery destination designated by the gene 52 in FIG. 5). Direction), and number them in the order of detection. When examining the load of the second and subsequent delivery vehicles, the examination specified with reference to a position where the angle θ (see FIG. 4) from the original line 33 in polar coordinates to the examination start delivery destination is slightly increased is used as a reference. Search in the direction and number them in the order they are found.

【００６２】これにより、以前に検討した配送車に割り
当てることができなかった配送先は、次の配送車に対し
て、優先的に割当の検討が行われる。〔Ｓ３３〕検討対象配送先の荷物を、検討対象配送車に
配送させることができるか否かを検討する。この処理の
詳細は、図１３において説明する。〔Ｓ３４〕検討対象配送車にまだ荷物を積む余地がある
か否かを判断する。更に積載可能であれば次のステップ
Ｓ３５に進み、限界であればステップＳ３７に進む。〔Ｓ３５〕予め設定されている「ｊｍａｘ」（このフロ
ーチャートの処理が開始された時点で、いずれの配送車
にも振り分けられていない配送先の総数）とｊを比較
し、等しければステップＳ３７に進む。ｊｍａｘに達し
ていなければ、次のステップＳ３６に進む。即ち、ｊｍ
ａｘに達した時点で、全ての配送先について検討された
ことになる。〔Ｓ３６〕ｊの値を１だけインクリメントし、ステップ
Ｓ３２に進む。これにより、ｊの値がｊｍａｘに達する
か、あるいは積載量が限界に達するまで処理が繰り返さ
れる。〔Ｓ３７〕正式な配送経路の改善を行い、処理を終了す
る。この処理の詳細は、図１６において説明する。As a result, a delivery destination that could not be assigned to a delivery vehicle previously examined is given priority to the next delivery vehicle. [S33] It is examined whether the package at the delivery destination to be examined can be delivered to the delivery vehicle to be examined. Details of this processing will be described with reference to FIG. [S34] It is determined whether or not there is still room for luggage in the delivery vehicle under consideration. If loading is possible, the process proceeds to the next step S35, and if the limit is reached, the process proceeds to step S37. [S35] j is compared with a preset “jmax” (total number of delivery destinations not allocated to any delivery vehicle at the start of the process of this flowchart), and if they are equal, the process proceeds to step S37. . If jmax has not been reached, the process proceeds to the next step S36. That is, jm
When the value of ax is reached, all delivery destinations have been examined. [S36] The value of j is incremented by 1, and the process proceeds to step S32. Thereby, the processing is repeated until the value of j reaches jmax or the load capacity reaches the limit. [S37] The formal delivery route is improved, and the process ends. Details of this processing will be described with reference to FIG.

【００６３】図１２は検討対象配送車の積荷の検討処理
の進行状況を示す図である。（Ａ）は最初の配送先３２
ａの検討状況を示す図である。この例では、配送先３２
ａの荷物を積むことができると判断し、配送センタ３１
と配送先３２ａとの間を往復する順路を決定する。FIG. 12 is a diagram showing the progress of the examination process of the load of the delivery vehicle to be examined. (A) is the first delivery destination 32
It is a figure showing the examination situation of a. In this example, the delivery destination 32
It is determined that the package a can be loaded, and the delivery center 31
A route to and fro between the delivery destination 32a is determined.

【００６４】（Ｂ）は２つめの配送先の検討状況を示す
図である。この例では、配送先検討方向は「＋」の方向
であり、配送先３２ｂが検討対象配送先となる。この配
送先３２ｂにも配送できると判断し、その経路を確定す
る。この際、配送先３２ａに向かう途中で配送先３２ｂ
に寄るべきか、配送先３２ａからの帰り路に寄るべきか
を判断し、最適な方を選ぶ。この例では、配送先３２ａ
に向かう途中で配送先３２ｂに寄る方を選ぶ場合を示し
ている。FIG. 11B is a diagram showing the situation of study of the second delivery destination. In this example, the delivery destination examination direction is the direction of “+”, and the delivery destination 32b is the study target delivery destination. It is determined that delivery can be made to this delivery destination 32b, and the route is determined. At this time, on the way to the delivery destination 32a, the delivery destination 32b
Or the return route from the delivery destination 32a, and the most appropriate one is selected. In this example, the delivery destination 32a
The case where the person who approaches the delivery destination 32b on the way to is selected.

【００６５】（Ｃ）は３つめの配送先の検討状況を示す
図である。この例では、配送先３２ｃが検討対象配送先
となる。この配送先３２ｃにも配送できると判断し、そ
の経路を確定する。この際、配送センタ３１と配送先３
２ｂとの間の区間、配送先３２ｂと配送先３２ａとの間
の区間、及び配送先３２ａと配送センタ３１との間のの
区間のどこで新たに加える配送先３２ｃに寄るべきかを
比較し、最良の経路に決定する。FIG. 11C is a diagram showing a state of study of a third delivery destination. In this example, the delivery destination 32c is the delivery destination to be considered. It is determined that delivery is possible to this delivery destination 32c, and the route is determined. At this time, the delivery center 31 and the delivery destination 3
2b, a section between the delivery destination 32b and the delivery destination 32a, and a section between the delivery destination 32a and the delivery center 31, where the new delivery destination 32c should be compared. Determine the best route.

【００６６】（Ｄ）は３つの配送先の検討結果を示す図
である。この例では、配送先３２ｂ、配送先３２ａ、配
送先３２ｃの順番が最良であると判断されている。図１
３は検討対象配送先への配送に関する検討の処理の詳細
を示すフローチャートである。〔Ｓ４１〕重量制約を満足しているか否かを判断する。
重量制約を満足していればステップＳ４２に進み、満足
していなければ処理を終了する。〔Ｓ４２〕体積制約を満足しているか否かを判断する。
体積制約を満足していればステップＳ４３に進み、満足
していなければ処理を終了する。〔Ｓ４３〕寸法制約を満足しているか否かを判断する。
寸法制約を満足していればステップＳ４４に進み、満足
していなければ処理を終了する。〔Ｓ４４〕侵入制約を満足しているか否かを判断する。
侵入制約を満足していればステップＳ４５に進み、満足
していなければ処理を終了する。〔Ｓ４５〕車種制約を満足しているか否かを判断する。
車種制約を満足していればステップＳ４６に進み、満足
していなければ処理を終了する。〔Ｓ４６〕最短時間の経路を探索する。結果として、仮
配送経路が作成される。この処理の詳細は、図１４にお
いて説明する。〔Ｓ４７〕時間制約を満足しているか否かを判断する。
時間制約を満足していればステップＳ４８に進み、満足
していなければ処理を終了する。〔Ｓ４８〕走行距離制約を満足しているか否かを判断す
る。走行距離制約を満足していればステップＳ４９に進
み、満足していなければ処理を終了する。〔Ｓ４９〕ステップＳ４６で作成された仮配送経路を、
正式な配送経路として、処理を終了する。FIG. 9D is a diagram showing the result of study of three delivery destinations. In this example, it is determined that the order of the delivery destination 32b, the delivery destination 32a, and the delivery destination 32c is the best. FIG.
3 is a flowchart showing details of a process of studying delivery to the study destination. [S41] It is determined whether the weight constraint is satisfied.
If the weight constraint is satisfied, the process proceeds to step S42, and if not, the process ends. [S42] It is determined whether the volume constraint is satisfied.
If the volume constraint is satisfied, the process proceeds to step S43, and if not, the process ends. [S43] It is determined whether the dimensional constraint is satisfied.
If the dimensional constraint is satisfied, the process proceeds to step S44, and if not, the process ends. [S44] It is determined whether the intrusion constraint is satisfied.
If the intrusion constraint is satisfied, the process proceeds to step S45, and if not, the process ends. [S45] It is determined whether or not the vehicle type restriction is satisfied.
If the vehicle type restriction is satisfied, the process proceeds to step S46, and if not, the process ends. [S46] The shortest route is searched. As a result, a temporary delivery route is created. Details of this processing will be described with reference to FIG. [S47] It is determined whether the time constraint is satisfied.
If the time constraint is satisfied, the process proceeds to step S48, and if not, the process ends. [S48] It is determined whether the travel distance constraint is satisfied. If the travel distance constraint is satisfied, the process proceeds to step S49, and if not, the process ends. [S49] The temporary delivery route created in step S46 is
The process ends as a formal delivery route.

【００６７】図１４は最短経路探索の処理の詳細を示す
フローチャートである。〔Ｓ５１〕経路上の検討配送先の挿入箇所の異なる配送
経路候補毎の配送コストを計算する。ここで配送コスト
とは、配送時間、走行時間、走行距離、及び燃料費の少
なくとも１つを考慮にいれた関数値である。この配送コ
ストが最小になる位置に、新たに割り当てる配送先を挿
入し、仮配送経路を生成する。〔Ｓ５２〕最善の仮配送経路を選択する。FIG. 14 is a flowchart showing details of the shortest route search process. [S51] A delivery cost is calculated for each delivery route candidate having a different insertion location of the study delivery destination on the route. Here, the delivery cost is a function value that takes into account at least one of delivery time, travel time, travel distance, and fuel cost. A delivery destination to be newly assigned is inserted at a position where the delivery cost is minimized, and a temporary delivery route is generated. [S52] The best temporary delivery route is selected.

【００６８】図１５は、図１４のステップＳ５１におけ
る処理内容を説明する図である。この例では、配送セン
タ３１→配送先３２ｄ→配送先３２ｅ→配送先３２ｆ→
配送センタ３１の間の配送順序が確定している状態で、
さらに配送先３２ｇを追加する場合である。この場合、
配送先３２ｇを、どの間に挿入すれば配送コストが安く
なるかを計算する。この例では、４通りの計算が必要で
ある。そして、配送コストが最も安い位置に配送先３２
ｇを挿入し、配送先３２ｇを加えた仮配送経路を生成す
る。FIG. 15 is a view for explaining the processing content in step S51 of FIG. In this example, the delivery center 31 → the delivery destination 32d → the delivery destination 32e → the delivery destination 32f →
With the delivery order between the delivery centers 31 determined,
This is a case where a delivery destination 32g is further added. in this case,
A calculation is performed to determine in which interval the delivery destination 32g is inserted to reduce the delivery cost. In this example, four calculations are required. The delivery destination 32 is located at the position where the delivery cost is the lowest.
g, and a provisional delivery route including the delivery destination 32g is generated.

【００６９】図１６は、図１１のステップＳ３７におけ
る処理内容を説明する図である。この例では、配送セン
タ３１→配送先３２ｊ→配送先３２ｋ→配送先３２ｍ→
配送先３２ｎ→配送センタ３１の仮配送経路が作られて
いる。図では、配送先の上の数字は、配送順を示してい
る。この状態から、先ず、配送先３２ｊを他の位置に移
動した場合に、制約条件を守る範囲で、配送コストが減
少するか否かを判断する。そして、配送コストが最も向
上する位置に、配送先３２ｊを移動する。FIG. 16 is a diagram for explaining the processing contents in step S37 of FIG. In this example, the delivery center 31 → the delivery destination 32j → the delivery destination 32k → the delivery destination 32m →
A temporary delivery route from the delivery destination 32n to the delivery center 31 is created. In the figure, the numbers above the delivery destinations indicate the delivery order. From this state, first, when the delivery destination 32j is moved to another position, it is determined whether or not the delivery cost is reduced within a range in which the constraint condition is maintained. Then, the delivery destination 32j is moved to a position where the delivery cost is most improved.

【００７０】もし、配送先３２ｊが他の場所、例えば、
配送先３２ｍと配送先３２ｎとの間に移動すると、配送
先３２ｋと配送先３２ｍが前（図中、左側）にずれる。
このように、検討した配送先３２ｊが移動した場合に
は、もう一度、配送順が「１」である配送先（配送先３
２ｋが該当する）を他の場所に移動して、配送コストの
向上が図れるか否かを判断する。If the delivery destination 32j is in another location, for example,
When moving between the delivery destination 32m and the delivery destination 32n, the delivery destination 32k and the delivery destination 32m are shifted forward (to the left in the figure).
As described above, when the examined delivery destination 32j moves, the delivery destination whose delivery order is “1” (the delivery destination 3
2k) to another location to determine whether the delivery cost can be improved.

【００７１】検討した配送先が移動しなかった場合に
は、次の配送順の配送先について検討する。このように
して、４番目の配送先まで検討する。これにより、最善
の仮配送経路を選択することができる。以上のような移
動による改善を更に何回か行う（予め与えられた回数に
従う）。If the examined delivery destination has not moved, the delivery destination in the next delivery order is examined. In this way, the fourth delivery destination is examined. Thereby, the best temporary delivery route can be selected. The above-described improvement by the movement is further performed several times (according to the number given in advance).

【００７２】この段階で、上記の移動によって配送時間
にゆとりが生じ、しかも元々積載容量にゆとりがある場
合は、さらに配送先を追加するという考え方を導入する
ことも可能である。At this stage, if the above-mentioned movement causes a margin in the delivery time, and if the load capacity originally has a margin, it is possible to introduce a concept of further adding a delivery destination.

【００７３】以上のように、遺伝的アルゴリズムにより
解の探索方針を定め、ＯＲ的手法によって具体的な配送
計画案を作成するようにしたため、高速に、且つ良好な
許容解を得ることができる。このようにして得られた配
送計画は、人間が同程度の時間で考えて作成したものよ
りも、格段に良い結果となる場合が多い。場合によって
は、例えば配送車数を３割以上減らすことができる。ま
た、上記に示したような配送計画であれば、通常のワー
クステーションを用いても極めて速く、例えば数秒で解
くことができる場合が少なくない。As described above, since the solution search policy is determined by the genetic algorithm and a specific delivery plan is created by the OR method, a high-speed and good allowable solution can be obtained. In many cases, the delivery plan obtained in this way is much better than a plan created by a person in the same amount of time. In some cases, for example, the number of delivery vehicles can be reduced by 30% or more. In addition, with the delivery plan as described above, it is often quite possible to solve the problem in a few seconds, for example, using a normal workstation.

【００７４】また、従来の配送計画システムでは、複数
の制約条件があるような問題を解くことが非常に難しか
った。ところが、本発明の配送計画システムによれば、
様々な制約条件を設定することが可能である。しかも、
従来は制約条件として時間的制約を加えるとアルゴリズ
ムが非常に複雑になり、解くことが難しくなることが多
かったが、本発明に係る配送計画システムでは、時間的
制約が付加されても、十分高速に処理できる。時間的制
約と配送車の積載制約との双方を指定することも可能で
ある。In the conventional delivery planning system, it is very difficult to solve a problem having a plurality of constraints. However, according to the delivery planning system of the present invention,
Various constraints can be set. Moreover,
Conventionally, if a time constraint is added as a constraint, the algorithm becomes very complicated and often difficult to solve.However, in the delivery planning system according to the present invention, even if a time constraint is added, a sufficiently high speed is required. Can be processed. It is also possible to specify both the time constraint and the loading constraint of the delivery vehicle.

【００７５】このように、複数の制約条件があっても高
速に解くことができるのは、大局的な探索を遺伝的アル
ゴリズムで行い、詳細な計算をＯＲ的手法に委ねている
ためである。即ち、本発明のＯＲ的手法では、検討対象
の配送車を１台ずつ選択するとともに、１台の配送車へ
の配送先割当において検討対照の配送先も１箇所づつ選
択し、その都度、できるだけ最適な配送経路を求めてい
る。このように、ＯＲ的手法による個々の配送車におけ
る制約条件の適否の判断や配送順の決定は、解空間全体
を対象として遺伝的アルゴリズムの操作を行う場合と比
較して、少ない計算ですむ。そのため制約条件が多くて
も、非常に高速に計算することができる。なお、探索方
針を遺伝的アルゴリズムで最適化するため、解全体の中
の大局的な最適値または準最適値を求めることができ
る。As described above, high-speed solving can be performed even when there are a plurality of constraint conditions because a global search is performed by a genetic algorithm, and detailed calculations are left to an OR method. That is, in the OR method of the present invention, the delivery vehicles to be examined are selected one by one, and the delivery destinations to be examined are also selected one by one in the allocation of the delivery destination to one delivery vehicle. Seeking the best delivery route. As described above, the determination of the suitability of the constraint condition in each delivery vehicle and the determination of the delivery order by the OR method require less calculation than the case where the genetic algorithm is operated for the entire solution space. Therefore, even if there are many constraint conditions, calculation can be performed at a very high speed. In addition, since the search policy is optimized by the genetic algorithm, a global optimum value or a sub-optimal value in the entire solution can be obtained.

【００７６】さらに、本発明では、新たな配送先を配送
経路に順次追加する方法で正式配送経路を生成した後、
更に各配送先の配送順の入替えを行っている。そのた
め、検討対象の配送先として選択された順番に影響され
ずに、最良の配送経路を求めることができる。Further, according to the present invention, after a formal delivery route is generated by a method of sequentially adding new delivery destinations to the delivery route,
Further, the delivery order of each delivery destination is changed. Therefore, the best delivery route can be obtained without being affected by the order selected as the delivery destination to be considered.

【００７７】なお、上記の説明では、配送センタと配送
先の位置を極座標で認識してる場合を示したが、直交座
標で認識することもできる。この場合、配送先検討方向
の指定は、例えば、Ｘ座標の「−∞」から「＋∞」ま
で、というように指定する。In the above description, the case where the positions of the delivery center and the delivery destination are recognized in polar coordinates has been described, but they may be recognized in rectangular coordinates. In this case, the delivery destination study direction is designated, for example, from “−∞” to “+ ∞” of the X coordinate.

【００７８】さらに、極座標の原点は配送センタに限る
必要はない。例えば、全配送先または全配送先に配送セ
ンタを含む集合の重心、直行座標を重ね合わせて考えた
場合の集合の横方向の中央且つ縦方向の中央点のいずれ
か、あるいはその他の点を極座標空間の原点とすること
もできる。これは、直交座標においても同じであり、直
交座標においても、配送センタ、全配送先または全配送
先に配送センタを含む集合の重心、集合の横方向の中央
且つ縦方向の中央点のいずれか、あるいはその他の点を
直交座標空間の原点とすることができる。Further, the origin of the polar coordinates need not be limited to the delivery center. For example, the center of gravity of the set including the delivery center at all the delivery destinations or all the delivery destinations, one of the horizontal center and the vertical center of the set when superimposing the orthogonal coordinates, or the other points are polar coordinates. It can also be the origin of space. This is the same in the rectangular coordinates, and in the rectangular coordinates, any one of the distribution center, the center of gravity of the set including the distribution center at all the destinations, or the center of the set in the horizontal direction and the vertical direction in the horizontal direction is set. , Or another point may be the origin of the rectangular coordinate space.

【００７９】また、上記の例では、配送コストの低減を
目的として適応度関数を定義したが、例えば、配送の負
荷バランスの観点から適応度関数を定義することもでき
る。また、各々の場合に、配送車台数制約以外の制約条
件も合わせて考えた制約条件満足度の観点から、適応度
関数を定義するともできる。制約条件満足度には、例え
ば、配送指定時間の遵守がある。なお、配送コストの低
減と制約条件満足度とを組み合わせて、双方を適度に満
足するような適応度関数を定義してもよい。In the above example, the fitness function is defined for the purpose of reducing the delivery cost. However, for example, the fitness function may be defined from the viewpoint of the load balance of the delivery. Further, in each case, a fitness function may be defined from the viewpoint of the constraint condition satisfaction considering the constraint condition other than the delivery vehicle number constraint. The constraint satisfaction degree includes, for example, compliance with a designated delivery time. It is also possible to define a fitness function that appropriately satisfies both by reducing the delivery cost and satisfying the constraint condition.

【００８０】また、配送計画作成部で、ＯＲ的手法によ
り各配送車への配送先の割当を行う際には、配送車の配
送先での滞在時間を考慮することができる。滞在時間を
考慮することにより、現実に配送を行った場合との誤差
を減らすことができる。Further, when the delivery plan creator assigns delivery destinations to each delivery vehicle by the OR method, the staying time of the delivery vehicles at the delivery destination can be considered. By considering the stay time, it is possible to reduce an error from the case where delivery is actually performed.

【００８１】また、配送計画作成部で、ＯＲ的手法によ
り配送経路を求める際に、巡回時間を最短にする経路を
求めているが、配送センタ帰着時刻、走行時間、燃料費
等を考慮の対象とすることもできる。また、それらの要
件を組み合わせた関数を用いても良い。In the delivery plan creation unit, when the delivery route is obtained by the OR method, the route that minimizes the traveling time is obtained. However, the delivery center return time, travel time, fuel cost, etc. are taken into consideration. It can also be. Also, a function combining those requirements may be used.

【００８２】[0082]

【発明の効果】以上説明したように本発明に係る数理計
画計算装置は、遺伝的アルゴリズムを用いて解の探索方
針を指定する個体を生成し、解の探索方針を最適化する
ようにしたため、遺伝的アルゴリズムによる解空間の中
の大局的な探索と同時に、詳細な解候補の探索を高速に
行うことができる。As described above, the mathematical programming calculation device according to the present invention generates individuals specifying a solution search policy using a genetic algorithm and optimizes the solution search policy. At the same time as a global search in a solution space by a genetic algorithm, a detailed solution candidate search can be performed at high speed.

【００８３】また、本発明に係る配送計画システムは、
遺伝的アルゴリズムを用いて解探索方針を指定する個体
を生成し、解探索方針を最適化し、その探索方針に従っ
て配送計画案が作成されるため、遺伝的アルゴリズムに
よる解空間の中の大局的な探索と同時に、詳細な配送計
画案の作成をＯＲ的な手法等を用いて高速に行うことが
できる。The delivery planning system according to the present invention
Generating an individual designating a solution search policy using a genetic algorithm, optimizing the solution search policy, and creating a delivery plan in accordance with the search policy, a global search in the solution space using the genetic algorithm. At the same time, it is possible to create a detailed delivery plan at a high speed by using an OR method or the like.

【００８４】また、本発明に係る数理計画プログラムを
記録した媒体は、記録された数理計画プログラムをコン
ピュータで実行することにより、遺伝的アルゴリズムに
よる解空間の中の大局的な探索と同時に、詳細な解候補
の探索を、コンピュータで高速に行うことができる。Further, the medium on which the mathematical programming program according to the present invention is recorded can be obtained by executing the recorded mathematical programming program on a computer to simultaneously perform a global search in a solution space by a genetic algorithm and a detailed search. The search for a solution candidate can be performed at high speed by a computer.

【００８５】また、本発明に係る配送計画プログラムを
記録した媒体は、記録された配送計画プログラムをコン
ピュータで実行することにより、遺伝的アルゴリズムに
よる解空間の中の大局的な探索と同時に、詳細な配送計
画案の作成を、コンピュータで高速に行うことができ
る。Further, the medium on which the distribution plan program according to the present invention is recorded can be obtained by executing the recorded distribution plan program on a computer, thereby simultaneously performing a global search in a solution space by a genetic algorithm and a detailed search. The creation of a delivery plan can be performed at high speed by a computer.

[Brief description of the drawings]

【図１】本発明の数理計画計算装置の原理構成図であ
る。FIG. 1 is a principle configuration diagram of a mathematical programming calculation device according to the present invention.

【図２】配送システム全体の概略構成を示すブロック図
である。FIG. 2 is a block diagram illustrating a schematic configuration of the entire delivery system.

【図３】配送計画シミュレータの内部構成を示すブロッ
ク図である。FIG. 3 is a block diagram showing an internal configuration of a delivery planning simulator.

【図４】配送問題の配送先と配送センタとを示す図であ
る。FIG. 4 is a diagram showing a delivery destination and a delivery center in a delivery problem.

【図５】染色体の構成を示す図である。FIG. 5 is a diagram showing the structure of a chromosome.

【図６】配送車割当順序検討部の処置手順を示すフロー
チャートである。FIG. 6 is a flowchart illustrating a procedure of a process performed by a delivery vehicle allocation order examination unit.

【図７】選択処理の手順を示すフローチャートである。FIG. 7 is a flowchart illustrating a procedure of a selection process.

【図８】図７のステップＳ１１において配送車割当順序
検討部が配送計画作成部に与える個体及びその染色体
と、配送計画作成部から受け取る配送計画案との組の例
を示す図である。8 is a diagram showing an example of a set of individuals and their chromosomes provided to a delivery plan creation unit by a delivery vehicle allocation order examination unit in step S11 of FIG. 7 and a delivery plan draft received from the delivery plan creation unit.

【図９】配送計画案の内容を示す図である。FIG. 9 is a diagram showing contents of a delivery plan draft.

【図１０】配送計画作成部の処置手順を示すフローチャ
ートである。FIG. 10 is a flowchart showing a procedure of a delivery plan creation unit.

【図１１】検討対象の配送車の積荷の検討処理の詳細を
示すフローチャートである。FIG. 11 is a flowchart illustrating details of a process of examining a load of a delivery vehicle to be examined.

【図１２】検討対象配送車の積荷の検討処理の進行状況
を示す図である。（Ａ）は最初の配送先３２ａの検討状
況を示す図であり、（Ｂ）は２つめの配送先の検討状況
を示す図であり、（Ｃ）は３つめの配送先の検討状況を
示す図であり、（Ｄ）は３つの配送先の検討結果を示す
図である。FIG. 12 is a diagram showing the progress of the process of examining the load of the delivery vehicle to be examined. (A) is a diagram showing a study status of a first delivery destination 32a, (B) is a diagram showing a study status of a second delivery destination, and (C) is a diagram showing a study status of a third delivery destination. It is a figure, (D) is a figure showing the examination result of three delivery destinations.

【図１３】検討対象配送先への配送に関する検討の処理
の詳細を示すフローチャートである。FIG. 13 is a flowchart showing details of a process of studying delivery to a study destination.

【図１４】最短経路探索の処理の詳細を示すフローチャ
ートである。FIG. 14 is a flowchart illustrating details of a shortest route search process.

【図１５】図１４のステップＳ５１における処理内容を
説明する図である。FIG. 15 is a diagram illustrating the processing content in step S51 of FIG.

【図１６】図１１のステップＳ３７における処理内容を
説明する図である。FIG. 16 is a diagram for explaining processing in step S37 of FIG. 11;

[Explanation of symbols]

１解探索方針最適化手段２解探索手段３個体群３ａ〜３ｃ個体４解候補群４ａ〜４ｃ解候補１０配送計画シミュレータ１１配送車割当順序検討部１２配送計画作成部 DESCRIPTION OF SYMBOLS 1 Solution search policy optimization means 2 Solution search means 3 Individual group 3a-3c individual 4 Solution candidate group 4a-4c Solution candidate 10 Delivery plan simulator 11 Delivery vehicle allocation order examination part 12 Delivery plan creation part

───────────────────────────────────────────────────── フロントページの続き (72)発明者中林歩東京都千代田区丸の内一丁目６番１号株式会社富士通システム総研内 (72)発明者高田和実東京都千代田区丸の内一丁目６番１号株式会社富士通システム総研内 ──────────────────────────────────────────────────続き Continuing on the front page (72) Inventor Ayumu Nakabayashi 1-6-1 Marunouchi, Chiyoda-ku, Tokyo Inside Fujitsu System Research Institute, Ltd. (72) Inventor Kazumi Takada 1-6-1 Marunouchi, Chiyoda-ku, Tokyo No. 1 Inside Fujitsu Systems Research Institute

Claims

[Claims]

1. A mathematical programming calculation device for finding a solution to a mathematical programming problem, comprising: an individual specifying a solution searching policy using a genetic algorithm; and a solution searching policy optimizing means for optimizing the solution searching policy. And a solution search means for searching for a solution candidate according to a solution search policy indicated by a chromosome of the individual.

2. The mathematical programming calculation apparatus according to claim 1, wherein said solution search policy optimizing means sets a designating order of elements as a solution search policy.

3. The solution search policy optimizing means is configured to convert a component constituting a solution into a first component type that is not fixed in a space and a second component type that is fixed in a predetermined space. And designating the examination order of the elements of the first element type, the examination start element of the second element type, and the examination direction of the second element type, as a solution search policy. The mathematical plan calculation device according to claim 2.

4. The solution search policy optimizing means comprises:
The chromosome of the individual is constituted by using, as a partial chromosome, each of the examination order of the elements of the element type, the examination start element of the second element type, and the designation of the examination direction of the second element type. The mathematical plan calculation device according to claim 3, wherein

5. The solution search policy optimizing means obtains a fitness value of a solution candidate searched according to a solution search policy indicated by a chromosome of the individual, and evaluates the individual based on the fitness value. The mathematical programming calculation device according to claim 1, wherein:

6. The solution searching means searches for an element array satisfying a constraint condition and satisfying a predetermined condition every time a new element is added to an array of elements constituting a solution. The mathematical plan calculation device according to claim 1, wherein

7. A delivery planning system for finding a solution to a delivery planning problem, wherein: a solution design policy optimizing means for generating an individual designating a solution search policy using a genetic algorithm and optimizing the solution search policy; A solution search means for searching for a delivery plan in accordance with a solution search policy indicated by an individual's chromosome.

8. The solution search policy optimizing means optimizes the solution search policy for one or both of reduction of delivery cost and satisfaction of constraint conditions. The described delivery planning system.

9. The solution search policy optimizing means includes: an examination order of delivery vehicles; a delivery start destination for first examining whether the assignment to the delivery vehicles to be examined is appropriate; and an assignment to the delivery vehicles to be examined. The delivery planning system according to claim 7, wherein a study direction of a delivery destination when sequentially examining suitability is optimized as a solution search policy.

10. The solution search policy optimizing means configures the chromosome of the individual using the examination order of the delivery vehicles, the study start delivery destination, and the study direction of the delivery destination as individual partial chromosomes. 10. The delivery planning system according to claim 9, wherein:

11. The solution search policy optimizing means obtains a fitness value of a delivery plan searched according to a solution search policy indicated by the individual, based on a predetermined fitness function, and calculates the individual fitness value by the fitness value. 10. The delivery planning system according to claim 7, wherein:

12. The delivery planning system according to claim 7, wherein said solution search means searches for a delivery plan by an operations research method.

13. The delivery planning system according to claim 7, wherein said solution search means manages the positions of the delivery center and the delivery destination in coordinates on a polar coordinate space.

14. The delivery planning system according to claim 13, wherein said solution search means sets a delivery center as an origin of said polar coordinate space.

15. The solution searching means may determine any of a center of gravity of a set including a distribution center at all delivery destinations or all the delivery destinations, and a center in the horizontal and vertical directions of the set as an origin of the polar coordinate space. The delivery planning system according to claim 13, wherein:

16. The delivery planning system according to claim 7, wherein said solution search means manages the positions of the delivery center and the delivery destination in coordinates on a rectangular coordinate space.

17. The delivery planning system according to claim 16, wherein said solution search means sets a delivery center as an origin of said rectangular coordinate space.

18. The solution searching means may determine any one of a center of gravity of a set including delivery centers at all delivery destinations or all delivery destinations, and a center point in the horizontal and vertical directions of the set as an origin of the Cartesian coordinate space. The delivery planning system according to claim 16, wherein:

19. The solution search means, when judging whether the assignment of a delivery destination to a delivery vehicle to be examined is appropriate or not, assigns the delivery destination to be examined to the delivery vehicle to be examined as long as the constraint condition is satisfied. The delivery planning system according to claim 7, wherein:

20. When allocating a delivery destination to a delivery vehicle to be considered, the solution search means selects all delivery destinations except delivery destinations already assigned to other delivery vehicles. 20. The delivery planning system according to claim 19, wherein:

21. The solution search means according to claim 1, further comprising: a work time constraint on the delivery vehicle, a delivery time constraint on the delivery destination, a restriction on intrusion into the delivery destination, a delivery vehicle type constraint on the delivery destination, a delivery vehicle capacity constraint, and a delivery vehicle capacity constraint. 8. The method according to claim 7, wherein one or more of a load temperature constraint, a delivery vehicle operating time constraint, a delivery vehicle travel distance constraint, and a delivery vehicle number constraint are considered as constraint conditions. Delivery planning system.

22. The solution search means includes one or more of a delivery vehicle loading weight constraint, a delivery vehicle loading volume constraint, and a delivery vehicle loading dimension constraint as the delivery vehicle capacity constraints. 22. The delivery planning system according to claim 21, wherein:

23. The delivery planning system according to claim 7, wherein said solution search means examines whether the assignment to a delivery vehicle to be examined is appropriate in consideration of a stay time at a delivery destination.

24. When allocating a new delivery destination to a delivery vehicle to be considered, the solution search means optimally evaluates a predetermined route within a range satisfying a time constraint or a space constraint. 8. The delivery planning system according to claim 7, wherein the determination of the traveling order is performed at the same time.

25. When determining an additional position of a delivery destination to be newly assigned to a delivery vehicle to be considered,
25. The delivery planning system according to claim 24, wherein a position that optimizes a predetermined route evaluation is determined by examining all positions between, or before and after, a delivery destination already assigned.

26. The solution search means repeatedly determines that a delivery route of the delivery vehicle is repeatedly added to a delivery destination newly assigned to the delivery vehicle, between the delivery destinations already assigned, or before and after the delivery destination. 25. The delivery planning system according to claim 24, further comprising: examining a rearrangement of a delivery destination on the delivery route of the delivery vehicle, and determining a traveling route that optimizes a predetermined route evaluation.

27. The method according to claim 27, wherein the solution search means visits the delivery order to each delivery destination first between the delivery center and the other delivery destinations when examining the rearrangement of the delivery destination. Consider a place to change between destinations, between adjacent destinations, or between other destinations that are to be visited last among other destinations and the distribution center. If none of them satisfy the constraints, the order of delivery is not changed.If any of them satisfy the constraints, the route evaluation is the highest among them. 25. The delivery planning system according to claim 24, wherein a case is selected.

28. The method according to claim 24, wherein the solution search means performs route evaluation in consideration of at least one of delivery time, travel time, travel distance, and fuel cost. Delivery planning system.

29. A medium recording a mathematical programming program for finding a solution to a mathematical programming problem by a computer, wherein an individual specifying a solution search policy is generated using a genetic algorithm, and the solution search policy is optimized. A medium for recording a mathematical planning program for causing a computer to function as a solution search policy optimizing means to perform, a solution search means to search for a solution candidate according to a solution search policy indicated by the chromosome of the individual.

30. A medium for recording a delivery plan program for finding a solution to a delivery plan problem by a computer, comprising generating an individual specifying a solution search policy using a genetic algorithm, and optimizing the solution search policy. A medium storing a distribution plan program for causing a computer to function as a search policy optimizing means, and a solution search means for searching for a distribution plan according to a solution search policy indicated by the chromosome of the individual.