JP3535342B2 - Delivery planning system and computer-readable recording medium recording delivery planning program - Google Patents
Delivery planning system and computer-readable recording medium recording delivery planning programInfo
- Publication number
- JP3535342B2 JP3535342B2 JP12052597A JP12052597A JP3535342B2 JP 3535342 B2 JP3535342 B2 JP 3535342B2 JP 12052597 A JP12052597 A JP 12052597A JP 12052597 A JP12052597 A JP 12052597A JP 3535342 B2 JP3535342 B2 JP 3535342B2
- Authority
- JP
- Japan
- Prior art keywords
- delivery
- solution
- destination
- plan
- planning system
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Description
【０００１】[0001]
【発明の属する技術分野】本発明は配送計画問題を解く
ための配送計画システム、及びコンピュータによって配
送計画問題の解を求めるための配送計画プログラムを記
録したコンピュータ読み取り可能な記録媒体に関し、特
に遺伝的アルゴリズム（ＧＡ）を用いて最適な配送計画
を探索する配送計画システム、及び遺伝的アルゴリズム
を用いて最適解を探索する配送計画プログラムを記録し
たコンピュータ読み取り可能な記録媒体に関する。The present invention is distributing feed programming problem delivery planning system for solving BACKGROUND OF THE INVENTION relates to a computer-readable recording medium recording a delivery schedule program for solving the Routing Problem by 及 beauty computer, in particular delivery planning system for searching the optimal delivery plan using genetic algorithm (GA), a computer-readable recording medium recording a delivery schedule program for searching the optimal solution using 及 beauty genetic algorithm.
【０００２】[0002]
【従来の技術】数理計画問題（最適化問題）とは、一般
に、１ないし複数の変数とこれらの変数によって定義さ
れる目的関数（評価関数）とが与えられ、所定の制約条
件の下でこの目的関数の値を最大あるいは最小とする変
数の組（最適解）を求める問題である。この数理計画問
題は、ジェットエンジンの設計やネットワークの設計等
の様々な分野に利用されている。そこで、数理計画問題
の解の探索手法は、従来より様々なものが考えられてい
る。2. Description of the Related Art A mathematical programming problem (optimization problem) is generally given one or a plurality of variables and an objective function (evaluation function) defined by these variables. This is a problem to find 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 solutions to mathematical programming problems have been conventionally considered.
【０００３】従来より広く用いられている数理計画問題
の解の探索手法として、オペレーションズ・リサーチ
（ＯＲ）に含まれる幾つかの解法がある。ＯＲ的手法に
含まれる解法として、例えば、目的関数が線形で表され
る線形計画の解法があり、この解法は古くから研究され
ている。これらの古典的な解法の一部は、山登り法と呼
ばれ、可能解（条件の全てを満たした変数の組）の変数
の値をすこしずつ変化させながら、目的関数の値を最適
解に近づけるものである（但し、可能解の集合内に閉じ
た変化は、山登り法の一部においては必須ではない）。As a search method for a solution to a mathematical programming problem that has been widely used in the past, there are several solution methods included in Operations Research (OR). As a solution included in the OR method, for example, there is a linear programming solution in which an objective function is represented by a linear method, and this solution has been studied for a long time. A part of these classical solution methods is called hill climbing method, which makes the value of the objective function close to the optimal solution while slightly changing the values of the variables of the possible solution (set of variables satisfying all the conditions). (However, closed changes within the set of possible solutions are not mandatory in some climbing methods).
【０００４】ところが、問題によっては、山登り法のよ
うな手法では最適解（厳密には、ある程度の許容範囲に
ある許容解）を得ることができない場合がある。即ち、
周辺（一部または全ての変数の値をすこしだけ変化させ
た場合）と比べれば一番良い値の可能解が得られても、
離れた位置（変数の値を大幅に変化させた場合）にはも
っと良い値の可能解が存在することがある。従って、一
般的な山登り法では、離れた位置に最適解が存在してい
ても、その解を導き出すことができない。However, depending on the problem, there are cases where an optimal solution (strictly speaking, an allowable solution within a certain allowable range) cannot be obtained by a method such as the hill climbing method. That is,
Even if the best possible solution is obtained when compared with the surroundings (when the values of some or all variables are changed slightly),
There may be better possible feasible solutions at distant locations (when the values of the variables are changed significantly). Therefore, even if the optimum solution exists at a distant position, the general hill climbing method cannot derive the solution.
【０００５】そこで、上記の問題を取り除くため、遺伝
的アルゴリズム（ＧＡ）という解探索手法を用いるとが
考え出された。遺伝的アルゴリズムとは、生物の遺伝の
機構を模倣して、それを工学的に応用した技術である。In order to eliminate the above problems, it has been proposed to use a solution search method called a genetic algorithm (GA). A genetic algorithm is a technology that imitates the genetic mechanism of living organisms and applies it engineeringly.
【０００６】生物の進化の過程では、既存の個体（親）
から新たな個体（子）が生まれる際に、個体の持つ染色
体同士の交叉、染色体上の遺伝子の突然変異などが起こ
り、既存の個体とは異なる性質の個体が生まれる。そし
て、環境に適応しない個体は淘汰され、環境に適応した
個体のみが生き延びて新たな子孫を作ることができる。
これにより、環境により適応した個体の集団が生き延び
る。[0006] In the process of evolution of living things, existing individuals (parents)
When a new individual (child) is born, crossover of the chromosomes of the individual, mutation of the gene on the chromosome, etc. occur, and an individual with a property different from the existing individual is born. 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 survives the population of individuals more adapted to the environment.
【０００７】このような生物の進化を数理計画問題に当
てはめたものが、遺伝的アルゴリズムによる解探索手法
である。遺伝的アルゴリズムでは、解候補を個体に見立
て、解候補に含まれる変数を、個体の持つ染色体上の遺
伝子として取り扱う。そして、数理計画問題の目的関数
が環境であり、目的関数の値が各個体の環境への適応性
を表す。なお、遺伝的アルゴリズムでは、目的関数を最
適にするものほど大きい値を取るような適応度関数を定
義し、適応度関数の値（適応度値）を用いて各個体の環
境への適応性を判断し、適応度関数の値が小さい解候補
ほど淘汰されるように制御する。即ち、後述する選択操
作において、適応度関数の値が小さい解候補ほど、より
選択されないように制御する。A solution search method using a genetic algorithm applies such evolution of living things to a mathematical programming problem. In a genetic algorithm, a solution candidate is regarded as an individual, and variables included in the solution candidate are treated as genes on the 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 is defined such that the one that optimizes the objective function takes a larger value, and the fitness function value (fitness value) is used to determine the fitness of each individual to the environment. Judgment is performed, and control is performed so that solution candidates with smaller values of the fitness function are selected. That is, in the selection operation described later, the solution candidate having a smaller fitness function value is controlled so as not to be selected.
【０００８】以上のような定義に基づき、個体に見立て
た複数の解候補に対して、選択(selection) ／自己複製
(reproduction)、交叉(crossover) 、突然変異(mutatio
n)の操作を繰り返し行う。以下に、遺伝的アルゴリズム
の最適解探索の手順を、簡単に説明する。[0008] Based on the above definition, selection / self-replication is performed for a plurality of solution candidates likened to individuals.
(reproduction), crossover, mutation (mutatio)
Repeat step n). The procedure for searching for the optimal solution of the 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, the selection operation is performed. In the selection, the fitness value is obtained from the chromosome (one-dimensional string of genes) of each individual of the first generation, and the individual having a high fitness is selected with a higher probability. An individual pair is created from the selected individuals. This pair of individuals becomes the next-generation parent.
【００１０】次に、交叉の操作を行う。交叉では、個体
対のそれぞれの個体の持つ染色体の一部を丁度互いに入
れ換えたような染色体を持つ、新たな個体を生成する。
このようにして生成された個体は、双方の親の性質をあ
る程度ずつ引き継いでいる。Next, a crossing operation is performed. In the crossover, a new individual having a chromosome in which a part of the chromosomes of each individual of the individual pair is just replaced with each other is generated.
The individual generated in this manner inherits the properties of both parents to some extent.
【００１１】さらに、突然変異の操作を行う。突然変異
では、交叉によって生成された個体の染色体の一部の遺
伝子を、ランダムに選ばれた別の値に置き換える。この
突然変異によって、親の持っていない遺伝子を有する個
体が生まれる。このようにして生成された複数の個体
（集団）が第２世代の集団となる。Further, a mutation operation is performed. Mutation replaces some genes in the chromosomes of an individual created by crossover with another randomly chosen value. This mutation creates an individual with a gene that the parent does not have. The plurality of individuals (groups) generated in this way constitutes a second generation group.
【００１２】以後、選択、交叉、突然変異を繰り返し、
世代を重ねていく。その結果、適応度の低い個体は淘汰
され、適応度の高い個体の集団が形成される。しかも、
交叉や突然変異があることにより解空間の中を大域的
に、且つ確率的に探索でき、山登り法のように最適解に
対しかなり劣る解に収束する現象を防止することができ
る。After that, selection, crossover and mutation are repeated,
The generations are repeated. 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 it is possible to prevent the phenomenon of converging to a solution that is considerably inferior to the optimal solution such as the hill climbing method.
【００１３】[0013]
【発明が解決しようとする課題】しかし、遺伝的アルゴ
リズムは解空間の中を大局的に探索できる反面、その実
行には膨大な量の計算が必要であり、実際の問題を解く
には時間がかかりすぎるという問題点があった。However, while the genetic algorithm can search the solution space in a global manner, its execution requires a huge amount of calculation, and it takes time to solve the actual problem. There was a problem that it took too much.
【００１４】例えば、荷物の配送問題において、配送コ
スト、制約条件満足度等の観点から遺伝的アルゴリズム
により最適解を探索する場合を考える。この場合、制約
条件には、配送センタの業務時間、配送先の受け付け時
間等、様々な制約条件がある。これらの全ての制約条件
を考慮した場合、解の探索空間が広大となる。このよう
に広大な探索空間を遺伝的アルゴリズムで探索した場
合、現在の計算機では、実用可能な時間内で許容解を得
ることはできない。Consider, for example, a case of searching for an optimum solution by a genetic algorithm from the viewpoint of delivery cost, satisfaction of constraint conditions, etc. in a parcel delivery problem. In this case, the constraint conditions include various constraint conditions such as the business hours of the delivery center and the acceptance time of the delivery destination. If all these constraints are taken into consideration, the solution search space becomes vast. When such a vast search space is searched by a genetic algorithm, the present computer cannot obtain an acceptable solution within a practicable time.
【００１５】本発明はこのような点に鑑みてなされたも
のであり、良好な解を高速に探索することができる配送
計画システムを提供することを目的とする。 The present invention has been made in view of the above points, and a delivery method capable of searching for a good solution at high speed.
The purpose is to provide a planning system .
【００１６】また、本発明の別の目的は、コンピュータ
に良好な結果の配送計画を高速に探索させることができ
る配送計画プログラムを記録したコンピュータ読み取り
可能な記録媒体を提供することである。[0016] Also, another object, the computer reads the recorded delivery planning program capable of searching the delivery plan good results to a computer at a high speed of the present invention
It is to provide a possible recording medium.
【００１７】[0017]
【課題を解決するための手段】本発明では上記課題を解
決するために、配送計画問題の解を求める配送計画シス
テムにおいて、配送先を配送車に割り当てるために満た
すべき条件を示す制約条件、適応度関数、および配送先
の位置情報を入力する入力手段と、検討対象の配送車へ
の割り当ての適否を最初に検討する検討開始配送先、及
び検討対象の配送車への割り当ての適否を順次検討する
際の配送先の検討方向が、解探索方針を示す染色体とし
て含まれた個体を、遺伝的アルゴリズムを用いて生成
し、解探索方針を最適化する解探索方針最適化手段と、
配送先の前記位置情報に基づいて、各配送先を、前記個
体の染色体で示された前記検討開始配送先から前記検討
方向に向かった順に検討対象の配送先として選択し、選
択された前記配送先から順番に前記制約条件に従って検
討対象の配送車への割り当ての適否を検討し、配送計画
案を探索する解探索手段と、前記解探索手段で探索され
た前記配送計画案を前記適応度関数に基づいて評価し、
評価が最も高い前記配送計画案を解として出力する出力
手段と、を有することを特徴とする配送計画システムが
提供される。 According to the present invention, in order to solve the above problems , a delivery plan system for obtaining a solution of a delivery plan problem is obtained.
System to meet the requirements for assigning the delivery destination to the delivery vehicle.
Constraints indicating the conditions to be met, fitness function, and shipping destination
To input the location information of the
First, consider the suitability of allocation of
And the suitability of allocation to the delivery vehicles under consideration
In this case, the direction of consideration of the delivery destination is the chromosome showing the solution search policy.
The included individuals using a genetic algorithm
And a solution search policy optimizing means for optimizing the solution search policy,
Based on the location information of the delivery destination,
Starting the examination indicated by the chromosome of the body
Select as a delivery destination to be considered in the order of direction, and select
In order from the selected delivery destination, the inspection is performed according to the constraint conditions.
Consider the suitability of allocation to the delivery vehicle to be discussed and plan delivery
The solution search means for searching the plan and the solution search means
Evaluating the delivery plan based on the fitness function,
Output that outputs the delivery plan with the highest evaluation as a solution
And a delivery planning system characterized by having
Provided.
【００１８】[0018]
【００１９】[0019]
【００２０】この配送計画システムによれば、遺伝的ア
ルゴリズムによって解探索方針が示され、その探索方針
に従って配送計画案が作成されるため、遺伝的アルゴリ
ズムによる解空間の中の大局的な探索と同時に、詳細な
配送計画案の作成は高速に行うことができる。According to this delivery planning system, the genetic algorithm indicates the solution search policy, and the delivery plan is created in accordance with the search policy. Therefore, at the same time as the global search in the solution space by the genetic algorithm is performed. , A detailed delivery plan can be created at high speed.
【００２１】[0021]
【００２２】また、配送計画問題の解を求める配送計画
システムにおいて、配送先を配送車に割り当てるために
満たすべき条件を示す制約条件、および適応度関数を入
力する入力手段と、配送車の検討順序が解探索方針を示
す染色体として含まれた個体を、遺伝的アルゴリズムを
用いて生成し、前記解探索方針を最適化する解探索方針
最適化手段と、前記個体の染色体で示された前記配送車
の検討順序に従って検討対象の配送車を選択し、選択さ
れた前記配送車から順番に前記制約条件に従って検討対
象の配送先の割り当ての適否を検討し、配送計画案を探
索する解探索手段と、前記解探索手段で探索された前記
配送計画案を前記適応度関数に基づいて評価し、評価が
最も高い前記配送計画案を解として出力する出力手段
と、を有することを特徴とする配送計画システムが提供
される。 A delivery plan for finding a solution to the delivery plan problem
To assign a delivery destination to a delivery vehicle in the system
Enter the constraint condition that indicates the condition to be satisfied and the fitness function.
Input method to input and delivery vehicle examination order indicate solution search policy
The individual included as a chromosome is
A solution search policy that is generated by using and optimizes the solution search policy
Optimization means and the delivery vehicle indicated by the chromosome of the individual
Select the delivery vehicle to be considered according to the
In order from the delivered vehicles that have been
Consider the suitability of elephant delivery destination assignments and search for a delivery plan.
The solution search means to search for, and the solution searched by the solution search means
The delivery plan is evaluated based on the fitness function, and the evaluation is
Output means for outputting the highest delivery plan as a solution
And a delivery planning system provided with
To be done.
【００２３】また、配送計画問題の解を求める配送計画
プログラムを記録したコンピュータ読み取り可能な記録
媒体において、前記コンピュータを、配送先を配送車に
割り当てるために満たすべき条件を示す制約条件、適応
度関数、および配送先の位置情報を入力する入力手段、
検討対象の配送車への割り当ての適否を最初に検討する
検討開始配送先、及び検討対象の配送車への割り当ての
適否を順次検討する際の配送先の検討方向が、解探索方
針を示す染色体として含まれた個体を、遺伝的アルゴリ
ズムを用いて生成し、前記解探索方針を最適化する解探
索方針最適化手段、配送先の前記位置情報に基づいて、
各配送先を、前記個体の染色体で示された前記検討開始
配送先から前記検討方向に向かった順に検討対象の配送
先として選択し、選択された前記配送先から順番に前記
制約条件に従って検討対象の配送車への割り当ての適否
を検討し、配送計画案を探索する解探索手段、前記解探
索手段で探索された前記配送計画案を前記適応度関数に
基づいて評価し、評価が最も高い前記配送計画案を解と
して出力する出力手段、として機能させることを特徴と
する配送計画プログラムを記録したコンピュータ読み取
り可能な記録媒体が提供される。 A delivery plan for finding a solution to the delivery plan problem
Computer-readable record of the program
In the medium, the computer is used as the delivery destination and the delivery vehicle is used.
Constraints that indicate the conditions that must be satisfied for allocation, adaptation
Input function to input the degree function and the location information of the delivery destination,
First consider the suitability of allocation to the delivery vehicle under consideration
Study start delivery destination and assignment to the delivery vehicle under consideration
When the suitability is examined sequentially, the direction of consideration of the delivery destination is the solution search method.
An individual included as a chromosome showing a needle is called a genetic algorithm.
Solution search that optimizes the solution search policy by generating
Based on the location information of the search policy optimization means and the delivery destination,
Start each study on each delivery destination indicated by the chromosome of the individual
Delivery under consideration in the order from the delivery destination to the above-mentioned examination direction
The destination is selected, and the delivery is selected in order from the delivery destination.
Adequacy of allocation to delivery vehicles under consideration according to constraints
And a solution search means for searching a delivery plan,
The delivery plan searched by the searching means is used as the fitness function.
Based on the evaluation, the delivery plan with the highest evaluation is solved.
And output as output means,
Computer-readable recording of a shipping planning program
Recordable recording medium is provided.
【００２４】また、配送計画問題の解を求める配送計画
プログラムを記録したコンピュータ読み取り可能な記録
媒体において、前記コンピュータを、配送先を配送車に
割り当てるために満たすべき条件を示す制約条件、およ
び適応度関数を入力する入力手段、配送車の検討順序が
解探索方針を示す染色体として含まれた個体を、遺伝的
アルゴリズムを用いて生成し、前記解探索方針を最適化
する解探索方針最適化手段、前記個体の染色体で示され
た前記配送車の検討順序に従って検討対象の配送車を選
択し、選択された前記配送車から順番に前記制約条件に
従って検討対象の配送先の割り当ての適否を検討し、配
送計画案を探索する解探索手段、前記解探索手段で探索
された前記配送計画案を前記適応度関数に基づいて評価
し、評価が最も高い前記配送計画案を解として出力する
出力手段、として機能させることを有することを特徴と
する配送計画プログラムを記録したコンピュータ読み取
り可能な記録媒体が提供される。 A delivery plan for finding a solution to the delivery plan problem
Computer-readable record of the program
In the medium, the computer is set as the delivery destination and the delivery vehicle is set as the delivery vehicle.
Constraints that indicate the conditions that must be met for allocation, and
Input method for inputting the fitness function and
Individuals included as chromosomes indicating the solution search policy are
Generate using algorithm to optimize the solution search policy
A solution search policy optimization means, which is indicated by the chromosome of the individual
Select the delivery vehicle to be considered according to the order of the delivery vehicle
Selected and selected from the delivery vehicle in order to the constraint conditions
Therefore, consider the suitability of the allocation of the delivery destination under consideration and
Solution search means for searching the transmission plan, and search by the solution search means
The delivered delivery plan based on the fitness function
Then, the delivery plan with the highest evaluation is output as a solution.
Characterized in that it has a function as an output means.
Computer-readable recording of a shipping planning program
Recordable recording medium is provided.
【００２５】[0025]
【発明の実施の形態】以下、本発明の実施の形態を図面
に基づいて説明する。図１は本発明の数理計画計算装置
の原理構成図である。この数理計画計算装置に数理計画
問題が入力されると、解探索方針最適化手段１が遺伝的
アルゴリズムを用いて、解探索方針を示す染色体を有す
る個体３ａ〜３ｃを生成する。これらの個体で個体群３
が形成され、この個体群３は、解探索手段２に渡され
る。BEST MODE FOR CARRYING OUT THE INVENTION Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing the principle of a mathematical program calculation device according to the present invention. When a mathematical programming problem is input to the mathematical program computing 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
Are formed, and this population 3 is passed to the solution search means 2.
【００２６】解探索手段２は、個体群３内の各個体３ａ
〜３ｃの染色体で示された解探索方針に従って数理計画
問題の解を探索し、解候補４ａ〜４ｃを作成する。この
とき、解候補４ａは個体３ａに基づき、解候補４ｂは個
体３ｂに基づき、解候補４ｃは個体３ｃに基づき、それ
ぞれ独立に作成される。そして、解候補４ａ〜４ｃを解
候補群４として、解探索方針最適化手段１に渡す。The solution searching means 2 is for each individual 3a in the individual group 3.
The solution of the mathematical programming problem is searched in accordance with the solution search policy indicated by the chromosomes 3c to 3c to create solution candidates 4a to 4c. At this time, the solution candidate 4a is created based on the individual 3a, the solution candidate 4b is created based on the individual 3b, and the solution candidate 4c is created based on the individual 3c. Then, the solution candidates 4a to 4c are passed to the solution search policy optimizing means 1 as the solution candidate group 4.
【００２７】解探索方針最適化手段１は、解候補群４の
各解候補４ａ〜４ｃの適応度値を求める。そして、さら
に次の世代の解候補を探索する必要があれば、適応度値
を用いて個体３ａ〜３ｃの選択、交叉、及び突然変異の
処理を施し、次の世代の個体群を作成し、解探索手段２
に渡す。一方、次の世代の解候補を探索する必要がなけ
れば、適応度値の最も良い解候補を、この数理計画問題
の解とする。なお、殆どの場合、この解は厳密な意味の
最適解ではなく、予め定められた許容範囲内にある比較
的良好な許容解である。The solution search policy optimizing means 1 obtains the fitness value of each of the solution candidates 4a to 4c of the solution candidate group 4. Then, if it is necessary to further search for a solution candidate for the next generation, the fitness value is used to perform selection, crossover, and mutation processing of the individuals 3a to 3c to create a population of the next generation, 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, the solution candidate having the best fitness value is set as the solution of this mathematical programming problem. In most cases, this solution is not an exact solution in a strict sense, but a relatively good allowable solution within a predetermined allowable range.
【００２８】このように、解を探索するための探索方針
を遺伝的アルゴリズムで最適化し、その方針に従って別
の高速な手法で解を探索することにより、全ての解探索
を遺伝的アルゴリズムで行う場合よりも、高速に処理す
ることができる。しかも、解探索方針が遺伝的アルゴリ
ズムで指定されるため、広大な解空間の中を大局的に探
索できる。In this way, when the search strategy for searching for the solution is optimized by the genetic algorithm and the solution is searched by another high-speed method according to the policy, all the solution searches are performed by the genetic algorithm. Can be processed faster than. Moreover, since the solution search policy is specified by the genetic algorithm, a vast solution space can be searched in a global manner.
【００２９】なお、上記の解探索方針最適化手段１と解
探索手段２とは、所定のプログラムをコンピュータに実
行させることにより、実現することができる。その場
合、これらの手段を実現するためのプログラムは、コン
ピュータで読み取り可能な記録媒体（半導体メモリや磁
気記録媒体等）に格納しておく。The solution searching policy optimizing means 1 and the solution searching means 2 can be realized by causing a computer to execute a predetermined program. In that case, the programs for realizing these means are stored in a computer-readable recording medium (semiconductor memory, magnetic recording medium, or the like).
【００３０】以上のような数理計画計算装置は、様々な
数理計画問題の解探索に利用することができる。その一
つに、配送計画問題がある。以下に、上記の数理計画計
算装置を適用した配送計画システムについて説明する。The above mathematical program computing device can be used for searching for solutions to various mathematical programming problems. One of them is the delivery planning problem. Below, a delivery planning system to which the above-mentioned mathematical planning calculation device is applied will be explained.
【００３１】図２は配送システム全体の概略構成を示す
ブロック図である。この配送システムは、配送計画シミ
ュレータ１０を中心に構成されている。この配送計画シ
ミュレータ１０は、遺伝的アルゴリズムとＯＲ的手法と
を用いて配送計画の計算を行う。FIG. 2 is a block diagram showing a schematic configuration of the entire delivery system. The delivery system mainly includes a delivery plan simulator 10. The delivery plan simulator 10 calculates a delivery plan using a genetic algorithm and an OR method.
【００３２】配送計画の計算を行う際には、配送計画シ
ミュレータ１０に対して、シミュレーション条件２１、
地図情報２２、配送先／配送車情報２３、及び出荷デー
タ２４が入力される。シミュレーション条件２１は、制
約条件、適応度関数、及び遺伝的アルゴリズムを用いる
際に第何世代まで計算するか等の計算条件である。地図
情報２２には、配送先の位置情報、配送先内所要時間情
報、及び道路情報等が含まれる。配送先／配送車情報２
３には、配送先の店着指定時刻、納品時間、停車車種制
限等が含まれる。出荷データ２４は、配送すべき荷物の
出荷伝票のデータである。この出荷データ２４は、品物
の在庫や、注文の受け付け等を管理している基幹システ
ムから送られてくる。When the delivery plan is calculated, simulation conditions 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 the constraint condition, the fitness function, and the number of generations to be calculated when using the genetic algorithm. 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 vehicle information 2
3 includes the designated delivery time at the delivery destination, delivery time, stop vehicle type restriction, and the like. The shipping data 24 is data of shipping slips for packages to be delivered. The shipping data 24 is sent from a core system that manages the inventory of goods and acceptance of orders.
【００３３】必要な情報を受け取った配送計画シミュレ
ータ１０は、配送計画を計算する。算出された配送計画
は、ルート表示部２５とタイムチャート表示部２６に送
られる。ルート表示部２５は、表示装置上に地図ウィン
ドウを開き、そのウィンドウの中に周辺の地図を表示
し、更に、その地図上に各配送ルートを表示する。The delivery plan simulator 10, which has 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 surrounding area in the window, and further displays each delivery route on the map.
【００３４】タイムチャート表示部２６は、地図ウィン
ドウとは別のタイムチャートウィンドウを開く。そのタ
イムチャートウィンドウには、各配送ルートに於ける時
間経過に伴う配送車両の状態の変化がタイムチャートで
表示される。The time chart display section 26 opens a time chart window other than the map window. In the time chart window, changes in the state of the delivery vehicle with the passage of time on each delivery route are displayed in a time chart.
【００３５】図３は配送計画シミュレータの内部構成を
示すブロック図である。配送計画シミュレータ１０内に
は、遺伝的アルゴリズムにより、検討すべき配送車の配
送先への割当順序等の解探索方針を最適化する配送車割
当順序検討部１１と、指定された探索方針に従ってＯＲ
的手法により配送計画案を作成する配送計画作成部１２
とが設けられている。FIG. 3 is a block diagram showing the internal structure of the delivery plan simulator. The delivery plan simulator 10 uses a genetic algorithm to optimize the solution search policy such as the order of allocation of delivery vehicles to be considered to the delivery destination, and the delivery vehicle allocation order examination unit 11 and OR according to the specified search policy.
Delivery plan creation unit 12 that creates a delivery plan proposal by a statistical method
And are provided.
【００３６】配送車割当順序検討部１１は、遺伝的アル
ゴルズムによる処理機能を有しており、解探索方針を染
色体で示す個体に対して、選択、交叉、及び突然変異の
操作を繰り返し行う。これにより、個体群の子孫を順次
生成する。解探索方針としては、検討の対象とする配送
車の配送先への割当順序、最初の配送車の検討を行う際
に、初めに検討対象とすべき配送先の指定、及び配送先
の検討を順次行う際の配送先の選択方向指定である。The delivery vehicle assignment order examination unit 11 has a processing function based on genetic algorithm, and repeatedly performs selection, crossover, and mutation operations on individuals whose solution search policy is indicated by chromosomes. As a result, the offspring of the population are sequentially generated. The solution search policy is to assign the delivery vehicles to be examined to the delivery destinations, specify the delivery destinations to be considered first when considering the first delivery vehicle, and consider the delivery destinations. This is a designation of a delivery destination selection direction when sequentially performing.
【００３７】配送車割当順序検討部１１が選択を行う際
には、その世代の個体群を配送計画作成部１２に渡し、
各個体に対応して作成された配送計画案を配送計画作成
部１２から受け取る。この配送計画案から適応度値を計
算し、適応度値に基づいて選択を行い、次世代を生成す
るための個体対を作る。また、処理の終了条件を満たし
た場合には、その世代の中で適応度値の値の大きい配送
計画案を解とする。When the delivery vehicle allocation order examination unit 11 makes a selection, it passes the population of that generation to the delivery plan creation unit 12,
The delivery plan creation unit 12 receives the delivery plan draft created corresponding to each individual. The fitness value is calculated from this delivery plan, selection is performed based on the fitness value, and an individual pair for generating the next generation is created. When the processing termination condition is satisfied, the delivery plan having the highest fitness value in the generation is set as the solution.
【００３８】配送計画作成部１２は、配送経路立案部１
２ａと配送経路修正部１２ｂとを有している。配送経路
立案部１２ａは、配送車割当順序検討部１１から送られ
たある世代の個体群を受け取ると、個体の染色体に示さ
れている順番で検討対象の配送車を選択する。そして、
検討対象の配送車について、配送先を割り当てる仮配送
経路を作成する。配送経路修正部１２ｂは、仮配送経路
を受け取り、各配送車が配送すべき配送先の配送順の入
替えを行い、時間が最短になるような配送順を見つけ
る。修正が加えられた配送経路が、新配送経路となる。
同様にして、全ての配送車に対する新配送経路を確定
し、配送計画案が作成される。そして、各個体に対応し
て作成した配送計画案を配送車割当順序検討部１１に送
る。The delivery plan creation unit 12 is the delivery route planning unit 1
2a and a delivery route correction unit 12b. When the delivery route planning unit 12a receives the group of individuals 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 shown in the chromosome of the individual. And
For the delivery vehicle under consideration, create a temporary delivery route to which the delivery destination is assigned. The delivery route correction unit 12b receives the temporary delivery route, replaces the delivery order of the delivery destinations to be delivered by each delivery vehicle, 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 corresponding to each individual is sent to the delivery vehicle allocation order examination unit 11.
【００３９】なお、上記の配送車割当順序検討部１１と
配送計画作成部１２とは、所定のプログラムをコンピュ
ータに実行させることにより、実現することができる。
その場合、これらの機能を実現するためのプログラム
は、コンピュータで読み取り可能な記録媒体（半導体メ
モリや磁気記録媒体等）に格納しておく。The delivery vehicle allocation order examining unit 11 and the delivery plan creating unit 12 can be realized by causing a computer to execute a predetermined program.
In that case, the programs for realizing these functions are stored in a computer-readable recording medium (semiconductor memory, magnetic recording medium, or the like).
【００４０】以上のような配送計画システムにより、遺
伝的アルゴルズムとＯＲ的手法とを組み合わせて、最適
解を探索する。以下に、配送問題の具体例を用いて、上
記の配送計画システムの処理手順を説明する。With the delivery planning system as described above, an optimal solution is searched for by combining the genetic algorithm and the OR method. The processing procedure of the above delivery planning system will be described below using a specific example of the delivery problem.
【００４１】図４は配送問題の配送先と配送センタとを
示す図である。この例では、配送センタ３１から各配送
先３２へ荷物を配送する際に必要となる車両数を最小に
することを目的とする。この空間は、配送センタ３１を
原点とする極座標で認識される。そして、検討対象とす
る配送先を選択するための線３４を定義する。この線３
４と原線３３との角度θを増大させるか（反時計回
り）、減少させるか（時計回り）を指定することによ
り、配送先検討方向が指定される。FIG. 4 is a diagram showing a delivery destination and a delivery center of a delivery problem. The purpose of this example is to minimize the number of vehicles required for delivering a package from the delivery center 31 to each delivery destination 32. This space is recognized in polar coordinates with the distribution center 31 as the origin. Then, the line 34 for selecting the delivery destination to be considered is defined. This line 3
The delivery destination study direction is designated by designating whether the angle θ between 4 and the original line 33 is increased (counterclockwise) or reduced (clockwise).
【００４２】制約条件としては、「配送センタの業務時
間制約」、「配送先の受け付け時間制約」、「配送先へ
の侵入制約（道路事情による侵入可否）」、「配送先の
受け付け配送車種類制約（配送先Ａ社には、Ａ社の社名
入りの配送車しか使用することができない場合等）」、
「配送車の容量制約」、「配送車の積載温度制約」、
「配送車の稼働時間制約」、「配送車の走行距離制
約」、「配送車台数制約」がある。なお、「配送車の容
量制約」には、「配送車積載重量制約」、「配送車積載
体積制約」、「配送車積載寸法制約」が含まれる。The constraint conditions are "business hours restriction of delivery center", "reception time restriction of delivery destination", "intrusion restriction on delivery destination (whether intrusion due to road conditions)", "delivery destination acceptance delivery vehicle type". Restrictions (for example, if the delivery company A can only use delivery vehicles with the company name A) ",
"Capacity of delivery vehicle", "Loading temperature limitation of delivery vehicle",
There are "Delivery vehicle operating time constraint", "Delivery vehicle mileage constraint", and "Delivery vehicle number constraint". Note that the "delivery vehicle capacity constraint" includes a "delivery vehicle loading weight constraint", a "delivery vehicle loading volume constraint", and a "delivery vehicle loading size constraint".
【００４３】この例では、配送コストの低減を目的とし
て最適化する。配送コストを左右する要素には、使用配
送車数、配送時間（人件費に影響する）、配送車走行距
離（燃料費に影響する）などがある。ここでは、特に使
用配送車数の削減を主たる目的とし、合わせて配送車積
載重量総和の削減も副次的目的として、最適化を行う。
１台の配送車両の１年間の維持費は高額であり、配送セ
ンタに必要な配送車両の数を減らせれば、コストの削減
の効果が非常に大きいためである。In this example, optimization is performed for the purpose of reducing the delivery cost. Factors that influence the delivery cost include the number of delivery vehicles used, delivery time (which affects labor costs), and distance traveled by delivery vehicles (which affects fuel costs). Here, in particular, optimization is performed with the main purpose of reducing the number of delivery vehicles used and the secondary purpose of reducing the total weight of 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 cost reduction effect is very large.
【００４４】そこで、ｋ番目の個体の示す探索方針で作
成された配送計画案の適応度関数ｆ k は、Therefore, the search policy indicated by the k-th individual is used.
Fitness function f of the created delivery plan kIs
【００４５】[0045]
【数１】ｆk ＝１／（ａ×配送車数＋ｂ×配送車積載重
量総和＋ｃ×配送車不足）
とする。ここで、ａ，ｂ，ｃは、予め設定された定数で
ある。配送車不足は、配送車が不足する場合は「１」、
そうでない場合は「０」である。この適応度関数を最大
にする解を求めれば、必要な配送車数及び配送車積載重
量総和を最小にすることができる。なお、ｃの値は、ａ
やｂよりも十分大きな値とする。ｃの値を大きな値とす
ることにより、配送車が不足するような解しか生成され
ない個体は、淘汰される可能性が大きくなる。## EQU1 ## Let f k = 1 / (a × number of delivery vehicles + b × total delivery vehicle loading weight + c × delivery vehicle shortage). Here, a, b, and c are preset constants. Delivery vehicle shortage is "1" when delivery vehicles are short,
Otherwise, it is "0". If the solution that maximizes this fitness function is obtained, the required number of delivery vehicles and the total weight of delivery vehicles loaded can be minimized. The value of c is a
Or a value sufficiently larger than b. When the value of c is set to a large value, an individual who can generate only a solution that runs short of delivery vehicles has a high possibility of being selected.
【００４６】選択確率は、The selection probability is
【００４７】[0047]
【数２】選択確率＝ｆk n ／Σ（ｆk n ）
とする。ここで、適応度関数ｆk をｎ乗したのは、この
ｎの値を変えることにより、個体の選択確率を容易に調
整することができるようにするためである。即ち、ｎの
値を大きくすれば、適応度値の大きな個体が選択される
可能性が大きくなり、ｎの値を小さくすれば、適応度値
の小さな個体であっても選択される可能性が大きくな
る。## EQU00002 ## Selection probability = f k n / Σ (f k n ). Here, the reason that the fitness function f k is raised to the power of n is that the selection probability of an individual can be easily adjusted by changing the value of n. That is, increasing the value of n increases the possibility that an individual having a large fitness value will be selected, and decreasing the value of n may select even an individual having a small fitness value. growing.
【００４８】また、交叉には２点交叉を用い、突然変異
は２遺伝子の交換とする。そして、個体の有する染色体
は、「配送車割当順」、「割当開始位置」、「検討方
向」を指定する部分染色体で構成する。Two-point crossover is used for crossover, and the mutation is exchange of two genes. Then, the chromosome of the individual is composed of partial chromosomes that specify the “delivery vehicle allocation order”, the “allocation start position”, and the “study direction”.
【００４９】図５は染色体の構成を示す図である。この
染色体５０は、６個の遺伝子を有している。染色体５０
は３つの部分染色体から構成されており、遺伝子５１、
遺伝子５２、及び遺伝子５３〜５６がそれぞれ１つの部
分染色体を形成している。FIG. 5 is a diagram showing the constitution of chromosomes. This chromosome 50 has 6 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 "+" or "-" is set. When the gene 51 is "+",
It shows that the delivery destination is examined in the direction in which the angle θ increases in polar coordinates with the delivery center as the origin. When the gene 51 is "-", the polar coordinate angle θ with the distribution center as the origin
It indicates that the delivery destination should be examined in the direction of decrease.
【００５１】遺伝子５２は、配送先の番号が設定され
る。１番目に検討を行う配送車は、この遺伝子５２に設
定された番号の配送先から検討を開始する。遺伝子５３
〜５６は、配送先割当の検討を行う配送車の順番を指定
している。遺伝子５３→遺伝子５４→遺伝子５５→遺伝
子５６の順で、その遺伝子の示す配送車の配送先割当を
検討する。As the gene 52, the delivery destination number is set. The delivery vehicle to be examined first starts the examination from the delivery destination of the number set in this gene 52. Gene 53
56 designate the order of delivery vehicles for which delivery destination allocation is to be considered. The 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 the element species not fixed in the space (genes 53 to 56) and the element species fixed in the predetermined space (genes 51, 52). .
【００５３】このような染色体に対して交叉と突然変異
とを行う際には、まず、染色体を３つの部分染色体に分
割する。そして、親となる２つの染色体の部分染色体ど
うしを互いに入れ換えることにより、２点交叉を行う。
交叉を行った後に、突然変異を行う。遺伝子５１と遺伝
子５２と（それぞれの遺伝子１つが、１つの部分染色体
である）に対する突然変異は、一定の確率で遺伝子の値
を別の値に変更することである。遺伝子５３〜５６（４
つの遺伝子で１つの部分染色体を構成している）に対す
る突然変異は、一定の確率で２つの遺伝子の値を互いに
他方の値に置き換えることである。When crossover and mutation are performed on such a chromosome, the chromosome is first divided into three partial chromosomes. Then, two-point crossover is performed by exchanging the partial chromosomes of the two parental chromosomes with each other.
After crossover, mutation is performed. The 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. Gene 53-56 (4
One gene constitutes one partial chromosome) is a mutation that replaces 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 optimum solution of the delivery plan is started. The search for the optimum solution is performed mainly by the delivery vehicle allocation order examining unit 11.
【００５５】図６は配送車割当順序検討部の処置手順を
示すフローチャートである。
〔Ｓ１〕集団の初期化として、第１世代を構成する個体
の集団を生成する。この第１世代の各個体は、例えばラ
ンダムに遺伝子を組み合わせることによって作成する。
〔Ｓ２〕生成された集団の各個体から、所定の判断基準
に基づき個体対を選択する。この処理の詳細は、図７に
おいて説明する。
〔Ｓ３〕ステップＳ２によって選択された個体対の各個
体の染色体を２点交叉によって交叉させ、新たな染色体
を生成する。
〔Ｓ４〕ステップＳ３で生成された各染色体の中の２つ
の遺伝子の値を互いに他方の値に換えることにより、突
然変異を行う。このステップで生成された染色体を有す
る個体が、次の世代の個体群となる。
〔Ｓ５〕処理が終了か否かを判断する。判断基準として
は、例えば、ある一定の世代に達していれば処理を終了
する。処理を終了するための基準を満たしていなけれ
ば、ステップＳ２に進み、次の世代による解の探索を行
う。処理を終了すると判断した場合には、現在の世代で
得られた配送計画案の中で、適応度値が最も良いものを
許容解とする。FIG. 6 is a flow chart showing the procedure of the delivery vehicle allocation order examining unit. [S1] As initialization of the population, a population of individuals forming 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. 7. [S3] The chromosome of each individual of the individual pair selected in step S2 is 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 the other value. The individuals having the chromosomes generated in this step become the next-generation population. [S5] It is determined whether the processing is completed. As a criterion, for example, the process is terminated if a certain number of generations has been reached. If the criterion for ending the process is not satisfied, the process proceeds to step S2 to search for a solution by the next generation. When it is determined that the processing is to be ended, the one having the best fitness value in the delivery plan proposals obtained in the current generation is set as the acceptable solution.
【００５６】図７は選択処理の手順を示すフローチャー
トである。
〔Ｓ１１〕集団を配送計画作成部１２に渡し、配送計画
作成部１２から、ＯＲ的手法により作成された配送計画
案を受け取る。
〔Ｓ１２〕受け取った配送計画案の適応度値を計算す
る。
〔Ｓ１３〕適応度値を判断基準として、個体対を選択す
る。FIG. 7 is a flow chart showing the procedure of the selection process. [S11] The group is transferred to the delivery plan creation unit 12, and the delivery plan proposal 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 that the delivery vehicle allocation order examination unit gives to the delivery plan creation unit 12 and the delivery plan proposal received from the delivery plan creation unit 12 in step S11 of FIG. Is. Delivery plan 41-4
3 is sent from the delivery route creation unit 12. By obtaining the fitness value from the delivery plans 41 to 43, the chromosomes 50, 50a and 50b can be evaluated.
【００５８】図９は配送計画案の内容を示す図である。
これは染色体５０の示す探索条件に従って作成された配
送計画案である。このように、各配送車６１〜６４がど
の配送先をどの順番で巡回するのかを示す情報が含まれ
ている。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. In this way, information indicating which delivery destinations each delivery vehicle 61 to 64 goes around in which order is included.
【００５９】以上が、配送車割当順序検討部１１の処置
手順である。次に、配送計画作成部１２の処理手順を説
明する。図１０は配送計画作成部の処置手順を示すフロ
ーチャートである。なお、以下のフローチャートの説明
において特に示さない限り、配送経路立案部１２ａが処
理を行う。
〔Ｓ２１〕ｉの初期値として「１」を設定する。
〔Ｓ２２〕検討対象配送車として、ｉ番目の遺伝子を選
択する。この場合のｉ番目とは、染色体の配送車割当順
序を示す遺伝子を左側から数えた場合の順番である。図
５に示した染色体５０では、遺伝子５３が１番目であ
り、以降、遺伝子５４、遺伝子５５、遺伝子５６の順で
ある。
〔Ｓ２３〕検討対象配送車の積荷の検討を行う。この処
理の詳細は、図１１において説明する。
〔Ｓ２４〕予め設定されている「ｉｍａｘ」（運行可能
な配送車の数）とｉを比較し、等しければ処理を終了す
る。ｉｍａｘに達していなければ、次のステップＳ２５
に進む。即ち、ｉｍａｘに達した時点で、全ての車両に
ついて検討されたことになる。
〔Ｓ２５〕ｉの値を１だけカウントアップし、ステップ
Ｓ２２に進む。これにより、ｉの値がｉｍａｘに達する
まで処理が繰り返される。The above is the procedure of the delivery vehicle allocation order examination unit 11. Next, the processing procedure of the delivery plan creation unit 12 will be described. FIG. 10 is a flowchart showing the procedure of the delivery plan creation unit. In addition, unless otherwise indicated in the following description of the flowchart, the delivery route planning unit 12a performs the process. [S21] "1" is set as the initial value of i. [S22] The i-th gene is selected as the delivery vehicle to be considered. In this case, the i-th is the order when the genes showing the order of allocating the delivery vehicles of the chromosomes are counted from the left side. On the chromosome 50 shown in FIG. 5, the gene 53 is the first, and then the gene 54, the gene 55, and the gene 56 in this order. [S23] The cargo of the delivery vehicle under consideration is examined. Details of this processing will be described with reference to FIG. [S24] The preset "imax" (the number of deliverable vehicles) is compared with i, and if they are equal, the process ends. If imax is not reached, the next step S25
Proceed to. That is, all the vehicles are considered when imax is reached. [S25] The value of i is incremented by 1, and the process proceeds to step S22. As a result, the process is repeated until the value of i reaches imax.
【００６０】図１１は検討対象の配送車の積荷の検討処
理（図１０のステップＳ２３）の詳細を示すフローチャ
ートである。
〔Ｓ３１〕ｊの初期値として「１」を設定する。
〔Ｓ３２〕検討対象配送先として、ｊ番目の配送先を選
択する。ここで、ｊ番目の配送先とは、このフローチャ
ートの処理が開始された時点で、いずれの配送車にも振
り分けられていない配送先に付けた番号である。FIG. 11 is a flow chart showing the details of the load examination process (step S23 in FIG. 10) of the delivery vehicle under consideration. [S31] "1" is set as the initial value of j. [S32] The j-th delivery destination is selected as the delivery destination under consideration. Here, the j-th delivery destination is a number assigned to a delivery destination that is not assigned to any delivery vehicle when the process of this flowchart is started.
【００６１】配送先への番号付けは、例えば次のように
行う。最初の配送車の積荷の検討を行う場合には、検討
開始配送先（図５の遺伝子５２で指定された配送先）を
基準として指定された検討方向（図５の遺伝子５１で指
定された検討方向）に検索し、検出された順に番号を付
ける。２台目以降の配送車の積荷の検討を行う場合に
は、極座標における原線３３から検討開始配送先への角
度θ（図４を参照）を若干増加させた位置を基準として
指定された検討方向に検索し、検出された順に番号を付
ける。The numbering of delivery destinations is performed as follows, for example. When the cargo of the first delivery vehicle is examined, the examination direction (the examination designated by the gene 51 of FIG. 5) designated based on the examination start delivery destination (the delivery destination designated by the gene 52 of FIG. 5) Direction) and number in the order of detection. When considering the cargo of the second and subsequent delivery vehicles, the study specified based on the position where the angle θ (see FIG. 4) from the original line 33 to the study start delivery destination in polar coordinates is slightly increased. Search in the direction and number in the order they are found.
【００６２】これにより、以前に検討した配送車に割り
当てることができなかった配送先は、次の配送車に対し
て、優先的に割当の検討が行われる。
〔Ｓ３３〕検討対象配送先の荷物を、検討対象配送車に
配送させることができるか否かを検討する。この処理の
詳細は、図１３において説明する。
〔Ｓ３４〕検討対象配送車にまだ荷物を積む余地がある
か否かを判断する。更に積載可能であれば次のステップ
Ｓ３５に進み、限界であればステップＳ３７に進む。
〔Ｓ３５〕予め設定されている「ｊｍａｘ」（このフロ
ーチャートの処理が開始された時点で、いずれの配送車
にも振り分けられていない配送先の総数）とｊを比較
し、等しければステップＳ３７に進む。ｊｍａｘに達し
ていなければ、次のステップＳ３６に進む。即ち、ｊｍ
ａｘに達した時点で、全ての配送先について検討された
ことになる。
〔Ｓ３６〕ｊの値を１だけインクリメントし、ステップ
Ｓ３２に進む。これにより、ｊの値がｊｍａｘに達する
か、あるいは積載量が限界に達するまで処理が繰り返さ
れる。
〔Ｓ３７〕正式な配送経路の改善を行い、処理を終了す
る。この処理の詳細は、図１６において説明する。As a result, the delivery destination that could not be assigned to the delivery vehicle previously examined is preferentially assigned to the next delivery vehicle. [S33] It is examined whether or not the parcel at the delivery destination under consideration can be delivered to the delivery vehicle under consideration. Details of this processing will be described with reference to FIG. [S34] It is determined whether or not there is still room for loading the delivery vehicle under consideration. If further stacking is possible, the process proceeds to the next step S35, and if there is a limit, the process proceeds to step S37. [S35] The preset "jmax" (the total number of delivery destinations not assigned to any delivery vehicle at the time when the process of this flowchart is started) is compared with j, and if they are equal, the process proceeds to step S37. . If it has not reached jmax, the process proceeds to the next step S36. That is, jm
When reaching ax, all delivery destinations have been considered. [S36] The value of j is incremented by 1, and the process proceeds to step S32. As a result, the process is repeated until the value of j reaches jmax or the loaded amount 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 load examination process of the delivery vehicle under consideration. (A) is the first delivery destination 32
It is a figure which shows the examination condition of a. In this example, the delivery destination 32
The delivery center 31 judges that the package a can be loaded.
And a delivery route between the delivery destination 32a and the delivery destination 32a is determined.
【００６４】（Ｂ）は２つめの配送先の検討状況を示す
図である。この例では、配送先検討方向は「＋」の方向
であり、配送先３２ｂが検討対象配送先となる。この配
送先３２ｂにも配送できると判断し、その経路を確定す
る。この際、配送先３２ａに向かう途中で配送先３２ｂ
に寄るべきか、配送先３２ａからの帰り路に寄るべきか
を判断し、最適な方を選ぶ。この例では、配送先３２ａ
に向かう途中で配送先３２ｂに寄る方を選ぶ場合を示し
ている。(B) is a diagram showing the examination status of the second delivery destination. In this example, the delivery destination examination direction is the "+" direction, and the delivery destination 32b is the examination destination delivery destination. It is determined that the delivery can be made to the delivery destination 32b, and the route is determined. At this time, on the way to the delivery destination 32a, the delivery destination 32b
It is determined whether to approach the customer or the return route from the delivery destination 32a, and the optimum one is selected. In this example, the delivery destination 32a
The case where the person closer to the delivery destination 32b is selected on the way to the destination is shown.
【００６５】（Ｃ）は３つめの配送先の検討状況を示す
図である。この例では、配送先３２ｃが検討対象配送先
となる。この配送先３２ｃにも配送できると判断し、そ
の経路を確定する。この際、配送センタ３１と配送先３
２ｂとの間の区間、配送先３２ｂと配送先３２ａとの間
の区間、及び配送先３２ａと配送センタ３１との間の区
間のどこで新たに加える配送先３２ｃに寄るべきかを比
較し、最良の経路に決定する。FIG. 9C is a diagram showing the examination status of the third delivery destination. In this example, the delivery destination 32c is the delivery destination under consideration. It is determined that the delivery can be made to the delivery destination 32c, and the route is determined. At this time, the delivery center 31 and the delivery destination 3
Interval between 2b, should stop at where newly added destination 32c between wards <br/> between the interval between the delivery destination 32b and destination 32a, and the delivery destination 32a and delivery center 31 To determine the best route.
【００６６】（Ｄ）は３つの配送先の検討結果を示す図
である。この例では、配送先３２ｂ、配送先３２ａ、配
送先３２ｃの順番が最良であると判断されている。図１
３は検討対象配送先への配送に関する検討の処理の詳細
を示すフローチャートである。
〔Ｓ４１〕重量制約を満足しているか否かを判断する。
重量制約を満足していればステップＳ４２に進み、満足
していなければ処理を終了する。
〔Ｓ４２〕体積制約を満足しているか否かを判断する。
体積制約を満足していればステップＳ４３に進み、満足
していなければ処理を終了する。
〔Ｓ４３〕寸法制約を満足しているか否かを判断する。
寸法制約を満足していればステップＳ４４に進み、満足
していなければ処理を終了する。
〔Ｓ４４〕侵入制約を満足しているか否かを判断する。
侵入制約を満足していればステップＳ４５に進み、満足
していなければ処理を終了する。
〔Ｓ４５〕車種制約を満足しているか否かを判断する。
車種制約を満足していればステップＳ４６に進み、満足
していなければ処理を終了する。
〔Ｓ４６〕最短時間の経路を探索する。結果として、仮
配送経路が作成される。この処理の詳細は、図１４にお
いて説明する。
〔Ｓ４７〕時間制約を満足しているか否かを判断する。
時間制約を満足していればステップＳ４８に進み、満足
していなければ処理を終了する。
〔Ｓ４８〕走行距離制約を満足しているか否かを判断す
る。走行距離制約を満足していればステップＳ４９に進
み、満足していなければ処理を終了する。
〔Ｓ４９〕ステップＳ４６で作成された仮配送経路を、
正式な配送経路として、処理を終了する。(D) is a diagram showing the examination results 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. Figure 1
3 is a flow chart showing the details of the processing of the examination regarding the delivery to the examination destination. [S41] It is determined whether or not the weight constraint is satisfied.
If the weight constraint is satisfied, the process proceeds to step S42, and if not satisfied, 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 satisfied, the process ends. [S43] It is determined whether or not the size constraint is satisfied.
If the size constraint is satisfied, the process proceeds to step S44, and if not satisfied, the process ends. [S44] It is determined whether the intrusion constraint is satisfied.
If the intrusion restriction is satisfied, the process proceeds to step S45, and if not satisfied, the process ends. [S45] It is determined whether or not the vehicle type constraint is satisfied.
If the vehicle type constraint is satisfied, the process proceeds to step S46, and if not, the process ends. [S46] The shortest time 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 satisfied, the process ends. [S48] It is determined whether or not 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 flow chart showing details of the shortest path search processing. [S51] A delivery cost is calculated for each delivery route candidate having a different insertion location of the examination delivery destination on the route. Here, the delivery cost is a function value that takes into account at least one of delivery time, traveling time, traveling distance, and fuel cost. A newly assigned delivery destination is inserted at a position where this delivery cost is minimized, and a temporary delivery route is generated. [S52] The best temporary delivery route is selected.
【００６８】図１５は、図１４のステップＳ５１におけ
る処理内容を説明する図である。この例では、配送セン
タ３１→配送先３２ｄ→配送先３２ｅ→配送先３２ｆ→
配送センタ３１の間の配送順序が確定している状態で、
さらに配送先３２ｇを追加する場合である。この場合、
配送先３２ｇを、どの間に挿入すれば配送コストが安く
なるかを計算する。この例では、４通りの計算が必要で
ある。そして、配送コストが最も安い位置に配送先３２
ｇを挿入し、配送先３２ｇを加えた仮配送経路を生成す
る。FIG. 15 is a diagram for explaining the processing contents in step S51 of FIG. In this example, the delivery center 31 → delivery destination 32d → delivery destination 32e → delivery destination 32f →
With the delivery order between delivery centers 31 confirmed,
This is a case where a delivery destination of 32 g is further added. in this case,
The place where the delivery destination 32g is inserted to calculate the delivery cost is calculated. In this example, four types of calculations are required. The delivery destination 32 is located at the position with the lowest delivery cost.
g is inserted, and a temporary delivery route including the delivery destination 32 g is generated.
【００６９】図１６は、図１１のステップＳ３７におけ
る処理内容を説明する図である。この例では、配送セン
タ３１→配送先３２ｊ→配送先３２ｋ→配送先３２ｍ→
配送先３２ｎ→配送センタ３１の仮配送経路が作られて
いる。図では、配送先の上の数字は、配送順を示してい
る。この状態から、先ず、配送先３２ｊを他の位置に移
動した場合に、制約条件を守る範囲で、配送コストが減
少するか否かを判断する。そして、配送コストが最も向
上する位置に、配送先３２ｊを移動する。FIG. 16 is a diagram for explaining the processing contents in step S37 of FIG. In this example, the delivery center 31 → delivery destination 32j → delivery destination 32k → delivery destination 32m →
A temporary delivery route is created from the delivery destination 32n to the delivery center 31. In the figure, the numbers above the delivery destinations indicate the order of delivery. 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 the range where the constraint condition is observed. Then, the delivery destination 32j is moved to the position where the delivery cost is most improved.
【００７０】もし、配送先３２ｊが他の場所、例えば、
配送先３２ｍと配送先３２ｎとの間に移動すると、配送
先３２ｋと配送先３２ｍが前（図中、左側）にずれる。
このように、検討した配送先３２ｊが移動した場合に
は、もう一度、配送順が「１」である配送先（配送先３
２ｋが該当する）を他の場所に移動して、配送コストの
向上が図れるか否かを判断する。If the delivery destination 32j is another place, for example,
When moving between the delivery destination 32m and the delivery destination 32n, the delivery destination 32k and the delivery destination 32m are displaced to the front (the left side in the drawing).
In this way, when the examined delivery destination 32j moves, the delivery destination whose delivery order is "1" (delivery destination 3
2k is applicable) is moved to another place, and it is determined whether or not the delivery cost can be improved.
【００７１】検討した配送先が移動しなかった場合に
は、次の配送順の配送先について検討する。このように
して、４番目の配送先まで検討する。これにより、最善
の仮配送経路を選択することができる。以上のような移
動による改善を更に何回か行う（予め与えられた回数に
従う）。When the examined delivery destination does not move, the delivery destination in the next delivery order is examined. In this way, the fourth delivery destination is considered. This makes it possible to select the best temporary delivery route. The above-mentioned movement improvement is performed several times (according to the number of times given in advance).
【００７２】この段階で、上記の移動によって配送時間
にゆとりが生じ、しかも元々積載容量にゆとりがある場
合は、さらに配送先を追加するという考え方を導入する
ことも可能である。At this stage, it is possible to introduce the concept of further adding a delivery destination when the above-mentioned movement causes a margin of delivery time and originally there is a margin of loading capacity.
【００７３】以上のように、遺伝的アルゴリズムにより
解の探索方針を定め、ＯＲ的手法によって具体的な配送
計画案を作成するようにしたため、高速に、且つ良好な
許容解を得ることができる。このようにして得られた配
送計画は、人間が同程度の時間で考えて作成したものよ
りも、格段に良い結果となる場合が多い。場合によって
は、例えば配送車数を３割以上減らすことができる。ま
た、上記に示したような配送計画であれば、通常のワー
クステーションを用いても極めて速く、例えば数秒で解
くことができる場合が少なくない。As described above, since the solution search policy is determined by the genetic algorithm and the concrete delivery plan is created by the OR-like method, it is possible to quickly obtain a good acceptable solution. The delivery plan obtained in this way often yields significantly better results than those created by human beings 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, if the delivery plan as shown above is used, it can be solved very quickly even in the case of using a normal workstation, for example, in a few seconds.
【００７４】また、従来の配送計画システムでは、複数
の制約条件があるような問題を解くことが非常に難しか
った。ところが、本発明の配送計画システムによれば、
様々な制約条件を設定することが可能である。しかも、
従来は制約条件として時間的制約を加えるとアルゴリズ
ムが非常に複雑になり、解くことが難しくなることが多
かったが、本発明に係る配送計画システムでは、時間的
制約が付加されても、十分高速に処理できる。時間的制
約と配送車の積載制約との双方を指定することも可能で
ある。Further, 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,
It is possible to set various constraint conditions. Moreover,
Conventionally, adding a time constraint as a constraint condition often makes the algorithm very complicated and difficult to solve, but the delivery planning system according to the present invention is sufficiently fast even if a time constraint is added. Can be processed. It is also possible to specify both the time constraint and the loading constraint of the delivery vehicle.
【００７５】このように、複数の制約条件があっても高
速に解くことができるのは、大局的な探索を遺伝的アル
ゴリズムで行い、詳細な計算をＯＲ的手法に委ねている
ためである。即ち、本発明のＯＲ的手法では、検討対象
の配送車を１台ずつ選択するとともに、１台の配送車へ
の配送先割当において検討対照の配送先も１箇所づつ選
択し、その都度、できるだけ最適な配送経路を求めてい
る。このように、ＯＲ的手法による個々の配送車におけ
る制約条件の適否の判断や配送順の決定は、解空間全体
を対象として遺伝的アルゴリズムの操作を行う場合と比
較して、少ない計算ですむ。そのため制約条件が多くて
も、非常に高速に計算することができる。なお、探索方
針を遺伝的アルゴリズムで最適化するため、解全体の中
の大局的な最適値または準最適値を求めることができ
る。Thus, the reason why a plurality of constraint conditions can be solved at high speed is that the global search is performed by a genetic algorithm and the detailed calculation is entrusted to an OR-like method. That is, in the OR method of the present invention, the delivery vehicles to be studied are selected one by one, and the delivery destinations to be examined are also selected one by one in the delivery destination allocation to one delivery vehicle, and each time, as much as possible, is selected. Seeking the best delivery route. As described above, the determination of suitability of the constraint condition or the determination of the delivery order in each delivery vehicle by the OR method requires less calculation than in the case of operating the genetic algorithm for the entire solution space. Therefore, even if there are many constraints, the calculation can be performed very quickly. Since the search policy is optimized by the genetic algorithm, it is possible to find a global optimum value or a suboptimal value in the entire solution.
【００７６】さらに、本発明では、新たな配送先を配送
経路に順次追加する方法で正式配送経路を生成した後、
更に各配送先の配送順の入替えを行っている。そのた
め、検討対象の配送先として選択された順番に影響され
ずに、最良の配送経路を求めることができる。Further, in the present invention, after the formal delivery route is generated by the method of sequentially adding new delivery destinations to the delivery route,
Furthermore, the delivery order of each delivery destination is changed. Therefore, the best delivery route can be obtained without being influenced by the order selected as the delivery destination to be considered.
【００７７】なお、上記の説明では、配送センタと配送
先の位置を極座標で認識してる場合を示したが、直交座
標で認識することもできる。この場合、配送先検討方向
の指定は、例えば、Ｘ座標の「−∞」から「＋∞」ま
で、というように指定する。In the above description, the positions of the delivery center and the delivery destination are recognized in polar coordinates, but they may be recognized in rectangular coordinates. In this case, the designation of the delivery destination examination direction is designated, for example, from “−∞” to “+ ∞” of the X coordinate.
【００７８】さらに、極座標の原点は配送センタに限る
必要はない。例えば、全配送先または全配送先に配送セ
ンタを含む集合の重心、直行座標を重ね合わせて考えた
場合の集合の横方向の中央且つ縦方向の中央点のいずれ
か、あるいはその他の点を極座標空間の原点とすること
もできる。これは、直交座標においても同じであり、直
交座標においても、配送センタ、全配送先または全配送
先に配送センタを含む集合の重心、集合の横方向の中央
且つ縦方向の中央点のいずれか、あるいはその他の点を
直交座標空間の原点とすることができる。Furthermore, the origin of polar coordinates need not be limited to the distribution center. For example, the center of gravity of a set including all delivery destinations or a delivery center at all delivery destinations, the center of the set in the horizontal direction and the center point in the vertical direction when the orthogonal coordinates are overlapped, or other points are polar coordinates. It can also be the origin of space. This is the same in the Cartesian coordinates, and also in the Cartesian coordinates, any of the distribution center, the center of gravity of all the delivery destinations, or the set including the delivery centers in all the delivery destinations, the horizontal center and the vertical center point of the set. , Or another point can be the origin of the Cartesian coordinate space.
【００７９】また、上記の例では、配送コストの低減を
目的として適応度関数を定義したが、例えば、配送の負
荷バランスの観点から適応度関数を定義することもでき
る。また、各々の場合に、配送車台数制約以外の制約条
件も合わせて考えた制約条件満足度の観点から、適応度
関数を定義するともできる。制約条件満足度には、例え
ば、配送指定時間の遵守がある。なお、配送コストの低
減と制約条件満足度とを組み合わせて、双方を適度に満
足するような適応度関数を定義してもよい。In the above example, the fitness function is defined for the purpose of reducing the delivery cost, but the fitness function may be defined from the viewpoint of delivery load balance, for example. Further, in each case, the fitness function can be defined from the viewpoint of the satisfaction degree of the constraint condition in which the constraint conditions other than the constraint of the number of delivery vehicles are also considered. The constraint satisfaction includes, for example, compliance with a designated delivery time. It is also possible to combine the reduction of the delivery cost and the satisfaction degree of the constraint condition to define the fitness function that satisfies both of them appropriately.
【００８０】また、配送計画作成部で、ＯＲ的手法によ
り各配送車への配送先の割当を行う際には、配送車の配
送先での滞在時間を考慮することができる。滞在時間を
考慮することにより、現実に配送を行った場合との誤差
を減らすことができる。When the delivery plan creation unit assigns the delivery destination to each delivery vehicle by the OR-like method, the staying time of the delivery vehicle at the delivery destination can be taken into consideration. By considering the stay time, it is possible to reduce the error from the actual delivery.
【００８１】また、配送計画作成部で、ＯＲ的手法によ
り配送経路を求める際に、巡回時間を最短にする経路を
求めているが、配送センタ帰着時刻、走行時間、燃料費
等を考慮の対象とすることもできる。また、それらの要
件を組み合わせた関数を用いても良い。Further, in the delivery plan creating section, when obtaining the delivery route by the OR method, the route which minimizes the traveling time is obtained, but the delivery center return time, the traveling time, the fuel cost, etc. are taken into consideration. Can also be Moreover, you may use the function which combined those requirements.
【００８２】[0082]
【発明の効果】以上説明したように本発明に係る数理計
画計算装置は、遺伝的アルゴリズムを用いて解の探索方
針を指定する個体を生成し、解の探索方針を最適化する
ようにしたため、遺伝的アルゴリズムによる解空間の中
の大局的な探索と同時に、詳細な解候補の探索を高速に
行うことができる。As described above, the mathematical program calculation apparatus according to the present invention generates an individual designating a solution search policy by using a genetic algorithm and optimizes the solution search policy. It is possible to perform a global search in a solution space using a genetic algorithm and a detailed solution candidate search at high speed.
【００８３】また、本発明に係る配送計画システムは、
遺伝的アルゴリズムを用いて解探索方針を指定する個体
を生成し、解探索方針を最適化し、その探索方針に従っ
て配送計画案が作成されるため、遺伝的アルゴリズムに
よる解空間の中の大局的な探索と同時に、詳細な配送計
画案の作成をＯＲ的な手法等を用いて高速に行うことが
できる。The delivery planning system according to the present invention is
A genetic algorithm is used to generate individuals that specify a solution search policy, the solution search policy is optimized, and a delivery plan is created according to the search policy. Therefore, a global search in the solution space is performed using the genetic algorithm. At the same time, a detailed delivery plan can be created at high speed using an OR-like method.
【００８４】また、本発明に係る数理計画プログラムを
記録した媒体は、記録された数理計画プログラムをコン
ピュータで実行することにより、遺伝的アルゴリズムに
よる解空間の中の大局的な探索と同時に、詳細な解候補
の探索を、コンピュータで高速に行うことができる。Further, the medium on which the mathematical programming program according to the present invention is recorded, by executing the recorded mathematical programming program on a computer, simultaneously with the global search in the solution space by the genetic algorithm, detailed The search for a solution candidate can be performed at high speed by a computer.
【００８５】また、本発明に係る配送計画プログラムを
記録した媒体は、記録された配送計画プログラムをコン
ピュータで実行することにより、遺伝的アルゴリズムに
よる解空間の中の大局的な探索と同時に、詳細な配送計
画案の作成を、コンピュータで高速に行うことができ
る。Further, the medium recording the delivery plan program according to the present invention executes the recorded delivery plan program by a computer, so that a detailed search can be performed at the same time as a global search in the solution space by the genetic algorithm. Computers can create a delivery plan at high speed.
【図１】本発明の数理計画計算装置の原理構成図であ
る。FIG. 1 is a principle configuration diagram of a mathematical planning calculation apparatus of the present invention.
【図２】配送システム全体の概略構成を示すブロック図
である。FIG. 2 is a block diagram showing a schematic configuration of an entire delivery system.
【図３】配送計画シミュレータの内部構成を示すブロッ
ク図である。FIG. 3 is a block diagram showing an internal configuration of a delivery plan simulator.
【図４】配送問題の配送先と配送センタとを示す図であ
る。FIG. 4 is a diagram showing a delivery destination and a delivery center of a delivery problem.
【図５】染色体の構成を示す図である。FIG. 5 is a diagram showing the constitution of chromosomes.
【図６】配送車割当順序検討部の処置手順を示すフロー
チャートである。FIG. 6 is a flowchart showing a procedure of a delivery vehicle allocation order examination unit.
【図７】選択処理の手順を示すフローチャートである。FIG. 7 is a flowchart showing a procedure of selection processing.
【図８】図７のステップＳ１１において配送車割当順序
検討部が配送計画作成部に与える個体及びその染色体
と、配送計画作成部から受け取る配送計画案との組の例
を示す図である。8 is a diagram showing an example of a set of an individual and a chromosome thereof given to the delivery plan creation unit by the delivery vehicle allocation order examination unit in step S11 of FIG. 7, and a delivery plan proposal received from the delivery plan creation unit.
【図９】配送計画案の内容を示す図である。FIG. 9 is a diagram showing the contents of a delivery plan.
【図１０】配送計画作成部の処置手順を示すフローチャ
ートである。FIG. 10 is a flowchart showing a procedure of a delivery plan creation unit.
【図１１】検討対象の配送車の積荷の検討処理の詳細を
示すフローチャートである。FIG. 11 is a flowchart showing the details of the load examination process for the delivery vehicle under consideration.
【図１２】検討対象配送車の積荷の検討処理の進行状況
を示す図である。（Ａ）は最初の配送先３２ａの検討状
況を示す図であり、（Ｂ）は２つめの配送先の検討状況
を示す図であり、（Ｃ）は３つめの配送先の検討状況を
示す図であり、（Ｄ）は３つの配送先の検討結果を示す
図である。FIG. 12 is a diagram showing a progress status of a load examination process of a delivery vehicle to be examined. (A) is a figure which shows the examination situation of the 1st delivery destination 32a, (B) is a figure which shows the examination situation of the 2nd delivery destination, (C) shows the examination situation of the 3rd delivery destination. It is a figure and (D) is a figure showing the examination result of three delivery destinations.
【図１３】検討対象配送先への配送に関する検討の処理
の詳細を示すフローチャートである。FIG. 13 is a flowchart showing the details of the processing of the study regarding delivery to the delivery destination under study.
【図１４】最短経路探索の処理の詳細を示すフローチャ
ートである。FIG. 14 is a flowchart showing details of the process of shortest path search.
【図１５】図１４のステップＳ５１における処理内容を
説明する図である。FIG. 15 is a diagram illustrating the processing content in step S51 of FIG.
【図１６】図１１のステップＳ３７における処理内容を
説明する図である。16 is a diagram for explaining the processing content in step S37 of FIG.
【符号の説明】 １ 解探索方針最適化手段 ２ 解探索手段 ３ 個体群 ３ａ〜３ｃ 個体 ４ 解候補群 ４ａ〜４ｃ 解候補 １０ 配送計画シミュレータ １１ 配送車割当順序検討部 １２ 配送計画作成部[Explanation of symbols] 1 Solution search policy optimization means 2 Solution search means 3 population 3a to 3c individuals 4 Solution candidate group 4a to 4c solution candidates 10 Delivery planning simulator 11 Delivery Vehicle Allocation Order Examination Department 12 Delivery Planning Department
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.7 識別記号 ＦＩ Ｇ０６Ｆ 17/60 １６２ Ｇ０６Ｆ 17/60 １６２Ａ 19/00 １２０ 19/00 １２０ (72)発明者 高田 和実 東京都千代田区丸の内一丁目６番１号 株式会社富士通システム総研内 (56)参考文献 特開 平６−273181（ＪＰ，Ａ) 特開 平９−160967（ＪＰ，Ａ) 特開 平７−230495（ＪＰ，Ａ) 吉原郁夫・他，「ＧＡによるヒューリ スティックスの適応的混合戦略」，情報 処理学会第51回全国大会講演論文集，日 本，社団法人情報処理学会，1995年 ９ 月22日，第２分冊，ｐｐ．49−50 吉原郁夫・他，「遺伝的アルゴリズム によるトラック配車システム」，情報処 理学会第50回全国大会講演論文集，日 本，社団法人情報処理学会，1995年 ３ 月17日，第２分冊，ｐｐ．265−266 (58)調査した分野(Int.Cl.7，ＤＢ名) G06N 1/00 - 7/08 G06F 17/60 G06F 19/00 B65G 61/00 ＪＳＴファイル（ＪＯＩＳ) ＣＳＤＢ（日本国特許庁)─────────────────────────────────────────────────── ─── Continuation of front page (51) Int.Cl. 7 Identification code FI G06F 17/60 162 G06F 17/60 162A 19/00 120 19/00 120 (72) Inventor Kazumi Takada Marunouchi, Chiyoda-ku, Tokyo (6) References JP-A-6-273181 (JP, A) JP-A-9-160967 (JP, A) JP-A-7-230495 (JP, A) Yoshihara Yoshihara Ikuo et al., “Adaptive Mixing Strategy of Heuristics by GA”, Proc. Of the 51st National Convention of Information Processing Society of Japan, Japan, Information Processing Society of Japan, September 22, 1995, 2nd volume, pp ． 49-50 Ikuo Yoshihara et al., “Truck dispatch system using genetic algorithm”, Proc. Of the 50th National Conference of Information Processing Society of Japan, Japan, Information Processing Society of Japan, March 17, 1995, 2nd volume , Pp. 265-266 (58) Fields investigated (Int.Cl. 7 , DB name) G06N 1/00-7/08 G06F 17/60 G06F 19/00 B65G 61/00 JST file (JOIS) CSDB (Japan Patent Office )
Claims (26)
テムにおいて、 配送先を配送車に割り当てるために満たすべき条件を示
す制約条件、適応度関数、および配送先の位置情報を入
力する入力手段と、 検討対象の配送車への割り当ての適否を最初に検討する
検討開始配送先、及び検討対象の配送車への割り当ての
適否を順次検討する際の配送先の検討方向が、解探索方
針を示す染色体として含まれた個体を、遺伝的アルゴリ
ズムを用いて生成し、解探索方針を最適化する解探索方
針最適化手段と、 配送先の前記位置情報に基づいて、各配送先を、前記個
体の染色体で示された前記検討開始配送先から前記検討
方向に向かった順に検討対象の配送先として選択し、選
択された前記配送先から順番に前記制約条件に従って検
討対象の配送車への割り当ての適否を検討し、配送計画
案を探索する解探索手段と、 前記解探索手段で探索された前記配送計画案を前記適応
度関数に基づいて評価し、評価が最も高い前記配送計画
案を解として出力する出力手段と、 を有することを特徴とする配送計画システム。 1. A delivery plan system for finding a solution to a delivery plan problem.
System, shows the conditions that must be met in order to assign the delivery destination to the delivery vehicle.
Constraints, fitness function, and location information of the delivery destination.
First consider the input means to be applied and the suitability of allocation to the delivery vehicle under consideration
Study start delivery destination and assignment to the delivery vehicle under consideration
When the suitability is examined sequentially, the direction of consideration of the delivery destination is the solution search method.
An individual included as a chromosome showing a needle is called a genetic algorithm.
Method to optimize the solution search policy
Based on the needle optimization means and the position information of the delivery destination,
Starting the examination indicated by the chromosome of the body
Select as a delivery destination to be considered in the order of direction, and select
In order from the selected delivery destination, the inspection is performed according to the constraint conditions.
Consider the suitability of allocation to the delivery vehicle to be discussed and plan delivery
A solution search means for searching a plan, and the delivery plan plan searched by the solution search means for the adaptation
The shipping plan evaluated based on the degree function and the highest evaluation
An output means for outputting the plan as a solution, and a delivery planning system.
前記各個体で示される探索方針に従って前記解探索手段
で探索された前記配送計画案の適応度値を前記適応度関
数に基づいて求め、前記各個体の前記適応度値に基づい
て、遺伝的アルゴリズムによる次世代を生成するための
親として選択される確率を決定することを特徴とする請
求項１記載の配送計画システム。 2. The solution search policy optimizing means is generated by
The solution search means according to the search policy indicated by each individual
The fitness value of the delivery plan searched in
Based on the fitness value of each individual
To generate the next generation by genetic algorithm
Contracts characterized by determining the probability of being selected as a parent
The delivery planning system according to claim 1.
索方針として配送車の検討順序を含み、 前記解探索手段は、各配送車を、前記配送車の検討順序
に従って検討対象の配送車として選択し、選択された前
記配送車から順番に、前記検討対象の配送先の割り当て
の適否を検討する、 ことを特徴とする請求項１記載の配送計画システム。 3. The solution search policy optimizing means is configured to perform the solution search.
The search policy includes the order of consideration of delivery vehicles, and the solution searching means determines each delivery vehicle as the order of consideration of the delivery vehicles.
Select as delivery vehicle to be considered according to
Allocation of the delivery destinations to be examined in order from the delivery vehicle
The delivery planning system according to claim 1 , wherein the suitability of the item is examined .
の配送先の割り当てを行う際には、既に他の配送車に割
り当てられた配送先を除いた全ての配送先を、検討対象
とする、 ことを特徴とする請求項３記載の配送計画システム。 4. The solution searching means is for delivering vehicles under consideration.
When assigning the delivery destination of the
Examine all delivery destinations except assigned delivery destinations
Delivery planning system according to claim 3, wherein that, characterized in that.
の配送経路を確定後、次の配送車を選択することを特徴
とする請求項１記載の配送計画システム。 5. The solution search means is the selected delivery vehicle.
After selecting the delivery route of, the next delivery vehicle is selected
The delivery planning system according to claim 1.
が入力されているとき、全ての前記制約条件を満たして
いる場合にのみ、検討対象の前記配送先を検討対象の前
記配送車へ割り当てることを特徴とする請求項１記載の
配送計画システム。 6. The solution searching means comprises a plurality of the constraint conditions.
When is input, all the above constraint conditions are satisfied.
If the delivery destination under consideration is
The delivery vehicle is assigned to the delivery vehicle according to claim 1.
Delivery planning system.
り当てる毎に、その時点で割り当てられている前記配送
先への前記配送車の巡回順序を決定することを特徴とす
る請求項１記載の配送計画システム。 7. The solution searching means assigns a delivery destination to a delivery vehicle.
Each time you apply, the delivery assigned at that time
Characterized by determining the order of patrol of the delivery vehicle to the destination
The delivery planning system according to claim 1.
に際し、時間的な制約条件または空間的な制約条件を満
たす範囲で、所定の経路評価が最適になるような巡回順
序を決定する、 ことを特徴とする請求項７記載の配送計画システム。 8. The solution search means determines the cyclic order.
Meet time or space constraints.
The patrol order that optimizes the predetermined route evaluation within the range
The delivery planning system according to claim 7 , wherein the order is determined .
新たに割り当てる配送先の追加位置を決める際には、既
に割り当てられている配送先の間、あるいは前後の全て
の位置を検討し、所定の経路評価が最適になるような位
置に決定する、 ことを特徴とする請求項７記載の配送計画システム。 9. The solution search means is provided for a delivery vehicle under consideration.
When deciding the additional position of the new delivery destination,
Between or before and after the delivery address assigned to
The position of the
Delivery planning system according to claim 7, wherein determining the location, characterized in that.
り当てる配送先を、既に割り当てられている配送先の
間、あるいは前後に追加するということを繰り返し、前
記配送車の配送経路を決定した後、前記配送車の配送経
路上で、配送先の組み換えを検討し、所定の経路評価が
最適になるような巡回経路の決定を行う、 ことを特徴とする請求項７記載の配送計画システム。 10. The solution search means is newly assigned to a delivery vehicle.
Assign the assigned shipping destination to the one already assigned.
Repeat adding in between or before and after
After determining the delivery route of the delivery vehicle,
Consider the recombination of delivery destinations on the street and evaluate the prescribed route.
The delivery planning system according to claim 7, wherein the optimal tour route is determined .
を検討する際に、各々の配送先への配送の順番を、配送
センタと他の配送先との中で最初に訪れることになって
いる配送先との間、または隣接する他の配送先同士の
間、または他の配送先の中で最後に訪れることになって
いる他の配送先と配送センタとの間に変える場所をそれ
ぞれ考え、それらの中に制約条件を満たすものがない場
合は、前記配送の順番の変更は行わず、それらの中に制
約条件を満たすものがある場合は、それらの中で、最も
経路評価が高くなるような場合を選択する、 ことを特徴とする請求項７記載の配送計画システム。 11. The solution searching means is a recombination of delivery destinations.
When considering the delivery order of delivery to each destination
To be the first to visit between the center and other destinations
Existing delivery destinations, or between other delivery destinations
To be the last to visit during or among other shipping destinations
It's a place to turn between other shipping destinations and distribution centers
Think of each, and if none of them meet the constraint conditions
If the delivery order is
If there are any that meet the conditions, then most of them
The delivery planning system according to claim 7 , wherein a case where the route evaluation is high is selected .
間、走行距離、及び燃料費の中の、少なくとも１つの要
件を考慮して経路評価を行う、 ことを特徴とする請求項７記載の配送計画システム。 12. The solution search means is for delivery time and traveling time.
Between at least one of
The delivery planning system according to claim 7 , wherein the route is evaluated in consideration of the number of cases .
先との位置を、極座標空間上の座標で管理している、 ことを特徴とする請求項１記載の配送計画システム。Wherein said solution search means, delivery center and the positions of the delivery destination, delivery planning system according to claim 1, wherein managed by coordinates on the polar coordinate space, characterized in that.
極座標空間の原点とする、 ことを特徴とする請求項１３記載の配送計画システム。14. The delivery planning system according to claim 13, wherein the solution searching means uses a delivery center as an origin of the polar coordinate space.
配送先に配送センタを含む集合の重心、集合の横方向の
中央且つ縦方向の中央点のいずれかを、前記極座標空間
の原点とする、 ことを特徴とする請求項１３記載の配送計画システム。15. The solution searching means defines, as an origin of the polar coordinate space, any one of a center of gravity of a set including all delivery destinations or a set of delivery centers in all delivery destinations, and a center of the set in a horizontal direction and a vertical direction. The delivery planning system according to claim 13, wherein:
先との位置を、直交座標空間上の座標で管理している、 ことを特徴とする請求項１記載の配送計画システム。16. The solution search means, delivery planning system according to claim 1, wherein the positions of the delivery center and destination, are managed by coordinates on the orthogonal coordinate space, characterized in that.
直交座標空間の原点とする、 ことを特徴とする請求項１６記載の配送計画システム。17. The delivery planning system according to claim 16, wherein the solution searching means uses a delivery center as an origin of the orthogonal coordinate space.
配送先に配送センタを含む集合の重心、集合の横方向の
中央且つ縦方向の中央点のいずれかを、前記直交座標空
間の原点とする、 ことを特徴とする請求項１６記載の配送計画システム。18. The origin of the Cartesian coordinate space is defined by the solution searching means, wherein any one of a center of gravity of a set including all delivery destinations or a delivery center including all delivery destinations, and a center of the set in the horizontal direction and a vertical direction is set in the orthogonal coordinate space. The delivery planning system according to claim 16, wherein:
への配送先の割り当ての適否を判断する際には、前記制
約条件を満たす限り、検討対象の配送先を検討対象の配
送車へ割り当てる、 ことを特徴とする請求項１記載の配送計画システム。19. The solution search means, when determining the destination of allocation of compliance with the appropriate delivery vehicle under consideration, the system <br/> about satisfying as long, considering the considered destination The delivery planning system according to claim 1 , wherein the delivery planning system assigns the delivery vehicle to a target delivery vehicle.
間を考慮して、検討対象の配送車への割り当ての適否を
検討する、 ことを特徴とする請求項１記載の配送計画システム。 20. The solution search means is for staying at a delivery destination.
Considering the time interval, whether the allocation to the delivery vehicle under consideration is appropriate or not
The delivery planning system according to claim 1, wherein the delivery planning system is examined .
ステムにおいて、 配送先を配送車に割り当てるために満たすべき条件を示
す制約条件、および適応度関数を入力する入力手段と、 配送車の検討順序が解探索方針を示す染色体として含ま
れた個体を、遺伝的アルゴリズムを用いて生成し、前記
解探索方針を最適化する解探索方針最適化手段と、 前記個体の染色体で示された前記配送車の検討順序に従
って検討対象の配送車を選択し、選択された前記配送車
から順番に前記制約条件に従って検討対象の配送先の割
り当ての適否を検討し、配送計画案を探索する解探索手
段と、 前記解探索手段で探索された前記配送計画案を前記適応
度関数に基づいて評価し、評価が最も高い前記配送計画
案を解として出力する出力手段と、 を有することを特徴とする配送計画システム。 21. A delivery planning system for finding a solution to a delivery planning problem.
The system shows the conditions that must be met in order to assign the delivery destination to the delivery vehicle.
Constraint conditions and input means for inputting the fitness function, and the order in which delivery vehicles are considered are included as chromosomes that indicate the solution search policy.
Generated individual using a genetic algorithm,
According to the solution search policy optimization means for optimizing the solution search policy, and the examination order of the delivery vehicle indicated by the chromosome of the individual.
Select the delivery vehicle to be considered, and select the delivery vehicle
The order of delivery destinations to be considered is
Solution searcher who examines suitability of allocation and searches for delivery plan
And applying the delivery plan found by the solution searching means
The shipping plan evaluated based on the degree function and the highest evaluation
An output means for outputting the plan as a solution, and a delivery planning system.
た前記各個体で示される探索方針に従って前記解探索手
段で探索された前記配送計画案の適応度値を前記適応度
関数に 基づいて求め、前記各個体の前記適応度値に基づ
いて、遺伝的アルゴリズムによる次世代を生成するため
の親として選択される確率を決定することを特徴とする
請求項２１記載の配送計画システム。 22. The solution search policy optimization means generates
The solution searcher according to the search policy indicated by each individual
The fitness value of the delivery plan found in the
Determined based on a function, based the on the fitness values of each individual
And to generate the next generation by genetic algorithm
Characterized by determining the probability of being selected as the parent of
The delivery planning system according to claim 21.
への配送先の割り当てを行う際には、既に他の配送車に
割り当てられた配送先を除いた全ての配送先を、検討対
象とする、 ことを特徴とする請求項２１記載の配送計画システム。 23. The solution search means is a delivery vehicle under consideration.
When assigning delivery destinations to
Examine all shipping destinations except assigned ones
The delivery planning system according to claim 21, wherein the delivery planning system is an elephant .
車の配送経路を確定後、次の配送車を選択することを特
徴とする請求項２１記載の配送計画システム。 24. The solution search means is configured to select the delivery.
After confirming the delivery route of the vehicle, select the next delivery vehicle.
22. The delivery planning system according to claim 21, wherein
ログラムを記録したコンピュータ読み取り可能な記録媒
体において、 前記コンピュータを、 配送先を配送車に割り当てるために満たすべき条件を示
す制約条件、適応度関数、および配送先の位置情報を入
力する入力手段、 検討対象の配送車への割り当ての適否を最初に検討する
検討開始配送先、及び検討対象の配送車への割り当ての
適否を順次検討する際の配送先の検討方向が、解探索方
針を示す染色体として含まれた個体を、遺伝的アルゴリ
ズムを用いて生成し、前記解探索方針を最適化する解探
索方針最適化手段、 配送先の前記位置情報に基づいて、各配送先を、前記個
体の染色体で示された前記検討開始配送先から前記検討
方向に向かった順に検討対象の配送先として選択し、選
択された前記配送先から順番に前記制約条件に従って検
討対象の配送車への割り当ての適否を検討し、配送計画
案を探索する解探索手段、 前記解探索手段で探索された前記配送計画案を前記適応
度関数に基づいて評価し、評価が最も高い前記配送計画
案を解として出力する出力手段、 として機能させることを特徴とする配送計画プログラム
を記録したコンピュータ読み取り可能な記録媒体。 25. A delivery planning process for finding a solution to a delivery planning problem.
Computer-readable recording medium for recording programs
In the body, the computer indicates the conditions that must be met in order to assign the delivery destination to the delivery vehicle.
Constraints, fitness function, and location information of the delivery destination.
First consider the input means to be applied and the suitability of allocation to the delivery vehicle under consideration
Study start delivery destination and assignment to the delivery vehicle under consideration
When the suitability is examined sequentially, the direction of consideration of the delivery destination is the solution search method.
An individual included as a chromosome showing a needle is called a genetic algorithm.
Solution search that optimizes the solution search policy by generating
Based on the search policy optimization means and the location information of the delivery destination,
Starting the examination indicated by the chromosome of the body
Select as a delivery destination to be considered in the order of direction, and select
In order from the selected delivery destination, the inspection is performed according to the constraint conditions.
Consider the suitability of allocation to the delivery vehicle to be discussed and plan delivery
Solution search means for searching a draft, the adapting the delivery plan which is searched by the solution search means
The shipping plan evaluated based on the degree function and the highest evaluation
A delivery plan program characterized by causing it to function as an output means for outputting a plan as a solution
A computer-readable recording medium in which is recorded.
ログラムを記録したコンピュータ読み取り可能な記録媒
体において、 前記コンピュータを、 配送先を配送車に割り当てるために満たすべき条件を示
す制約条件、および適応度関数を入力する入力手段、 配送車の検討順序が解探索方針を示す染色体として含ま
れた個体を、遺伝的アルゴリズムを用いて生成し、前記
解探索方針を最適化する解探索方針最適化手段、 前記個体の染色体で示された前記配送車の検討順序に従
って検討対象の配送車を選択し、選択された前記配送車
から順番に前記制約条件に従って検討対象の配送先の割
り当ての適否を検討し、配送計画案を探索する解探索手
段、 前記解探索手段で探索された前記配送計画案を前記適応
度関数に基づいて評価し、評価が最も高い前記配送計画
案を解として出力する出力手段、 として機能させることを有することを特徴とする配送計
画プログラムを記録したコンピュータ読み取り可能な記
録媒体。 26. A delivery planning process for finding a solution to a delivery planning problem.
Computer-readable recording medium for recording programs
In the body, the computer indicates the conditions that must be met in order to assign the delivery destination to the delivery vehicle.
Constraint conditions, input means for inputting fitness function, and order of consideration of delivery vehicles are included as chromosomes indicating the solution search policy.
Generated individual using a genetic algorithm,
A solution search policy optimizing means for optimizing a solution search policy, according to an examination order of the delivery vehicle indicated by the chromosome of the individual.
Select the delivery vehicle to be considered, and select the delivery vehicle
The order of delivery destinations to be considered is
Solution searcher who examines suitability of allocation and searches for delivery plan
And applying the delivery plan searched by the solution searching means to the solution.
The shipping plan evaluated based on the degree function and the highest evaluation
A delivery meter characterized by having a function as an output means for outputting the plan as a solution.
A computer-readable record that stores the image program
Recording medium.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP12052597A JP3535342B2 (en) | 1996-05-29 | 1997-05-12 | Delivery planning system and computer-readable recording medium recording delivery planning program |
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8-134701 | 1996-05-29 | ||
| JP13470196 | 1996-05-29 | ||
| JP12052597A JP3535342B2 (en) | 1996-05-29 | 1997-05-12 | Delivery planning system and computer-readable recording medium recording delivery planning program |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH1055349A JPH1055349A (en) | 1998-02-24 |
| JP3535342B2 true JP3535342B2 (en) | 2004-06-07 |
Family
ID=26458092
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP12052597A Expired - Lifetime JP3535342B2 (en) | 1996-05-29 | 1997-05-12 | Delivery planning system and computer-readable recording medium recording delivery planning program |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3535342B2 (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3161529B2 (en) | 1998-05-15 | 2001-04-25 | サントリー株式会社 | Vehicle dispatching equipment |
| JP3534392B2 (en) * | 1999-12-28 | 2004-06-07 | 日立ソフトウエアエンジニアリング株式会社 | Optimal delivery planning method and system |
| JP4502330B2 (en) * | 2005-09-20 | 2010-07-14 | 財団法人電力中央研究所 | Loop controller layout optimization method, layout optimization apparatus, and layout optimization program |
| JP4811806B2 (en) * | 2006-05-29 | 2011-11-09 | 独立行政法人海上技術安全研究所 | Ship allocation planning device, ship allocation planning method and program |
| JP4801132B2 (en) * | 2008-11-17 | 2011-10-26 | 日本たばこ産業株式会社 | Course creation system and course creation method |
| CN118103856A (en) * | 2021-11-16 | 2024-05-28 | 株式会社野村综合研究所 | Delivery plan support system, delivery plan support method, and computer program |
-
1997
- 1997-05-12 JP JP12052597A patent/JP3535342B2/en not_active Expired - Lifetime
Non-Patent Citations (2)
| Title |
|---|
| 吉原郁夫・他，「ＧＡによるヒューリスティックスの適応的混合戦略」，情報処理学会第５１回全国大会講演論文集，日本，社団法人情報処理学会，１９９５年 ９月２２日，第２分冊，ｐｐ．４９−５０ |
| 吉原郁夫・他，「遺伝的アルゴリズムによるトラック配車システム」，情報処理学会第５０回全国大会講演論文集，日本，社団法人情報処理学会，１９９５年 ３月１７日，第２分冊，ｐｐ．２６５−２６６ |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH1055349A (en) | 1998-02-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5897629A (en) | Apparatus for solving optimization problems and delivery planning system | |
| Bräysy et al. | Evolutionary algorithms for the vehicle routing problem with time windows | |
| Francis Gorman | An application of genetic and tabu searches to the freight railroad operating plan problem | |
| US7840319B2 (en) | Core area territory planning for optimizing driver familiarity and route flexibility | |
| Lee et al. | Vehicle capacity planning system: A case study on vehicle routing problem with time windows | |
| Kachitvichyanukul et al. | Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO | |
| Mokhtarinejad et al. | A novel learning based approach for a new integrated location-routing and scheduling problem within cross-docking considering direct shipment | |
| CN111309837A (en) | Intelligent storage map platform building and AGV path optimizing method | |
| Parragh et al. | A survey on pickup and delivery models part ii: Transportation between pickup and delivery locations | |
| CN116151499A (en) | Intelligent multi-mode intermodal route planning method based on improved simulated annealing algorithm | |
| Li et al. | A hybrid simulated annealing heuristic for multistage heterogeneous fleet scheduling with fleet sizing decisions | |
| Kamsopa et al. | Hybrid genetic algorithm for multi-period vehicle routing problem with mixed pickup and delivery with time window, heterogeneous fleet, duration time and rest area | |
| JP3535342B2 (en) | Delivery planning system and computer-readable recording medium recording delivery planning program | |
| CN113128839B (en) | High-end equipment distributed manufacturing and multi-mode transportation oriented cooperative scheduling method | |
| Ruan et al. | A double traveling salesman problem with three-dimensional loading constraints for bulky item delivery | |
| Rüther et al. | A grouping genetic algorithm for multi depot pickup and delivery problems with time windows and heterogeneous vehicle fleets | |
| Comert et al. | EFFECTIVE CLUSTER-FIRST ROUTE-SECOND APPROACHES USING METAHEURISTIC ALGORITHMS FOR THE CAPACITATED VEHICLE ROUTING PROBLEM. | |
| CN109598443B (en) | Mission planning method and machine-readable storage medium for vehicle in dynamic environment | |
| CN109636023B (en) | Task planning system of multiple vehicle platforms under negotiation mechanism | |
| JP2005084848A (en) | Optimization program and delivery planning program | |
| JPH07219920A (en) | Optimization problem solving method and apparatus | |
| CN118839887A (en) | Whole vehicle logistics scheduling optimization method | |
| CN116382099A (en) | A robot path scheduling planning method and system | |
| de Araujo Sabry et al. | Evolutionary algorithms for the traveling car renter with passengers | |
| Joubert | An integrated and intelligent metaheuristic for constrained vehicle routing |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20031215 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040309 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040311 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080319 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090319 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100319 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100319 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110319 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110319 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120319 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130319 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130319 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140319 Year of fee payment: 10 |
|
| EXPY | Cancellation because of completion of term |