デリバリー・プランニング・システム

−速達配達順路作成機能の改良−

１　はじめに

　年間約２５０億通もの郵便物を全国あまねく翌日又は翌々日に低料金で届ける郵便サービスは、機械化・情報化による効率化の推進と、区分・輸送・集配等の郵便業務に代表される熟練担当者の膨大なノウハウの蓄積に支えられてきた。しかし、我が国の少子化・高齢化という中にあって今後これらのノウハウの継承はより困難なものとなることが予想される。
　一方、様々な計画問題解決のための意志決定を支援する方法としては、代表的かつ最も頻繁に利用される「オペレーションズ・リサーチ（OR）」等の科学的な手法があり、これらの手法は複雑かつ広範なノウハウの継続の困難さを克服し、かつより臨機応変なシステム改善を可能とする可能性がある。
　このため、今後のノウハウの継承の困難さを克服し、かつより臨機応変なシステム改善を可能にするため、このノウハウを継承しつつOR等の科学的手法を適用した意志決定支援の仕組みを構築し、業務の最適化・迅速化を図っていく必要がある。本郵政研究所技術開発研究センターでは、このような意志決定を行うためのOR手法等の検討及びこれらの手法を用いた意志決定支援システムの開発を目的として、平成６年度から「郵便処理における意志決定支援に関する研究」を実施している。
　本稿で述べるデリバリー・プランニング・システム（郵便配達業務支援システム）は、平成６年度に行った郵便処理における意志決定支援に関する調査研究の適用例の一つとして抽出されたものである。研究の目的は、これまで郵便外務担当者の知識と経験で行われてきた集配区画の調整案の作成及び速達郵便配達順路の作成をパソコンを用いて、より迅速にかつ適正に行うアルゴリズムを確認することに主眼をおいている。
　研究内容としては、平成７年度から８年度にかけて「郵便の配達区画調整システムの開発」を実施、また平成８年度から９年度にかけて「速達の配達順路作成システムの開発」を実施した。ここで、「郵便の配達区画調整システムの開発」及び平成８年度に実施した「速達の配達順路作成システムの開発」については、それぞれ郵政研究所月報No．９５（１９９６年８月）及びNo．１０７（１９９７年８月）に詳細に報告されているので、そちらを参照されたい。
　平成９年度には、デリバリー・プランニング・システムの機能の中の速達配達順路作成機能について改良を行った。その結果、非常に実用的な結果が得られたので報告する。

２　速達配達の現状とシステム要求課題

２．１　速達配達の現状と課題

　速達配達は、一日約３回（１号便から３号便）通常の郵便物とは別に手渡しで配達される、配達物数は便毎に異なるため、配達の担当者数及び担当地域を便毎に変えている。
　配達箇所は点在するが、配達地域は通常の配達区の数区分を合わせた広い地域（混合区と呼ばれている）となる。この広い地域の道順組立作業及び配達作業には、多大な労力と経験的なノウハウが必要なため、通区率が低い場合には要員配置に苦慮することとなる。
　また、実際の配達作業では幹線道路を主体として回る経験的な順路のパターンがあるが、これは必ずしも最短順路となっているとは限らずこの辺りにも検討の余地がある。

２．２　システム要求課題

　２．１に示すような背景を踏まえ、通区訓練中の非常勤職員等の速達等の道順組立作業を容易にし、配達作業時間の短縮及び効率的な要員配置を図ることを目的として、平成８年度から速達郵便物の配達順路作成システムの開発を行った。
　これらを達成するために考えられるシステム要求課題として、

1. 熟練担当者と同等の時間内に配達順路作成を完了すること。
2. 乗行機器に合わせた速度設定が可能であること。
3. 実際の道路状況（一方通行、Uターン禁止等を含む）を反映できること。
4. 経験的なノウハウの反映が可能であること。

があげられる。
　これらの課題を考慮して、速達の配達順路作成アルゴリズムに反映するようなシステムの開発を行うこととした。

３　速達配達順路作成システム

　本章では、今回の改良の基となった主に平成８年度に開発した速達の配達順路作成システムの概要と成果について報告する。

３．１　速達順路作成システムの概要

　速達配達順路作成システムとは、速達配達及び書留郵便物の夜間再配達を行う配達担当者が配達に出発する前に最短順路の考案及び郵便物の道順組立作業を支援するためのパソコンシステムである。
　配達担当者が、それぞれ１台のLAN端末を用いてキーボード等により配達郵便物の住所を入力すると、パソコン画面の地図上に最短順路案が表示されるとともに、配達地図、配達先リストがプリントアウトされる。ここで速達順路の作成において、組合せ最適化問題を解くためのOR手法を用いている。

３．２　ソフトウエアの最適化手法

　配達箇所を漏れなく巡回する効率的配達順路を作成する問題は、巡回セールスマン問題（Traveling Salesman Problem）と等価である。この問題は、基本的には巡回する箇所の順列をすべて調べる方法（列挙法）で最適解を見つけることが可能であるが、巡回する箇所が増えると箇所の組み合わせ数が爆発するため実用時間内では解くことができない。
　今回の目的である速達の配達順路作成問題の場合は、１人の速達配達担当者の配達担当地域の配達対象箇所の総数は、今回対象とした郵便局の場合、数千箇所以上となる。このため、２．２節で定義した実用的な時間内に列挙法で解くことはできない。
　このような問題を実用的な時間内で解くためには、近似的な解法を用いることとなる、代表的な近似解法として遺伝的アルゴリズム（GA）、シミュレーティッド・アニーリング（SA）等の確率的探索手法が考えられる。平成８年度に開発したシステムでは、まず初期順路を作成し、近似解法で評価しながら解く基本的な方法を用いた。また、配達箇所もすべての建物を対象とするのではなく、交差点から交差点までの街区の道路の一辺（リンク）をユニットリンクとして、このユニットリンクを巡回する配達箇所と再定義することによりアルゴリズムの効率化を図っている。
　初期順路の作成には、基本的な方法である最近接探索法（Nearest Neighbor法：郵便局を出発点として現在地点に最も近い配達箇所を探索する方法）を用いて作成することとした。
　近似解法としては、問題の解空間を広域に探索することができるGAと、最適性を追求することにGAよりは優れているSAを組合せたハイブリッドGAを採用した。
　また、確率的探索では短時間では十分な解の改善が得られない場合もある。このようなケースも想定して、確率的な探索のあとのローカルサーチとして２―opt法との組合せも実施することとした。

３．３　平成８年度の成果

　品川区を対象地域として、配達箇所の分散状況に応じて離散型、集中型及び混合型の３種類のパターンについて実験を行った。
　その結果、アルゴリズムの検証については、GA及びSAの世代交代数をいろいろ変化させて実験を行ったところ、SAによる改善を得るためには千回以上の世代交代を必要とする場合が多く、現状の計算能力では実用的な計算時間を超えてしまうことがわかった。計算時間を重視すると５００回程度のGAと２―opt法の組合せが実用解を得る方法としては適当であることがわかった。
　システムの最適化状況を表す図２では、世代数（計画回数）が増えるにしたがって、解の評価値（稼動時間）が改善されていく様子がわかる。そして、最終的には初期順路に対し１割程度の改善が得られている。図２以外の場合においても、最適化アルゴリズムを適用した結果、初期順路に対して１割程度の改善が得られた。この結果、今回開発した速達順路作成システムは実効性があり、有効性の高いシステムであるといえる。

４　速達順路作成機能の改良

４．１　平成９年度に残された課題

　３章に示したように、平成８年度に開発した速達順路作成システムは実効性があり、有効性の高いシステムであるといえる。しかし、実用性の面からみるといくつか残された課題があることも事実である。平成９年度はシステムの実用性を高めるため以下の改良を行った。

• 順路作成アルゴリズムの改良
• マンマシンインターフェースの改良

それぞれの改良点について考察する。

４．２　順路作成アルゴリズムの改良

　次の４点を中心として、順路作成アルゴリズムの改良を行った。

４．２．１　リアルタイム性の保証

　平成８年度のアルゴリズムでは、配達箇所が３０箇所程度になると計算時間が約５分かかる。これは待ち時間としては限界に近く、速達郵便物の特性を考慮すると少しでも早くしたい。このため今年度は索引表（インデックステーブル）を導入し、配達箇所が３０箇所の場合において１分以内に解を得られるように全体のソフトウエアのコーディング作業を実施した。

４．２．２　解の品質の保証

　本最適化アルゴリズムは３章で示すように近似解を求めている、このため解の品質が問題となる。このような最適化問題で最も重要なことは局所的な最適解（Local Minimum）に捕らわれないで、常に最適解（Minimum）が得られる必要がある。
　平成８年度は図３の(a)に示す様な単点探索方式を用いていた。単点探索方式では、世代数が少ない場合にMinimumであるDへたどり着く確率が低く、Local MinimumであるA〜CあるいはE〜Gになる確率が高い。そこで平成９年度は、図３(b)に示す様な多点探索機能を導入して少ない世代数においてもMinimumであるDが得られるように改良を行った。

４．２．３　解の安定性の保証

　有限の世代数で効率よくかつ安定的に最適解に近づくためには、初期順路の設定が重要である。平成８年度に開発した順路作成アルゴリズムでは、Nearest Neighbor法を採用した。Nearest Neighbor法の場合、部分的には最適な順路の組み合わせとなっている場合が多いが、全体的には効率が悪いことも多くある。
　そこで平成９年度は、Nearest Neighbor法に簡単な知識処理（AI）機能を導入して経路戦略等をあらかじめ盛り込むことにより、より効率的な初期順路を作成することができる。さらに、次に示すようなノウハウを反映した目的試行型協調推論を行うことにより安定した解を得られるようにした。

４．２．４　ノウハウの反映

　平成９年度に開発したアルゴリズムのもう一つの大きな目的は、熟練担当者のノウハウの継承である。これを実現するために、左折優先や幹線道路優先など各要素データに重み付けを行ったり、町区優先配達経路や一筆書き経路など個別に戦略を選択できるようにした。そして、最短時間経路にこだわらず、実際の経験的な配達経路を選択枝の中から実現できるようにした。

４．３　マンマシンインターフェースの改良

　平成８年度の速達郵便物の配達順路作成システムについての配達担当者からの意見として、出力地図が見づらい、操作性が悪いなどの意見があった。そこで平成９年度のシステムでは、出力地図として２，５００分の１相当の縮尺の住宅地図にも対応した。
　データの入力方法などのシステムの操作性については、他のシステムとの共通性を考慮して対応せず、画面表示機能や個別戦略の効果などアルゴリズムの使いやすさに限ったインターフェース機能の改善を行った。

５　評価実験と実験結果

５．１　順路作成アルゴリズムの改良

５．１．１　リアルタイム性

　索引表導入等のソフトウエアコーディングの効果を確認するため、配達箇所が３０箇所以上で世代数９０００世代の配達順路を作成するシミュレーション実験を実施した。
　シミュレーションの試行は様々な条件でそれぞれ３０回行った。この結果を表１に示す、表１においてケース１、２、３は配達箇所数がそれぞれ３０、３５、３０箇所で配達箇所のばらつきが異なっている。表１から、ソフトウエアコーディングによっていずれの場合も要求条件である１分以内に解を得ることができ、動作速度改善の効果が得られた。

５．１．２　解の品質

　安定した解の品質向上のため、多点探索機能を導入した。その効果を確認するため、GAの世代数がトータルで同じになる条件で単点探索と多点探索の性能比較した。配達箇所は３０箇所、各方式の試行回数は３０回としてシミュレーションを実施した。
　単点探索方式と多点探索方式の計画回数を等しくするために、単点探索方式では世代数を９０００世代、多点探索方式では３０個体による探索でそれぞれの世代数を３００世代として計算した。実験結果を表２に示す。
　表２から、多点探索方式の場合には個体数は多くなるが、世代数が少ないため結果的に処理時間が短くなり１．７倍の速度改善が得られた。また、多点探索機能の効果によって平均配達時間が１分早くなり、解のばらつきも半分となった。

５．１．３　解の安定性

　前項までのアルゴリズムは基本的に平成８年度のアルゴリズムを用いてそれぞれの改良を加えている。
　本項からは、平成９年度から採用している目的志向型協調推論を用いたアルゴリズムの結果である。本アルゴリズムでは、初期順路を設定する際に単純なNearest Neighbor法に知識処理（AI）機能を導入して配達順路全体の経路バランスをとることにより、初期順路から安定した経路が設定できる。配達箇所は３０箇所以上で試行回数は３０回としてシミュレーションを実施した。
　AI初期順路を導入した場合の解の安定性についての実験結果を表３に示す。最適解への到達率ではAI初期順路を導入した本年度方式の方が到達率が高い。また、解の平均値の最適解からのずれもどのケースの場合も最適解から１０％未満で安定して最適解あるいは最適解に近い値が得られていることがわかる。

５．１．４　ノウハウの反映

　これまでの改良では最短時間となる経路を最適解としてきたが、実際の配達の場合では左折を優先したり同じ町丁目を重視する等、配達する人のノウハウを反映させる必要がある。目的志向型協調推論を用いたアルゴリズムの目的の一つとしてこのノウハウの反映がある。
　品川郵便局の周辺３５箇所に配達箇所を設定したケース２の場合について、初期順路を設定する際に単純なNearest Neighbor法で配達順路を作成した結果を次ページの図４に示す。
　この地域は商店街と住宅街が入り組んでおり、かつ一方通行や右折禁止など経路設定上の様々な制約がある。図４においては、大井町駅西側のポイント�Aから�Kまでの地域を配達した後に駅東側の�Lから�S地域を順に配達し、駅の北側地域を配達した後に再び駅西側で(32）から(35)地域を配達している。
　この例では、配達時間も比較的かかり、なによりも地域の行き来が多く感覚的に配達しづらい。この理由として図４の経路は、初期順路にNearest Neighbor法を用いたことにより経路途中に取り残されたポイント(32)〜(35)が生じたため、入り組んだ形にならざるを得ない。
　この昨年度方式にAI機能を導入して配達順路全体の経路バランスをとって回るようにしたのが図５である。図４に比べ地域の行き来が少ないことがわかる。
　さらに町内優先と一筆書きになる戦略を協調させたものが図６である。最もすっきりした形となり、最適解とほぼ同程度の時間で配達できる。
　このように目的志向型協調推論を用いることにより、配達する人のノウハウを組み込んだ速達配達順路の提案ができる。

５．２　マンマシンインターフェース

　平成９年度のシステムでは、図４から図６に用いている道路地図のほかに、出力地図として２，５００分の１相当の縮尺の住宅地図にも対応した。これは昨年の検討項目の反映である。
　データの入力方法などのシステムの操作性については、新型区分機の情報を活用するなど、本システムを連動させるであろう他のシステムとの共通性を考慮する必要があるため、今回のシステムには組み込まなかった。しかし、画面表示機能や個別戦略の効果などアルゴリズムの使いやすさに限ったインターフェース機能の改善を行った。
　基本的な表示機能の拡張として、任意倍率による地図の表示が可能となった。これにより込み入っている地域の拡大や全体地域の把握などが行いやすくなった。
　今回のアルゴリズムの最適化状況を示すシステム評価グラフを図７に示す。平成９年度からノウハウを反映するために目的志向型協調推論を行うための様々な戦略を選択できるようになった。そこで、図２と異なり、システム評価グラフ上に戦略表示機能を付加して、配達地域の状況に応じてどのような戦略が有効であるかが確認でき、これにより効果的な戦略の選択が可能となった。　

６　おわりに

６．１　速達配達順路作成機能についてのまとめ

　デリバリー・プランニング・システムの機能の一つである速達配達順路作成システムの改良を実施した。この結果、リアルタイム性が向上し、かつ解の品質及び安定性を上昇させた。また、本システムの目的であった速達配達者のノウハウの反映が可能となった。
　図８は平成８年度に特定の住所への郵便物に対する熟練配達者の想定する実際の配達経路のヒアリング結果である。これに対し図９は本年度のアルゴリズムで同一町内優先や幹線道路による移動などの戦略を目的志向型で協調させて作成したルートである。この結果、かなり実際に近いルートの作成が可能であることが実証できた。
　このシステムはアルゴリズム的にはほぼ完成されたが、実用化に向けて、次に挙げるような課題も残っている。
�@アルゴリズムの検討
　実用化するに当たっては、配達担当者のノウハウを反映してより実用的な順路を作成するため、最短時間とあい反する要素をいかに順路の評価関数に取り入れるかを検討する必要がある。
　また、本研究では道路の一辺をユニットリンクと考えたが、今後は個別の配達箇所を回るより最適な順路を短時間で作成する方法の検討も重要である。
�Aデータ入力方法の検討
　速達郵便物の住所入力に関しては、キーボード、音声、ハンディスキャナとOCR等の組み合せなどが考えられるが、迅速で疲労の少ない住所入力を検討するとともに、機械処理対象の定型郵便物については、区分機からの情報の利用を考える必要がある。
�Bソフトウエアチューニング
　実際に利用するためには、適用する郵便局の配達パターンや配達局、配達地域の実データによる正確な地図データベースの構築が必要不可欠である。
　また、アルゴリズムを最適に運用するために、導入時等に熟練担当者に近いレベルまでの調整を行う必要がある。

６．２　デリバリー・プランニング・システムについてのまとめ

（参考文献）

・磯部他：「郵便配達区画決定支援支援システム（デリバリー・プランニング・システム）」　郵政研究所月報No．９５，pp．１１８−１２２，１９９６．８．
・磯部他：「郵便配達区画決定支援支援システム（デリバリー・プランニング・システム）」　第８回郵政研究所研究発表会　技術開発セッション発表論文No．１９９６−０３，１９９６．５．
・磯部他：「デリバリー・プランニング・システム」　郵政研究所月報No．１０７，pp．７９−９０，１９９７．８．
・磯部他：「デリバリー・プランニング・システム−速達配達順路作成機能の拡張−」第９回郵政研究所研究発表会　技術開発セッション発表論文No．１９９７−０２，１９９７．５．
・岩間他：「デリバリー・プランニング・システム−速達配達順路作成機能の改良−」第１０回郵政研究所研究発表会　技術開発セッション発表論文�G，１９９８．５．
・岩間他「速達郵便配達のための順路作成アルゴリズムの開発」１９９８電子情報通信学会ソサイエティ大会A―１３―２，１９９８．１０．