遺伝的アルゴリズムを用いた通信ビル内施工業務の効率化
2005MT039 伊藤 祥平 2005MT076 中村 雄人
指導教員 奥村 康行

1. はじめに
近年，インターネットの普及に伴い，ブロードバンドネットワークサービスの需要が急激に増加しており，ユーザからの申し込みに対する迅速なサービスの提供が求められている．そのためには業務の効率化，人的リソースの有効活用が重要である．光通信設備
は，光ファイバやスプリッタなど遠隔操作が困難な媒体が対象であるために人的作業がサービスに大きく影響する．
申し込み(オーダ)ごとに作業を処理する方法では，無駄な移動などが発生し非効率的になる．需要が尐ない時期であれば，このような方法でも作業量そのものが尐ないため大きな問題とはならない．しかし，需要が多くなると移動や作業の中断が何度も発生し，リードタイムに大きな影響を与える．よって，需要興隆期におけるリードタイム削減のためにはオーダ単位の枠を超えて，時には複数の作業者で分業していくことが必要になってくる．
本研究では，この問題を，巡回セールスマン問題(TSP:Traveling Salesman Problem)を元にした，n 人で分業する分業巡回セールスマン問題(n-TSP)の解を，遺伝的アルゴリズム(GA:Genetic Algorithm)を用いて導出する方法を研究する．また，作業者の能力に応じた重み付けを行うことで，より最適な解へと近づけるようにする．

主に顧客宅間の移動コストが作業コストの大部分を占めているので，n-TSP と同等と考えることができる．
(2)所外設備施工業務
作業の規模が大きく，また作業空間が限定されているため，作業方面ごとに作業者を割り当てる方法で対処できる．
(3)所内装置施工業務
所内装置は遠隔からの設定が可能なので，人的作業は殆ど発生しない．
(4)所内光設備施工業務
所内光設備の施工業務は，作業量や作業種別が多く，移動コストのほかに作業コストに影響を与える様々な要因を考慮する必要があるので，問題が複雑になる．
よって，本研究では(4)の所内光設備の施工業務効率化を対象とする．その主な業務は事前に部分的に接続してあるケーブルを CR 内でコネクタ接続・融着接続することである．オーダの取り消しやルートの変更などがおこるため考慮すべき点が多い．

2. 設備構成・施工業務の種類と課題
2.1 設備構成
光通信設備の構成を図 1 に示す．光通信設備は宅内に設置に存在する ONU(Optical Network Unit)，主に光ケーブルなどの高速通信ケーブルで構成される所外光設備(O-ODN:Outside optical distributionnetwork)，所内光ファイバやケーブルラック，光コネク
タ か ら 構 成 さ れ る 所 内 光 設 備 (I-ODN:Intra-office
optical distribution network)，所内装置(OLT:OpticalLine Terminal)から構成される．
2.2 施工業務の種類
人手を介する施工業務の種類は主に 4 つに分かれ，それぞれ作業効率化のための方法は異なる．
(1)宅内設備施工業務

図１ 光設備の構成
2.3 課題所 内光 設備 は所 内光 ファイ バ，ケーブ ルラッ ク(CR:Cable Rack)，光コネクタから構成されている．光ファイバは，任意での切断・融着が困難であるため，CR 間にケーブルをあらかじめ配線して保留している．
よってオーダが発生した場合の作業は，接続工事(コネクタ接続・融着接続)，開放工事となる．これをオーダの都度処理していく方法では，フロア間の移動など無駄なコストが発生するため，迅速なサービス提供に悪影響を及ぼす．（図 2）①～⑥は作業地点（タスク）を表しており，オーダはオーダ A：「①→②→③」の作業を終えた後にオーダ B：「④→⑤→⑥」の作業をするように指示している．この方法では，実際に作業を行う場合，フロアの移動が３回も行われており非効率的である．
このような課題に対して本研究では，オーダの枠を超え位置関係や作業内容などを考慮した効率的な作業プロセスを導出していく方法を提案する．（図 3）「①→②→③→⑤→⑥→④」と移動することで無駄なフロア間の移動や往複を無くしている．この方法により，総作業コストを最小化する．

２３４５６個体数 1000 個

初期個体の生成デコーディング

2F①②⑤300 回以上

試行回数300 回未満

選択終了

実際の移動

オーダの施工指示
１3.1 遺伝的アルゴリズム
GA は，生物の進化プロセスに着目した探索アルゴリズムであり，淘汰・交叉・突然変異などの操作を用いて解を生成し，解を高速に発見する手法である．
GA の簡単なフローを図４に示す．

コーディング③交叉突然変異1F④⑥
図 4 GA のフロー

図 2 光設備施工業務の課題⑥提案する移動
１４２５

実際の移動
３６2F
1F

①②③⑤④⑥

図 3 タスクの枠を超えた作業プロセス

3. 課題の解決に向けて
TSP は，対象となる顧客宅数(本研究では作業場所)が増えていくにつれて探索量が膨大な量になっていき，（探索量=（n-1）!/2）これに伴い解の数も増えていく．そのため，全ての解を列挙し吟味した上で最適解を導出することは不可能に近い．本研究で取り扱う問題はオーダの変更や取り消しなど突発的な事態にも対応しなければならないため，時間をかけて最適解を導くよりも，短時間で精度の高い近似解を求める事が重要であると考えられる．そこで，TSP を解決する際に多く利用されている遺伝的アルゴリズム（GA）に着目した．

選択や交叉には複数の方法があるが，本研究のプログラムではエリート選択と一様交叉を使用している．
エリート選択(トーナメント選択とも呼ばれる)とは，個体群の中で最も適応度の高い個体を無条件でそのまま次世代に残す手法である．利点として，その時点での最良の個体は交叉や突然変異などで破壊されることがなくなるという点が上げられる．
また，一様交叉とは，二つの遺伝子の各要素ごとを独立に 1/2 の確率で入れ換えるというものである．図5 は遺伝子 A，B の一様交叉を表した簡単な例である．また，矢印の指す要素を交叉位置とする．
A０１１０１０１B１０１１０１
交叉前の遺伝子００A００１１００

B１１１００１
交叉後の遺伝子０１１００

図 5 一様交叉

交叉には他に一点交叉や二点交叉などがあるが，一点交叉は他の交叉方法より効率が悪く，二点交叉はヒッチハイキングという最適解の生成を妨げる現象が起きてしまう可能性があるので，本研究では採用していない．
作業者一人の場合は，A・B の遺伝子の要素がそのままタスクとなる．また複数作業者の場合，導出されたタスク順序を作業者数で均等に分割し，それぞれに割り当てる方法で処理する．
3.2 分業巡回セールスマン問題
巡回セールスマン問題(TSP)とは，顧客宅(または都市)の集合とその２点間の移動コストが与えられたとき，全ての点をちょうど一度ずつ巡り出発地点に戻る総移動距離が最小のものを求める，組み合わせ最適化問題である．それをｎ人で分業し作業量の平準化と効率化を図る問題が，「分業巡回セールスマン問題（n-TSP）」である．フロア間の移動距離最小化の問
題は，n-TSP の概念とほぼ同じなので，プログラム内では顧客宅をフロアと置き換えている．また，TSP と同等の理由で GA による解の導出を行っている．
3.3 作業量の平準化
本研究では，複数の作業者の総作業コストに偏りを持たせないために作業量の平準化を行っている．これにより，各作業者にできるだけ平等に作業が分担されるようになる．
(1)式は平準化のためにコストに加算するペナルティ，(2)式は(1) を加えた総コストである．

Penalty=（Cmax－Cmin）(1)

Ct= C+α*Penalty(2)

Ct：総コスト
C：計算した作業コスト
Cmax：作業者 n 人中の作業コストの最大値
Cmin：作業者 n 人中の作業コストの最小値
α：平準化の重み

3.5 プログラムの実装について
本プログラムにおける処理は以下の 4 つに分類される．
1．まず初めに，ランダムに初期個体を生成する．
2．作業間コストをフロア数と CR 数に従って生成し，作業実行コストを外部のファイルから読み込む．
3．それらのデータを基にコストの計算が行われ，近似解が導出される．
4．次世代を生成するため，交叉や突然変異などの操作を行う．
5．3 から 4 の過程を 300 回繰り返す．
6．作業者別にコストを振り分け，その際に作業者のスキルを考慮して計算する．
7．最適化された経路とそのコストを導出する．
8．経路と各作業地点でかかるコストを表示する．この際，作業者毎の作業順序やコスト，作業者間のコストの差など実用的なパラメータも合わせて表示する．
これらを C 言語を使い表現し実装した結果，398 行で記述されたプログラムとなった．

4.シミュレーション
4.1 GA と総当たり探索の比較
3.5 と同じ仕様で CR（作業地点）10 から 13，作業者 1 人のプログラムを作成し総当たり探索による最適解と GA による近似解を求め、それらの比較を行った．
その結果，次の表 1 と表 2 からわかるように，GA は総あたり探索に比べて解を求める時間が大幅に短縮されているのがわかる．その反面，最適解に比べて 1割程度コストが増加する結果となった．このような事か
ら，作業地点が 150 のオーダになると，総当たり計算
では，ほぼ不可能な計算時間になると予想され，現実的ではない．そこで，近似解ではあるが現実的な時間で解を求められる GA の詳細な評価を行う．
表 1 GA と総当たり探索のコスト比較
作業地点の数(総当り)(GA )Penalty をコスト C に加算して総コスト Ct として計算する．重みの値を変え，どの値が最適かをシミュレーションを通して判断する．
3.4 作業者のスキル
作業者別のコスト計算の際に作業効率を表すパラメータを付与し，より現実的なプログラムへと近づける．
本研究では平均的に作業をこなせる作業者のスキルを 1.0 とし，0.5 から 1.5 までのスキルを実装する．

10788711881081298118

13108131

表 2 GA と総当たり検索の計算時間比較
作業地点の数(総当り)101秒1110 秒

1280 秒

13800 秒(GA )2秒

2秒2秒2秒

4.2 条件仮定
シミュレーションで対象となる通信ビルのモデルは，1 フロア 50 個の CR（作業地点），3 階建てで計 150個の CR を有するビルとする．また，①全ての階でCR が同じように整列されている．②CR 間の移動は全て同じ速度とする．③CR 間の往路，復路は同じコストである．という条件のもとに表 3，表 4 の作業の割合，スキルの割合で，作業者は 10 人という条件のもとにシミュレーションを行う．
表 3 作業の割合
作業の内容
作業の割合
コネクタ接続(コスト 5)
コネクタ解放(コスト 7)
融着接続(コスト 9)

42％
33％
25％

表 4 スキルの割合
作業者のスキル
スキルの割合0.520％

1.060％

1.520％

4.3 実行結果
以下の図は 3.3 で述べた平準化の重み係数 α を 1から 3 まで変えて 100 回試行し平均をとった結果である．図 7 の横軸は重み係数 α，縦軸は総コスト Ct，
図 8 の横軸は重み係数 α，縦軸は Penalty(Cmax－Cmin)となっている．

5. 考察
図 7 によると，スキル設定有の場合の重み係数 1と 2 の Ct の差は約 30 であるのに対し，重み係数 3の場合は重み 1 と約 200 の差が発生している．
また図 8 によると，Penalty が重み 1 から 2 で約 70程度減っているのに対して，重み 2 から 3 では 10 未満とあまり減尐していない．
そして，スキルなしの場合と比較しても，スキルありの方がαの値に関わらず総コストは 100 程度減尐し，平準化においても同じようにコストが減尐しており，スキルの有用性が証明された．
以上のシミュレーションの結果のように，重みを増すほど作業者間の作業量の平準化は進み，コストは増えていく，という結果は狙い通りの結果である．しかしながら，重み 3 では総コストは多量に増えるものの，平準化はあまりなされておらず，あまり実用的ではない．よって，本研究のプログラムでは総コスト軽減を重視する場合は重み 1，作業者間の作業量平準化を重視する場合は重み 2 と設定し，シミュレーションを行った場合の方がよい結果が得られると考えられる．

6. まとめ本研究では遺伝的アルゴリズムを用いて通信設備を有したビルの施工業務の効率化を目指した．また平準化により作業者間の偏りを軽減した．加えて作業者のスキルに応じたパラメータを設定し付与することにより作業量の配分が可能になり，さらにコストを削減する効果を得ることができた．今後の課題としては，実際の通信設備を有したビルの詳しい条件を設定し，シミュレーションと考察を行うことが挙げられる．また，GA の世代数や突然変異確率といったパラメータの工夫，そして新たな選択方法や交叉方法でのシミュレーションも考えられる．

参考文献
図 7 重み別の総コスト
[1]

[2]
[3]

図 8 重み別の作業者の差

柴木 雅也，田山 健一，山村 哲哉，奥村 康
行：“通信ビル内施工業務の効率的作業プロセス導出方法の提案”，電子情報通信学会論文誌
Vol.J89‐B No.2 pp.253-263(2006)
伊庭斉志：“遺伝的アルゴリズムの基礎～GA の謎を解く～”，㈱オーム社，ISBN4-274-07802-7
長久 勝：“最適解を模索する遺伝的アルゴリズム”
http://www6.plala.or.jp/mnagaku/cmag/ac19999/ ，2008 年 9 月 30 日