社内便の配送計画立案支援システムの作成と導入
M2012MM036

櫻井 裕

指導教員 : 三浦 英俊

1

はじめに
本研究では銀行で扱われる社内便の配送計画の問題について考える．銀行業務を進めるうえで重要な社内便でで，本研究では効率的な配送計画の作成を自動で行うためのシステムを短時間かつ低コストで作成し，実際の業務に反映させることを目的とする．

あるが，その配送計画の作成は熟練者の勘に頼っているところも多い．本研究ではこの配送計画の作成を自動化するシステムの作成と導入を試みる．

3

関連研究
この種の問題は配送計画問題として，既にいくつかの研究がなされている[1]．配送計画問題とは，デポ(depot)

2

社内便の現状と問題点と呼ばれる特定の施設に待機する運搬車によって, 顧客一般的に，複数の支店を持つ銀行は，本支店間を結ぶの需要を運搬(または収集)し, 再びデポに戻る. このと社内便を有している．情報技術の発達により，一般的なき顧客の位置・需要量・作業時間, 利用可能な運搬車台

企業においては拠点間の書類のやり取りにイントラネッ

数ならびに運搬車の最大積載量・最大稼働時間, 地点間トやファックス等の通信回線を用いるケースが増えているが，法令により紙ベースでの書類の作成および保管が厳格に定められている金融機関においては未だに多くの書類のやり取りを紙に頼っている．また業務の特性上現の移動時間・移動距離・移動費用などが与えられたとき,総移動時間・総移動距離・総移動費用・必要な運搬車台数などを最小化する顧客訪問順(ルート)を求める問題を指す．

金を扱うことも多く，このことから銀行では本支店間を結ぶ多くの社内便路線を有している．
このように銀行において重要な社内便であるが，その配送計画の作成には熟練者の勘に頼っているところも多い．また，回らなければならない本支店の数が数十から数百と多く，便によって回らなければならない本支店がその日によって異なるのが現状である．毎日必ず全支店を訪れる定期便に対し，必要に応じて派遣する運搬車（ここでは臨時便と称する．
）は派遣する支店がその日ごとに異なり，その都度配送計画を作成しなければならない．
この配送計画の作成には 3 つの問題がある．ひとつは熟練した経験者でなければ作成が困難なこと，その配送計

図 1：配送計画問題の概念図

画がコストなどの面から最適なものかどうかが不確かなこと，そしてこの配送計画の作成のために担当者が多くの時間を割いていることである．熟練した経験者でなければ作成が困難ということは，その者が欠勤もしくは退配送経路問題のバリエーションのほとんどは NP 困難(NP-hard)であり,厳密解法による本問題の解決は現実的ではない．近似解法としては，セービング法 (saving

職した際の対応が困難であり，不確かな計画に基づいたmethod)等が挙げられる. 多くの近似解法は, 顧客をグ運搬車の運用や，その計画の作成に多くの時間を割いてループ(クラスター)に分割した後に, 個々のクラスターいることは経費増加の一因となる．

に対してルートを設定する解法, クラスター先・ルート研究対象とした銀行でも同様に，配送計画の作成においては経験者の勘に頼って手作業で行われている．そこ後法(cluster-first/route-second method)に基づいている[2]．

4 問題解決の手順
配送計画問題解決のための近似解法にはいくつかの種類があるが，実際の業務時間内で実用可能な精度を得られる近似解法を実装するためには多大な開発コストと時間を要する．そこで，本研究では既にプログラムベースに落とし込まれたオープンソースの巡回セールスマン問
題の近似解法を用いてこの配送計画問題の解決を図る．
巡回セールスマン問題は，都市の集合と各 2 都市間の移動コスト（距離など）が与えられたとき，全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうち，総移動コストが最小のものを求める問題である．巡回セー
ルスマン問題もまた NP 困難であるが，その解決のための近似解法は数多く存在する[3]．また，それらの近似解法

図 3：移動時間を求める区間を実装したプログラムのソースコードが，オープンソースとして数多く公開されている．そのためこのソースコ最後に，分割したそれぞれのエリアごとに発着点と目ードを使用すれば，短時間かつ低コストでこの問題を解的地の入力を行い，これを巡回セールスマン問題として決するシステムの作成が可能となると考えた．

再度計算を行う．以上により，それぞれの運搬車が担当

本研究において，配送計画問題を解決する方法を次にするエリアと巡回経路が確定する．
（図 4）

示す．
まず，配送の拠点（発着点）および目的地を設定する．
この各点に対し，巡回セールスマン問題として近似解法を用いて一つの巡回経路を作成する．
（図 2）

図 4：確定した配送経路
このように巡回セールスマン問題として解決を図ることにより，短時間かつ低コストでの実装が可能となる．
また，本研究においては出発地から目的地までの 2 点間のルーティングおよび移動時間と距離の算出に Google
図 2：作成された巡回路
次に，この経路の最初の目的地から最後の目的地の間（図 3 で示す区間）の移動時間を求める．
得られた移動時間に対し，それぞれの時間が均等になるように目的地を運搬車の台数で分割する．ここで分割したエリアが，それぞれの運搬車に割り当てる目的地となる．

Maps™を使用する．Google Maps™は Google Inc.が提供するオンラインの地図情報サービスで，利用者は原則無料で使用することが出来る．また，Google Maps™には利用者が独自に作成したソフトウェアとの連携が可能な Maps
API と呼ばれるインターフェースが備えられている．このインターフェースは，二点の住所の入力に対して最新の道路地図に基づく二点間のルーティングと，移動時間および移動距離の応答を行う機能を備えている．本研究では二点間のルーティングに Maps API を用いることにより，コストの削減と一定期間ごとに行わなければならない地

表 2：実際の店舗配置に基づく試験結果
試験番号
厳密解
近似解
134.1km

34.1km以上が本研究における配送計画問題の解法である．こ267.0km

67.0kmの方法での解決に際し，次の 2 点の選定および評価を行

312.8km

13.3kmう．

487.4km

87.4km・巡回セールスマン問題に対する近似解法の選定

512.1km

12.1km

図更新の煩雑さを低減している．

・本方法により導出された解の評価
巡回セールスマン問題に対する近似解法の選定は，本実験の結果，6 店舗では厳密解との差はほぼ見受けられ研究で対象としている銀行の実際の店舗配置に基づき，ない．ただし，試験番号 3 については厳密解に対し，得特定の地域の 8 店舗を抽出してノードとし，実行時間とられた近似解は約 4％総走行距離が増加している．これは解の精度に着目して選定を行った．選定の対象とした近配送拠点に対して店舗が極端に偏って配置されているケ

似解法は，先行研究[4]を参考に貪欲法，最近傍法・2-optースで生じており，配送拠点から店舗への行き帰りの距法，蟻コロニー最適化（Ant Colony Optimization，ACO）

離を考慮できない本解法の欠点により生じていると考えの 4 つとし，プログラムのソースコードは Google code

られる．集配送拠点の配置によっては精度が低下するが，project において公開されているものを用いることによ得られた結果は概ね良好なものであったため，本システって実装期間の短縮を図った．

ムではこの解法を用いることとした．

選定の結果，本研究で用いる近似解法を貪欲法と蟻コ
ロニー最適化の 2 つに絞り，評価に用いるノード数を変化させて更に詳細な実験を行った．実験の結果を次に示す．

6 予想される導入効果
本システムを導入することにより，次のような効果が予想される．

表 1：近似解法の試験結果
最適解
貪欲法

ノード数・管理職（計画立案者）への負荷，人件費の軽減
ACO・合理的な配送計画による運搬車コストの削減

9個

26739m30263m26937m

試作中の本システムが導き出した解については現在評価

10 個

28167m34011m28563m

中であるが，仮にこの解を用いるとすると，研究の対象

11 個

28294m29758m29542mとした銀行においてはそれぞれ次のような導入効果が見込まれる．

12 個

36204m41211m

39404m

実行時間

412.56 sec.

0.0052 sec.

1.16 sec.

6.1 管理職（計画立案者）に関するもの
表 1 は 2 列目の最適解の値に対し，3 列目および 4 列目は近似解法によって求められた値が記載されている．結果

本システムの利用による計画立案 1 回分の管理職の負担削減と人件費の削減効果を次に示す．

が最適解に近いものほど精度が高い．実験の結果，精度と実行時間のバランスから蟻コロニー最適化を本研究に

表 3：導入により管理職に与える効果おける近似解法として用いることとした．

5 解の評価次に，比較的小規模な問題を用いて，先述の手法で導出した解に対する評価を行った．評価方法は研究対象とした銀行の実際の配送拠点 1 ヶ所に対し，目的地である支店をランダムに 6 店舗選び出し，これらを 2 台の運搬車で担当するケースについて厳密解との比較を行うことで評価を行う．
表 2 は 2 列目の厳密解の値に対し，3 列目は近似解法によって求められた値が記載されている．

導入前の作業時間は計画立案者及び同室スタッフへのヒアリングから試算した．作業コストについては計画立案の結果が得られた．

者の年収と勤務時間から，1 分あたりの作業コストを導出

なお，研究対象とした銀行では，配送に使用する運搬した．その結果，現状において計画立案者は臨時便の計車およびドライバーは外部の警備会社へ委託運用する形

画立案に前日の午後と当日の午前に計 3 時間程度を費やを採っており，コストは単純に使用する運搬車の台数にしている．

応じて決定する．そのため全運搬車の総走行距離の削減

仮に本システムを導入したとすると，計画の立案に要は，運搬車の使用台数を通じてメリットとなる．

する時間およびその人件費を導入前の 16.6％程度まで削減することが可能と考えられ，計画立案担当者に対する一極集中型の負担の削減と，立案に要するコストの削減が期待出来るものと考えられる．

7 今後の課題
現状では発着点や目的地の入力に際しテキストエディタを用いなければならないなど入出力の作業が煩雑であり，現場での使用に際してはユーザーインターフェース

6.2 現場（運搬車運用等）に関するものの改善が必要である．

次に，本システムの利用による現場（運搬車運用等）

また，本研究における解法は，研究の対象とした銀行に与える効果の試算を行った．この試算は，実際に計画の集配拠点に基づき，得られた解の評価を行っている．

立案者が作成した過去 5 日分の担当エリアの配送計画書

集配拠点の地理的特性が異なるその他の銀行等では得らを提供して頂き，担当者が作成した配送計画と，本シスれる解の精度が大きく変化する恐れがあるため，その他テムが出力した配送計画とを比較して行った．の地域や用途での使用に際しては再度解の評価が必要と考えられる．

表 4：手動で作成された配送計画に基づく運用結果
導入前

8 おわりに

日付

台数

総距離

コスト

本研究では，Google Maps™と巡回セールスマン問題の16288.2km

27.2 千円

近似解法を応用することにより，短時間かつ低コストで

2

6231.4km

27.2 千円

研究の対象とした銀行での実用に耐えうる配送計画作成

35231.6km

22.7 千円システムの作成と導入に取り組んでいる．結果，ユーザ

46276.4km

27.2 千円

ーインターフェースの問題を除いて概ね実用に耐えうる

56298.2km

27.2 千円と考えられるシステムを作成することができ，研究の対象とした銀行で運用した場合には，概算で年間 1,400 万導入前の各数値は，計画立案担当者によって手作業で作円程度のコスト削減効果が得られる見込みである．

成された配送計画にもとづいて運用された運搬車台数と，現在はユーザーインターフェースについて，外部の事

それらの運搬車の総移動距離，および運搬車の運用コス業者と協力して開発を行っている最中である．引き続き

トを表している．これらの各日付の出発地と目的地のデ利用現場と外部の事業者との調整を行い，最終的な目標ータを本システムに入力し，得られた結果を次に示す．

である実際のシステム運用を目指したい．

表 5：自動作成された配送計画での試算結果
導入後

参考文献

日付

台数

総距離

コスト

15229.5km

22.7 千円[1] 中原郷史， 小澤朋美， 武田好史， 「瀬戸市における資源ごみ回収ルートの最適化」, 卒業論文，南山大学
数理情報学部数理科学科，2007．

24184.2km

18.1 千円[2] 「配送計画問題」, http://goo.gl/zKDqlf, 平成 2534189.9km

18.1 千円

年 9 月．

45225.8km

22.7 千円[3] 山本芳嗣, 久保幹雄, 「巡回セールスマン問題への55239.1km

22.7 千円

招待」, 朝倉書店，1997.
[4] 関原啓太, 伊藤祐基, 和久田崇, 「蟻コロニー最適

このように，本システムによる立案では手動で立案され化を用いた渋滞時の巡回経路探索」, 卒業論文，南山大たものよりも少ない運搬車台数での配送が可能であると学数理情報学部情報通信学科，2008.