調査・研究

［要約］

１. はじめに

　年間240億通もの郵便物を全国あまねく一定日数内に低料金で届ける郵便サービスは、機械情報化による効率化の推進と、集配・区分・輸送等の郵便業務計画に代表されるベテラン担当者の膨大なノウハウの蓄積に支えられてきた。しかし、今後、複雑かつ広範なノウハウの継続の困難さを克服し、かつより臨機応変なシステム改善を可能にするため、このノウハウを活かしつつ、オペレーションズ・リサーチ（OR）等の科学的手法を適用した意思決定支援の仕組みを構築し、計画決定の最適化・迅速化を図っていく必要がある。
　そこで、技術開発研究センターでは、このような意思決定を行うためのOR等の手法の検討及びこれらの手法を用いた意思決定支援システムの開発を目的として、平成６年度から「郵便処理における意思決定支援に関する研究」を行っている。ここで述べるデリバリー・プランニング・システム（郵便配達業務支援システム）は、平成６年度に行った研究調査の中で意思決定支援システムの適用例の１つとして抽出されたもので、これまで担当者の知識と経験で行われてきた郵便配達区画の設定、速達配達順路の考案を、パソコンによるシステムを用いてより迅速にかつ適正に行うことを目的として研究を進めているものである。本システムは、各配達区の作業時間の算出等に基づいて区画調整案を作成する機能をもつ区画調整モジュール及び速達・夜間再配達等の最適な配達順路を作成する機能を持つ順路作成モジュールからなる。

２. 研究の背景

2.１　海外の事例　［１］、［２］、［３］
　配達ルートの最適化はフランス等で研究されているが、カナダで実用になっているPOSTCARDS (Computer Aided Route Design System)がここで考えているシステムに近いものである。
　POSTCARDSは、パソコン上で地図情報データベースにより効果的な配達ルートの決定、配達担当者の作業時間管理等が視覚的に行えるシステムで、1987年から先行導入が開始された。画面上に配達人毎の経路が色分けされて表示され、配達に要する時間等が計算される。カナダでは、専任の配達ルート選定マネージャと呼ばれる職種があり、人口移動や郵便配達区の変更に伴い、全国の配達ルート（日本では配達区に相当）の見直しを行っているが、このシステムによって全国の配達箇所をみるのに５年かかっていた作業が17ヵ月に短縮され、残りの時間を別のマネージメント業務に当てることができるようになった。また、1.2％の配達区の削減が行われた。
　95年の調査時点で、カナダポストで使われている計算機は、CPU：486 50MHz、メインメモリ12MB、ハードディスク340MBのノートパソコンである。システムに必要な地図情報及び物量情報は、それぞれ別のシステムからオフラインで取り入れている。

2.２　配達業務の現状と課題

2.2.１　配達業務の概要
　配達業務は、大きく局内作業と局外作業（配達）に分けられる。局内作業のほとんどは郵便物を配達順に並べる「道順組立」で、これは、配達担当者毎に区分された郵便物を、まず数十口ある区分棚を用いて街区等を単位に区分する大区分と、この大区分された郵便物を配達順路に従って並べる戸別組立の２段階からなる。大区分口は街区符号や番地の順に従って１つが50世帯程度に設定されている。道順組立が完了した郵便物は、バイクあるいは自転車によってあて先に配達される。通常郵便物の１日の配達回数は、ほとんどの地域で１回である。
　平成10年２月から導入予定の新郵便番号制における新しい処理では、現在配達担当者が手作業で行っている道順組立までが機械化されるため、局内作業が少なくなり、１人当たりの配達区域が広がる。また、担当エリアを地域で分割する従来の方法とは違って、配達区数区分をまとめた地域内で一筆書きのルートを作り、その日の物数により担当のエリア（ルートの区切り）を変える「エリア配達」と呼ばれる方法があり、この導入が推進されつつある。このような状況に対し区画調整等の配達計画がより適正に行われる必要がある。

2.2.２　区画調整とその課題
　配達区は、その区画の平常時における１日の配達物数を１人が所定の時間内に処理できる大きさの適正な区画となるように設定されている。区画決定の要素としては物数、配達手段（バイク、自転車等）、地況、道路状況等があり、ビルやマンションの建設等によりこれらが変化した場合に見直し（区画調整）が行われる。
　配達区画の調整が必要かどうかは次の項目により総合的に判断する。
�@　実際に配達に要している時間を分析。
�A　地況（住宅、道路）、物数、箇所数の変化。
�B　作業方法（標準作業方法、順路）は適当か。
�C　標準時間（物数、箇所数、距離、速度等により計算される）と実働時間の比較。
　上記の検討の結果、調整が必要と判断された場合には、大区分口毎の物数、箇所数に基づく作業時間を用いて調整が行われる。
　区画調整作業は、複雑かつ多くの経験・知識を要すること、必要なデータの収集・整理に多大な労力を要することから、ビルやマンションの建設等の地況変化への素早い対応が困難になっている。

2.2.３　速達配達とその課題
　調査を行った都市部の郵便局における速達配達では、一日約３回通常郵便物の配達とは別の担当者が手渡しで配達する。配達物数は各回によって異なる（午前の１回目と、書留の夜間再配達が加わる夕方の３回目が多く数十通から百通程度）ため、配達担当者数及び担当地域を回毎に変えている。配達箇所は点在するが、一人が担当する地域は通常の配達区の数区分を合わせた広い地域（「混合区」と呼ばれている）となる。この道順組立作業及び配達作業は、いくつかの区に精通している担当者が十分な経験とノウハウに基づき行っている。このため、不慣れな新規採用者や非常勤職員等は、この業務に割り当てられず担務の指定に苦慮しているのが実情である。また、実際の配達作業では、幹線道路を主体として回る経験的な順路のパターンがあるが、計算機の結果が改善のヒントを与える可能性がある。

３. 研究のねらい

　デリバリー・プランニング・システムの研究開発は上記のことを背景として郵政研究所が自主的に行っているもので、実用に耐える区画や順路作成のアルゴリズムの研究に主眼を置いている。
　実際には、ORの最適化手法（例えば遺伝的アルゴリズム）に直接加味しきれない経験的なノウハウあるいは作業全体としての効率性が存在し、これらは最適化とあい反する場合あるいは最適化に全てを含ませられない場合がある。例えば、順路としては最短でなくても、住居表示の序列性を活かした方が局内作業も短縮されるので、作業時間全体として効率的となることがある。これらをどの様にあるいはどこまで取り入れて実用的なアルゴリズムにするかという点が、区画調整、順路作成両アルゴリズムについて共通にいえる開発ポイントである。
　また、都市部の通常配達の順路は、ほとんどすべての道路を少なくとも１回通って配達する最適ルートで、この最適化アルゴリズムは、この種の業務ではまだ実用例のない新規性の高いものである。
　本システムの導入により、業務が効率化されるばかりでなく、配達時刻の問合せに対する対応等のサービスの向上を図ることも可能となる。

４. 区画調整モジュールにおけるアルゴリズムの検討

4.１　モジュールの概要
　このモジュールは、前回の区画調整からある一定期間経過した後、あるいは地況変化により増区あるいは減区が必要な場合に計画担当者が用いるパソコンシステムで、一定時間内で効率良く配達作業ができる配達区を指定することと配達区毎の負荷を平準化することを目的としている。　アルゴリズムでは、作成された区画に対して、配達物数、箇所数、密集度等から、配達時間、局内作業時間を含めた総作業時間を算出し、これにより各配達担当者の作業量の平準化度合を評価する。ある程度平準化が進むまでパソコンが自動的に計算するが、計画担当者が出力結果にマニュアルで変更を加えて、パソコンに評価させながら修正することも可能である。

4.２　問題のとらえ方
　ここでは、調整の考え方、調整の単位、使用するデータについては、現状の方法をある程度踏襲することにした。　配達順路、配達区画設定において、実際にはいくつかの原則があるが、特に次のものは本アルゴリズムの検討でも考慮すべきである。
�@　配達順路は住居表示番号の降順又は昇順で道路の片側ずつ配達。特に都市部の密集地ではこの方が局内作業が短縮され、全体として効率的な場合が多い。
�A　配達区画は町、丁目、字を基本単位に設定。河川、鉄道、幹線道路横断はなるべく避ける。
　配達区毎の作業時間の平準化を目的とする区画設定と作業時間の短縮化をめざす順路作成は相互に関係しあう。アルゴリズムの考え方として、次の３つが考えられる。
�@　まず初期区画を与えて、区毎のルートを考慮しながら区画案を評価し、改善していく方法［２］。
�A　先に対象エリア全体のルートを引き、それを分割する形で区画を設定し、その中のルートを改善する方法。
�B　小単位のルート（サイクル）を結合しながら、ルートと区画を同時に作成する方法［３］。
　今回は、現状の区画調整に近い�@を採用することとした。

◎　ユニット区の設定
　区画調整を行う場合、調整の最小単位（ユニット区）をどう設定するかは一つの課題である。ユニット区としては、大区分口、街区（道路で囲まれた部分）、道路の一辺（リンク）などが考えられる（図２参照）。大区分口は、配達大区分を行う時の区分単位で、現行の区画調整に使われており、街区をまとめてある場合も街区を分割してある場合もある。
　ユニット区が細かくなるほど平準化の精度はあがるが、ユニット区情報（配達物数、配達箇所数、走行時間等）のデータ量が増大するとともにデータ取得が困難になるという問題点がある。例えば、リンクをユニット区とするとその数は、街区数の５倍くらいになる。平準化の要求度合、住宅密集度等の地域性によって、適度なユニット区を設定する必要がある。
　ここでは、使えるデータが大区分口毎で、道路の一辺毎に分割するのは困難なこと、道路ネットワークデータとの対応がとりやすいことから、街区をユニット区として採用することとした。

4.３　最適化アルゴリズム
　区画調整アルゴリズムには、�@適当な初期値から隣接ユニット区を交換し改良していく方法、�Aユニット区の選択の方法を決定していく方法等が考えられるが、ここでは�@の方法の中で、高速で近似解が得られる遺伝的アルゴリズム（Genetic Algorithm:GA）とシミュレーテッド・アニーリング（Simulated Annealing:SA）を採用し、両者を比較することとした。どちらのアルゴリズムにおいても、基本的には、配達区を構成する街区の内、境界街区群の中からの適当なものを抽出して、それを作業量の低い配達区に移動することと、適応度（各配達区の作業量の標準偏差の逆数）を評価してより最適な案を残すことを適当な回数だけ繰り返すことによって最適解を得る。ただし、街区を移動した後、元の配達区の平面的連属性をチェックし、飛び地が発生しないようにする。
　今回、GAでは配達区の境界街区を取得し、その移動パターン（０：移動なし、１：移動あり）を初期個体として作成するコーディング方法を採用しているため、境界街区が初期配達区設定の段階で決まってしまう。一方、SAでは境界街区は配達区の更新処理により変化していくので、GAよりも最適性に優れる可能性がある。そこで、ここではSAによる処理フロー（図３）を説明する。
Ａ：予め設定したある初期配達区情報を基に、配達区の境界街区を取得する。図３では、街区０、１、３、４、５、６、７、８が境界街区として取得されることになる。
Ｂ：取得した境界街区の内、任意に移動対象街区を選択する。
Ｃ：移動対象街区を隣接する配達区の内、負荷の最も小さい配達区に移動する。このとき、移動元の配達区において平面的連続性が失われる場合、街区移動は取り消す。
Ｄ：街区を移動した後、移動元、及び移動先配達区の負荷を再計算して、当該街区の移動に関する適応度を算出する。ここで、当該街区の移動に対応する適応度が悪化した場合もある確率でその移動を許可し、確率外となる移動は取り消す。なお適応度の悪化を許す場合、移動前の区画調整案は一時的に退避しておく。
Ｅ：ＡからＤまでの処理を適当な回数だけ繰り返して求めた区画調整案と退避してあった区画調整案の適応度を比較して、優れた適応度を持つ案を出力する。

4.４　最適化度合の評価
　区画調整の平準化の度合を評価するには、総作業時間の標準偏差を用いている。そして、適正に評価するためには、配達物数、配達箇所数、走行距離、配達箇所の密集度、種類（個人住宅、集合住宅、事業所等）などの基礎データから、ユニット区毎に局内作業時間、配達に要する時間を精度良く算出することが重要である。この精度をどこまで上げる必要があるかは検討しなけばならないが、精度を上げるためには、道路から郵便受箱が離れている場合の位置（道路からの奥行き、ビルの階数）など新たなデータの取得が必要である。また、密集度による配達時間の違い等の算出方法を検証するためには、実際にかかっている時間を計測する必要がある。さらに、局内作業時間は、必ずしも物数、箇所数だけではなく、住居表示の序列性による作業速度も影響するので、区画あるいはルートの決め方も含めて考慮する必要がある。
　ここでは、総作業時間は以下の式により算出した。
　　　総作業時間＝局内作業時間（道順組立時間）＋
　　　局区間移動時間（郵便局から配達区までの移動時間）＋
　　　配達時間（配達しながら移動する時間）＋
　　　その他の時間（車両点検等一定時間）
　ここで、局内作業時間は物数を用いた標準時間の算出方法により求め、局区間移動時間及び配達時間は、それぞれの距離を物数調査結果から洗い出した平均的速度で割った値とした。

５　順路作成モジュールにおけるアルゴリズムの検討

5.１　モジュールの概要
　本モジュールは、速達配達及び書留郵便物の夜間再配達を行う配達担当者が配達に出発する前に最短順路の考案及び郵便物の道順組立作業を支援するための機能を備えている。配達担当者がそれぞれ１台のパソコン（LAN端末）を用いてキーボード等により配達郵便物の住所を入力すると、パソコン画面の地図上に最短順路案が表示されるとともに、配達地図、配達先リストがプリントアウトされる。

5.２　問題のとらえ方
　配達箇所を漏れなく巡回する効率的配達順路を作成する問題は、巡回セールスマン問題（Traveling Salesman Problem）と等価である。この問題は、基本的には、箇所の順列をすべて調べる方法（列挙法）で最適解を見つけることが可能であるが、巡回する箇所が増えると箇所の組み合わせ数が膨大となるため実用時間内では解くことができない。例えば、配達箇所が20箇所で10１８以上の組合せが発生する。このような問題を実用的な時間内で解くためには、近似解法として遺伝的アルゴリズム(GA)、シミュレーティッド・アニーリング(SA)等の確率的探索手法が考えられる。
　バイクによる順路を作成する際、一方通行を考慮することは重要な要素である。これを可能にするため、道路ネットワークとしてリンクとノードの結合を定義する際に、一方通行の場合は片方向のみのリンクを、両側通行の場合、両方向のリンクを定義している。また、幹線道路優先、左折優先等を考慮するため、リンクの属性として道路の区間距離のみでなく、移動速度、右折時間等を与えられるようにしている。

◎　ユニットリンクの設定
　１人の配達担当者の担当地域の配達箇所の総数は、今回対象とした郵便局の場合数千箇所になる。巡回セールスマン問題を解くにはネットワーク上の都市間距離がわかっている必要があるが、数千箇所の相互間の距離を求めるのは現実的でない。そこで、いくつかの配達箇所をまとめたユニットリンクという概念を導入する必要がある。新住居表示がされている都市部では、街区が整備され道路の一辺に10箇所位までの配達箇所が属している。ここでは、図４に示すように道路の一辺（リンク）に属する配達箇所をユニットリンクとした。

5.３　最適化アルゴリズム
　サービスユニットリンクの巡回順を求める問題を解くための確率的探索手法としてGAが考えられるが、できるだけ早く良い解を見つけ出すには複数のアルゴリズムを組み合わせることがよいとされている［４］　。そこで、問題の解空間を広域に探索することができるGAと、最適性を追求することにGAよりは優れているSAを組み合せたハイブリッドGAが１つの案として考えられる。
�@　初期順路
　確率的探索手法では、評価値を改善するための初期順路（初期個体）が必要であるが、ここでは、配達順路作成としては基本的な方法であるNearest Neighbor法（郵便局を出発点として近い順に配達箇所を並べる方法）を用いて作成することとした。この時、任意の２つのサービスユニット間の最短距離は、最短ルート探索アルゴリズムとして一般的なダイクストラ法を用いて予め計算しておく。
�A　遺伝的操作
　Nearest Neighbor法で初期順路を作成した場合、部分的には、最適解と同じ巡回路を含むことが多い［５］　。したがって、GAの１世代の更新の過程（交叉や突然変異といった遺伝的操作）によって、そのような順回路が崩されるようなことは避けることが望ましい。そこで、サービスユニットリンクの順列をGAの個体表現とした場合、交叉は行わず、山登り法で用いられる順路の一部（サブ・ツアー）を逆順に並び替えるリバース処理を遺伝子操作（突然変異）として行うこととした。山登り法と異なる点は、リバース処理の基点となる２点を戦略的に行うのではなく、確率的に選択することでGAの突然変異の特徴を踏襲していることである。
　この方針を採った場合、局所解に陥りやすいと言われているので［４］　、今回は、局所解の脱出効力を持つSAをGAの処理後に組み合わせるハイブリッドGAを採用することとした。SAでは、評価値の差分と温度（計画回数の逆数）で決まる確率で改悪の場合であっても解を更新している。
　また、確率的探索では確率変動の状況によっては短時間で十分な解の改善が得られないことも考えられるので、この影響をより少なくするために確率的な探索のあとのローカルサーチである2-opt法を近傍のサービスユニットリンクに対して行うこととした。今回のアルゴリズムの処理フローを図５に示す。

5.４　最適化度合の評価
　順路の評価は、今回は計算に負担をかけないために移動時間（距離÷一定速度）で行うこととし、次式により算出している。
　　評価値＝郵便局と最初の区の間の移動時間＋
　　区自身の移動時間の合計＋区間の移動時間の合計＋
　　最後の区と郵便局の間の移動時間

６. 実験システムの概要

6.１　システムの構成
�@　ハードウェア　パソコン（Windows95、CPU:Pentium200MHz、メモリ80MB）
�A　ソフトウェア
　プログラム本体：約600kB
　データ：背景地図、道路ネットワーク、最短距離情報（昭島局の場合約33MB）
�B　地図データ　
　郵便地図をベースとしたイメージ地図とイメージ地図上で入力した道路ネットワークデータ（ノード、リンク、距離）

6.２　ソフトウェアの主要機能
　本ソフトウェアは、配達物数等物数調査データを入力・変更できる機能、地図データを入力・変更できる機能及び各種アルゴリズムにより配達区の区画調整、配達ルートの計画（以下計画と呼ぶ）立案機
能等、表１に示すように大きく分けて７種の機能をもつ。

７. 実験方法及び結果

7.１　区画調整実験
　今回、都市密集地として品川区、郊外住宅地として昭島市の１部を実験対象地域に選び、物数を街区単位で想定し、現行に近い配達区で初期値を設定し、GA及びSAにより繰り返し回数を変化させて配達区画調整を行った。
　品川区における区画調整結果（対象地域の一部）を初期値とあわせて図６に示す。実験の結果から次のことがわかった。
�@　SA、GAとも作業時間偏差が初期値（50分）に比べて、20分程度まで少なくなり、かなり平準化される。
�A　SAはGAよりも同じ繰り返し回数に要する時間が1/18位ですむ。また、GAのほうが少ない回数で最適化されていくが、１回に要する時間が長いので、SAの方が時間的処理性に優れている。
�B　SAの方がGAに比べてより平準化される。これは、基本的にはSAの方が境界街区が変わっていく点で調整の自由度があるからである。特定の配達区に物数変化を与えた場合のSAとGAによる結果では、今回は実験の回数が十分でないため、顕著な傾向が見られなかった。

初期配達区画	調整後の配達区画

7.２　速達順路作成実験
　アルゴリズムの検証については、GA及びSAの世代交代数をいろいろ変化させて実験を行ったところ、パターンや箇所数によって改善が得られる世代交代数が異なる。SAによる改善を得るためには千回以上の世代交代を必要とする場合があり、その場合は現状の計算能力では実用的な計算時間を超えてしまう。実用的な時間内で解を得ることを前提とすると、今回の実験では、多くの場合500回程度のGAと2-opt法の組合せにより実用解が得られることがわかったが、より詳細な実験が必要である。
　GAと2-opt法の組合せによる品川区及び昭島市の各ケースの実験結果を表２に示す。表の値は移動時間のみの値であるが、どのケースにおいても初期解に対して１割程度の改善が得られている。
　最適化状況を表す図７では、世代数（計画回数）が増えるにしたがって、解の評価値（稼動時間）が改善されていく様子がわかる。実験で得られた順路の一例を図８に示す。郵便局の周辺の通行規制の関係で右回りの順路になっているが、それを除けば担当者が実際に回る順路に近いものになっている。

８. おわりに

　ここでは、デリバリー・プランニング・システムにおけるアルゴリズムの検討結果及び実験結果について述べた。区画調整モジュールの開発では、配達物数・箇所数・走行距離等により算出した各配達区の業務量を評価値とし、SAによるアルゴリズムを用いて区画の平準化が行えることがわかった。また、順路作成モジュールの開発では、遺伝的アルゴリズムを基本としたアルゴリズムを用いて、一方通行等を考慮しながらサービスユニットリンク（道路の一辺）を回る配達順路の作成が可能なことがわかった。
　今後、次のような課題が考えられる。
�@　区画調整における課題
　実際の区画調整では、町丁目や鉄道、幹線道路等の境界条件が設定されることが多い。アルゴリズムの中に境界条件重視ということを加味しながら、かつ、計算機では困難な部分については、人の判断を組み合わせるといったシステムの検討が必要である。
�A　順路作成アルゴリズムの改良
　道路の属性として右折時間、移動速度等を加えることにより左折優先、幹線道路優先の順路が作成できるようにする。配達担当者のノウハウを反映してより実用的な順路を作成するため、最短時間とあい反する要素をいかに順路の評価関数に取り入れるかを検討する必要がある。
　また、今回は、道路の一辺をユニットリンクと考えたが、個別の配達箇所を回るより最適な順路を、短時間で作成する方法の検討が重要である。
�B　実用化に向けての検討
　例えば、住所入力に関しては、キーボード、音声、ハンディスキャナとOCRの組合せ等が考えられるが、迅速で疲労の少ない住所入力を検討するとともに、機械処理対象の小型通常郵便物については、区分機からの情報の利用を考える必要がある。
�C　データベースの共有
　実用段階においていかに低コストで地図等のデータベースを整備するかが大きな課題である。データベース整備と更新の低コスト化のためにも、配達総合情報システムや将来的に可能性のある郵便地図情報システム等の他の情報システムとのデータベースの共有を考慮すべきである。
　本研究は、今後、計画担当者の評価を得て、先に述べた課題等に対して検討を続けながらアルゴリズムの改良を行う予定である。また、並行してシステムの処理性能の改善、操作性の改良等を進めていく予定である。

参考文献

［１］　"Canada Post's Experience in Applying Computerized Techniques to Redesign Mail Delivery Routes", 11th International Conference on Postal Mechanisation, Melbourne, 1994. 3.
［２］　L. Levy: "The Arc Oriented Location Routing Problem", INFOR Vol.27, No. 1, 1989.
［３］　S. Roy, J.M. Rousseau: "The Capacitated Canadian Postman Problem", INFOR Vol. 27, No. 1, 1989.
［４］　北野編：「遺伝的アルゴリズム」、産業図書、1993.
［５］　久保：「巡回セールスマン問題への招待�T�U�V」、オペレーションズ・リサーチ誌、1994.１〜３.
［６］　磯部他：「郵便配達区画決定支援システム（デリバリー・プランニング・システム）」郵政研究所月報No. 95、pp. 118‐122、1996. 8.
［７］　磯部他：「郵便配達区画決定支援システム（デリバリー・プランニング・システム）」第８回郵政研究所研究発表会技術開発セッション発表論文No. 1996‐03、1996. 5.
［８］　磯部他：「デリバリー・プランニング・システム‐速達配達順路作成機能の拡張−」第９回郵政研究所研究発表会技術開発セッション発表論文No. 1997‐02、1997. 5.