集配経路選択システム
【課題】集配経路が定まった複数のトラックから、要求する経路を満足するトラックを選択できるシステムを提供する。
【解決手段】トラックの運用事業者１１０は予め、各トラックの集配経路を変更するたびにその経路をトラック識別子とともに、電気回線に接続されている端末を用いて経路選択システム１００の経路データベース１０４に登録する。発荷元事業者（荷物の渡す側）１２０Ａ〜１２０Ｃ、または集荷先事業者（荷物を受け取る側）は、それぞれの集配要求・制約を各端末から、予めＲＦＩＤに書き込んだ集配順序等の集配場所・制約条件を読取機から入力する。経路選択システム１１０から要求・制約に合致したトラックがある場合は、そのトラックの識別子を受け取る。経路選択システム１００は、特定の言語で記述された集配経路や要求経路を受け取り、その言語で適切なトラックを判別する。
【解決手段】トラックの運用事業者１１０は予め、各トラックの集配経路を変更するたびにその経路をトラック識別子とともに、電気回線に接続されている端末を用いて経路選択システム１００の経路データベース１０４に登録する。発荷元事業者（荷物の渡す側）１２０Ａ〜１２０Ｃ、または集荷先事業者（荷物を受け取る側）は、それぞれの集配要求・制約を各端末から、予めＲＦＩＤに書き込んだ集配順序等の集配場所・制約条件を読取機から入力する。経路選択システム１１０から要求・制約に合致したトラックがある場合は、そのトラックの識別子を受け取る。経路選択システム１００は、特定の言語で記述された集配経路や要求経路を受け取り、その言語で適切なトラックを判別する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集配経路の選択に関し、特に、複数の経路を有する集荷・配達のうち、条件にあう集配経路の選択に関するものである。
【背景技術】
【０００２】
材料や部品（例えば、牛乳）を集めて、酪農工場で酪農製品を作る場合、ジャストインタイム方式に代表されるように、発荷主（例えば農場）に集荷先（例えば酪農工場）へ納入させることが前提となっている。
このため、図１（ａ）のように牧場Ａ〜牧場Ｃ等の発荷主ごとにトラックを用意して、集荷先（酪農工場Ｄ）に材料や部品（牛乳）を運ぶことになり、ジャストインタイムなどの即応性はよくなるが、その一方でトラックの台数が増えるうえに、さらに集荷先から発荷主に戻るときのトラックは空となり、効率面でも無駄が多い。
これを解決する方法として注目されているのが、ミルクラン(Milk-run)方式である。図１（ｂ）のようにミルクラン方式では、集荷先となる業者（もしくは委託された輸送業者）である酪農工場Ｄが、一台または複数台のトラックを用意して、複数の発荷主（牧場Ａ〜牧場Ｃ）をまわるルートで集荷を行う。この結果、既存方式と比べてトラックの台数は少なくて済むだけでなく、空のトラックを走らせる回数も減ることになり、トラックによる二酸化炭素排出量を減らすことができる。
【０００３】
ミルクラン方式はトラックによる二酸化炭素量の削減の有効手法として注目を集めているが、ミルクラン方式を利用している事業者はまだ少ない。これはミルクラン方式が、集荷に求められる要求や制約を満足するのが難しいことに起因する。
実際、集荷には数多くの要求がある。例えば食品などは鮮度が要求されるため、トラック輸送中に傷みにくい食材を先に集荷して、鮮度が要求されるような部材については後回しにして、トラックが集荷先に到着する直前に集荷することになる。また、発荷主が工場などである場合、ある工場で作った材料や部品を別の工場に輸送することもあるが、この場合、トラックが発荷主をまわるべき順番もあらかじめきまっていることがある。なお、複数の発荷主の材料や部品を集めるためにミルクラン方式では、一台のトラックでは積みきれるとは限らないために複数トラックで運用することになるが、トラックの経路は違うことが多い。
【０００４】
カンバン方式などでは発荷主や部品ごとにトラックを用意することから、これらの制約や条件を満足させることは簡単であったが、ミルクランでは複数トラックを共用するために、発荷側または集荷側は制約や条件を満足する経路をたどるトラックを選ぶことになる。しかし、制約や条件は満足しながら、効率的に集配するトラックを選択することは容易ではなく、さらに制約や条件が複雑な場合や、集配先が多くなる場合はその選択は困難となる。例えば、図２は集配先の依存関係を示したものである。
図２において、工場Ａは工場Ｂと工場Ｃに部材をおくり、工場Ｂと工場Ｃは工場Ｄに部材を送り、工場Ｄは工場Ｅに部材を送った場合を表している。
【０００５】
図３は、ミルクラン方式で運行されている４台のトラックの経路を表したものである。図３（１），図３（２），図３（３）のトラックは、図２に示す制約を満足する経路となる。しかし、図３（４）のトラックは図２の制約を満足しない。どのような経路が、図２に示す制約（条件）を満たすのか、判断するのが難しいことが理解されるであろう。
しかも、制約を満足する経路（図３（１）〜（３））の中でも、二酸化炭素量の排出量を小さくするには、効率的な集配経路のトラックを選択する必要がある。
【０００６】
【特許文献１】特開２００４−３６３９０７
【非特許文献１】R. Milner, Communication and Concurrency, Prentice Hall, 1989.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、集配経路が定まった複数のトラックから、要求する経路を満足するトラックを選択できるシステムを提供することである。
【課題を解決するための手段】
【０００８】
上記本発明の目的を達成するために、本発明は、予め複数の集配経路を蓄積した記憶手段を有する集配経路選択システムであって、集配経路に乗せるべき対象の要求経路を入力する要求経路入力手段と、入力された該要求経路と、前記蓄積された複数の集配経路とを比較し、該要求経路を満足する集配経路を求める比較手段と、該要求経路を満足する集配経路の内、満足するための移動回数が最小の集配経路を出力する出力手段とを備え、前記要求経路は、集配箇所の順序の制約や要求を記述したものであり、前記集配経路は、集配箇所の順序を、前記要求経路記述のサブセットで記述したものであり、前記比較手段は、前記要求経路と前記集配経路とを木構造に変換したもので比較するとともに、満足するために必要な移動回数も得ることを特徴とする。
さらに、前記記憶手段に集配経路を蓄積するときに、集配経路の記述を木構造に変換して蓄積する手段を備え、前記比較手段は、入力された要求経路の記述を木構造に変換し、前記記憶手段から木構造に変換された集配経路を読み出して比較するとよい。
前記比較手段は、移動回数ではなく、移動ごとの移動距離の総和を出力し、前記出力手段は、該要求経路を満足する集配経路の内、満足するための移動距離の総和が最小の集配経路を出力することもできる。
上述において、「要求経路」とは、例えば以下で説明する経路記述言語で記載され、該経路記述言語は、発荷元や集荷先において、集配する対象（例えば、工場から出荷する製品）に対する経路順序の要求・制限を規定しており、比較するために木構造に変換できる。
また、「集配経路」とは、「要求経路」を記述したもののサブセット（例えば、以下の経路記述言語のサブセット）で記述され、集配を行うトラック等の経路順序を記述している。
【発明の効果】
【０００９】
上述の構成により、集配経路が定まった複数のトラックから、要求する経路を満足するトラックを素早く、適切に判定することができる。
【発明を実施するための最良の形態】
【００１０】
上述のように、ミルクラン方式はトラックによる二酸化炭素量の削減の有効手法として注目を集めているが、ミルクラン方式を利用している事業者はまだ少ない。これはミルクラン方式が、集配に求められる要求や制約を満足するのが難しいことに起因する。
これは、集配トラックの経路は日々変更されることはあるが、集配中に経路を変更することは現実には、難しいこともその理由の１つである。
本発明では、ミルクランを含むトラックの集配経路を記述するための言語と、制約や条件を満足する経路のトラックを選択する手法を提案していく。
なお、以下で説明することは、複数トラックそれぞれに割り当てられた経路から、制約や条件を満足するトラックを選択する手法であって、最短経路を発見する手法を提案するものではない。
【００１１】
＜集配トラックや経路記述言語について＞
さて、集配のトラックや言語の性質としては、以下で説明することが考えられる。
・ 集配トラックは一台以上であり、複数台の場合は、経路順序が相違することがある。経路は発荷元または集荷先として表され、トラックはそれぞれの経路に従ってまわる。
・ 集配順序に関する制約や要求は複雑になる。発荷元または集荷先と、その到着順番として表されるが、到着順は不定である場合や、集配中に他の発荷元または集荷先に０回以上立ち寄ってもいい場合もある。
・ 経済的な理由からトラック自体への設備追加は不可能である。また、提案手法のために追加的業務は必要最小限にしないといけない。
・ 経路要求は個々の製品や材料によって相違することがある。このためRFID タグや２次元バーコードに経路要求を埋め込めるように、記述はコンパクト化する。
・ トラックの集配経路を記述するためのプログラミング言語。
この言語はプロセス計算(Process Calculus) として定義され、集配箇所の移動順序を記述する。
・ 集荷順序の制約や要求を記述するプログラミング言語。
この言語は集配箇所の順序の記述言語に対して、複数集荷箇所を選択的に回ることや、集荷順序不問等を拡張した言語となる。
【００１２】
＜提案言語の概要＞
トラックの集配経路が制約や要求を満足するかを判定する手法が適用される言語であり、経路が制約や要求を満足することに加えて、制約や要求に反した経路をたどらないことを判定することができるものである。
集配順序の制約や要求を満足する経路をもつトラックを選択する必要があるが、その制約や要求は複雑であり、その選択は容易ではない。さらに不当な選択をすると生産・納期遅れや集荷品の品質に悪影響をあたえることがある。そこで本発明では、通信システム（特許文献１参照）やソフトウェアの検証手法を利用した経路選択を提案していく。
【００１３】
例えば、図３（１）に示すＡ，Ｂ，Ｃ，Ｄ，Ｅを順に回るトラックと、図３（２）に示すＡ，Ｃ，Ｂ，Ｄ，Ｅを順に回るトラックを例にすると、前者をＡ；Ｂ；Ｃ；Ｄ；Ｅと、後者をＡ；Ｃ；Ｂ；Ｄ；Ｅと表記する。
また、工場Ａに立ち寄った後に、工場ＢとＣに集配順序が不問であり、次にＤに行き、そのあとＥに行くという集配制約をＡ；（Ｂ％Ｃ）；Ｄ；Ｅと表記する。さらに、工場ＢとＣのどちらか一方で集配すればいい場合は、Ａ；（Ｂ＃Ｃ）；Ｄ；Ｅと表記するものである。
【００１４】
そして、提案する言語で記述された集配経路と要求経路に対して、集配経路が要求経路を満足するかを判定する手法を提案する。ただし、満足するか否かの判定は経路が複雑になるとともに困難になってくる。また、実際の集荷では一つの部材が足りないだけでも工場全体の稼働に影響する。また、鮮度が要求される部材では集荷の順番によっては部材が腐る場合もある。このため、経路要求を確実に満足するルートのトラックを選ぶ必要がある。そこで本発明では数学の代数学を利用したものを提案する。
【００１５】
これは、トラックの経路と要求経路を代数的順序関係として定義することであり、実用的であると同時に数学的に厳密性が保証される。これは言語で記述されたトラック経路が、同言語で記述された要求経路に示されている集荷が要求された目的地に、要求された順番に到達できるかを判定するとともに、要求された経路に書かれていない目的地や順番では集配しないことを判定するものである。
この順序関係は、下記のような集配経路選択システムとして運用される。集荷先はトラックの経路を登録する。一方、集荷先または発荷元の事業者は、要求された集配経路をシステムに示して、その要求経路を満足する経路を辿るトラックを提示してもらう。
なお、複数のトラックが要求経路を満足する場合は、集荷先の数が少ない経路のトラック、また各集荷先間の距離がわかっている場合は、距離の短いトラックの提示を受けることになる。
【００１６】
＜言語の詳細説明＞
以下に、例えばトラックの経路の選択の基礎となる移動経路の記述言語と順序関係を定義する。
さて、例えば荷物の要求する移動経路は下記の構文εにより、例えば各トラックの移動経路Ｓにより記述されるとする。
【００１７】
定義１ 以下のような構文規則を持つ式の集合εを次のように定義し、その要素をＥ，Ｅ１，Ｅ２，…と記す。
【数１】
ここでｌは集荷先または発荷元の集合Ｌの要素である。なお、各演算子の結合力は強い方から；，＋，＆，＃，％の順となる。
上記のうち、規則Ｅ１＃Ｅ２とＥ１％Ｅ２，Ｅ１＆Ｅ２，Ｅ＊を除いた式の集合をＳとし、その要素をＳ，Ｓ１，Ｓ２，…と記す。なお、適宜省略することがある。
【００１８】
構文ε及びＳの各演算子の意味は、後で説明する定義２そして定義３の順序関係をまたないといけないが、ここで基本的な記述式の非形式的な意味を述べておく。
０（移動終了）は、集配の終了を示す。
ｌ（移動）は、トラックが名前ｌの発荷元・集荷先に行くことを示す。
Ｅ１；Ｅ２（逐次合成）は、経路Ｅ１に従って集配した後に経路Ｅ２に従って集配することを表す。
Ｅ１＋Ｅ２（選択合成）は、経路Ｅ１とＥ２のどちらか一方に従って集配するが、その選択はＥ１とＥ２の集配先に行けるか否かで明示的に決められる。これは交通渋滞などでどちらか一方にいくことを示す。
Ｅ１＃Ｅ２（非決定的選択合成）は、経路Ｅ１とＥ２の非決定的選択を表す。トラックは経路Ｅ１とＥ２のどちらの経路を辿ってもよいことを示す。
Ｅ１％Ｅ２（非決定的可換合成）は、経路Ｅ１とＥ２の可換合流性を表す。トラックは経路Ｅ１とＥ２の順序は入れ換えて移動してもよいことを示す。
Ｅ１＆Ｅ２（非同期合成）は経路Ｅ１による集配中にＥ２による集配を行ってよい、または、経路Ｅ２による集配中にＥ１による集配を行ってよいことを示す。
Ｅ１Ｅ２＊（閉包）は任意回の経路繰り返しを表す。トラックは経路Ｅ１を集配中に経路Ｅ２を０回以上の繰り返しを行って移動してもよいことを表す。
【００１９】
この言語はラベル付き遷移システムとしての動作が、以下のように定義される。
定義２ εの遷移関係
【数２】
を下記の構造的操作意味論(Structural Operational Semantics)に基づく推論規則により定義する。
【数３】
さらに、ｎをアスタリスク（＊）とするときは、不定回のτ−遷移の繰り返しを意味する。
上述のそれぞれの表記は、上段の前提で、下段に遷移できることを表している。
【００２０】
【表１】
【００２１】
なお、再帰や繰り返し記述を持たないが、それは、トラックが集配後は車庫にもどるために、連続して稼働することがないためである。代表的な記述例をその経路である図４とともに示す。なお、図４で複数のトラックが記載されている場合は、経路の選択肢を示している。
（１）例えばトラックの集配の経路記述ａ；ｂ；ｃ；ｄ；ｅ，ｉｎＳの遷移は次のようになる。
【数４】
この経路は、図４（１）に示す。
【００２２】
（２）経路要求（例えば荷物の配送経路）εの例（ａ；（ｂ＃ｃ）；ｄ；ｅ，ｉｎε）を示す。
【数５】
ここで、経路記述中の＃はトラックが二つの経路のどちらをたどってもいいことを表している。図４（２）に示すように、トラックはａに行った後に、ｂまたはｃのどちらかに立ち寄り、そのあとはｄにいき、最後にｅに行くことになる。
【００２３】
（３）経路要求の他の例として、（ａ；（ｂ％ｃ）；ｄ；ｅ，ｉｎε）を示す。
【数６】
図４（３）に示すように、経路記述中の% は集配先の訪問順序が不問であることを表す。
【００２４】
（４）経路要求の次の例として、（ａ；（（ｂ；ｃ）＆ｄ）；ｅ）を示す。これは＆の意味を示す例である。
【数７】
ここで、＆は二つの経路が同時に実行していいことを示す。例えばトラックはａに訪れ
たあと、（ｂ；ｃ）＆ｄに従って、ｂからｃに移動する途中でｄに行くことを表す（図４（４）参照）。
【００２５】
図４（４）に示すように、以下の遷移も可能である。
【数８】
【００２６】
（５）さらに、経路要求の例として、（ａ；（ｂ％ｃ））＆ｄ＊＆ｅ＊の遷移を考える。
【数９】
これは、さらに、下記の遷移も可能である。
【数１０】
【００２７】
＜移動経路による順序関係＞
次にトラックの移動経路（Ｓの式）が、発荷元や集荷先、配送対象の荷物の要求や制約（Ｅの式）を満足するかの判定方法を双模倣性(Bisimulation) をもとに順序関係として定式化していく。なお、その順序関係ではトラックの移動回数も調べられるようにする。
定義３ ある自然数ｎ（ｎ≧０）に対して次の３つの条件を満足する関係Ｒｎ（Ｒｎ⊆ Ｅ×Ｓ）を考える。
【数１１】
【００２８】
充足順序関係の非形式的意味を述べておく。
まず、トラックの経路Ｓは配送要求Ｅを充足する必要がある。
上述の定義（１）は、要求Ｅが集配順序をＳが満足し、さらにＥが集配先を選択できる場合は同様の選択をＳも持ち、その各選択先でもＳはＥを同様に充足することを示す。
定義（２）は、経路要求Ｅにおける非決定性演算子（＃や％，Ｅ＊）による選択候補のうち、少なくても一つをＳが充足していることを示す。
定義（３）は、Ｓの経路であれば、Ｅの経路となること、つまりＳがＥにより要求されている経路以外で移動しないことを示している。
なお、充足順序関係のｎはＥの充足に必要な移動回数を表す。
【００２９】
この性質により経路要求を充足する集配経路は、他の充足可能な集配経路と合成しても充足されることが保証される。次にいくつかの比較例を示す。
複数経路を任意に選択してよい場合
【数１２】
【００３０】
・到着順序が任意となる場合
【数１３】
ここで、左辺の経路要求は、集配箇所ａ，ｂ，ｃの任意の順番で一巡して、集配先ｈに戻ることを要求している。右辺の集配経路をａ；ｂ；ｃ；ｈにした場合も充足順序関係となるが、ａ；ｂ；や、ａ；ｈ；ｂ；ｈ；ｃ；ｈの場合は、充足順序関係とならない。
【実施例】
【００３１】
提案するシステムの構成は、図５に示すように、トラックの運用事業者（１１０）、発荷元または集荷先（１２０）、トラック選択処理を行う集配経路選択システム（１００）の３者にわかれる。
【００３２】
・トラック側（１１０）：
トラック運転手または運送事業管理者は、各トラックの集配経路を変更するたびに、その経路をトラック識別子とともに、電気回線に接続されている端末を用いて集配経路選択システム（１００）の経路データベース（１０４）に登録する。
道路貨物運輸法により義務づけられている運行指示書または運行表は、集配順序に相当する情報を含んでいる。このために、運行指示書または運行表の記述から、集配順序のデータを得ることができる。このデータを端末のキーボードやマウス等の入力装置により、ユーザインターフェースを介して入力することができる。
端末から集配順序のデータが入力されると、Ｓ記述へ自動変換されて、集配経路選択システム（１００）の経路データベース（１０４）に登録される。
【００３３】
サーバにおける判定コストを低減するため、集配経路選択システム（１００）はトラックの集配経路を端末から受け取った段階で、記述式に対応した、判定に使用する木構造（後述）を生成して、経路データベース（１０４）に登録しておくとよい。なお、トラック経路の木構造は非決定的な選択がないために決定的かつ有限木となる。
【００３４】
・発荷元または集荷先側（１２０Ａ〜１２０Ｃ）：
発荷元事業者（荷物を渡す側）（１２０Ａ〜１２０Ｃ）、または集荷先事業者（荷物を受け取る側）は、それぞれの集配要求・制約をＥ形式で、各端末から、ユーザインターフェースを介して集配経路選択システム（１００）に入力する。集配経路選択システム（１００）から要求・制約に合致したトラックがある場合は、そのトラックの識別子を受け取る。
【００３５】
集配要求・制約のＥ記述は、例えば、集配順序等の集配箇所・制約条件を、端末の画面上で表示選択する等で入力し、Ｅ記述に変換して、予め、ＲＦＩＤに書き込み、又は、2次元バーコードでラベルに印刷しておき、荷物に添付しておく。
これらのＲＦＩＤやラベルから、端末に接続されたそれぞれの読取器により読み込むことで、集配経路選択システム（１００）に接続された端末からＥ記述を集配経路選択システム（１００）に送って、荷物ごとの適切なトラックを選択することができる。
【００３６】
・集配経路選択システム（１００）：
集配経路選択システム（１００）は、トラック側の端末からトラック集配経路を登録するデータベース（１０４）をもち、トラックの経路を蓄積・管理する。
そして、発荷元または集荷先側の端末から集配要求・制約を受け取ると、経路選択エンジン（１０２）により、その要求・制約を満足して、移動回数が一番小さい経路をもつトラックの識別子を返す。
【００３７】
＜集配経路選択システム（１００）における処理＞
集配経路選択システム（１００）の経路選択エンジン（１０２）における処理を、図６のフローチャートを用いて説明する。
集配経路選択システム（１００）は、例えば、ＲＦＩＤ読取機で読み取った、集配経路に関する要求・制約のデータ（Ｅ記述）を、端末から受け取る（Ｓ２０２）と、上述の定義３の充足順序関係を利用して、経路データベース（１０４）に登録されたトラック経路（Ｓ記述）から要求・制約を満足して、さらに移動回数が最小となる経路を探す。
比較対象となる二つの記述式（Ｅ，Ｓ）に対して定義２の状態遷移先を節点、ラベル付き遷移を名前付き枝とする木構造を生成して比較している。
そのため、経路要求を行っているＥ記述を木構造に変換する（Ｓ２０４）。そして、トラックの集配経路であるＳ記述は、トラックのデータを経路データベース（１０４）に登録するときに、木構造に変換されて登録されているので、Ｓ記述のトラックの経路の木構造をデータベースから取得する（Ｓ２０６）。
【００３８】
そして、定義３に従って、その二つの木構造において、互いに対応する節点同士が同じ名前をもつ枝を持つことをすべての節点に関して調べ、双模倣性(Bisimulation)により、充足順序関係を判断している（Ｓ２０８，Ｓ２１０）。この判断手法については、後で詳細に説明する。トラックの経路と充足順序関係があれば（Ｓ２１０でＹＥＳ）、トラックの識別番号（ＩＤ）と充足順序関係を保存する（Ｓ２１２）。
上述の充足関係を全てのトラックの経路に対してを調べる（Ｓ２１４，Ｓ２１６）。
全てのトラックの経路との充足順序関係を調べ終わる（Ｓ２１４でＹＥＳ）と、充足順序関係を満たすトラックが存在し（Ｓ２１８でＹＥＳ）、タスク依頼の移動経路要求と充足順序関係を満足するトラック経路が複数存在するときは、定義３の充足順序関係のｎが最小のもの、つまり移動回数が最小なものを選ぶ（Ｓ２２０）。
このとき、全ての移動経路の距離が既知の場合は、移動毎に移動距離の総和を計算して、それが最小の経路を選択するとよい。
【００３９】
＜充足順序関係の判定（Ｓ２０８，Ｓ２１０）＞
その充足順序関係の判定（Ｓ２０８，Ｓ２１０）は、双模倣性(Bisimulation)により、二つの木構造のそれぞれの根を、起点に部分木を持たない節点に至るまで、次の動作を実行することで行う。なお、双模倣性(Bisimulation)については、非特許文献１を参照されたい。
（１）まず、比較対象の節点が互いに同じ名前の枝を持つか調べる。
（２）同等の枝を持つ場合は枝の先にある節点について（１）を繰り返す。
（３）逆に持たない場合は一つ前の節点に後戻りして、残りの節点に関して（１）を繰り返す。
【００４０】
これを、図７を用いて説明する。図７において、左側は経路要求のＥ記述（ａ；（（ｂ；（ｃ＋ｄ））♯ｄ）の木構造３１０を示し、右側は集配経路のＳ記述（ａ；ｂ；（ｃ＋ｄ））の木構造３２０を示している。
上述の（１）により、起点である根が同じ名前の枝を持つか調べる（Ｓ３０２）と、同じ「ａ」という名前を持っている。そのため、上述の（２）により、その先の接点の枝で、同じ名前を有するか調べる（Ｓ３０４）。その結果、同じ「ｂ」を持っている。そのため（２）により、その先の枝を調べる（Ｓ３０６，Ｓ３０８）と「ｃ」及び「ｄ」で一致する。なお、節点を移動する毎（階層が深くなるごと）に移動回数を＋１する。
これで、双方の木構造に対して、起点を持たない節点に来たので、処理を終了し、「充足順序関係あり」とし、この集配経路を有するトラックの識別番号と節点を移動した回数（移動回数）ｎ（この場合３）とを得ることができる。
【図面の簡単な説明】
【００４１】
【図１】従来の集荷を説明する図である。
【図２】集配先の依存関係を示した図である。
【図３】トラックの経路を示す図である。
【図４】経路の記述例とその経路を示す図である。
【図５】実施例としてのシステム構成図である。
【図６】集配経路選択システムの処理を示すフローチャートである。
【図７】木構造を利用した判定処理を説明する図である。
【技術分野】
【０００１】
本発明は、集配経路の選択に関し、特に、複数の経路を有する集荷・配達のうち、条件にあう集配経路の選択に関するものである。
【背景技術】
【０００２】
材料や部品（例えば、牛乳）を集めて、酪農工場で酪農製品を作る場合、ジャストインタイム方式に代表されるように、発荷主（例えば農場）に集荷先（例えば酪農工場）へ納入させることが前提となっている。
このため、図１（ａ）のように牧場Ａ〜牧場Ｃ等の発荷主ごとにトラックを用意して、集荷先（酪農工場Ｄ）に材料や部品（牛乳）を運ぶことになり、ジャストインタイムなどの即応性はよくなるが、その一方でトラックの台数が増えるうえに、さらに集荷先から発荷主に戻るときのトラックは空となり、効率面でも無駄が多い。
これを解決する方法として注目されているのが、ミルクラン(Milk-run)方式である。図１（ｂ）のようにミルクラン方式では、集荷先となる業者（もしくは委託された輸送業者）である酪農工場Ｄが、一台または複数台のトラックを用意して、複数の発荷主（牧場Ａ〜牧場Ｃ）をまわるルートで集荷を行う。この結果、既存方式と比べてトラックの台数は少なくて済むだけでなく、空のトラックを走らせる回数も減ることになり、トラックによる二酸化炭素排出量を減らすことができる。
【０００３】
ミルクラン方式はトラックによる二酸化炭素量の削減の有効手法として注目を集めているが、ミルクラン方式を利用している事業者はまだ少ない。これはミルクラン方式が、集荷に求められる要求や制約を満足するのが難しいことに起因する。
実際、集荷には数多くの要求がある。例えば食品などは鮮度が要求されるため、トラック輸送中に傷みにくい食材を先に集荷して、鮮度が要求されるような部材については後回しにして、トラックが集荷先に到着する直前に集荷することになる。また、発荷主が工場などである場合、ある工場で作った材料や部品を別の工場に輸送することもあるが、この場合、トラックが発荷主をまわるべき順番もあらかじめきまっていることがある。なお、複数の発荷主の材料や部品を集めるためにミルクラン方式では、一台のトラックでは積みきれるとは限らないために複数トラックで運用することになるが、トラックの経路は違うことが多い。
【０００４】
カンバン方式などでは発荷主や部品ごとにトラックを用意することから、これらの制約や条件を満足させることは簡単であったが、ミルクランでは複数トラックを共用するために、発荷側または集荷側は制約や条件を満足する経路をたどるトラックを選ぶことになる。しかし、制約や条件は満足しながら、効率的に集配するトラックを選択することは容易ではなく、さらに制約や条件が複雑な場合や、集配先が多くなる場合はその選択は困難となる。例えば、図２は集配先の依存関係を示したものである。
図２において、工場Ａは工場Ｂと工場Ｃに部材をおくり、工場Ｂと工場Ｃは工場Ｄに部材を送り、工場Ｄは工場Ｅに部材を送った場合を表している。
【０００５】
図３は、ミルクラン方式で運行されている４台のトラックの経路を表したものである。図３（１），図３（２），図３（３）のトラックは、図２に示す制約を満足する経路となる。しかし、図３（４）のトラックは図２の制約を満足しない。どのような経路が、図２に示す制約（条件）を満たすのか、判断するのが難しいことが理解されるであろう。
しかも、制約を満足する経路（図３（１）〜（３））の中でも、二酸化炭素量の排出量を小さくするには、効率的な集配経路のトラックを選択する必要がある。
【０００６】
【特許文献１】特開２００４−３６３９０７
【非特許文献１】R. Milner, Communication and Concurrency, Prentice Hall, 1989.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、集配経路が定まった複数のトラックから、要求する経路を満足するトラックを選択できるシステムを提供することである。
【課題を解決するための手段】
【０００８】
上記本発明の目的を達成するために、本発明は、予め複数の集配経路を蓄積した記憶手段を有する集配経路選択システムであって、集配経路に乗せるべき対象の要求経路を入力する要求経路入力手段と、入力された該要求経路と、前記蓄積された複数の集配経路とを比較し、該要求経路を満足する集配経路を求める比較手段と、該要求経路を満足する集配経路の内、満足するための移動回数が最小の集配経路を出力する出力手段とを備え、前記要求経路は、集配箇所の順序の制約や要求を記述したものであり、前記集配経路は、集配箇所の順序を、前記要求経路記述のサブセットで記述したものであり、前記比較手段は、前記要求経路と前記集配経路とを木構造に変換したもので比較するとともに、満足するために必要な移動回数も得ることを特徴とする。
さらに、前記記憶手段に集配経路を蓄積するときに、集配経路の記述を木構造に変換して蓄積する手段を備え、前記比較手段は、入力された要求経路の記述を木構造に変換し、前記記憶手段から木構造に変換された集配経路を読み出して比較するとよい。
前記比較手段は、移動回数ではなく、移動ごとの移動距離の総和を出力し、前記出力手段は、該要求経路を満足する集配経路の内、満足するための移動距離の総和が最小の集配経路を出力することもできる。
上述において、「要求経路」とは、例えば以下で説明する経路記述言語で記載され、該経路記述言語は、発荷元や集荷先において、集配する対象（例えば、工場から出荷する製品）に対する経路順序の要求・制限を規定しており、比較するために木構造に変換できる。
また、「集配経路」とは、「要求経路」を記述したもののサブセット（例えば、以下の経路記述言語のサブセット）で記述され、集配を行うトラック等の経路順序を記述している。
【発明の効果】
【０００９】
上述の構成により、集配経路が定まった複数のトラックから、要求する経路を満足するトラックを素早く、適切に判定することができる。
【発明を実施するための最良の形態】
【００１０】
上述のように、ミルクラン方式はトラックによる二酸化炭素量の削減の有効手法として注目を集めているが、ミルクラン方式を利用している事業者はまだ少ない。これはミルクラン方式が、集配に求められる要求や制約を満足するのが難しいことに起因する。
これは、集配トラックの経路は日々変更されることはあるが、集配中に経路を変更することは現実には、難しいこともその理由の１つである。
本発明では、ミルクランを含むトラックの集配経路を記述するための言語と、制約や条件を満足する経路のトラックを選択する手法を提案していく。
なお、以下で説明することは、複数トラックそれぞれに割り当てられた経路から、制約や条件を満足するトラックを選択する手法であって、最短経路を発見する手法を提案するものではない。
【００１１】
＜集配トラックや経路記述言語について＞
さて、集配のトラックや言語の性質としては、以下で説明することが考えられる。
・ 集配トラックは一台以上であり、複数台の場合は、経路順序が相違することがある。経路は発荷元または集荷先として表され、トラックはそれぞれの経路に従ってまわる。
・ 集配順序に関する制約や要求は複雑になる。発荷元または集荷先と、その到着順番として表されるが、到着順は不定である場合や、集配中に他の発荷元または集荷先に０回以上立ち寄ってもいい場合もある。
・ 経済的な理由からトラック自体への設備追加は不可能である。また、提案手法のために追加的業務は必要最小限にしないといけない。
・ 経路要求は個々の製品や材料によって相違することがある。このためRFID タグや２次元バーコードに経路要求を埋め込めるように、記述はコンパクト化する。
・ トラックの集配経路を記述するためのプログラミング言語。
この言語はプロセス計算(Process Calculus) として定義され、集配箇所の移動順序を記述する。
・ 集荷順序の制約や要求を記述するプログラミング言語。
この言語は集配箇所の順序の記述言語に対して、複数集荷箇所を選択的に回ることや、集荷順序不問等を拡張した言語となる。
【００１２】
＜提案言語の概要＞
トラックの集配経路が制約や要求を満足するかを判定する手法が適用される言語であり、経路が制約や要求を満足することに加えて、制約や要求に反した経路をたどらないことを判定することができるものである。
集配順序の制約や要求を満足する経路をもつトラックを選択する必要があるが、その制約や要求は複雑であり、その選択は容易ではない。さらに不当な選択をすると生産・納期遅れや集荷品の品質に悪影響をあたえることがある。そこで本発明では、通信システム（特許文献１参照）やソフトウェアの検証手法を利用した経路選択を提案していく。
【００１３】
例えば、図３（１）に示すＡ，Ｂ，Ｃ，Ｄ，Ｅを順に回るトラックと、図３（２）に示すＡ，Ｃ，Ｂ，Ｄ，Ｅを順に回るトラックを例にすると、前者をＡ；Ｂ；Ｃ；Ｄ；Ｅと、後者をＡ；Ｃ；Ｂ；Ｄ；Ｅと表記する。
また、工場Ａに立ち寄った後に、工場ＢとＣに集配順序が不問であり、次にＤに行き、そのあとＥに行くという集配制約をＡ；（Ｂ％Ｃ）；Ｄ；Ｅと表記する。さらに、工場ＢとＣのどちらか一方で集配すればいい場合は、Ａ；（Ｂ＃Ｃ）；Ｄ；Ｅと表記するものである。
【００１４】
そして、提案する言語で記述された集配経路と要求経路に対して、集配経路が要求経路を満足するかを判定する手法を提案する。ただし、満足するか否かの判定は経路が複雑になるとともに困難になってくる。また、実際の集荷では一つの部材が足りないだけでも工場全体の稼働に影響する。また、鮮度が要求される部材では集荷の順番によっては部材が腐る場合もある。このため、経路要求を確実に満足するルートのトラックを選ぶ必要がある。そこで本発明では数学の代数学を利用したものを提案する。
【００１５】
これは、トラックの経路と要求経路を代数的順序関係として定義することであり、実用的であると同時に数学的に厳密性が保証される。これは言語で記述されたトラック経路が、同言語で記述された要求経路に示されている集荷が要求された目的地に、要求された順番に到達できるかを判定するとともに、要求された経路に書かれていない目的地や順番では集配しないことを判定するものである。
この順序関係は、下記のような集配経路選択システムとして運用される。集荷先はトラックの経路を登録する。一方、集荷先または発荷元の事業者は、要求された集配経路をシステムに示して、その要求経路を満足する経路を辿るトラックを提示してもらう。
なお、複数のトラックが要求経路を満足する場合は、集荷先の数が少ない経路のトラック、また各集荷先間の距離がわかっている場合は、距離の短いトラックの提示を受けることになる。
【００１６】
＜言語の詳細説明＞
以下に、例えばトラックの経路の選択の基礎となる移動経路の記述言語と順序関係を定義する。
さて、例えば荷物の要求する移動経路は下記の構文εにより、例えば各トラックの移動経路Ｓにより記述されるとする。
【００１７】
定義１ 以下のような構文規則を持つ式の集合εを次のように定義し、その要素をＥ，Ｅ１，Ｅ２，…と記す。
【数１】
ここでｌは集荷先または発荷元の集合Ｌの要素である。なお、各演算子の結合力は強い方から；，＋，＆，＃，％の順となる。
上記のうち、規則Ｅ１＃Ｅ２とＥ１％Ｅ２，Ｅ１＆Ｅ２，Ｅ＊を除いた式の集合をＳとし、その要素をＳ，Ｓ１，Ｓ２，…と記す。なお、適宜省略することがある。
【００１８】
構文ε及びＳの各演算子の意味は、後で説明する定義２そして定義３の順序関係をまたないといけないが、ここで基本的な記述式の非形式的な意味を述べておく。
０（移動終了）は、集配の終了を示す。
ｌ（移動）は、トラックが名前ｌの発荷元・集荷先に行くことを示す。
Ｅ１；Ｅ２（逐次合成）は、経路Ｅ１に従って集配した後に経路Ｅ２に従って集配することを表す。
Ｅ１＋Ｅ２（選択合成）は、経路Ｅ１とＥ２のどちらか一方に従って集配するが、その選択はＥ１とＥ２の集配先に行けるか否かで明示的に決められる。これは交通渋滞などでどちらか一方にいくことを示す。
Ｅ１＃Ｅ２（非決定的選択合成）は、経路Ｅ１とＥ２の非決定的選択を表す。トラックは経路Ｅ１とＥ２のどちらの経路を辿ってもよいことを示す。
Ｅ１％Ｅ２（非決定的可換合成）は、経路Ｅ１とＥ２の可換合流性を表す。トラックは経路Ｅ１とＥ２の順序は入れ換えて移動してもよいことを示す。
Ｅ１＆Ｅ２（非同期合成）は経路Ｅ１による集配中にＥ２による集配を行ってよい、または、経路Ｅ２による集配中にＥ１による集配を行ってよいことを示す。
Ｅ１Ｅ２＊（閉包）は任意回の経路繰り返しを表す。トラックは経路Ｅ１を集配中に経路Ｅ２を０回以上の繰り返しを行って移動してもよいことを表す。
【００１９】
この言語はラベル付き遷移システムとしての動作が、以下のように定義される。
定義２ εの遷移関係
【数２】
を下記の構造的操作意味論(Structural Operational Semantics)に基づく推論規則により定義する。
【数３】
さらに、ｎをアスタリスク（＊）とするときは、不定回のτ−遷移の繰り返しを意味する。
上述のそれぞれの表記は、上段の前提で、下段に遷移できることを表している。
【００２０】
【表１】
【００２１】
なお、再帰や繰り返し記述を持たないが、それは、トラックが集配後は車庫にもどるために、連続して稼働することがないためである。代表的な記述例をその経路である図４とともに示す。なお、図４で複数のトラックが記載されている場合は、経路の選択肢を示している。
（１）例えばトラックの集配の経路記述ａ；ｂ；ｃ；ｄ；ｅ，ｉｎＳの遷移は次のようになる。
【数４】
この経路は、図４（１）に示す。
【００２２】
（２）経路要求（例えば荷物の配送経路）εの例（ａ；（ｂ＃ｃ）；ｄ；ｅ，ｉｎε）を示す。
【数５】
ここで、経路記述中の＃はトラックが二つの経路のどちらをたどってもいいことを表している。図４（２）に示すように、トラックはａに行った後に、ｂまたはｃのどちらかに立ち寄り、そのあとはｄにいき、最後にｅに行くことになる。
【００２３】
（３）経路要求の他の例として、（ａ；（ｂ％ｃ）；ｄ；ｅ，ｉｎε）を示す。
【数６】
図４（３）に示すように、経路記述中の% は集配先の訪問順序が不問であることを表す。
【００２４】
（４）経路要求の次の例として、（ａ；（（ｂ；ｃ）＆ｄ）；ｅ）を示す。これは＆の意味を示す例である。
【数７】
ここで、＆は二つの経路が同時に実行していいことを示す。例えばトラックはａに訪れ
たあと、（ｂ；ｃ）＆ｄに従って、ｂからｃに移動する途中でｄに行くことを表す（図４（４）参照）。
【００２５】
図４（４）に示すように、以下の遷移も可能である。
【数８】
【００２６】
（５）さらに、経路要求の例として、（ａ；（ｂ％ｃ））＆ｄ＊＆ｅ＊の遷移を考える。
【数９】
これは、さらに、下記の遷移も可能である。
【数１０】
【００２７】
＜移動経路による順序関係＞
次にトラックの移動経路（Ｓの式）が、発荷元や集荷先、配送対象の荷物の要求や制約（Ｅの式）を満足するかの判定方法を双模倣性(Bisimulation) をもとに順序関係として定式化していく。なお、その順序関係ではトラックの移動回数も調べられるようにする。
定義３ ある自然数ｎ（ｎ≧０）に対して次の３つの条件を満足する関係Ｒｎ（Ｒｎ⊆ Ｅ×Ｓ）を考える。
【数１１】
【００２８】
充足順序関係の非形式的意味を述べておく。
まず、トラックの経路Ｓは配送要求Ｅを充足する必要がある。
上述の定義（１）は、要求Ｅが集配順序をＳが満足し、さらにＥが集配先を選択できる場合は同様の選択をＳも持ち、その各選択先でもＳはＥを同様に充足することを示す。
定義（２）は、経路要求Ｅにおける非決定性演算子（＃や％，Ｅ＊）による選択候補のうち、少なくても一つをＳが充足していることを示す。
定義（３）は、Ｓの経路であれば、Ｅの経路となること、つまりＳがＥにより要求されている経路以外で移動しないことを示している。
なお、充足順序関係のｎはＥの充足に必要な移動回数を表す。
【００２９】
この性質により経路要求を充足する集配経路は、他の充足可能な集配経路と合成しても充足されることが保証される。次にいくつかの比較例を示す。
複数経路を任意に選択してよい場合
【数１２】
【００３０】
・到着順序が任意となる場合
【数１３】
ここで、左辺の経路要求は、集配箇所ａ，ｂ，ｃの任意の順番で一巡して、集配先ｈに戻ることを要求している。右辺の集配経路をａ；ｂ；ｃ；ｈにした場合も充足順序関係となるが、ａ；ｂ；や、ａ；ｈ；ｂ；ｈ；ｃ；ｈの場合は、充足順序関係とならない。
【実施例】
【００３１】
提案するシステムの構成は、図５に示すように、トラックの運用事業者（１１０）、発荷元または集荷先（１２０）、トラック選択処理を行う集配経路選択システム（１００）の３者にわかれる。
【００３２】
・トラック側（１１０）：
トラック運転手または運送事業管理者は、各トラックの集配経路を変更するたびに、その経路をトラック識別子とともに、電気回線に接続されている端末を用いて集配経路選択システム（１００）の経路データベース（１０４）に登録する。
道路貨物運輸法により義務づけられている運行指示書または運行表は、集配順序に相当する情報を含んでいる。このために、運行指示書または運行表の記述から、集配順序のデータを得ることができる。このデータを端末のキーボードやマウス等の入力装置により、ユーザインターフェースを介して入力することができる。
端末から集配順序のデータが入力されると、Ｓ記述へ自動変換されて、集配経路選択システム（１００）の経路データベース（１０４）に登録される。
【００３３】
サーバにおける判定コストを低減するため、集配経路選択システム（１００）はトラックの集配経路を端末から受け取った段階で、記述式に対応した、判定に使用する木構造（後述）を生成して、経路データベース（１０４）に登録しておくとよい。なお、トラック経路の木構造は非決定的な選択がないために決定的かつ有限木となる。
【００３４】
・発荷元または集荷先側（１２０Ａ〜１２０Ｃ）：
発荷元事業者（荷物を渡す側）（１２０Ａ〜１２０Ｃ）、または集荷先事業者（荷物を受け取る側）は、それぞれの集配要求・制約をＥ形式で、各端末から、ユーザインターフェースを介して集配経路選択システム（１００）に入力する。集配経路選択システム（１００）から要求・制約に合致したトラックがある場合は、そのトラックの識別子を受け取る。
【００３５】
集配要求・制約のＥ記述は、例えば、集配順序等の集配箇所・制約条件を、端末の画面上で表示選択する等で入力し、Ｅ記述に変換して、予め、ＲＦＩＤに書き込み、又は、2次元バーコードでラベルに印刷しておき、荷物に添付しておく。
これらのＲＦＩＤやラベルから、端末に接続されたそれぞれの読取器により読み込むことで、集配経路選択システム（１００）に接続された端末からＥ記述を集配経路選択システム（１００）に送って、荷物ごとの適切なトラックを選択することができる。
【００３６】
・集配経路選択システム（１００）：
集配経路選択システム（１００）は、トラック側の端末からトラック集配経路を登録するデータベース（１０４）をもち、トラックの経路を蓄積・管理する。
そして、発荷元または集荷先側の端末から集配要求・制約を受け取ると、経路選択エンジン（１０２）により、その要求・制約を満足して、移動回数が一番小さい経路をもつトラックの識別子を返す。
【００３７】
＜集配経路選択システム（１００）における処理＞
集配経路選択システム（１００）の経路選択エンジン（１０２）における処理を、図６のフローチャートを用いて説明する。
集配経路選択システム（１００）は、例えば、ＲＦＩＤ読取機で読み取った、集配経路に関する要求・制約のデータ（Ｅ記述）を、端末から受け取る（Ｓ２０２）と、上述の定義３の充足順序関係を利用して、経路データベース（１０４）に登録されたトラック経路（Ｓ記述）から要求・制約を満足して、さらに移動回数が最小となる経路を探す。
比較対象となる二つの記述式（Ｅ，Ｓ）に対して定義２の状態遷移先を節点、ラベル付き遷移を名前付き枝とする木構造を生成して比較している。
そのため、経路要求を行っているＥ記述を木構造に変換する（Ｓ２０４）。そして、トラックの集配経路であるＳ記述は、トラックのデータを経路データベース（１０４）に登録するときに、木構造に変換されて登録されているので、Ｓ記述のトラックの経路の木構造をデータベースから取得する（Ｓ２０６）。
【００３８】
そして、定義３に従って、その二つの木構造において、互いに対応する節点同士が同じ名前をもつ枝を持つことをすべての節点に関して調べ、双模倣性(Bisimulation)により、充足順序関係を判断している（Ｓ２０８，Ｓ２１０）。この判断手法については、後で詳細に説明する。トラックの経路と充足順序関係があれば（Ｓ２１０でＹＥＳ）、トラックの識別番号（ＩＤ）と充足順序関係を保存する（Ｓ２１２）。
上述の充足関係を全てのトラックの経路に対してを調べる（Ｓ２１４，Ｓ２１６）。
全てのトラックの経路との充足順序関係を調べ終わる（Ｓ２１４でＹＥＳ）と、充足順序関係を満たすトラックが存在し（Ｓ２１８でＹＥＳ）、タスク依頼の移動経路要求と充足順序関係を満足するトラック経路が複数存在するときは、定義３の充足順序関係のｎが最小のもの、つまり移動回数が最小なものを選ぶ（Ｓ２２０）。
このとき、全ての移動経路の距離が既知の場合は、移動毎に移動距離の総和を計算して、それが最小の経路を選択するとよい。
【００３９】
＜充足順序関係の判定（Ｓ２０８，Ｓ２１０）＞
その充足順序関係の判定（Ｓ２０８，Ｓ２１０）は、双模倣性(Bisimulation)により、二つの木構造のそれぞれの根を、起点に部分木を持たない節点に至るまで、次の動作を実行することで行う。なお、双模倣性(Bisimulation)については、非特許文献１を参照されたい。
（１）まず、比較対象の節点が互いに同じ名前の枝を持つか調べる。
（２）同等の枝を持つ場合は枝の先にある節点について（１）を繰り返す。
（３）逆に持たない場合は一つ前の節点に後戻りして、残りの節点に関して（１）を繰り返す。
【００４０】
これを、図７を用いて説明する。図７において、左側は経路要求のＥ記述（ａ；（（ｂ；（ｃ＋ｄ））♯ｄ）の木構造３１０を示し、右側は集配経路のＳ記述（ａ；ｂ；（ｃ＋ｄ））の木構造３２０を示している。
上述の（１）により、起点である根が同じ名前の枝を持つか調べる（Ｓ３０２）と、同じ「ａ」という名前を持っている。そのため、上述の（２）により、その先の接点の枝で、同じ名前を有するか調べる（Ｓ３０４）。その結果、同じ「ｂ」を持っている。そのため（２）により、その先の枝を調べる（Ｓ３０６，Ｓ３０８）と「ｃ」及び「ｄ」で一致する。なお、節点を移動する毎（階層が深くなるごと）に移動回数を＋１する。
これで、双方の木構造に対して、起点を持たない節点に来たので、処理を終了し、「充足順序関係あり」とし、この集配経路を有するトラックの識別番号と節点を移動した回数（移動回数）ｎ（この場合３）とを得ることができる。
【図面の簡単な説明】
【００４１】
【図１】従来の集荷を説明する図である。
【図２】集配先の依存関係を示した図である。
【図３】トラックの経路を示す図である。
【図４】経路の記述例とその経路を示す図である。
【図５】実施例としてのシステム構成図である。
【図６】集配経路選択システムの処理を示すフローチャートである。
【図７】木構造を利用した判定処理を説明する図である。
【特許請求の範囲】
【請求項１】
予め複数の集配経路を蓄積した記憶手段を有する集配経路選択システムであって、
集配経路に乗せるべき対象の要求経路を入力する要求経路入力手段と、
入力された該要求経路と、前記蓄積された複数の集配経路とを比較し、該要求経路を満足する集配経路を求める比較手段と、
該要求経路を満足する集配経路の内、満足するための移動回数が最小の集配経路を出力する出力手段とを備え、
前記要求経路は、集配箇所の順序の制約や要求を記述したものであり、
前記集配経路は、集配箇所の順序を、前記要求経路記述のサブセットで記述したものであり、
前記比較手段は、前記要求経路と前記集配経路とを木構造に変換したもので比較するとともに、満足するために必要な移動回数も得る
ことを特徴とする集配経路選択システム。
【請求項２】
請求項１に記載の集配経路選択システムにおいて、
さらに、前記記憶手段に集配経路を蓄積するときに、集配経路の記述を木構造に変換して蓄積する手段を備え、
前記比較手段は、入力された要求経路の記述を木構造に変換し、前記記憶手段から木構造に変換された集配経路を読み出して比較する
ことを特徴する集配経路選択システム。
【請求項３】
請求項１又は２に記載の集配経路選択システムにおいて、
前記比較手段は、移動回数ではなく、移動ごとの移動距離の総和を出力し、
前記出力手段は、該要求経路を満足する集配経路の内、満足するための移動距離の総和が最小の集配経路を出力する
ことを特徴とする集配経路選択システム。
【請求項１】
予め複数の集配経路を蓄積した記憶手段を有する集配経路選択システムであって、
集配経路に乗せるべき対象の要求経路を入力する要求経路入力手段と、
入力された該要求経路と、前記蓄積された複数の集配経路とを比較し、該要求経路を満足する集配経路を求める比較手段と、
該要求経路を満足する集配経路の内、満足するための移動回数が最小の集配経路を出力する出力手段とを備え、
前記要求経路は、集配箇所の順序の制約や要求を記述したものであり、
前記集配経路は、集配箇所の順序を、前記要求経路記述のサブセットで記述したものであり、
前記比較手段は、前記要求経路と前記集配経路とを木構造に変換したもので比較するとともに、満足するために必要な移動回数も得る
ことを特徴とする集配経路選択システム。
【請求項２】
請求項１に記載の集配経路選択システムにおいて、
さらに、前記記憶手段に集配経路を蓄積するときに、集配経路の記述を木構造に変換して蓄積する手段を備え、
前記比較手段は、入力された要求経路の記述を木構造に変換し、前記記憶手段から木構造に変換された集配経路を読み出して比較する
ことを特徴する集配経路選択システム。
【請求項３】
請求項１又は２に記載の集配経路選択システムにおいて、
前記比較手段は、移動回数ではなく、移動ごとの移動距離の総和を出力し、
前記出力手段は、該要求経路を満足する集配経路の内、満足するための移動距離の総和が最小の集配経路を出力する
ことを特徴とする集配経路選択システム。
【図６】
【図７】
【図１】
【図２】
【図３】
【図４】
【図５】
【図７】
【図１】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００９−２８１７９１（Ｐ２００９−２８１７９１Ａ）
【公開日】平成２１年１２月３日（２００９．１２．３）
【国際特許分類】
【出願番号】特願２００８−１３２５２０（Ｐ２００８−１３２５２０）
【出願日】平成２０年５月２０日（２００８．５．２０）
【出願人】（５０４２０２４７２）大学共同利用機関法人情報・システム研究機構 (119)
【Ｆターム（参考）】
【公開日】平成２１年１２月３日（２００９．１２．３）
【国際特許分類】
【出願日】平成２０年５月２０日（２００８．５．２０）
【出願人】（５０４２０２４７２）大学共同利用機関法人情報・システム研究機構 (119)
【Ｆターム（参考）】
[ Back to top ]