(57)【要約】  【課題】  集配先などの巡回先を巡回する巡回順序を算出するプログラムであって、簡易な計算手法で素早く計算でき、また巡回先が増えても計算の負担の増大が少なく、比較的最短ルートに近似した巡回順序の算出ができる巡回順序算出プログラムを提供することであり、もって各巡回業務に適した巡回順序算出の選択肢を増やすことに寄与する巡回順序算出プログラムを提供すること。    【解決手段】  コンピュータを、各巡回先の地理的位置をＸ／Ｙ座標として取得する座標取得手段、１回で巡回する全巡回先の前記Ｘ座標の平均値Ｘｃと前記Ｙ座票の平均値Ｙｃとを算出してこの座標(Ｘｃ、Ｙｃ)でなる中心点Ｃを得る中心点算出手段、前記中心点を原点とする極座標で前記巡回先Ｐを表示した場合における各巡回先の回転角の順で巡回順序を決める順序手段、として機能させることを特徴とする。  【選択図】  図５
2005134997.tif 000002
【特許請求の範囲】
【請求項１】
集配先などの巡回先を巡回する巡回順序を算出するプログラムであって、コンピュータを、
各巡回先の地理的位置をＸ／Ｙ座標として取得する座標取得手段、１回で巡回する全巡回先の前記Ｘ座標の平均値Ｘｃと前記Ｙ座票の平均値Ｙｃとを算出してこの座標(Ｘｃ、Ｙｃ)でなる中心点を得る中心点算出手段、前記中心点を原点とする極座標で前記巡回先を表示した場合における各巡回先の回転角の順で巡回順序を決める順序手段、
として機能させることを特徴とする巡回順序算出プログラム。
【請求項２】
請求項１記載の巡回順序算出プログラムであって、順序手段による順序がｎ番目の巡回先からｎ＋１番目の巡回先に行く場合、コンピュータを、
ｎ＋２番目以降の所定件数内の巡回先の中に、前記ｎ＋１番目の巡回先より先に巡回することが巡回距離に関する所定の短縮化条件に合う巡回先があるかどうかを判断する判断手段、
前記巡回先がある場合にはこの巡回先を先に巡回した後に前記ｎ＋１番目の巡回先を巡回するように順序を修正する第一の順序修正手段、
として機能させることを特徴とする巡回順序算出プログラム。
【請求項３】
請求項１記載の巡回順序算出プログラムであって、コンピュータを、
ある巡回先から所定の回転角θ内に存在する巡回先の件数Ｍが所定のしいき値Ｋ以上となる巡回先を全ての巡回先から検出する検出手段、
順序手段の順序づけによるｎ番目の巡回先が前記検出手段により検出された巡回先に該当する場合には、ｎ番目〜（ｎ+Ｍ−１）番目までのＭ件の巡回先をこれらＭ件の巡回先が短距離で巡回できる順序に順序を修正する第二の順序修正手段、
として機能させることを特徴とする巡回順序算出プログラム。
【請求項４】
座標取得手段は、巡回先の住所からその住所の緯度と経度を前記巡回先の座標として得ることを特徴とする請求項１〜３いずれか記載の巡回順序算出プログラム。
【請求項５】
巡回に出発する出発地を、巡回先の１つと見なして算出の対象にすることを特徴とする請求項１〜４のいずれか記載の巡回順序算出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、荷物などの集配業務その他の巡回業務の際に、巡回車両などの巡回順序を算出する巡回順序算出プログラムに関する。
【背景技術】
【０００２】
上記の様な順序の算出には、本願出願人がした特願２００３−３３５６１の特許出願がある。これは巡回先を所定の順序で並べるものであり、例えば巡回先の郵便番号順に並べる方法であり、郵便番号をソートキーとしてソート処理をするのである。郵便番号は、郵便物の配達順序を意識して付番されており、よって巡回に適している確率が高いからである。
或いは集配先そのものをソートキーとしてソート処理をするのである。これによれば同一会社の支店や営業所が並ぶことになり、特定メーカーの商品を積載するために巡回する場合には都合のよい順序が決定できるメリットがある。
また巡回先の全ての順列を考え、その順列順序で巡回した場合の距離を、各順列ごとに計算すると、その中から最短ルートとなる順列（つまり順序）を得ることができる。距離の計算には、移動する２点間をその緯度・経度から求めるなどするのである。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ただ全ての順列を考える手法の場合、巡回先が増えると急激に順列の数が増えてしまい、計算量とその計算時間が膨大となって、事実上計算が困難となる場合がある。
また、適切な巡回順序というのは、その時々の巡回が対象とする業種や目的により様々であり、巡回順序を決める場合には、その業務などに適した決め方が好ましい。
【０００４】
以上の状況を踏まえ、本願発明の目的は、簡易な計算手法で素早く計算でき、また巡回先が増えても計算の負担の増大が少なく、比較的最短ルートに近似した巡回順序の算出ができる巡回順序算出プログラムを提供することであり、もって各巡回業務に適した巡回順序算出の選択肢を増やすことに寄与する巡回順序算出プログラムを提供することにある。
【課題を解決するための手段】
【０００５】
本願発明の請求項１記載の発明は、集配先などの巡回先を巡回する巡回順序を算出するプログラムであって、コンピュータを、各巡回先の地理的位置をＸ／Ｙ座標として取得する座標取得手段、１回で巡回する全巡回先の前記Ｘ座標の平均値Ｘｃと前記Ｙ座票の平均値Ｙｃとを算出してこの座標(Ｘｃ、Ｙｃ)でなる中心点を得る中心点算出手段、前記中心点を原点とする極座標で前記巡回先を表示した場合における各巡回先の回転角の順で巡回順序を決める順序手段、として機能させることを特徴とする。
これによれば、巡回先が増えても計算負担が余り増えずに計算をすることができる、それでいて比較的最短ルートに近いルートを得ることができる。なお座標の平均値とは、各座標の総和を巡回先の件数で割った単純平均に限らず、どの様な規則で規定される中心点であってもよい。また回転角の順での順序とは、回転角の値に基づいた昇順に限らず、降順でもよい。
【０００６】
請求項２記載の発明は、請求項１記載の巡回順序算出プログラムであって、順序手段による順序がｎ番目の巡回先からｎ＋１番目の巡回先に行く場合、コンピュータを、ｎ＋２番目以降の所定件数内の巡回先の中に、前記ｎ＋１番目の巡回先より先に巡回することが巡回距離に関する所定の短縮化条件に合う巡回先があるかどうかを判断する判断手段、前記巡回先がある場合にはこの巡回先を先に巡回した後に前記ｎ＋１番目の巡回先を巡回するように順序を修正する第一の順序修正手段、として機能させることを特徴とする。
これは、巡回順序は、概ね請求項１記載の発明により定めるものの、順序の部分々々によっては、近接する巡回先の回る順番を入れ替えた方が効率的である場合があり、この様な場合に対処するものである。例えばｎ番目からｎ＋１番目に行く場合、巡回先の分布状況によっては、それが回転角では隣接した巡回先であっても距離的には離れている場合もあり得る。そのため、ｎ番目の近くにｎ＋１番目以外の他の巡回先があるのなら、そちらを先に回ってから、元の順番に戻る様な方法をとる様にするのである。短縮化条件とは、この様に請求項１できまった巡回順を一部、修正した方がよい場合であるかどうかを判断する条件であればどの様な条件でもよい。
【０００７】
請求項３記載の発明は、請求項１記載の巡回順序算出プログラムであって、コンピュータを、ある巡回先から所定の回転角θ内に存在する巡回先の件数Ｍが所定のしいき値Ｋ以上となる巡回先を全ての巡回先から検出する検出手段、順序手段の順序づけによるｎ番目の巡回先が前記検出手段により検出された巡回先に該当する場合には、ｎ番目〜（ｎ＋Ｍ−１）番目までのＭ件の巡回先をこれらＭ件の巡回先が短距離で巡回できる順序に順序を修正する第二の順序修正手段、として機能させることを特徴とする。
これも、請求項２同様に、巡回順序は、概ね請求項１記載の発明により定めるものの、順序の部分々々によっては、近接する巡回先の回る順番を入れ替えた方が効率的である場合に対処したものである。請求項２と異なり、回転角度の近接したものがあった場合に、その近接したもの同志の中で順序を修正することにより、巡回をより効率よく使用というものである。
【０００８】
請求項４記載の発明は、請求項１〜３いずれか記載の巡回順序算出プログラムにおいて、座標取得手段は、巡回先の住所からその住所の緯度と経度を前記巡回先の座標として得ることを特徴とすることを特徴とする。
住所から緯度・経度を取得するについては、住所を入力するとその住所の緯度と経度が得られる市販ソフトが提供されており、この様なものを利用してもよい。
【０００９】
請求項５記載の発明は、請求項１〜４のいずれかに記載の巡回順序算出プログラムにおいて、巡回に出発する出発地を、巡回先の１つと見なして計算の対象にすることを特徴としたものである。
【発明の効果】
【００１０】
以上述べた様に、本願発明によれば、簡易な計算手法で素早く計算でき、また巡回先が増えても計算の負担の増大が少なくてすむ。例えば、巡回先の組み合わせごとにより最短距離を計算するので有れば、全巡回先の全組み合わせを計算することとなるが、その場合の組み合わせ数は巡回先の階乗となるので、巡回先が増えると計算量が急激に増えることとなるが、本願発明で有ればその様なこともない。
また本願の算出プログラムによれば、算出される順序が最短距離とは限らないものの、比較的最短なルートに近似した巡回順序の算出ができるのである。
【００１１】
また本願発明の回転角による順序付けでは、巡回先の分布状況によっては、中心に近い巡回先と遠い巡回先とを交互に巡回する様な無駄な回り方が算出される場合もあり得るが、この様な場合には、近くの巡回先を回ってから行く様にすることができ、しかも、この算出方法であっても、巡回先の増大による計算の負担増が少なくて済む。
【発明を実施するための最良の形態】
【００１２】
次ぎに本願発明の実施例を説明する。
（実施例１）図１に示すのは、宅配業者や運送会社で運用される集配管理システム１００であり、コンピュータ内に、集配業務における集配受付プログラム１０と、計算対象を抽出する抽出プログラム２０と、本実施例の巡回順序算出プログラム３０を有したものである。またこれら集配受付プログラム１０と抽出プログラム２０と巡回順序算出プログラム３０とは必要に応じてファイル４１，４２にアクセスできる様になっていて、必要なデータの共有ができる形態により、各プログラムによる計算結果を他のプログラムに引き渡せる様になっている。
【００１３】
集配受付プログラム１０は、集配業務の受注を入力するものであり、宅配業者などが、顧客から電話やＦＡＸで受け付けた集配依頼の内容を、社内の入力端末１から入力することができる様になっている。またこの集配受付プログラム１０は、インターネット端末２からも入力できる様になっており、一般の顧客が、その各自のインターネット端末２から集配業務の依頼を入力することができ、この様に入力された集配依頼が集配受付プログラム１０により受け付けられる様になっている。
この様にして受注した集配依頼により、その集配先名やそれらの住所は、受注データとして受注ファイル４１に出力される。
【００１４】
次ぎに、何らかの指示により、抽出プログラム２０がこの受注ファイル４１から、１回の巡回で集配する集配先データを抽出して、抽出ファイル４２に出力する。この場合、当該巡回車両が出発する場所も集配先データの１件として付け加えて出力しておくのである。
【００１５】
抽出された集配先データは、抽出ファィル４２から巡回順序算出プログラムに入力され、これら集配先の巡回順序を決める計算を開始するのである。
【００１６】
この様にして算出された巡回順は、集配管理システムの画面３に表示されると共に、印刷指示により印刷出力４ができる様になっているのである。
【００１７】
次ぎに巡回順序算出プログラムの構成とその作動について、仮に、算出の対象となる巡回先が図２に示す様な配置にある場合を例として説明する。また図２に示した巡回先は、抽出プログラムにより受注ファィルから抽出ファィルに抽出されたものであり、出発点Ａから各巡回先Ｐを巡回するものである。
巡回順序算出プログラムは、図３に示す様に、座標取得手段Ｓ１０と、中心点算出手段Ｓ４と、順序手段としてのソート処理Ｓ７を主要な手段として有している。
【００１８】
座標取得手段Ｓ１０は、抽出ファイルからの入力工程Ｓ１と、この入力工程Ｓ１により入力された集配先データから全巡回先（仮にＮ件とする）の住所を取り出す住所取得工程Ｓ２と、この様にして取得された住所からその経緯度を取得するために経緯度取得サブルーチンを呼び出すサブルーチン呼び出し工程Ｓ３とを有する。つまり、この呼び出しにより得られた各集配先Ｐｉの経緯度の数値をそのまま座標値と見なして、つまり経度をＸ座標、緯度をＹ座標とするのである。
【００１９】
中心算出手段Ｓ４は、この座標に基づき、
Ｘｃ＝ΣＸｉ／Ｎ  ，  Ｙｃ＝ΣＹｉ／Ｎ
の計算式により、中心点の座標（Ｘｃ、Ｙｃ）を計算して得るのである。中心点は、例えば図２におけるＣ点である。
【００２０】
順序手段としては、以下のことを行う。まず、各集配先ＰｉのＸＹ座標を、図４に示す様に、中心点Ｃを原点としたＸＹ座標に変換し、更にこの原点Ｃを中心としてＸ軸が出発点を通過する様に回転させた新ＸＹ座標での座標値に変換する。次ぎに、この変換された新しいＸ／Ｙ座標を、中心点Ｃを原点とする極座標に座標変換するのである。
【００２１】
以上により各集配先Ｐｉの極座標を得たら、出発地Ａを含む各集配先Ａ、Ｐｉをその回転角を値の小さい順に並べるのであり、具体的には、出発先を１番目の見なし巡回先として、これに続き、回転角の小さい順に順序づけるのである。この様にして決められた順序は、図５に示す様なルートRになり、この順序が必要に応じて画面表示や印刷など出力されるのである。
【００２２】
（実施例２）なお以上の方法においては、例えばｎ番目からｎ＋１番目に行く場合、巡回先の分布状況によっては、それが回転角では隣接した巡回先であっても距離的には離れている場合もあり得る。そのため、ｎ番目の近くに他の巡回先があるのなら、そちらを先に回ってから、元の順番に戻る様な方法をとってもよい。
その様な場合には、例えば、１０番目から１１番目に行く場合、その次ぎの１２番目以降を先に回った方がいい様な近い巡回先が有るかどうかを、所定の条件（短縮化条件）でチェックするのである。ただ１２番目以降の全てをチェックすると、チェックの計算負担が多大になってしまい、計算の負担を軽くしたいという本願の課題に反してしまう。そのため、例えば１２番目以降の２件とか３件だけなどの様に、チェックする範囲を所定件数にすると決めておくのである。
また１２番目以降の中に近い巡回先が有っても、本来の順番である１１番目も近くにあり、１２番目以降を先に回るという必要のない場合もある。従って短縮化条件には、ｎ番目から見てｎ＋１番目が一定距離以上遠くにあり、且つｎ＋２番目以降がｎ番目から見て近い距離にあるもの等の条件で考えられる。その他、状況に応じてこの短縮化条件は、色々に工夫してもよい。
【００２３】
ｎ番目からの各巡回先への距離は、各巡回先のＸＹ座標から算出することができる。経緯度の１度、或いは１分などの経緯度の幅は、１つの集配エリアのなかでは一定の距離に相当すると見なすことができ、従って２点間の距離はそのＸ座標からＸ方向の距離、Ｙ座標からＹ方向の距離を得て、これにより２点間の距離を計算することができるのである。
また、近いものが２つ以上ある場合、どちらを先に行くかはどの様に決めてもよい。上記の方法で各巡回先までの距離を計算し、近い順に巡回してもよい。
【００２４】
（実施例３）この実施例は、請求項３に対応したものであり、巡回先の極座標を（R、θ）とし、回転角の小さい順から巡回先のそれぞれを、一番目（R1、θ1）、２番目（R2、θ2）、３番目（R3、θ3）、・・・・・Ｊ番目（RJ、θJ）とする。この場合、まず、ある巡回先から所定の回転角θ内に存在する巡回先の件数Ｍを全巡回先について算出して、Ｍ1、Ｍ2、Ｍ3・・・、ＭJを得る。これにより、回転角的に見て、どこに巡回先が密集いているかを判断することができる。Ｍの値が大きい方が回転角的に巡回先の密集していることを示す。
【００２５】
ここで、Ｍがあるしきい値Ｋ以上の場合には、以下の計算を行うこととし、巡回順序を計算するのである。即ち、回転角の順番では、図６(ａ)に示す様に、出発点、1番目、２番目、３番目、・・・、Ｊ番目の順に巡回先をまわるとし、それぞれの巡回先で求めた上記のＭの値が、Ｍ1＝１、Ｍ2＝３、Ｍ3＝２、・・・、ＭJとなったとする。ここで、Ｋの値は予め３に設定されていたとすると、Ｍ2＝３であることから、２番目の巡回先から４番目の巡回先までは回転角的に近いところにあることを示している。この場合には、2番目から４番目までの巡回順を第二の順序修正手段で修正するのである。例えば、順序手段で得られた  ２番目、３番目、４番目の３つの巡回先の順列が６通り考えられるので、この６通り順序でまわった場合の距離を各々計算し、その中で最短のルートを決定し、順序手段で決めた順序をこの順序に修正するのである。例えば、図６(ａ)に示した順序を、図６（ｂ）に示す様な、１番目→２番目→４番目→３番目、の様な順序に修正するのである。
【００２６】
この様にして２〜４番目の順序を修正したら、５番目以降の順番についても、Ｍの値が３以上であるかどうかを判断し、３以上の場合には同様の計算を行いながら短距離を求めてその順序を決定するのであり、Ｍが３より小さい場合には順序手段で決定した当初の巡回順とするのである。
【００２７】
なお、上記の計算は、仮にＭ2＝３、Ｍ3＝４、Ｍ4＝３の様になっている場合にも同様に行い、２番目から４番目の順序を修正するのである。又なお、上述の短距離の算出は様々であってよく、例えば各巡回先間の直線距離を求める方法で短距離を算出してもよく、また、地図ソフト等を利用して道路に沿った距離を算出して短距離を求めてもよい。
【００２８】
また、上記の短距離を計算する方法の代わりに、以下の方法を用いて最適ルートを求める計算時間を短縮してもよい。即ち、Ｍ２＝３は、２番目の巡回先においてθの範囲にある地点が３ヶ所あることを示しており、その地点は２番目、３番目、４番目の地点である。これらの極座標はそれぞれ、（R2、θ2）、（R3、θ3）、（R4、θ4）であり、これらの地点の中心点を求め（例えば、実施例１に示した中心算出手段で求め）、この中心からの距離を優先して、距離の小さいほうから順に巡回するという方法である。即ち、R3＜R4＜R2であれば、巡回順序を、１番目→３番目→４番目→２番目と修正するという方法である。この方法は、上記の短距離を求める方式に比べれば、精度は悪いかも知れないが、計算時間を短縮できるメリットを有しており、比較的良好な結果が得られることが多い。
【図面の簡単な説明】
【００２９】
【図１】この図は、実施例１の集配管理システムのプログラム関係図である。
【図２】この図は、巡回先の分布を表した図であり、併せてＸＹ座標軸との関係を表している。
【図３】この図は、巡回順序算出プログラムのフロー図である。
【図４】この図は、図２に示した図において、そのＸＹ座標軸を変換し、更に巡回先を極座標で表した図である。
【図５】この図は、図４で表した極座標に基づき決められた巡回順を表した図である。
【図６】この図は、実施例３の説明をする図である。
【符号の説明】
【００３０】
１００  集配管理システム
１０  集配受付プログラム
２０  集出プログラム
３０  巡回順序算出プログラム
４１  受注ファィル
４２  抽出ファィル
Ａ  出発点
Ｐ  巡回先
Ｃ  中心点
【図１】
2005134997.tif 000003
【図２】
2005134997.tif 000004
【図３】
2005134997.tif 000005
【図４】
2005134997.tif 000006
【図５】
2005134997.tif 000007
【図６】
2005134997.tif 000008