＝‖‖＝‖‖‖＝‖‖‖‖‖‖＝＝‖‖‖＝‖‖＝‖＝‖＝‖‖‖＝‖‖＝＝‖‖＝‖‖‖＝‖‖≠ll……l……ll……ll……l‖‖‖‖＝‖‖‖＝‖‖＝‖＝‖＝‖‖‖＝‖‖＝‖‖‖＝州………‖‖‖＝‖‖＝‖‖‖＝‖‖Wl……ll……l……l‖＝‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖仙

配送経路最適化の適用：銀行における配送を例として
岡野 裕之
Il…………lll…lll…lllll……l…l‖‖‖＝‖‖‖‖‖‖‖‖Wlll……l…＝‖‖‖‖‖刷Il‖＝‖‖‖‖‖‖‖‖冊Ill…llllll…………lll…llll……l…‖‖‖＝‖‖‖Wll…‖‖＝州………ll…‖‖‖‖‖川l‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖＝‖‖‖＝‖‖‖＝‖‖刑Ill‖‖‖冊l

1． はじめに報システムと呼ばれるソフトウェアの画面上で，イン近年デジタル通路地図が安価で入手可能になったこと，メタ・ヒューリスティックを中心とした最適化技術が発達してきたこと，計算機の能力が飛躍的に向上したことなどを背景に，各種制約を加味した実問題を扱う配送経路最適化が可能となってきた．それに伴い，配送経路最適化を適用して物流費の削減を試みる気運が，製造，販売，金融，運輸など多岐に渡る業種において高まってきた．これに対し筆者らは，実問題に適用することを目的として配送経路最適化の研究をタラクティブに実行するものを研究・開発中である．こ
こでは，入力データにおける問題の設定を変えながら何度も実行できるように，ある程度の高速性が求められる．

さらに，実装した解法を用いて実問題を解くためには，解法が扱う問題のモデル・制約条件を用いて実問題を記述（モデリング）しなければならない．ここでは，必要なら対象の問題を単純化したり，等価な別のモデルに写したりといった技法が用いられる．
本稿では，配送経路最適化の実問題への適用にまつ行っており，お客様の問題に適用してきた．
配送経路最適化は，ある拠点を基地とする車両の配送経路を扱う問題，拠点間の輸送における車両や人員の割付けを扱う問題など，配送形態により様々な問題に分類される．さらにこれらの問題には，扱うべき制約条件によって多数の変種が存在する．その中でも本稿で取り上げるのは，ある拠点を基地とする車両が，いくつかの地点を巡回しながら物品を集配し，元の拠点に戻るといったタイプの問題である．これは一般に車両経路問題（VehicleRoutingProblems（VRP））と呼ばれる．

VRPは様々な業種における配送形態をモデル化できる問題クラスであり，適用できる実問題の種類は多い．ただし実問題に適用する上では，様々なモデルや細かな条件を考慮することが要求されるため，遭遇するであろう問題をできる限り記述できるような，モデル・制約条件を扱う問題を定義しておく必要がある．
（ここでモデルとは巡回型であるといったような配送形態を指し，制約条件とは集配時間枠といったようなわる上記のような要点，すなわち，問題の定義，解法の設計と実装，モデリングについて，筆者らが行ったことを一つの企業事例として報告する．特にモデリン
グについては，銀行における配送業務への適用事例を通して紹介する．

2．問題の定義
VRPの基本的な問題を理解するために，文献でよく見られる時間枠付きVRP（VRP with Time Win−dows（VRPTW））を定義しておく．vRPTWで扱う拠点は1つである．これを便宜的に地点0とし，配達先を地点1，2，…，m，これらの地点の集合をⅤとする．
各地点宜∈Ⅴ＼（0）には配達量‰作業時間明，時間枠［eゎりが関連づけられており，必ず1回だけ訪問されなければならない．すべての車両は容量Qを持ち，時間e。に拠点を出発して地点を巡回した後，時間Joかそれ以前に拠点に戻らなければならない．ある車両の総配達量はQを越えてはいけない（容量制約）．また，各地点戌への到着時間α￡はg虐かそれ以前でなければな付加的な条件を指している．）
定義した問題に対する解法として筆者らは，地理情らない（時間枠制約）．ある車両が地点宜に時間α壷＜e豆に到着した場合，その地点ではe塩−α豆の待ち時間がおかのひろゆき 日本アイ・ピー・エム株式会社東京発生する．2地点盲，メ∈Ⅴ間の移動時間cjJは与えられ基礎研究所

る．このとき，必要車両数が最小の，さらに同じ車両〒242t8502大和市下鶴間1623−14数であれば総移動時間が最小の解（配送経路）を求め

E−mail：Okanoh＠jp．ibm．com

るのがVRPTWである．

604（18）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチこれに村し，筆者らが取り組んでいる配送経路最適化問題は，次のようなモデル・制約条件を扱う：
1．複数の拠点から多種類の車両が出発し，いくつかの地点を巡回し，元の拠点に戻る．

は，各拠点に割り当てられる経路の内，数が最大のものを最小化するというものである．これは，実問題をモデル化し最適化することを要請される中で，「ある地点は週に1回しか配送しない」といった長い視野の配送計画を立てる必要が生じ，それを取り入れるため

2．そのとき，必要なら途中何度でも拠点に立ち寄り荷物を積降しすることができる（車両の再利用）．
3．各地点では物品を，それぞれ指定された数量だけ配達するか，あるいは引き取る．に筆者らが導入したものである．これは例えば，物理的には1つしかない拠点を，月曜日の配送を受け持つ拠点，火曜日の配送を受け持つ拠点といったように仮想的に複数持ち，各地点をどれかの拠点に受け持たせ

4．任意の2地点に対し，一方で引き取った物品を他方に（同じ経路内で）輸送するように指定できる（順序制約）．

るというように用いる．毎日配送する地点についても同様に仮想的に複数持ち，それぞれを対応する拠点に受け持たせるように制約する．このように，モデル・

5．任意の2地点に対し，一方を訪問した直後に他方を訪問するように指定できる（隣接制約）．
6．各物品には重量，容積などに対応するいくつかの制約条件の記述をモデル化する場合にそれをどのような意味として用いるのかは任意である．

数億が関連づけられており，各車両にはそれらに対応する容量が関連づけられている．
7．各車両にはさらに，その車両が基地とする拠点，3．解法の設計と実装

VRPRC とVRPTWは共にNP−hardに属する組運転手の労働時間枠（9時から17時など），昼のみ合わせ最適化問題である．VRPTWの解法にはメ休憩時間（例えば12時過ぎから1時間）などが関タ・ヒューリスティックによる方法［1］や，経路集合連づけられている．

を列とする集合分割問題として形式化し，列生成に8．各地点には，集配する物品とその数量の他に，積よって解を求める方法などがある［2］．VRPRCの性質

降しに要する作業時間，集配時間枠，集配可能なは，順序制約を除けばVRPTWに近いため，基本的車両の集合と拠点の集合などを指定する．にVRPTWの解法を利用することができる．ただし，9．各地点間の移動時間は，デジタル道路地図上で得VRPRCが現在の仕様に至った経緯からも分かるようられる最短経路にしたがって与えられる．
これらのモデル・制約条件は，当初は文献で使用されるような基本的なもの（VRPTW）から始まり，銀行や製造業における実問題をモデル化し最適化することを要請される度に拡張を繰り返して，現在の仕様に至ったものである．上記のモデル・制約条件を扱う問題を，本稿では実問題制約付きVRP（VRPwithReal−worldConstraints（VRPRC））と呼ぶことにする．

このVRPRCには次の3つの目的を設定することができる：に，筆者らの目的では新しい制約を簡単に取り込むことができる柔軟な方法が望ましく，さらにインタラクティブに実行できる程度の高速性が求められる．したがって，それらの要求を満たしうるメタ・ヒューリス
ティックによる近似解法を採用している．この方法は，構築法，局所探索，メタ・ヒューリスティックの3つの部品で構成される．

3．1 構築法
構築法は初期解を生成する方法で，制約を満たす最も近い地点を次々に訪問する方法（最近傍法），それぞれ1地点だけを訪問する経路を地点の数だけ生成し，1■経路数（必要車両数）最小化

最もコストが減少する順にそれらを併合してゆく方

2．最大経路数最小化法（セービング法）などが用いられる．筆者らは最近

3．所要時間最小化

傍法にランダム性を加味し，何度も実行して最良解
ここで経路とは1つの車両の行程とする．車両の再利を選択している．構築法で得られる初期解は通常あま用をするので，1つの経路の途中で拠点に立ち寄る可りよくなく，すべての制約を満たしていない場合もあ能性があることに注意する．拠点を出発して拠点に着る．したがって，局所探索によって解を改善する必要くまでの行程をサブ経路と呼ぶ．最大経路数最小化とがある．

1999年11月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（19）605

． ． ︒ 三 賞 † ≒・う1
図3．パス交換

図2．パス移動

図1．パス反転・・︐・010−dr．f︑︑‡‡一室￣′二子

図4．放出連鎖3．2 局所探索

経路数最小化，最大経路数最小化の評価関数では，ペ局所探索は目的関数値（コスト）を減少するようにある解の近傍を見つけ，次々にその近傍に遷移してゆくことで，近傍の範囲でそれよりコストを減少できない解（局所最適解）を見つける方法である．目的関数，近傍，遷移規則の3つで定義される．まず目的関数としては，次の3つを組み合わせて用いている：

ナルティが増加せず，かつ経路数が減少する場合には経路長を気にしない．その他の場合は基本的に，所要時間とペナルティの合計を減少するように遷移するが，ペナルティが0の時には，経路数が増加する遷移を禁止している．

近傍を定義する近傍操作としては次のものを用いている‥パス反転（図1），パス移動（図2），パス交換

エ（β）所要時間（移動時間と停車時間の総和）
P（β）ペナルティ（制約違反を数値化したもの）
月（β）経路数（ただし，最大経路数最小化の場合は，各拠点に割り当てられた経路数の内で最大の数）（図3），放出連鎖（図4）．
パス反転（2−Opt）はサブ経路内の近傍操作で，パス移動，パス交換はサブ経路内およびサブ経路間の近傍操作である．これら3つは，解においてVRPTWの制

ここで，解βの近傍の解集合をⅣ（β）して，解f∈Ⅳ（β）

約を持つ部分を効率的に改善することで広く用いらに遷移可能かどうか（コストが減少するかどうか）をれている．放出連鎖（qiectionchain）は強い制約があ調べる評価関数ダ（β，才）＝（rⅣ）を，最適化の目的にる場合に有効な近傍操作として知られている．これは応じて次のように定義する：

探索の手間が大きいので，筆者らの実装では順序制約を持つ部分を改善するためだけに用いている．

経路数最小化，最大経路数最小化：
P（β）≧P（りand兄（β）＞兄（りダ（β，り＝Or高速に探索する手法が知られている．これらの近傍操

エ（β）＋P（β）＞エ（り＋P（りand作は2つの点を基点として探索される．例えば，反転（P（5），P（f）＞00r月（占）≧R（f））

otherwise
所要時間最小化：ダ（β，f）＝

するパスの始点と終点卜移動するパスの始点とその移動先が2つの基点である．このとき，一方の基点を含む近傍操作が所要時間を減少するには，もう一方の点

エ（β）＋P（β）＞エ（り＋P（りotherwise

606（20）

パス反転，パス移動，パス交換の3つの近傍には，はある探索半径以内になければならない．そのような探索半径は容易に計算でき，通常その半径以内に見つ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

かる基点の数は定数個程度である［3】．探索対象をれ・タブー探索（m）【7，8］点，見つかる点がた点として，0（氾log†l）時間の準備

・誘導局所探索（GLS）［9】をしておけば近傍点探索は0（た）時間で実行できる．

・遺伝的アルゴリズム（GA）［10］

また，VRPTWにおいては，近傍操作適用後に時間枠・適応型メモリ（AM）［11］

制約が満たされるかどうかは，0（1）時間で調べるこ・反復局所探索（ILS）とができる［4】．VRPRCにおいても，時間枠制約が満たされる「かも知れない」ことを0（1）時間で調べられSA，TA，GLSは，局所探索をコストの増加を許してるので，経路のスキャンが必要なコスト計算の回数を長く続けるタイプ．GAおよびILSは，高速な局所探効率的に減少できる．さらに，ある基点を含む適用可索を多数繰り返すタイプ．AMは，それまでに得られ能な近傍操作が「見つかりそうか」を示すフラグを基た局所最適解を用いて新しい初期解を生成する方法

点ごとに持っておくことで，局所最適解の質をあまりである．これはその他の方法と組み合わせることがで悪くせずに探索を高速化できる［5］．一度その基点かきる．筆者らは，以下で述べるような経路数最小化のらの近傍が見つからなければそのフラグをクリアし，機構のために，また高速性に対する要求を満たすため別の場所で適用された近傍操作にその基点が含まれに，局所探索を多数繰り返すタイプであるILSを採用ていればフラグをセットする．そして，フラグがセッしている．

トされている基点からだけ近傍探索を行う．

VRPTWのテスト・インスタンスを対象にして経遷移規則には，大きく分けて，最もコストを減少路数を最小化する場合，あらかじめ経路数の上限を設する近傍を選択するベスト改善と，最初に見つかった定して初期解を生成し，通常の経路で訪問しきれない遷移可能な近傍を選択するファースト改善がある．フ

地点をダミーの経路に組み込み，その経路にペナルテ

ァースト改善では，ある基点を含む近傍操作で最もよィを付加するといった手法が用いられる．例えば文献いものを探索し，基点ごとにそれを適用する．ベスト［12］では，すでに文献で知られている最良解での経路改善の方が1匝Iの局所探索ではよい解が得られるが，数を設定して最適化し，それで実行可能解が得られな実行時間がファースト改善に比べ約基点数倍かかるのい場合，その数に1あるいは2を加えた値を設定してで，単位時間内に実行できる局所探索の回数は少な再実行している．この方法は，最良解（あるいは最適い．その結果VRPRCでは，ファースト改善を用いて解）の経路数が既知の場合には有効である．筆者らの得られる局所最適解の方がよくなる．そこで筆者らは場合，最適解が未知のインスタンスを対象としなけれファースト改善を用いている．

ばならず，その場合に経路数をあらかじめ与えること局所探索をVRPRCの近似解法として用いる場合，は好ましくない．トラックの実際の保有台数を与える

次の2点に注意する必要がある．まず，パスの反転・ことはもちろん可能とするが，その内の何台使用すれ移動・交換を近傍操作とする局所探索では，時間制約ば十分かは計算で求めるべきである．そこで，初期解が強い場合に近傍が小さく，質の悪い局所最適解に陥で得られた経路を次々に1つずつ（場合によっては数個りやすいということ．そして，最適化の目的が経路数ずつ）選択し，それらにペナルティを付加して局所探最小化や最大経路数最小化でも，経路数を減少する近索を適用する方法を考案した．ペナライズされた経路傍が見つからなければ，所要時間を最小化するようにを収縮して消滅させるように局所探索が誘導される．

しか遷移しないという点である．これらの性質のため

目的関数と近傍で与えられる解空間を修正する（局所に，次々に局所最適解から脱出し，なおかつ（目的が最通解を非局所最適解であるように見せかける）といそうなら）経路数を最小化するように局所探索を誘導う意味で，これを目的修正法と呼んでいる．

するためのメタ・ヒューリスティックが必要となる．
3．3 メタ・ヒューリスティック

4．モデリング
実問題のモデルは，VRPRCのモデルと同一とは限知られているメタ・ヒューリスティックの内，VRPらないため，問題に合わせてVRPRCのモデルと問題のモデルをすり合わせる必要がある．例えば，2日間に使われるものには次のものなどがある：

で配送するように配達先を2つのグループに分けたい
・シミュレーテツド・アニーリング（SA）【6］1999年11月号

が，中には両日とも配送しなければならない配達先も© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（21）607図5．最適化結果ト1

図6．最適化結果1−2ある，といった類の問題は多く存在する．これは一見，ぞれ別々の曜日の計画と考える．現状の配送業務ではVRPRCのモデルでは扱えなさそうだが，1つの拠点各拠点の車両は1台なので，現状問題のモデルにおいを論理的に2拠点として表現し，拠点ごとの最大経路ては各拠点の車両数を最大5と制約する．仮定問題の数を最小化することで扱うことが可能である．またあモデルでは車両数を制限しない．

る場合には，モデルを単純化して解かなければならない場合もある．実問題を扱う動機には，配送形態を変更する時にコストがどう変化するかを見積りたい場
合と，日々の業務のための作業計画を作成したい場合の2つがあるが，前者の場合であれば少々の単純化は許されるのが普通である．そのような実世界での配送

結果：現状のモデルで最適化を実行すると経路数48の解が得られた（図5）．これはほぼ現実の経路数と同じである．各拠点の（5日分の）経路数は5以下なので，必要車両台数は計20であり，現実の数と一致する．与えられた仮定で最適化を実行すると経路数18の解が得られた（図6）．このとき，両拠点の経路数はそれぞ業務とそのモデリングの事例として，本稿では銀行にれ11と7であった．そこで，さらに両拠点の車両数おけるATMへの現金補充業務を取り上げる．

を最大10に制約したところ，両拠点の経路数が9の4．1 配送経路最適化の適用事例：銀行におけ解が得られた．これをそれぞれ5日分の計画と考えると，必要車両台数は計4台となる．

る配送業務

この銀行の場合，拠点はすでにある通常の店舗なの銀行では，無人店舗に設置されているATMへの現金の補充（あるいは回収）業務を行っている．扱う荷姿はATMに充填するカートリッジである．

で，配送拠点を集約しても拠点の維持費用は変わらない．しかし，車両台数は5分の1となり，したがって輸送費も約5分の1になることが判明した．

4．1．1 ケース1

問題：ある銀行では，ある県内の約200か所に設置し4．1．2 ケース2てあるATMに対し，現在20か所の拠点から現金補充

間蓮：ある銀行では，ATMが設置されている地点を2を行っている．ATMl台につきカートリッジの交換時つに分割し，それぞれへの現金補充を別々の業者A，B間は30分，現金輸送車の稼働時間は午前中の4時間に委託している．地点は必ずしも地区ごとに分離してで，各ATMには週5日の営業日の間に1回の補充をいない．配送の拠点は1か所である．業者Aに割り当行う．このとき，拠点を2か所（場所は与えられる）にてられた112地点の内，52地点は週1匝し60地点は週集約し，ATMl台あたりの作業時間を20分とし，現2回の補充を必要とする．業者Bに割り当てられた72

金輸送車を9時間稼働させることでコストは削減され地点の内，51地点は週1回，21地点は週2回の補充るか．ただし，作業者は昼に1時間の休憩をとる．

を必要とする．配送を行うのは週の内4日間である．

モデリング：この問題では曜日ごとの変則的な計画が作業時間は各地点ごとに細かく指定される．また，作必要ないため，VRPRCのモデルを使って素直に記述できる．すべての地点を含む1つの問題として解を求め，各拠点について得られた経路を5分割して，それ608（22）

業者は昼に1時間の休憩をとる．このとき，2つの業者を1つにまとめることでコストは削減されるか．
モデリング：拠点は1つであるが，論理的に2つの拠© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

点（拠点1，2）として表現する．入力データにおいて，週2便の地点をそれぞれ重複して表現し，一方には拠点1，もう一方には拠点2を指定し，それぞれ指定した拠点から配送を受けるように制約する．週1便の地点は1点として普通どおり表現し，拠点1，拠点2のいずれからでも配送を受けられるようにする．最大経路数最小化目的で最適化を行い，得られた結果の経路を，拠点1，拠点2のそれぞれで2つの集合に分け，そ

参考文献【1］E・H・L・Aarts，J・K・Lenstra（eds，）：LocalSearch

inCombinatorialOptimization，Wiley−InterscienceSeriesinDiscreteMathematicsandOptimization，
NewYork，1997．
［2】J・Bramel，D・Simchi−Levi：TheLogicofLogistics，

SpringerSeriesinOperationsResearch，NewYbrk，
1997．

れぞれ別々の配送日の計画と考える．
結果：現状のモデルで最適化を実行した結果，業者Aに委託している配送については拠点1，拠点2の経路数がそれぞれ10となり，業者Bに委託している配送についてはそれぞれ6と5になった．これはそれぞれ，車両数5台と3台に相当し，ほぼ現実の台数と同じで［3］N・Park，H・Okano，H・Imai：

Apath−eXChange−

typelocalsearchalgorithmforvehicleroutingand
its e伍cient search strategy，tO appearinJ．qf

O月gJ．

［4】M．W．P．Savelsbergh，Ane用．cientimplementation

ある．与えられた仮定で最適化を実行した結果，両拠Oflocalsearchalgorithmsforconstrainedrouting

点とも経路数が14となった．これは車両数7台に相problems

当する．

47，75−85，1990．

得られた結果より，現在2つの業者に委託している，EuropeanJ．qf Operations ResearY：h，［5］J・L・Bentley：

Fhst Algorithmsfor Geometric

配送業務を，1つの業者への委託に変更することで，TtavelingSalesmanProblems使用する車両を1台減少できることが判明した．

卵血糊4，387−411，1992．

，ORSAJ．onCom一【6］S．Kirkpatrick，C・D・Gelatt，Jr．，M・P．Vecchi： Op−
timizationbySimulatedAnnealing

5． おわりに，Science，220，671−680，1983．

配送経路最適化の一例として，問題の定義，解法の設計と実装，モデリングについて，筆者らの研究を紹介し，その適用例として銀行における現金輸送の事例を紹介した．

【7］F・Glover：

TabuSearch，PartI，ORSAJ・On

Co†r岬祝如タ，1，190−206，1989．
［8】F・Glover：

TabuSearch，partII，ORSAJ．on

Co叩p那加タ，2，4−32，1990．

取り上げた事例ではいずれも，配送業務を変更することで現状の配送コストを削減する余地があるという結果を得た．これは，これまで経験と勘による手計算に頼ってきた配送計画を，デジタル道路地図と最適化技術を組み合わた配送経路最適化によって，幅広い［9］C・Vbudouris，E・Tsang：

Guidedlocalsearch，二陀chnicalR印Ort CSM−247；Department ofCom−
PuterScience，UniversityofEssex，1995．
【10］J・H・Holland： AdaptationinNaturalArtificial

方面で大きく改善できる可能性があることを示唆しSystems ，University qFMichi9anPrt：SS，AnnAr−ている．例えば，配送経路最適化は手計算と比べ格段

bor，MI，1975．に高速であることから，固定の定期便による配送に替【11］Y・Rochat，E・Taillard： ProbabilisticDiversifica−

えて，配送計画をその日の朝に組み上げることも可能

tionandInten＄ificationinLocalSearchforV6hicle

である．あるいほ需要予測と連動した，中期的な配送

Routing ，J．げ月七視r由￡豆cβ，1，147−167，1995．

業務委託契約の見直いこ用いることも可能である．このほかにも，様々な方向への応用が可能である．

技術的な今後の課題としては，VRPRCのモデル・制約条件にさらに一般性を持たせること，各地点での在庫量を考慮すること，より大規模な問題に対応する【12】P．Kilby，P．Prosser，P．Shaw：

Guided Local

SearchfortheVbhicleRoutingProblemwithTime
Windows，inS．Voss，S．Martello，Ⅰ．H．Osman，C．

Roucairol（eds．），META−HEURISTl−ag，Kluwer
AcademicPublishers，473−486，1999．

ために並列化実装することなどがあげられる．

1999年11月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（23）609