局所クラスタリング組織化法による配送路問題の解法

全文

(1)情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2009-MPS-75 No.1 2009/9/10 revised solution representation is presented. The proposed method and other meta-heuristic methods are attempted to solve some benchmark problems and randomly generated problems as numerical experiments. The experiments verify that the proposed method bring us good solutions in term of computation time and solution’s accuracy.. 局所クラスタリング組織化法による配送路問題の解法坂本山本. 延寛†1 雅人†1. 鈴木古川. 育正. 男†1 志†1. 渡辺. 美知子†2 1. はじめに配送計画問題 (Vehicle Routing Problem, VRP) とは，複数台の車両を用いて倉庫か. 配送計画問題とは複数の車両を用いて倉庫から顧客へ品物を配送する経路長を最小化する問題である．この問題は，輸送，流通やロジスティクス等の分野の中心的な問題であり，数多くの実用的応用を持つ．また，この問題は NP 困難なクラスに属するため，厳密解法では問題の規模が増大すると実用的な時間内で最適解を得ることが難しく，近似解法，特にメタヒューリスティクスによる研究が多くなされてきた．本研究では，メタヒューリスティクス手法の一つである局所クラスタリング組織化法を用いた配送計画問題の解法を提案し，ベンチマーク問題を用いた数値計算実験によりその有効性を検証する．さらに，局所クラスタリング組織化法は大規模問題に適した手法であるため，ベンチマーク問題より問題規模の大きな問題をランダムに作成し，数値計算実験で大規模問題に対する有効性も同様に検証する．. ら顧客へ品物を配送する経路を決定する問題の総称である．一般的に，その目的は制約条件を満たし総経路長が最小となる経路を探索することである．この問題は，運送，流通やロジスティック分野の中心的な問題であり，数多くの現実的な応用を持つ．これは，運送やロジスティックに関わる多くの業界では，輸送コストが大きな割合を占めているために，その最適化によって多くのコスト削減が期待できるためである．実際，流通分野でのコストが最適化により 5% から 20% 削減されたと報告されている16) ．また，VRP は良く知られた組合せ最適化問題であり，NP 困難である．本研究では，VRP に対し局所クラスタリング組織化法 (Local Clustering Organization, LCO)8) を用いた解法を提案する．LCO は，大規模な TSP に対し高速に近似解を得ることを目的に開発された. A New Solution for Vehicle Routing Problem Using Local Clustering Organization. 手法であり，数値計算実験により TSP に対する有効性が示されている．LCO はランダムに順序付けした解の要素に対し局所的なクラスタリングを繰り返すことで最適化を行. SAKAMOTO,†1. SUZUKI,†1. う手法である．VRP は TSP としての特徴も有することから，LCO を用いた場合の有. Nobuhiro Ikuo †2 Michiko WATANABE, Masahito YAMAMOTO†1 and Masashi FURUKAWA†1. 効性も同様に示されることが期待される．さらに，一般的に VRP の有効性の検証に使用されるベンチマーク問題4) は問題のサイズ (顧客数) が最大 200 程度と比較的小さい．よって，より大規模な問題をランダムに作成し，大規模な問題に対する有効性も同様に検証する．. The Vehicle Routing Problem (VRP) is a well-known combinatorial optimization problem and has been widely studied because it arises in many situations. The objective of VRP is to find out m Hamilton paths for m vehicles, each of which delivers some goods (items) to demanded customers from a depot place and return to the same place under some criteria and constraints. This study proposes a new solution on VRP, applying “ Local Clustering Organization (LCO) ”. LCO is a meta-heuristic method developed by one of our authors to give a highly accurate solution to the large-scale traveling salesman problem (TSP). It can deal with almost a hundred of thousands cities ’ TSP. The advantage of LCO is that it only uses costs among cities unlike recently developed other meta-heuristic solutions request cities ’ coordinates such as the self-organizing map (SOM) and the ant colony optimization (ACO). For the use of LCO to VRP, the algorithm of LCO is modified. Furthermore, a. 以下では，2 章で関連研究の説明，3 章で LCO の学習原理とアルゴリズムの概略，4 章で LCO の VRP に対する適用方法，5 章で数値計算実験の結果を示す．最後に 6 章で本研究のまとめを行う．. †1 北海道大学情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University †2 北見工業大学工学部機械工学科 Department of Mechanical Engineering, Kitami Institute of Technology. 1. ⓒ2009 Information Processing Society of Japan.

(2) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2009-MPS-75 No.1 2009/9/10. 3.2 対象とする VRP. 2. 関連研究. 本研究で対象とする VRP の目的は，車両の移動距離（時間）の総和を最小化するこ. VRP は 50 年ほど前に提案され6) ，それ以来厳密解法および近似解法を用いた数多. とであり，制約条件は以下の通りである．. くの研究がなされている．しかし，一般的に顧客数が 50 以上の場合，最適解を求めら. 1. 車両は倉庫から出発し倉庫へ戻る. れる厳密解法は知られていないと報告されている10) ．これは，VRP が NP 困難な問題. 2. 顧客は一台の車両で一度だけ配送される. であることに起因し，これ以上の規模の問題に対しては近似解法が有効とされている．. 3. 車両が配送する品物の総量は車両の積載量の上限 Q を超えない. 近似解法には, ”Constructive method”5) , ”Two-phase method”7) ,14) , ”Improvement. 4. 車両の移動距離（時間）は上限 L を超えない. method”15) ,17) などがある．さらに，近年ではメタヒューリスティクスによる解法の研究も数多く行われ，従来より高精度な近似解を高速に得ている．メタヒューリスティクス. また，本研究では顧客集合 N ，顧客間の距離（移動時間） cij ，顧客の需要量 qi ，顧. は，特定の解法ではなく，幅広い問題に対し対応可能なアルゴリズムの基本的な枠組みを. 客での作業時間 si ，車両の移動距離（時間）の上限 L，車両の積載量の上限 Q は既知. 指す．メタヒューリスティクスに属する解法には，焼きなまし法 (Simulated Annealing,. とする．. SA)12) ,17) , タブーサーチ (Tabu Search, TS)14) ,9) ,13) ), 遺伝的アルゴリズム (Genetic. 本研究で扱う VRP の目的は車両の総移動距離（時間）を最小化することであり，以. Algorithm, GA)2) ,1) , 蟻コロニー最適化 (Ant Colony Optimization, ACO)11) ,3) など. 下の式で表現できる．. がある．この中でもタブーサーチが VRP に対して最も成功したメタヒューリスティッ. minimize. クであるとされる．実際，14 個のベンチマーク問題のうち 12 個において14) が，2 個に m n ∑ ∑. ∑∑. 3.1 記号の定義. M. : 車両の集合 {Mi : i = 1, 2, ..., m}. qi. : 顧客 Ni の需要量. si. : 顧客 Ni での作業時間. c(Ni , Nj ). : 顧客 Ni , Nj 間の距離（移動時間）. L. : 車両の移動距離（時間）の上限. Q. : 車両の積載量の上限. xijk. (2). xkij = 1. (i = 1, 2, ..., n). (3). k=0 j=0 m n. 以下に必要な記号を定義し，その上で VRP を定式化する． n : 顧客数. : 顧客の集合 {Ni : i = 1, 2, ..., n}. xk0j = m. k=0 j=0 m n. この章では本研究で扱う VRP について定式化を行う．. N. (1). さらに，各制約条件は以下の式で表現できる．. 3. 配送路問題の定式化. : 車両台数. xkij (cij + si ). k=0 i=0 j=0. おいて13) がそれぞれ現在知られている最良解を求めている.. m. m n n ∑ ∑ ∑. ∑∑. xki0 = m. (4). k=0 i=0 m n. ∑∑. xkij = 1. (j = 1, 2, ..., n). (5). k=0 i=0. xkij (1 − xkij ) = 1. (6). xkij ≤ Q. (7). n ∑ i=0 n. n ∑ ∑. qi. n ∑ j=0. xkij (cij + δi ) ≤ L. (8). i=0 j=0. : 車両 k が顧客 i へ配送した後に j へ配送すれば 1, そうでなければ 0. 2. ⓒ2009 Information Processing Society of Japan.

(3) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2009-MPS-75 No.1 2009/9/10. 4. 局所クラスタリング組織化法この章では，局所クラスタリング組織化法 (Local Clustering Organization, LCO)8) の概要を説明する．LCO は要素間のコストが定義された問題の解に対し，局所的なクラスタリングを繰り返すことで最適化を行う最適化手法である．クラスタリングの際には，解のランダムに選択した要素を起点とし，その周辺の要素集合内で評価関数に基づく順序付けを行う．この概念は自己組織化マップ (Self-Organizing Map, SOM) におけ図1. るニューロンの自己組織化に基づいている．SOM を組合せ順序問題に適用した場合，入. An example solution of VRP. 図2. An example initital solution of VRP. 力ベクトルに対するシナプスベクトルの局所的な学習により，ニューロンの自己組織化を結果的に行っている．しかしながら，組合せ順序問題において，入力ベクトルおよびシ. を超えないという制約を満たすかの判定は，要素の交換によって変化した順序解を評価. ナプスベクトルとみなせる情報が与えられない問題も存在し，そのような場合には SOM. しなければ行えない．また，解集合のうち，制約条件を満たすものは実行可能解，満た. を適用することは困難である．そこで，LCO では SOM におけるシナプスベクトルを用. さないものは実行不可能解と呼ばれる．本研究では，実行可能解の集合内で解の探索を. いた学習の代わりとして，費用関数による局所的なクラスタリングを行うことで，費用. 行うため，操作の結果実行不可能解へ遷移する場合は，その操作をキャンセルし操作適. 関数のみに基づいた最適化を可能としている．. 用前の解に戻すこととする．. 5.2 初期解. 5. LCO の VRP への適用. 本研究では，実行可能解の集合内のみで探索を行うため，初期解も実行可能解である. LCO を VRP へ適用するためには，VRP における解要素の順序解と，その順序解を. 必要がある．また，VRP には車両の移動距離（時間）と積載量の制約が存在するが，一. 評価する方法が必要となる．本研究では，LCO を VRP へ適用するための解表現を次の. 台の車両が一人の顧客へ配送する状態は必ず制約条件を満たす．もし，この状態でも制. ように定める．. 約条件を満たさない場合は，実行可能解を持つ問題として成立しない．よって，初期解. 5.1 解表現. として一台の車両が一人の顧客へ配送する状態を用いる．この初期解を用いる場合，解. まず，VRP を LCO で扱うための順序解の要素として，顧客番号 1, ..., n と倉庫を表. の要素数は顧客数の 2 倍となる．図 2 に初期解の例を示す．. す番号 0 を用いる．ここで，各車両は倉庫から出発し，割当てられた顧客へ順に配送し. 5.3 車両台数削減. た後，倉庫へ戻る．よって，各車両の経路は，倉庫を表す 0 を先頭とし，配送先の顧客. 一般的に，車両台数が少ないほど総移動距離（時間）は減少する．ただし，制約条件. 番号が配送順に並べ，最後に再び 0 が並ぶ順列で表現できる．さらに，各車両の先頭と. があるため最低限必要な台数が決まっている．また，前節の初期解を用いた場合，車両. 最後は必ず 0 のため，ある車両の先頭と別の車両の最後を連結し，各車両の経路全体で. 台数は顧客数と等しい．よって，この初期解にクラスタリングを適用した場合，解表現. リング状のトポロジーを形成する．図 1 に顧客数 10，車両台数 3 の場合の例を示す．. 上で倉庫を表す 0 が隣り合い，どの顧客へも配送しない車両が存在することになる．さ. LCO の局所的なクラスタリングは，順序付けられた解要素の交換や，要素間の解要素. らに，二次元平面上に配置された顧客間のユークリッド距離を顧客間の移動距離（時間）. 順序の逆転（逆位）を解に対する基本操作とする．従って，順序解表現上の任意の要素. とする場合，再びこの車両に顧客を割当てた際に総移動距離（時間）が減少することは. に対し基本操作を適用しても，矛盾の無い順序解表現を維持し，評価を行えなければな. ない．よって，解表現上で隣合った倉庫を示す 0 の内ひとつを残し，残りは削除するこ. らない．上記の解表現はこの条件を満たしており，車両は倉庫から出発し最後に倉庫へ. ととする．これによって，車両台数と解の要素数が減少する．図 3 にその例を示す．. 戻るという制約と，顧客は一台の車両に一度しか配送されないという制約を必ず満たす．. 5.4 アルゴリズムの変更. ただし，車両の積載量が上限を超えないという制約と，車両の移動距離（時間）が上限. LCO を VRP に適用した解法のアルゴリズムを以下に示す．. 3. ⓒ2009 Information Processing Society of Japan.

(4) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2009-MPS-75 No.1 2009/9/10. 3. 交換後の近傍解が制約条件を満たし，評価値が改善されるかどうかを以下の式で判定し，条件を満たす場合 S を S ′ と置き換える．図3. C(S ′ ) ≤ C(S) ∧ L(S ′ ) ≤ L ∧ Q(S ′ ) ≤ Q. An example of erasing depot. ′. ′. (9) ′. ′. ここで，C(S)，C(S ) は解 S ，S の総移動距離（時間），L(S ) は解 S の最大移動距離（時間），Q(S ′ ) は解 S ′ の最大積載量とする．. 1. 上記の初期解作成方法に従い初期解 S を生成する. 4. k = −i とし (2)，(3) を行う．. 2. S からランダムに c 番目の要素 Sc を選択し，Sc の左右 d までの要素を近傍集. 5. i > d(t) ならば終了する．そうでなければ i = i + 1, k = i とし (2) へ戻る．. 合 Nc として設定する．. 5.5.2 逆位交換法 (Inverse Exchange Method, IEM). 3. 近傍集合 Nc に対し局所的なクラスタリングを行う．. 逆位交換法とは，解表現上で二要素間の要素の順序を逆転させること（逆位）を解に. 4. 車両台数の削減. 対する基本操作とする手法である．よって，IEM における近傍解 S ′ は，解 S から c 番. 5. 一定回数解の改善が行われない場合終了する．それ以外は (2), (3) を繰り返す．. 目の要素と c + i 番目の要素間の要素順序を逆転させた解とするその他の部分は SEM と同じなため詳細は省く．. ここで，クラスタリングを行う近傍範囲を決定する d は，上限を解要素数の 1/2 とし. 5.5.3 平滑法 (Smoothing Method, SM). ランダムで決定する．. 5.5 局所クラスタリングアルゴリズム. 平滑法とは，解表現上で二要素の交換を基本操作とする手法であり，その点では SEM. 前節のアルゴリズムでは，LCO を VRP へ適用した場合の局所的なクラスタリング方. と似た手法である．しかし，SM は交換を行う二要素の選択方法が SEM とは異なり，ク. 法が示されていない．. ラスタリングの起点となる要素番号 c を順次移動させつつ，SEM の総当りを行う手法. 局所的なクラスタリングとは，S からランダム選択した c 番目の要素の近傍の要素集. である．以下にそのアルゴリズムを示す. 合 Nc に対して行われる，評価値に基づく要素の順序付けである．TSP の最適化におい. 1. i = 0，j = 2 とする．. て LCO では複数ののクラスタリング手法が用いられ，それらを確率的に混合すること. 2. 近傍解 S ′ を，現在の解から c − d(t) + i 番目の要素と c − d(t) + i + j を交換し. が有効であると示されている8) ．これは，採用された複数のクラスタリング手法がそれ. た解とする．. ぞれ異なる特性を持つため，混合することで単独のクラスタリング手法では到達できな. 3. 交換後の近傍解が制約条件を満たし，評価値が改善されるかどうかを式 (9) で判. い近傍解に遷移することが可能であると考えられる．本研究では，TSP のために用いら. 定する．条件を満たす場合 S を S ′ と置き換える．. れた 3 種類のクラスタリング手法を利用し，近傍解への遷移判定を VRP に合わせ修正. 4. j = j + 1 とする．j < d(t) − i なら (2) へ戻る．. を行う．以下にその 3 種類のクラスタリング手法を示す．. 5. i = i + 1，j = 2 とする．i > d(t) ならば終了し，そうでなければ (2) へ戻る．. 5.5.1 単純交換法 (Simple Exchange Method, SEM) 単純交換法とは，解表現上で二要素の交換を解に対する基本操作とする手法である．. 5.6 LCO の局所クラスタリングの拡張. この際，現在の解 S からランダムに選択した c 番目の要素と，その近傍要素集合 Nc 内. 従来の LCO の局所クラスタリングアルゴリズムでは，二要素の交換や，二要素間の. の要素に対し，c の隣の要素から順次 c と交換を行うか判定し，制約条件を満たし評価. 逆位のみを基本操作とする．そこで，より多くの近傍解を探索することを目的とし，別. 値が改善される場合のみに交換を行う手法である．そのアルゴリズムを以下に示す．. の基本操作を用いたクラスタリング手法を採用する．用いる基本操作には，操作がなるべく簡単，かつ従来の LCO で採用されている基本操作では到達できない解にも到達で. 1. i = 1, k = i とする．. きることが望ましい．よって，本研究ではその基本操作として，解表現上のある要素を. 2. 近傍解 S ′ を，現在の解から c 番目の要素と c + i を交換した解とする．. 4. ⓒ2009 Information Processing Society of Japan.

(5) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2009-MPS-75 No.1 2009/9/10. 別の要素間に挿入することを採用する．. C1-C5, C11-C12 には各車両の移動距離（時間）の上限制約は存在しないが，C6-C10,. 5.6.1 単純挿入法 (Simple Insert Method, SIM). C13-C14 には存在する． 6.2 大規模問題. 単純挿入法とは，解表現上である要素を別の要素間に挿入することを解に対する基本操作とする手法である．この際，現在の解 S からランダムに選択した c 番目の要素と，. 上記のベンチマーク問題では，顧客数が 50 から 199 までである．LCO は本来大規模. その近傍要素集合 Nc 内の要素に対し，c の隣の要素間に順次 c を挿入を行うか判定し，. な問題に対して実用的な時間内で，高精度な近似解を得ることを目的に開発された手法. 制約条件を満たし評価値が改善される場合のみに交換を行う手法である．そのアルゴリ. である．そこで，より大規模な問題を独自に作成し数値計算実験を行う．実際に作成し. ズムを以下に示す．. た問題のパラメータを表 2 に示す．. 6.3 実験結果. 1. i = 1, k = i とする．. ベンチマーク問題に対する実験結果を表 1 に示す．表 1 によると，LCO では問題 C12. 2. 近傍解 S ′ を，現在の解から c 番目の要素と c + i と c + i + 1 番目の要素間に挿. でのみ最適解が得られている．また，現在知られている最良解との平均誤差は 4.12% と. 入した解とする．以下にその遷移を示す．. なり，C11 においては 14.83% と他の問題に比べ特に悪い値が得られた．. 変更前:(..., Sc−1 , Sc , Sc+1 , ..., Sc+i , Sc+i+1 , ...). 大規模問題の実験結果を表 2 に，得られた最良解のうち (b) と (d) に対する最良解を. 変更後:(..., Sc−1 , Sc+1 , ..., Sc+i , Sc , Sc+i+1 , ...). 図 4, 図 5 に示す．表 2 によると，顧客数 1000，2000 の問題に対しても，最大 86 秒と. 3. 交換後の近傍解が制約条件を満たし，評価値が改善されるかどうかを式 (9) で判. 十分実用的な時間で，近似解が得られていることがわかる．. 定する．条件を満たす場合 S を S ′ と置き換える．. 4. k = −i とし (3)，(4) を行う．. 7. 結. 5. i > d(t) ならば終了し，そうでなければ i = i + 1, k = i とし，(2) へ戻る．. 論. 本研究では，大規模 TSP に対し有効な解法である LCO を VRP に適用し，VRP に対する LCO の有効性の検証を行った．以下にまとめと今後の課題を示す．. 6. 数値計算実験 1. 本研究では，大規模 TSP に対し有効な LCO を用いた VRP の解法を提案した．. LCO を用いた VRP の解法の有効性を検証するために数値計算実験を行う．クラスタ. そして，VRP の有効性のためによく使用されるベンチマーク問題を用い，数値. リング手法の混合割合は SEM, IEM, SIM=1:1:1 とする．近傍要素集合 Nc を決定する. 計算実験により VRP に対する有効性の検証を行った．. 値である d(t) は，d(t) = α(m + n)/2 で決定される．ここで，α は 0 から 1 の間でラ. 2. LCO の改良のため，新たなクラスタリング手法として，単純挿入法 (Simple Insert. ンダムに設定される実数とする．終了条件は解が一定回数更新されないこととし，その. Method, SIM) を提案した．この手法を導入した結果における解の改善に対する. 回数は 1000 回とする．本研究において，プログラムは C++で記述され，Core 2 Duo. 有効性を検証した．. (3.00GHz) で実行される．各実験結果は 50 回の試行の結果を用いる．. 3. 従来の VRP のベンチマーク問題は 50 以上 200 未満程度の顧客数である．LCO. 6.1 ベンチマーク問題. は大規模 TSP のために開発された手法であり，より大規模な VRP の問題を独自. 数値計算実験では VRP の有効性検証によく利用されるベンチマーク問題を用いる．こ. に作成し数値計算実験を行うことで，LCO の大規模な VRP に対する有効性の検. のベンチマーク問題は 14 種類の問題 (C1-C14) を含み，50 から 199 までの顧客と単一. 証も行った．. の倉庫から構成される．ここで，顧客と倉庫は二次元平面上に配置され，顧客間の移動距. 4. 本研究では，新たなクラスタリング手法を追加したが，基本的には VRP の TSP. 離（時間）は顧客間のユークリッド距離を用いる．また，14 種類の問題のうち C1-C10. としての特徴を利用して解の探索を行ってきた．そこで，今後の課題としては，よ. の 10 種類は，二次元平面状に顧客をランダムに一様に配置した問題であり，C10-C14. り VRP へ適したクラスタリング手法の提案や修正を行うことを考えている．. の 4 種類は，顧客がいくつかのクラスターに別れ配置されている問題である．さらに，. 5. ⓒ2009 Information Processing Society of Japan.

(6) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2009-MPS-75 No.1 2009/9/10 (b). 参考. 文. 献. 1) Baker, B. and Ayechew, M.: A genetic algorithm for the vehicle routing problem, Computers and Operations Research, Vol.30, No.5, pp.787–800 (2003). 2) Berger, J. and Barkaoui, M.: A new hybrid genetic algorithm for the capacitated vehicle routing problem, Journal of the Operational Research Society, Vol.54, No.12, pp.1254–1262 (2003). 3) Chen, C. and Ting, C.: An improved ant colony system algorithm for the vehicle routing problem, Journal of the Chinese Institute of Industrial Engineers, Vol.23, No.2, pp.115–126 (2006). 4) Christofides, N., Mingozzi, A. and Toth, P.: The vehicle routing problem, Combinatorial optimization, Vol.11, p.315338 (1979).. 表1. prob.. n 50 75. 160 140. ∞ ∞. 0 0. 524.6114) 835.2614). 1.42 3.37. 9.57 7.22. 23.17 13.40. 0.17 0.55. C3 C4. 100 150. 200 200. ∞ ∞. 0 0. 826.1414) 1028.4214). 2.24 3.51. 5.64 7.89. 11.93 11.96. 1.21 3.57. C5. 199. 100. ∞. 0. 1291.4513). 4.79. 10.05. 14.10. 8.80. C6 C7. 50 75. 160 140. 200 160. 10 10. 555.4314) 909.6814). 0.64 3.65. 6.00 6.88. 13.34 11.80. 0.19 0.62. C8 C9. 100 150. 200 200. 230 200. 10 10. 865.9414) 1162.5514). 2.39 3.85. 6.71 8.45. 10.72 12.82. 1.22 4.23. C10. 199. 200. 200. 10 1395.8513) 6.09 Clustered Problem. 9.88. 13.75. 9.91. C11. 120. 200. ∞. 0. 1042.1114). 14.83. 23.26. 35.69. 2.19. C12. 100. 200. ∞. 0. 819.5614). 0.00. 11.98. 23.54. 1.29. C13 C14 Average. 120 100. 200 200. 720 1040. 50 90. 1541.1414) 866.3714). 8.49 3.74 4.21. 15.14 11.24 9.99. 25.79 20.64 17.33. 2.31 1.22. prob. (a) (b) (c) (d). n 1000 1000 2000 2000. Q 500 500 1000 1000. 0 10 0 10. 42324 51818 49096 69016. 43076 52865 50210 69980. 44591 53844 51504 70897. 900. 800. 800. 700. 700. 600. 600. 500. 500. 400. 400. 300. 300. 200. 200 100. 0. 0 0. 100. 200. 300. 400. 500. 600. 700. 800. 900. 1000. 図 4 A best Solution of (b). 0. 図5. 100. 200. 300. 400. 500. 600. 700. 800. 900. 1000. A best Solution of (d). 5) Clarke, G. and Wright, J.: Scheduling of vehicles from a central depot to a number of delivery points, Operations research, pp.568–581 (1964). 6) Dantzig, G. and Ramser, J.: The truck dispatching problem, Management Science, pp.80–91 (1959). 7) Fisher, M. and Jaikumar, R.: A generalized assignment heuristic for vehicle routing, Networks, Vol.11, No.2 (1981). 8) Furukawa, M., Watanabe, M. and Matsumura, Y.: Local Clustering Organization (LCO) Solving a Large-Scale TSP, Journal of Robotics and Mechatronics, Vol.17, No.5, p.560 (2005). 9) Gendreau, M., Hertz, A. and Laporte, G.: A tabu search heuristic for the vehicle routing problem, Management Science, pp.1276–1290 (1994). 10) Golden, B., Assad, A. and Wasil, E.: Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries, The vehicle routing problem, pp.245–286 (2002). 11) Mazzeo, S. and Loiseau, I.: An ant colony algorithm for the capacitated vehicle routing, Electronic Notes in Discrete Mathematics, Vol.18, pp.181–186 (2004). 12) Osman, I.: Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, Vol.41, No.4, pp. 421–451 (1993). ´ Probabilistic diversification and intensification in 13) Rochat, Y. and Taillard, E.: local search for vehicle routing, Journal of heuristics, Vol.1, No.1, pp.147–167 (1995). 14) Taillard, E.: Parallel iterative search methods for vehicle routing problems, Networks, Vol.23, No.8 (1993). 15) Thompson, P. and Psaraftis, H.: Cyclic transfer algorithms for multivehicle routing and scheduling problems, Operations Research, pp.935–946 (1993). 16) Toth, P. and Vigo, D.: An overview of vehicle routing problems, The Vehicle Routing Problem, pp.1–26 (2002). 17) VanBreedam, A.: Improvement heuristics for the vehicle routing problem based on simulated annealing, European Journal of Operational Research, Vol.86, No.3, pp.480–490 (1995).. 表 2 Large Scale Problems proposed solution result L s best average worst time. ∞ 2000 ∞ 2500. 1000. 900. 100. Benchmark Problem and Proposed Solution Result best proposed solution result Q L s published best average worst time Uniform Problem. C1 C2. (d). 1000. 14.00 13.73 86.99 80.22. 6. ⓒ2009 Information Processing Society of Japan.

(7)