JPH07219920A

JPH07219920A - 最適化問題解決処理方法および装置

Info

Publication number: JPH07219920A
Application number: JP903694A
Authority: JP
Inventors: Mamoru Kunimoto; 衛国本
Original assignee: Nippon Steel Corp
Current assignee: Nippon Steel Corp
Priority date: 1994-01-31
Filing date: 1994-01-31
Publication date: 1995-08-18

Abstract

(57)【要約】（修正有）【目的】最適化問題において短時間に最適解あるいは準
最適解を発見できるようにする。【構成】人工知能による方法などの決定論的な手法で解
の一部を発見するＡＩ処理部２１と、ＡＩ処理部２１で
発見された解を除くものを解空間として遺伝的アルゴリ
ズムで解を探索するＧＡ処理部２２とを設ける。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、最適化問題を解決する
ための最適化問題解決処理方法および装置に関し、特
に、遺伝的アルゴリズムを使用した最適化問題解決処理
方法および装置に関する。

【０００２】

【従来の技術】最適化問題は、一般に、１ないし複数の
変数とこれらの変数によって定義される目的関数（評価
関数）とが与えられ、所定の制約条件の下でこの目的関
数の値を最大あるいは最小とする変数の組を求める問題
である。最適化問題は、古典的な線形計画法を含むとと
もに、幅広く応用されており、例えば、ジェットエンジ
ンの設計、通信ネットワークの設計、ジョブスケジュー
リング、図形の配置などにも適用されている。最適化問
題の解法としては、目的関数が線形関数である場合を中
心として、古くより各種のものが開発されている。ま
た、変数の数が多いあるいは目的関数が複雑であるなど
の理由により解析的には解けないあるいは解を得るのに
時間がかかりすぎるなどの場合のために、数値算法、近
似算法も開発されている。

【０００３】ところで近年、遺伝的アルゴリズムという
解探索手法が開発されている。遺伝的アルゴリズムは、
確率的探索法の一手法であって、生物の進化過程（選択
淘汰、突然変異）をモデルとしたものである。図１(a)
は、遺伝的アルゴリズムの概要を説明する図、(b)は染
色体における配座例を示す図である。遺伝的アルゴリズ
ムを最適化問題に適用する場合、各変数がそれぞれ遺伝
子座に割り付けられた「染色体（遺伝子）２００」を考
える。そしてこのような染色体を複数本発生させて（ス
テップ２０１）、第１世代の個体群２０２とする。第１
世代に属する染色体は、乱数を用いて生成するのが一般
的であるが、予め定めた初期値を用いるようにしてもよ
い。第１世代の個体群２０２について、目的関数の値に
応じた適応度を各染色体２００ごとに算出し、適応度の
高い染色体を選択し、さらにこの選択された染色体に交
差（生物相同染色体間の交差に対応する）や突然変異
（一定の確率でランダムに遺伝子座にマッピングされた
変数の値を変化させる）といった操作を加え（ステップ
２０３）、第２世代の個体群２０４を生成する。この過
程で、適応度の小さい染色体（個体）は淘汰される。な
お、交差や突然変異で生成する新たな染色体の数は、淘
汰された染色体の数と同じになるようにし、全体として
の個体数が一定に維持されるようにするのが一般的であ
る。そして第２世代の個体群２０４に対しても、選択、
交差、突然変異、淘汰などからなる同様の進化プロセス
を施して第３世代の個体群を生成し、以下、進化プロセ
スを繰り返して次世代の個体群を順次生成することによ
り、第ｎ世代の個体群２０５が生成する。進化プロセス
において適応度の小さい個体が淘汰されているので、第
１世代の個体群２０２に比べ、第ｎ世代の個体群２０５
はより適応度の高い染色体のみから構成されていること
になる。また、進化の過程で突然変異が加えられている
ことにより、解空間の中をくまなく探索できることにな
り、大域的最適解に的確に到達することが可能となる。

【０００４】ここで、染色体の構成について説明する。
図１(b)は、トラックの配車計画の作成に遺伝的アルゴ
リズムを適用した場合の染色体２００の構成例を示すも
のである。ここでは、２５台のトラックを使用して２２
箇所の配送先（Ａ社〜Ｖ社）に荷物を配送する場合を考
える。トラックごとに規定積載量が定められ、配送先ご
とに荷物の量が定められ、各トラックはそれぞれ１日に
３往復できるものとする。なお、ある配送先への荷物の
量はトラック１回で運べる量であるとは限らず、このよ
うな場合には何台ものトラック（同一のトラックが複数
回往復してもよい）を用いて輸送するものとする。染色
体２００は、それぞれのトラックの各回の往復での行き
先を示すものであって、染色体２００上には７５（＝２
５×３）個の遺伝子座２１０が設けられている。また、
各遺伝子座２１０に付与された数字は配送先の番号を表
わし、番号０は待機を表わしている。すなわち、第ｍ番
目（１≦ｍ≦２５）のトラックの第ｎ回目（１≦ｎ≦
３）の往復での行き先は、３ｍ＋ｎ−３番目の遺伝子座
によって表わされる。図１(b)に例示した染色体２００
では、１番目のトラックは、１回目に８番の配送先（Ｈ
社）へ行き、２回目は待機、３回目に２２番の配送先
（Ｖ社）へ行くこととなり、２５番目のトラックは、１
回目、２回目とも１０番の配送先（Ｊ社）へ行き、３回
目は待機ということになる。

【０００５】このように設計された染色体を用い、遺伝
的アルゴリズムにより最適解（＝最適な配車計画）を求
めるためには、各遺伝子座２１０にランダムに配送先
（待機も含む）を設定して第１世代の個体群を形成し、
例えば、下記式で表わされるような評価関数ｆを用いて
選択を行なうようにすればよい。この評価関数ｆでは、
値が小さいほど優れているすなわち適応度が高くなって
いる。

【０００６】

【数１】もちろん、各配送先への荷物が全て配送されることが前
提（制約条件）なので、各トラックの規定積載量を考慮
して配送先ごとに実際に配送され得る荷物の量を計算
し、計算された荷物の量が配送先ごとに設定された荷物
の量より多いかどうかをチェックし、この条件を満たさ
ない染色体については、淘汰されるべきものとして、極
端に大きな値を評価関数ｆに与えるようにすればよい。

【０００７】遺伝的アルゴリズムを使用することによ
り、従来法では不可能であったあるいは著しく計算時間
を要した最適化問題を短時間で解くことが可能となった
ことの実例が、例えば、「遺伝的アルゴリズム」、北野
宏明編、産業図書、１９９３年(ISBN4-7828-5136-7)に
記載されている。また、遺伝的アルゴリズムは大域的探
索に強く、最適化問題の従来の解法（例えば、最急降下
法などを用いた方法やエキスパートシステムによる方
法、ヒューリスティックアルゴリズムによる方法）は局
所的探索に強いので、両者を組み合わせ、まず、遺伝的
アルゴリズムで大域的に解を探索し、その探索結果に基
づいて最適化問題の従来の解法によって解を探索し、短
時間のうちに最適解を得ようとする試みもある。

【０００８】

【発明が解決しようとする課題】最適化問題としては、
一方の極に、ジェットエンジンの設計などのように、現
在入手し得る最高の計算機を使用した上でかなりの時間
（例えば、日単位、週単位）をかけても最適解を見つけ
たい問題があり、他方の極に、日々の生産計画の立案や
ロボットの実時間制御などのように、それほどの計算機
パワーを使用せずに短時間に準最適解ないし実用解を見
つけたい問題とがある。ここで準最適解とは、厳密な意
味では最適解ではないが、最適解に近い解であって実用
上の意味のある解のことである。遺伝的アルゴリズム
は、これまで知られている最適化問題の解法のうち最も
高速のものの一つであるが、解空間が大きければそれな
りに計算時間を要し、特に、少ない計算機パワーで短時
間に準最適解を求めたいという要求を必ずしも満足する
ものではない。また、大域的探索に遺伝的アルゴリズム
を使用し、その上で局所的探索に他の最適化問題の解法
を用いる場合、局所的探索に時間がかかるので、短時間
で最適解あるいは準最適解を求めることは困難である。

【０００９】本発明の目的は、最適化問題において短時
間に最適解あるいは準最適解を発見できる最適化問題解
決処理方法および装置を提供することにある。

【００１０】

【課題を解決するための手段】本発明の最適化問題解決
処理方法は、決定論的な手法によって解の一部を発見す
る第１の過程と、前記第１の過程の実行後、前記第１の
過程で発見された解を除外した解空間を対象として遺伝
的アルゴリズムを適用し残りの解を発見する第２の過程
とを有する。

【００１１】本発明の最適化問題解決処理装置は、決定
論的な手法によって解の一部を発見する第１の処理手段
と、前記第１の処理手段で発見された解を除外した解空
間を対象として遺伝的アルゴリズムに基づく探索を行な
い残りの解を発見する第２の処理手段とを有する。

【００１２】

【作用】最適化問題を解くに当たり、まず決定論的な手
法を用いて解の一部を発見し、続いて、発見された解を
除いた解空間を対象として遺伝的アルゴリズムを適用し
残りの解を見つけるので、以下に述べる理由により、短
時間に解全体を発見することができる。

【００１３】一般に、最適化問題が対象とする解は、複
数の変数の集合として表わされる。したがって、最適化
問題の目標は、最適解あるいは準最適解における各変数
の値を求めることである。もし、変数の集合の一部につ
いて最適解あるいは準最適解を構成する場合の値が判れ
ば、その判った値を解の一部として固定することによ
り、残りの変数のみを対象とした最適化問題に帰着させ
ることができる。従来の技術でも述べたように、決定論
的な方法だけで最適解を見つけるのには、多大な時間を
要する。しかし、決定論的な方法によって解の一部を見
つけるのにも多大な時間がかかるというわけではない。
問題の性質にもよるが、決定論的な方法によって、解の
一部を極めて容易に見つけ出せることが多い。したがっ
て、まず決定論的な手法で解の一部を探索して固定し、
そののち遺伝的アルゴリズムによって残りの解を探索し
た場合には、決定論的な手法で発見された解が探索対象
から外されているので探索範囲が狭まり、遺伝的アルゴ
リズムに探索時間が大幅に減少する。決定論的な手法で
の探索は見つけやすい部分に限定されるので大した時間
を要せず、結局、解全体を発見するのに要する総時間が
短縮されることになる。

【００１４】本発明において、決定論的な手法には、最
適化問題の解決に従来から使用されていた方法、例え
ば、線形計画法やオペレーションリサーチ（ＯＲ）の
他、人工知能（ＡＩ）を用いた方法、エキスパートシス
テム、ニューラルネットワークによる方法などが含まれ
る。初期値に発生などには乱数を使用するが、その後は
決定論的に推移するような方法も、本発明でいう決定論
的な手法に含まれる。なお、遺伝的アルゴリズムと決定
論的な手法との相違は、遺伝的アルゴリズムでは、各世
代の個体群の形成に、確率的過程が本質的に関与してい
ることにある。

【００１５】本発明の最適化問題解決処理方法および装
置は、各種の最適化問題に適用することができる。小さ
な計算機パワーで短時間に準最適解を求める必要がある
最適化問題の解決に特に適している。このような最適化
問題としては、各種のスケジューリング、生産工程にお
ける最適条件の算出、実時間制御、ロボットの適応制御
などが挙げられ、とりわけリアルタイム性が要求される
スケジューリングなどに適している。リアルタイム性が
要求されるスケジューリングとしては、運輸産業におけ
るスケジューリング、具体的には日々の配車計画の作成
などがある。

【００１６】本発明の最適化問題解決処理方法では、制
約条件と目的関数が与えられれば自動的に解が得られる
が、解が得られる過程あるいは解そのものに人為的に介
入することも可能である。具体的には、決定論的な手法
で得られた解を操作者が判断して修正したり、遺伝的ア
ルゴリズムの各世代ごとに途中結果を操作者が判断して
修正し、修正されたものを解の一部として以後の世代で
の探索範囲から除外したりすることができる。

【００１７】本発明の最適化問題解決処理装置では、制
約条件と目的関数が与えられれば自動的に解が得られる
が、得られる解に対して操作者の判断結果などを反映さ
せたり、突発的な制約条件の変更に対応するために、決
定論的な手法で求められる解を修正するための第１の修
正手段や、遺伝的アルゴリズムによる解の探索過程に介
入して解の修正を行なうための第２の修正手段を設ける
ことができる。ここでいう解の修正とは、外部からの入
力に応じて解の一部を確定することであり、このように
確定された部分解は以後の解探索過程の解空間（探索空
間）からは除外されることになる。

【００１８】第１の処理手段で発見される解を外部から
の入力に応じて修正する第１の修正手段を設けた場合に
は、第２の処理手段での解空間は、第１の修正手段によ
る修正後の解を除外したものとなる。また、第２の修正
手段は、遺伝的アルゴリズムのでの解の探索過程、具体
的には各世代の個体群に介入して解の一部を決定する。
そして決定された部分解に応じて、以後の探索における
解空間が狭められる。遺伝的アルゴリズムによる探索過
程の進行中に解空間を狭める方法としては、具体的に
は、決定された部分解に対応する変数の遺伝子座を削除
することによって染色体を短くすることが挙げられる。

【００１９】

【実施例】次に本発明の実施例について図面を参照して
説明する。図２は、本発明の一実施例の最適化問題解決
処理装置の構成を示すブロック図、図３は本発明の最適
化問題解決処理方法に基づきこの装置を用いて最適化問
題を解決するときの手順を示すフローチャートである。
ここでは、トラックの配車計画の作成を例にあげて説明
する。

【００２０】まず、配車計画それ自体について説明す
る。この配車計画は、複数のトラックを用いて複数の配
送先に荷物を輸送するときに、どのトラックでどの配送
先にどれだけの荷物を運ぶかというものであって、各ト
ラックは、規定積載量や車種（通常のトラックなのか冷
蔵トラックなのかなど）、コストなどがそれぞれ異なっ
ており、また、各配送先への荷物の種類や量もそれぞれ
異なっている。さらに、配送先によっては、途中の道路
事情等により大型トラックでは配送できない場合もあ
る。このトラックの配車計画は、例えば翌日配送の荷物
の申込を正午に一応締切り、夕方には翌日の第１回目の
輸送のための荷積みを行なうというサイクルの中で立案
されるものであって、実質的に午後の２〜３時間程度し
か作成に時間を割くことができないというものである。
しかも、申込締切り後にも追加注文がなされることが多
く、この追加注文にもできるだけ対応しなければならな
いという制約がある。

【００２１】結局、配車計画の作成は、トラックの規定
積載量や車種、配送先への荷物の種類や量、さらには途
中の道路事情などを制約条件として、コストを最小にす
るような解を求めるという最適化問題に帰着する。この
場合、配車計画の作成には時間をかけることはできず、
また、追加注文などによる条件の変化に対して柔軟に対
応できることが望まれる。要求される解は、厳密に最適
解である必要はなく、それなりに優れた解（準最適解）
であればよい。すなわち、厳密な最適解に比べてコスト
が多少大きくても構わないが、短時間で解を得ることが
要求されるという最適化問題である。

【００２２】ところで、トラック２５台が各３往復して
２２箇所の配送先に配送するとして配車計画を作成する
と仮定すると、待機することも考慮して場合の数を計算
すると２３⁷⁵（≒１.３５×１０¹⁰²）通りとなる。ま
た、１台のトラックに複数の仕向先への荷物を積み、配
送基地に戻ることなく順繰りにこれらの配送先を回るこ
とを許容するとなると、場合の数はさらに大幅に増え
る。つまり、総当たりで最適解を求めるすなわち最適の
配車計画を作成することはほとんど不可能である。従来
は、勘に頼った方法により人手によって配車計画が作成
されており、作成に割ける時間が短いこともあって、作
成される配車計画はコストが最小あるいは最小に近いと
いうものからはほど遠いものである。

【００２３】次に、本実施例の最適化問題解決処理装置
について説明する。この最適化問題解決処理装置は、大
別すると、最適化問題を実際に解いて配車計画を作成す
る計画エンジン部１１と、最適化問題を解く際に必要と
なる各種データを保持するデータベース部１２と、操作
者とのインタフェース部となるマンマシンインタフェー
ス部１３と、受け付けた注文に応じてオーダデータを作
成するとともに得られた解に応じた処理を行なうホスト
コンピュータ１４とによって構成されている。ここでオ
ーダデータとは、どの配送先にどの荷物をどれだけ運ぶ
かを表わすデータであり、配車計画作成のための前提と
なるデータである。データベース部１２には、ホストコ
ンピュータ１４で作成されたオーダデータを格納して計
画エンジン部１１に出力するオーダテーブル２５と、Ａ
Ｉ処理部２１で使用される基本ルールを格納する基本ル
ールテーブル２６と、ＧＡ処理部２２での探索過程で評
価値を算出するために必要となる評価値算出用テーブル
２７とが設けられている。またマンマシンインタフェー
ス部１３には、ＣＲＴなどで構成され最適化問題を解く
過程の進行状態を操作者に対して逐一表示する表示部２
８と、マウスやキーボードなどで構成され操作者からの
指示が入力する入力部２９とが設けられている。

【００２４】次に、計画エンジン部１１について説明す
る。計画エンジン部１１は、オーダデータや他の条件を
制約条件とする最適化問題を解くことにより配車計画を
作成するものであり、ＡＩ処理部２１、ＧＡ処理部２
２、第１および第２の修正部２３,２４を備えている。
他の条件にはトラックの規定積載量などが含まれる。Ａ
Ｉ処理部２１は、決定論的手法の一つである人工知能を
用いた方法によって解の一部を探索し、配車計画の一部
として決定するものである。ここで解の一部を探索する
とは、具体的には、一部のトラックについてその行き先
などを決定することである。ＡＩ処理部２１での処理に
必要となる知識ルールは、基本ルールテーブル２６に格
納されている。第１の修正部２３は、ＡＩ処理部２１で
の処理結果を操作者の判断に基づいて修正するためのも
のである。ＧＡ処理部２２は、ＡＩ処理部２１での処理
（第１の修正部２３による修正後のもの）によって探索
された解を除外したものを対象（解空間）として、遺伝
的アルゴリズムによって残りの解を探索するものであ
る。遺伝的アルゴリズムでは探索中に適応度を算出する
必要があるが、適応度を算出するためにＧＡ処理部２２
は評価値算出用テーブル２７を参照するようになってい
る。第２の修正部２４は、遺伝的アルゴリズムによる解
の探索過程に介入して解の一部を決定し、ＧＡ処理部２
２での探索対象の解空間から、決定された部分解を除外
するものである。第１および第２の修正部２３,２４
は、後述する入力部２９からの指示によって解を修正
し、解の一部を決定するように構成されている。

【００２５】次に、本実施例の動作について図３を用い
て説明する。まず、ホストコンピュータ１４によって作
成されオーダテーブル２５に格納されたオーダデータを
計画エンジン部１１に読み込む（ステップ１０１）。す
ると、ＡＩ処理部２１は、オーダデータに基づき、基本
ルールテーブル２６を参照しながら、人工知能に基づく
手法によって、初期配車を行なう（ステップ１０２）。
初期配車とは、複数のトラックのうちの一部のトラック
について、配送先や配送順を決定することである。本実
施例の場合、大口すなわち何台ものトラックで輸送しな
ければならない配送先に対する配車や、小口であっても
複数の配送先が地域的に近接して存在しかつこれら配送
先への荷物の量がちょうどトラック１台分になるのでル
ート配送が効率的に行なえる場合の配車などを、初期配
車として決定する。全ての配送先に対する配車を決定す
るのではなく、大口の配送先や効率よくルート配送でき
る配送先に対する配車のみを決定するので、この初期配
車はごく短時間のうちに行なうことができる。また、初
期配車の決定のために使用される知識ルール（基本ルー
ル）も簡単なものでよい。ここでは人工知能を用いてい
るので、基本ルールの適用順などによって、配車が逐次
決定することになる。後述するように表示部２８にはこ
の初期配車の決定過程が随時表示される。

【００２６】ＡＩ処理部２１による初期配車が終了した
ら、続いてマニュアル修正を行なう（ステップ１０
３）。このマニュアル修正は、操作者からの指示が入力
部２９を介して第１の修正部２３に入力することによっ
て行なわれる。具体的には、ＡＩ処理部２１の決定した
配車計画を一部変更したり、ＡＩ処理部２１では見つけ
られなかった初期配車を決定したりすることが行なわれ
る。

【００２７】続いて、ＧＡ処理部２２によって、遺伝的
アルゴリズムに基づく配車が行なわれる（ステップ１０
４）。ここでは、上述のステップ１０３までで配車が完
了したトラックを除外し、残りのトラックについての配
車を行なう。遺伝的アルゴリズムでは各世代ごとに解が
改善されていくが、本実施例では、世代ごとにその時点
での解すなわち配車計画の例が表示部２８に逐次表示さ
れる。それと同時に、操作者からの指示が入力部２９を
介して第２の修正部２４に入力することにより、解が修
正され解の一部が決定される（ステップ１０５）。すな
わち、その決定された部分解に対応する配車が決定され
る。そして、配車が全て終了したかどうかが判定され
（ステップ１０６）、トラックに割り当てられていない
配車されていない荷物が残っている場合や、評価値が悪
いなど得られた解が所定の条件を満たしていない場合に
は、ステップ１０４に戻り、それまでに配車が決定され
たトラックを除外した残りのトラックについての遺伝的
アルゴリズムによる配車が引続き行なわれる。ステップ
１０６で配車が全て終了したと判定された場合には、配
車計画作成のための動作を終了する。なお、配車計画を
作成する場合、作成された配車計画に基づき出荷伝票等
を作成することが一般的であるが、本実施例の装置で
は、逐次的に各トラックの配送先が決定することになる
ので、トラックごとに配送先が決定した時点で出庫伝票
等を作成するようにしてもよいし、最終的に配車計画が
完成した時点で出庫伝票等を作成するようにしてもよ
い。

【００２８】ここで、遺伝的アルゴリズムによる配車に
ついて、図４を用いてさらに詳しく説明する。

【００２９】まず、乱数によって染色体３０をｎ個発生
させ、第１世代の個体群を生成する（ステップ１１
１）。染色体３０は、図１(b)に示した染色体２００と
同様に、各トラックの配送先を表わす染色体であるが、
初期配車されたトラックはここでは対象としないので、
初期配車されたトラックを除いたトラックの台数に応じ
た長さとなる。また、図１(b)に示した場合では１回の
配送で１箇所の配送先しか行かないものとしているが、
本実施例では、複数の配送先を巡回できるものとしてい
る。例えば１回に３箇所まで回れるものとする場合に
は、トラックの各回の配送に関して３個の遺伝子座を割
り当てるようにすることにより、１回に複数の配送先を
巡回するような配車を行なうことが可能となる。

【００３０】そして、各染色体３０のそれぞれについ
て、評価値を算出する（ステップ１１２）。評価値ｆと
してはさまざまなものが考えられるが、例えば、

【００３１】

【数２】に表わされるものを使用できる。ここでは評価値が小さ
いほどよい染色体、すなわち適応度の大きい染色体であ
る。さらに、燃費や人件費などを考慮して評価値が定め
られるようにしてもよい。配送先やトラックの種別など
に応じて定まるパラメータ例えば配送時間や燃費を考慮
して評価値を算出する場合、算出の根拠となるデータは
過去の実績に基づいて定められることになるが、各トラ
ックにデジタルタコメータなどを搭載して日々データを
集めることにより、評価値を常に的確に算出することが
できるようになる。なお、低温輸送を必要とする荷物を
通常の（冷蔵でない）トラックで配送するようなことに
なっている染色体や、その他、遵守することが強く求め
られている制約条件に反するような染色体については、
式(2)による評価値でなく極めて悪い評価値が与えられ
たり、乱数によって生成される別の染色体に置き換えら
れたりするようにする。

【００３２】次に、最良の染色体に基づく解を表示部２
８に表示し（ステップ１１３）、操作者からの修正指示
を受け付ける（ステップ１１４）。修正指示によって解
の一部が決定すなわち一部のトラックについての配車が
決定した場合には、各染色体からそのトラックに関する
遺伝子座を削除し、遺伝的アルゴリズムにおける解空間
を狭くする。

【００３３】次に、各染色体ごとにその評価値から適応
度を算出し、選択用ルーレットを作成する（ステップ１
１５）。選択用ルーレットは、各染色体をその適応度に
応じた確率で選択するためのものである。そして、選択
用ルーレットを用い親となる染色体を各１個ずつ選択し
全部でｎ／２組の両親を選び出し（ステップ１１６）、
両親となる染色体から子となる染色体を交差により各２
個ずつ生成する（ステップ１１７）。そして、子の染色
体に対し適当な確率で突然変異を施し（ステップ１１
８）、第２世代の個体群を生成する。そしてこの第２世
代の各染色体について上述と同様に評価値を計算し（ス
テップ１１９）、最良の染色体に基づく表示を行ない
（ステップ１２０）、修正指示を受け付ける（ステップ
１２１）。続いて終了条件を満足しているかどうかの判
定、すなわち配車が終了したかどうかの判定を行なう
（ステップ１２２）。ここでの終了条件としては、例え
ば、最良の染色体の評価値が何世代にわたってほとんど
変化しないとか、評価値が所定の値に達したなどの条件
を採用することができる。終了条件が満足されていれば
遺伝的アルゴリズムによる処理を終了し、満足していな
ければステップ１１５に戻って次の世代で同様の処理を
繰り返す。

【００３４】遺伝的アルゴリズムでは、各染色体にその
適応度に応じた淘汰圧力が加わることになるが、単純に
適応度に比例して染色体が選択される（適応度比例戦
略）ようにするだけでなく、例えば、最もよい染色体
は必ず次世代に生き残るようにする（エリート保存戦
略）、適応度によって各染色体をいくつかのランクの
うちの１つにランク付けしランクに応じた確率で子孫を
残せるようにする（ランク戦略）、各染色体が残す子
孫の期待値を計算した上でその染色体が選択された場合
にその期待値から０.５を引く（期待値戦略）などの戦
略をとるようにしてもよい。エリート保存戦略は最良の
染色体を生き残らす戦略であり、期待値戦略は染色体数
が少ない場合の乱数のゆらぎの影響を抑える戦略であ
る。

【００３５】次に、表示部２８での表示例について、図
５を用いて説明する。

【００３６】図５の表示画面４０において、□で囲まれ
た１からｎまでの数字はトラックの番号を表わしてい
る。各トラックがどのようなトラックであるかは、アイ
コン４１によって表示されている。すなわちアイコン４
１は、対応するトラックの規定積載量に応じた大きさで
あり、また、タンク車や冷蔵車などトラックの車種はア
イコン４１の形状で判別されるようになっている。この
表示画面４０では、各トラックが１回転目にどこへ行く
か、２回転目にどこへ行くかが示され、各回での積載量
が、規定積載量を１００％として「積載率」の欄にグラ
フで示されている。配送先は文字で表現することも可能
であるが、ここでは、配送先を表わすマーク４２で表わ
されている。マーク４２としては、配送先の社章などを
用いることができる。同じ会社の異なる支店を区別する
ために、マーク４２に「Ａ店」、「Ｂ店」などの支店名
を併記するようにしてもよい。また、全トラックの規定
積載量の和、１回転目の配送荷物の総量と積載率、２回
転目の荷物の総量と積載率が、合計の欄に示されてい
る。所要時間の欄では、各配送先への到着予定時刻が点
線で、配送基地への帰着予定時刻が実線で示されてい
る。さらに、表示画面４０の左下部分には、配車が未定
の荷物（未配車オーダ）が配送先のマークで示されてい
る。表示画面４０の右下の窓部４３には、傭車によって
使用する輸送業者ごとの実績シェアが表示されている。

【００３７】本実施例では、初期配車を行なう前には、
全てのオーダが未配車オーダであるが、ＡＩ処理部２１
の処理によって初期配車が決定するにつれ、配送先のマ
ーク４２が未配車オーダの欄から初期配車で決定された
トラックの欄に移行する。また、操作者がマウスを用い
て配送先のマーク４２を未配車オーダの欄から各トラッ
クの欄へあるいはその逆さらには各トラックの欄の相互
間でドラッグすることにより、図３のステップ１０３で
のマニュアル修正を実行することができる。

【００３８】遺伝的アルゴリズムによる配車を行なって
いるときは、各世代ごとに、最良の染色体の表わす解す
なわち配車計画に応じ、配送先のマーク４２が各トラッ
クの欄あるいは未配送オーダの欄に表示される。この場
合、初期配車によって決定した状態にあるものと、遺伝
的アルゴリズムによる探索過程にある未確定の状態にあ
るものとを区別するため、トラックのアイコン４１の表
示色を変化させたり白黒を反転させたりする。遺伝的ア
ルゴリズムによる配車の過程において、未確定の状態の
トラックの番号をクリックした場合には、その配車が確
定したことになって（解の一部の決定）、トラックその
アイコン４１の色が確定状態の色などになるとともに、
上述と同様にマーク４２をドラッグすることによって、
解の修正を行なうことができる。

【００３９】

【発明の効果】以上説明したように本発明の最適化問題
解決処理方法は、まず決定論的な手法を用いて解の一部
を発見し、続いて、発見された解を除いた解空間を対象
として遺伝的アルゴリズムを適用し残りの解を見つける
ことにより、少ない計算量で短時間に最適解あるいは準
最適解を見つけられるという効果がある。

【００４０】また、本発明の最適化問題解決処理装置
は、決定論的な手法によって解の一部を発見する第１の
処理手段と、第１の処理手段で発見された解を除外した
解空間を対象として遺伝的アルゴリズムに基づく探索を
行なって残りの解を発見する第２の処理手段とを設ける
ことにより、ごく短時間での第１の処理手段での処理に
よって遺伝的アルゴリズムが対象とする解空間が狭くな
るので、全体としての解探索時間が大幅に短縮するとい
う効果がある。また、外部からの入力に応じて解を修正
する第１あるいは第２の修正手段を設けることにより、
操作者の判断を反映させたり、急激な制約条件の変化に
も即応することができるようになる。

【００４１】そして本発明の最適化問題解決処理方法あ
るいは装置を運輸産業におけるスケジューリングに応用
した場合には、スケジューリングに要する時間と労力を
大幅に削減できるとともに、人手ではなし得なかったよ
うなスケジューリングの最適化を達成することができ、
物流コストを大幅に削減できるという効果がある。

【図面の簡単な説明】

【図１】(a)は遺伝的アルゴリズムの概要を説明する
図、(b)は染色体の構成例を示す図である。

【図２】本発明の一実施例の最適化問題解決処理装置の
構成を示すブロック図である。

【図３】図２の装置を使用し本発明の最適化問題解決処
理方法に基づいて最適化問題を解決する場合の処理手順
を示すフローチャートである。

【図４】遺伝的アルゴリズムによる処理の詳細を示す流
れ図である。

【図５】表示部に表示される画像の一例を示す図であ
る。

【符号の説明】

１１計画エンジン部１２データベース部１３マンマシンインタフェース部１４ホストコンピュータ２１ＡＩ処理部２２ＧＡ処理部２３第１の修正部２４第２の修正部２５オーダーテーブル２６基本ルールテーブル２７評価値算出用テーブル２８表示部２９入力部３０，２００染色体４０表示画面１０１〜１０６，１１１〜１２２，２０１，２０３
ステップ２０２，２０４，２０５個体群２１０遺伝子座

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号庁内整理番号ＦＩ技術表示箇所Ｇ０６Ｆ 17/00 17/60

Claims

【特許請求の範囲】

【請求項１】最適化問題を解決する最適化問題解決処
理方法であって、決定論的な手法によって解の一部を発見する第１の過程
と、前記第１の過程の実行後、前記第１の過程で発見された
解を除外した解空間を対象として遺伝的アルゴリズムを
適用し残りの解を発見する第２の過程とを有する最適化
問題解決処理方法。
【請求項２】最適化問題が運輸産業におけるスケジュ
ーリング問題である請求項１に記載の最適化問題解決処
理方法。
【請求項３】最適化問題を解決する最適化問題解決処
理装置であって、決定論的な手法によって解の一部を発見する第１の処理
手段と、前記第１の処理手段で発見された解を除外した解空間を
対象として遺伝的アルゴリズムに基づく探索を行なって
残りの解を発見する第２の処理手段とを有する最適化問
題解決処理装置。
【請求項４】第１の処理手段で発見される解を外部か
らの入力に応じて修正する第１の修正手段をさらに有
し、修正後の解を除外したものを対象として第２の処理
手段で探索が行なわれる請求項３に記載の最適化問題解
決処理装置。
【請求項５】第２の処理手段での解の探索過程中に外
部からの入力に応じて解の一部を決定する第２の修正手
段をさらに有し、前記第２の修正手段で解の一部が決定
された後は決定された解を除外した解空間で以後の前記
探索過程が進行する請求項３または４に記載の最適化問
題解決処理装置。
【請求項６】最適化問題が運輸産業におけるスケジュ
ーリング問題である請求項３ないし５いずれか１項に記
載の最適化問題解決処理装置。