(57)【要約】【課題】  挿入法において、種顧客を適切に選択して、より適切な暫定解を生成することが可能な経路探索方法等を提案する。【解決手段】  挿入法により暫定解を生成する場合に、顧客管理部３は、空間を複数の領域に分割し、種顧客選択部５は、分割された領域に存在する顧客からそれぞれ種顧客を選択する。暫定解生成部７は、選択された各種顧客とデポとの閉路に対して、他の顧客を挿入することにより、暫定解を生成する。これにより、種顧客として、ある地点の周辺に存在する顧客を集中的に選択することを防ぎ、挿入法の実行回数が少なくても良い暫定解を作成することが可能になる。【選択図】図１
2015038429.tif 000002
【特許請求の範囲】
【請求項１】
制約条件を満たして複数の顧客を巡回する経路を生成する経路探索方法であって、
顧客管理手段が、前記複数の顧客を２つ以上の顧客グループにグループ分けするグループ分けステップと、
種顧客選択手段が、種顧客として、前記各顧客グループから一つ又は複数の顧客を選択する種顧客選択ステップと、
暫定解生成手段が、前記制約条件の下で開始地点と前記各種顧客を結ぶ閉路に対して前記種顧客以外の顧客を挿入して暫定解を生成する暫定解生成ステップと、
経路生成手段が、前記暫定解に基づいて前記複数の顧客を巡回する経路を生成する経路生成ステップを含む経路探索方法。
【請求項２】
前記顧客管理手段が、前記複数の顧客のグループ分けを変更して、前記グループ分けステップにおいて分けられた前記顧客グループとは異なる第２顧客グループに変更するグループ変更ステップと、
前記種顧客選択手段が、第２種顧客として、前記各第２顧客グループから一つ又は複数の顧客を選択する種顧客選択ステップと、
前記暫定解生成手段が、前記開始地点と前記各第２種顧客を結ぶ閉路に対して、前記制約条件を満たす前記第２種顧客以外の顧客を挿入して第２暫定解を生成する第２暫定解生成ステップを含み、
前記経路生成ステップにおいて、前記経路生成手段は、前記複数の顧客を巡回する経路を、前記暫定解生成ステップ及び前記第２暫定解生成ステップにおいて生成された前記暫定解及び前記第２暫定解に基づいて生成する、請求項１記載の経路探索方法。
【請求項３】
前記各顧客は、空間又は平面上の経由地点に対応し、
前記グループ分けステップにおいて、前記顧客管理手段は、前記空間又は前記平面を複数の領域に分割し、前記各顧客グループは、前記各領域に含まれる経由地点に対応する顧客をグループ化したものであり、
前記経路生成ステップにおいて、前記経路生成手段が生成する経路は、前記複数の顧客を巡回するコストを小さくするものである、請求項１又は２に記載の経路探索方法。
【請求項４】
制約条件を満たして複数の顧客を巡回する経路を生成する経路探索装置であって、
前記複数の顧客を２つ以上の顧客グループにグループ分けする顧客管理手段と、
種顧客として、前記各顧客グループから一つ又は複数の顧客を選択する種顧客選択手段と、
前記制約条件の下で開始地点と前記各種顧客を結ぶ各閉路に対して前記種顧客以外の顧客を挿入して暫定解を生成する暫定解生成手段と、
前記暫定解に基づいて前記複数の顧客を巡回する経路を生成する経路生成手段を備える経路探索装置。
【請求項５】
コンピュータにおいて、請求項１から３のいずれかに記載の経路探索方法を実現するためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、経路探索方法、経路探索装置及びプログラムに関し、特に、制約条件を満たして複数の顧客を巡回する経路を生成する経路探索方法等に関する。
【背景技術】
【０００２】
現在、運送業界は、例えば、原油高騰による輸送燃料の増加，運送業に携わる労働者の減少などの重大な問題を抱えている。これらの問題は、最適な輸送路の算出による打開が見込まれる。これは、配送経路問題（VRP：Vehicle  Routing  Problem）を最適化することで解決が期待される。
【０００３】
発明者らは、ＶＲＰを解決するために、列生成法に、挿入法とtwo-opt法を組み合わせたものを提案した（非特許文献１参照）。これは、挿入法により暫定解（タイムウインドウなどの制約条件を守っていて、最適ではないが、それなりに良い解）を複数個生成し、その暫定解をtwo-opt法により改善した後、それを列生成法と組み合わせて最適解を探索するものである。ここで、挿入法は、種顧客と呼ばれる顧客を結ぶ閉路に対して、残りの顧客を、評価値を用いて挿入する手法である（非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】加来佑一朗、外４名，“物流コスト削減のための配送集荷経路問題の最適化”，火の国情報シンポジウム2013論文集，C-5-2，2013．
【非特許文献２】久保幹雄，“ロジスティクス工学”，朝倉書店，2003
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の手法では、挿入法において、種顧客をランダムに選択していた。そのため、例えばある地点の周辺に存在する複数の顧客が集中的にして選択された場合などには、精度のよい暫定解が得られなかった。
【０００６】
そこで、本願発明は、種顧客を適切に選択して、より適切な暫定解を生成することが可能な経路探索方法等を提案することを目的とする。
【課題を解決するための手段】
【０００７】
本願発明の第１の観点は、制約条件を満たして複数の顧客を巡回する経路を生成する経路探索方法であって、顧客管理手段が、前記複数の顧客を２つ以上の顧客グループにグループ分けするグループ分けステップと、種顧客選択手段が、種顧客として、前記各顧客グループから一つ又は複数の顧客を選択する種顧客選択ステップと、暫定解生成手段が、前記制約条件の下で開始地点と前記各種顧客を結ぶ閉路に対して前記種顧客以外の顧客を挿入して暫定解を生成する暫定解生成ステップと、経路生成手段が、前記暫定解に基づいて前記複数の顧客を巡回する経路を生成する経路生成ステップを含むものである。
【０００８】
本願発明の第２の観点は、請求項１記載の経路探索方法であって、前記顧客管理手段が、前記複数の顧客のグループ分けを変更して、前記グループ分けステップにおいて分けられた前記顧客グループとは異なる第２顧客グループに変更するグループ変更ステップと、前記種顧客選択手段が、第２種顧客として、前記各第２顧客グループから一つ又は複数の顧客を選択する種顧客選択ステップと、前記暫定解生成手段が、前記開始地点と前記各第２種顧客を結ぶ閉路に対して、前記制約条件を満たす前記第２種顧客以外の顧客を挿入して第２暫定解を生成する第２暫定解生成ステップを含み、前記経路生成ステップにおいて、前記経路生成手段は、前記複数の顧客を巡回する経路を、前記暫定解生成ステップ及び前記第２暫定解生成ステップにおいて生成された前記暫定解及び前記第２暫定解に基づいて生成するものである。
【０００９】
本願発明の第３の観点は、第１又は第２の観点の経路探索方法であって、前記各顧客は、空間又は平面上の経由地点に対応し、前記グループ分けステップにおいて、前記顧客管理手段は、前記空間又は前記平面を複数の領域に分割し、前記各顧客グループは、前記各領域に含まれる経由地点に対応する顧客をグループ化したものであり、前記経路生成ステップにおいて、前記経路生成手段が生成する経路は、前記複数の顧客を巡回するコストを小さくするものである。
【００１０】
本願発明の第４の観点は、制約条件を満たして複数の顧客を巡回する経路を生成する経路探索装置であって、前記複数の顧客を２つ以上の顧客グループにグループ分けする顧客管理手段と、種顧客として、前記各顧客グループから一つ又は複数の顧客を選択する種顧客選択手段と、前記制約条件の下で開始地点と前記各種顧客を結ぶ各閉路に対して前記種顧客以外の顧客を挿入して暫定解を生成する暫定解生成手段と、前記暫定解に基づいて前記複数の顧客を巡回する経路を生成する経路生成手段を備えるものである。
【００１１】
本願発明の第５の観点は、コンピュータにおいて、第１から第３のいずれかの観点の経路探索方法を実現するためのプログラムである。
【００１２】
なお、本願発明を、第５の観点のプログラムを定常的に記録するコンピュータ読み取り可能な記録媒体として捉えてもよい。
【発明の効果】
【００１３】
本願発明によれば、顧客は、複数のグループに分け、各グループから種顧客を選択することにより、種顧客が集中して選択されることを防ぎ、挿入法の実行回数が少なくても良い暫定解を作成することが可能になる。
【００１４】
さらに、本願発明の第２の観点によれば、グループを変更して改めて挿入法を実行することにより、新たな基準により種顧客を選択して、種顧客が集中的に選択されることを防ぐことが可能になる。
【００１５】
さらに、本願発明の第３の観点によれば、ＶＲＰは、平面又は空間上での移動を前提としており、この平面又は空間における領域分割を基準にして顧客をグループ化することにより、ＶＲＰに適した暫定解を得ることが可能になる。
【図面の簡単な説明】
【００１６】
【図１】本願発明の実施の形態の一例である経路探索装置の概略ブロック図である。
【図２】図１の経路探索装置１の動作の一例を示すフロー図である。
【図３】図１の顧客管理部３により設定される平面上の領域の一例を示す図である。
【図４】挿入法における評価値演算の一例を示す図である。
【図５】列生成法おける処理の一例を示す図である。
【図６】実験により得られたルートの一例を示す第１図である。
【図７】実験により得られたルートの一例を示す第２図である。
【発明を実施するための形態】
【００１７】
以下では、図面を参照して、本願発明の実施例について説明する。なお、本願発明は、この実施例に限定されるものではない。
【実施例】
【００１８】
図１は、本願発明の実施の形態の一例である経路探索装置の概略ブロック図である。経路探索装置１は、顧客管理部３（本願請求項の「顧客管理手段」の一例）と、種顧客選択部５（本願請求項の「種顧客選択手段」の一例）と、暫定解生成部７（本願請求項の「暫定解生成手段」の一例）と、経路生成部９（本願請求項の「経路生成手段」の一例）と、制御部１０と、顧客記憶部１１と、制約条件記憶部１２と、領域記憶部１３と、種顧客記憶部１５と、暫定解記憶部１７と、経路記憶部１９を備える。
【００１９】
顧客記憶部１１は、複数の顧客を記憶する。本実施例で、各顧客は、平面上の地点に対応付けられているものとする。当該平面上の所定の位置には、デポが存在する。デポは、探索する経路の開始地点である。例えば、各顧客から集荷したり、各顧客に配荷したりする場合には、デポは、配荷する荷物が集められている場所であり、集荷した荷物が集められる場所である。
【００２０】
制約条件記憶部１２は、制約条件を記憶するものである。制約条件は、例えば、各車両の最大積載量や、各顧客や各車両のタイムウインドウなどである。例えば、集荷や配荷する場合には、車両の最大積載量を超えて荷物を載せることはできない。そのため、探索する経路上では、各閉路を移動する車両の最大積載量を超えない範囲で、集荷及び配荷がなされるようにする。また、各顧客には、配送可能な時間帯がある。また、各車両にも、デポから出る時間及びデポに帰る時間には制限がある。そのため、探索する経路上では、各車両が、適切な時間帯にデポから出て、各顧客を配送可能な時間帯に経由して、適切な時間帯にデポに戻る必要がある。制約条件記憶部１２は、制約条件として、各車両の最大積載量や、各顧客や各車両のタイムウインドウなどを記憶する。
【００２１】
顧客管理部３は、平面を複数の領域に分割し、前記顧客記憶部１１に記憶された顧客を、各領域によってグループ化するものである。また、顧客管理部３は、分割された領域を変更することにより、グループ化された顧客を変更する。具体的な動作の一例については、図３を参照して説明する。領域記憶部１３は、顧客管理部３によって設定された領域を記憶するものである。
【００２２】
種顧客選択部５は、顧客管理部３によって設定された各顧客グループから、種顧客を一つ又は複数選択する。これにより、種顧客が特定の領域に集中することを防ぐことができる。暫定解は、複数存在した方が、探索された経路はよくなる。そのため、種顧客の選択は、複数回行われることとなる。ここで、各グループから選択する種顧客の個数は、選択によって変更することが望ましい。挿入法では、種顧客の数の閉路が生じることとなるため、閉路の個数を変えて、暫定解を求めることが望ましいためである。種顧客記憶部１５は、選択された種顧客を記憶する。
【００２３】
暫定解生成部７は、制約条件記憶部１２に記憶された制約条件を満たすように、デポと各種顧客を結ぶ各閉路に対して、種顧客以外の顧客を挿入して暫定解を生成する。具体的な動作については、後に説明する。暫定解記憶部１７は、生成された暫定解を記憶する。
【００２４】
経路生成部９は、暫定解に基づき、複数の顧客を巡回する経路を生成する。具体的な動作については、後に説明する。経路記憶部１９は、経路生成部９が生成した経路を記憶する。
【００２５】
制御部１０は、経路探索装置１の動作を制御するものである。
【００２６】
続いて、図２を参照して、図１の経路探索装置１の動作について説明する。図２は、図１の経路探索装置１の動作の一例を示すフロー図である。
【００２７】
まず、顧客管理部３は、平面上を複数の領域に分割し、領域を設定する（ステップＳＴ１）。図３を参照して、一例を説明する。図３では、実線２３にあるように、デポ２１を中心に４つの領域に分割する場合を示す。各領域に存在する顧客をグループ化する。
【００２８】
続いて、種顧客選択部５は、各顧客グループから種顧客を選択する（ステップＳＴ２）。図３では、各領域から一つの種顧客が選択され、４つの種顧客２５、２７、２９及び３１が選択されたとする。
【００２９】
続いて、暫定解生成部７は、制約条件を満たすように、デポと各種顧客を結ぶ各閉路に対して、評価値を用いて種顧客以外の顧客を挿入して、暫定解を生成する（ステップＳＴ３）。その処理について、一例を説明する。
【００３０】
使用される評価値Δは、式(1)により算出される。ここで、ｄjiは、あるルート上で、顧客ｉの次に顧客ｊを訪問したときの、その間の距離とする。図４にあるように、評価値Δkijは、（ａ）にあるように、顧客ｉから顧客ｊに直接行くことに代えて、（ｂ）にあるように、顧客ｉから顧客ｋを経由して顧客ｊへ到達する場合の距離の増加を評価するものである。暫定解生成部７は、各顧客を、制約条件を守れるもののうち、評価値Δが最も小さい箇所に挿入する。なお、評価値を計算するとき、制約条件を守れないものには大きな値を与え、全体としてΔが最も小さな箇所に挿入するようにしてもよい。
【００３１】
【数１】
2015038429.tif 000003
【００３２】
挿入法のみで作成された暫定解は、ルート上に交差があるなど、改良の余地のあるルートを多く含む場合がある。そこで、暫定解生成部７は、two-opt法を用いることで、暫定解を改良する。two-opt 法とは、ルート上に存在する枝の交差をなくす手法である。
【００３３】
ある閉路の中で、顧客ｉと顧客ｊの間の経路と、顧客ｋと顧客ｌの間の経路が存在するとする。暫定解生成部７は、顧客ｉ，ｊ間と顧客ｋ，ｌ間で式(2)が成立する場合、ルートが交差していると判断する。交差する箇所があると判定された場合は、顧客ｉ，ｊ間と顧客ｋ，ｌ間を、顧客ｉ、ｋ間と顧客ｊ、ｌ間のルートにつなぎかえる。このとき、交差を取り除くことでタイムウインドウが守られなくなる場合は、交差は削除しない。
【００３４】
【数２】
2015038429.tif 000004
【００３５】
制御部１０は、同じ領域分割の下で、暫定解の生成処理が所定の回数行われたか否かを判断する（ステップＳＴ４）。所定の回数が行われていない場合には、ステップＳＴ２の処理に戻る。種顧客選択部５は、各顧客グループから、選択する個数を変更して、種顧客を選択することが望ましい。挿入法は、アルゴリズムの性質上、種顧客数の閉路しか作られない。そのため、種顧客数を増減させることにより、様々な形の暫定解を作成することができるためである。
【００３６】
所定の回数が行われた場合、顧客管理部３は、領域を変更する（ステップＳＴ５）。本実施例では、図３の破線３３にあるように、領域を回転することにより変更するとする。これにより、種顧客２５及び２７は、以前は別のグループに属し、別々のグループから選択されたのに対し、変更後は同じグループから選択されることとなり、例えば種顧客選択部５が各グループから１つずつ種顧客を選択する場合には、同時には選択されないようになる。このように、領域を変更することにより、様々なバリエーションの暫定解を得ることができる。このように、顧客管理部３は、領域の少なくとも一つが、デポ２１を中心に放射状となるように設定し、この位置を回転等により変更することにより、領域を変更してもよい。
【００３７】
続いて、制御部１０は、領域の変更が所定の回数行われたか否かを判断する（ステップＳＴ６）。領域の変更が所定の回数行われていない場合には、ステップＳＴ２に戻り、種顧客選択部５は、新たに設定された領域に基づき種顧客を選択し（ステップＳＴ２）、暫定解生成部７は、挿入法及びtwo-opt法により暫定解を生成する（ステップＳＴ３）。このように、所定の回数繰り返すことにより、複数の暫定解が得られる。
【００３８】
経路生成部９は、複数の暫定解に対して、列生成法を用いて最適解を探索する。列生成法は、暫定解の個々のルートを組み合わせることで、最適解を探索するものである。図５は、列生成法による処理の一例を示す。暫定解５１及び５３が得られたとする。ここで、暫定解５１における閉路５５と、暫定解５３における閉路５７を組み合わせることにより、暫定解５１及び５３よりも移動距離等のコストの低い経路５９を得ることができる。列生成法では、組み合わせの候補が増えるほど、解は良くなる。そのため、暫定解は、複数作成しておくことが望ましい。経路生成部９は、最終的な経路として、例えば最も移動距離が短いもののようにコストの低いものを選択する。
【００３９】
続いて、実験について説明する。以下では、領域を設定して種顧客を選択することを提案手法といい、ランダムに選択することを従来手法という。はじめに、提案手法と従来手法の計算時間及び総走行距離の分散の比較を行う。次に、それを受けて、提案手法の有用性を検証するためにベンチマーク（http://web．cba．neu．edu/~msolomon/problems．htm参照）を用いた実験を行う。使用したPCのCPUはES-2620  2.00GHz、メモリ64GB、OSはWindows（登録商標）7、プログラミング言語はCである。
【００４０】
表１は、提案手法と従来手法の計算時間の比較である。計算時間は、顧客分布により、提案手法及び従来手法の解の変化がそれぞれ1%以内で収束するまで、挿入法の反復回数を変化させた場合の結果である。表１より提案手法の方が高速であることが確認できた。これは、種顧客を適切に選択したことで列生成法に用いる暫定解を削減できたからである。
【００４１】
【表１】
2015038429.tif 000005
【００４２】
また，表２は、試行回数５回での総走行距離の分散の比較である。提案手法は、従来手法に比べて分散が少なく、安定した解を導出できていることが確認できた。これは、種顧客の選択がより均等に行えたためと考えられる。
【００４３】
【表２】
2015038429.tif 000006
【００４４】
続いて、提案手法の有用性を確かめるために、顧客数が異なる4つのベンチマークを用いて実験を行う。実験結果がベンチマークテストの解に近いほど、最適解が得られたと評価することができる。
【００４５】
表３は、実験10回のうち、最も総走行距離の短かった結果を示す。また、図６及び図７は、ルートの一例を示す。表３より、提案手法は、ほとんど最適解を導出できたといえる。詳細には、図６のルートは、表３から最適化できたといえる。図７のルートは、ベンチマークの解よりも総走行距離が0.6%程長い結果になった。例えば、or-opt法などの他の局所探索法を用いて暫定解の質を向上することにより、暫定解を向上させることが期待される。
【００４６】
【表３】
2015038429.tif 000007
【符号の説明】
【００４７】
１  経路探索装置、３  顧客管理部、５  種顧客選択部、７  暫定解生成部、９  経路生成部、１０  制御部、１１  顧客記憶部、１２  制約条件記憶部、１３  領域記憶部、１５  種顧客記憶部、１７  暫定解記憶部、１９  経路記憶部、２１  デポ、２３  領域分割、２５，２７，２９，３１  種顧客、３３  領域分割、４１  デポ、４３，４５，４７  顧客、５１，５３  暫定解、５５，５７  閉路、５９  経路
【図１】
2015038429.tif 000008
【図２】
2015038429.tif 000009
【図３】
2015038429.tif 000010
【図４】
2015038429.tif 000011
【図５】
2015038429.tif 000012
【図６】
2015038429.tif 000013
【図７】
2015038429.tif 000014