JP5612817B2 - 複数車両の配送経路を求めるための方法、コンピュータ・システム及びコンピュータ・プログラム - Google Patents

Description

本発明は、複数の地点に車両で物品を届けるための配送経路を求める方法、装置及びプログラムに関する。詳細には、車両数及び車両間の稼働率等のばらつきの観点から、局所探索法を行なうことによって、より少ない車両数の解を求める方法に関する。

配送経路問題については、種々の解法が提案されている。例えば、遺伝アルゴリズム法（特許文献１、４）、最近傍法（特許文献２）、クラスタリング法（特許文献３）などがある。

該配送経路問題では、車両数の低減が最も重要な目的であり、車両数が同じであるならば、走行距離（あるいは走行時間）が短縮されることが次に重要な目的である。この２つの目的は、多くの場合、同時には達成できないトレードオフの関係にある。例えば、図１に示すように配置された６つの配送地点に、物品を３個まで積載できる車両で、中央にある拠点から物品を１つずつ届ける場合、（Ｂ）の経路は車両数２であるので、（Ａ）の経路より良いと言えるが、走行距離だけを見ると（Ａ）の方が短く、より良い経路であることが分かる。

上の例について、すべての解を列挙して車両数と走行距離についてプロットしたのが図２である。△を記した解が（Ａ）経路に対応し、○を記した解が（Ｂ）経路に対応する。前者は、所定の初期解から走行距離を短縮する方向に局所探索して得られた解であり、走行距離の点では最も優れた解である。ところが、車両数の点では、後者より劣る。

この問題に対処するために、局所探索で得られた解に対し所定の評価値を悪くする方向に解を更新することを許容する方法が知られている。その一つがタブー探索（非特許文献１）である。タブー探索は、評価値がより良い近傍の配送経路に遷移するときに、タブーリスト中の操作を行なわないことにより、探索を停滞させることなく最適解を探す方法である。しかし、車両数を低減する様に方向付けする手段は何も採られておらず、車両数に関しては、ランダムな方向へ探索される。たとえ車両数が低減された解が見つかったとしても、それは偶然に過ぎない。上記特許文献１、２、及び４においてもその点は同様である。また、上記クラスタリング法（特許文献３）は、配送地点がある程度地理的にまとまっている場合への適用に限定されてしまう。
特開２００１−２３３４1１３号公報 特開２００１−２８３１３６号公報 特開２００３−２６３３５号公報 特開２００５−４３９７４号公報 Ｉ． Ｈ． Ｏｓｍａｎ， "Ｍｅｔａｓｔｒａｔｅｇｙ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｎｄ ｔａｂｕ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ"， Ａｎｎａｌｓ ｏｆ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， Ｖｏｌ． ４１， ｐｐ． ４２１−４５１， １９９３．

そこで、本発明は配送経路問題における最も重要な目的である、車両数が低減された解を求める方法を提供する。

即ち、本発明は、下記の方法である。
記憶手段を備えるコンピュータにより、複数の車両が、或る拠点から複数の配送地点に物品を届ける配送計画を作成する方法であって、
所与の現在の解Ｓの近傍解からなる解集合（Ｎ（Ｓ））について、所与の終了条件に達するまで、局所探索を反復して、前記Ｓを更新して、最適解Ｓ^ｂｅｓｔを求めるステップを含み、
該局所探索において、車両数が最も少ない解を探索するステップ、次いで、車両数が最も少ない解が複数ある場合には、該複数の解について、下記式（１）で定義される、車両ごとの評価値Ｂ_ｋ（ｔ）（ｔ∈Ｎ（Ｓ））の、下記式（２）で定義される車両間のばらつきの少なさを示す指標β（ｔ）が最も小さい解を探索するステップを含む、ことを特徴とする方法。
Ｂ_ｋ（ｔ）＝Σ_{ｉ∈Ｃｋ（ｔ）} ｐ_ｉ／Ｍ （１）

β（ｔ） ＝ １−Σ_{ｋ∈σ（ｔ）}Ｂ_ｋ（ｔ）^ｍ／｜σ（ｔ）｜ （２）

ここで、
ｐ_ｉ：各配送地点ｉの所与の特徴量
Ｍ：１つの車両が訪問する配送地点の特徴量の上限値もしくは特徴量の全車両に亘る総和
σ（ｔ）：解ｔで使用される車両の集合
|σ（ｔ）|：解ｔで使用される車両の合計数
Ｃ_ｋ（ｔ）：車両ｋ∈σ（ｔ）が訪問する配送地点の集合
ｍ：１より大きい数値

上記本発明は、配送経路問題に、車両数が少なくなるように荷物等を割り当てる等の方向付けした点を特徴とする。これにより、巡回セールスマン問題に積載容量や稼動時間枠を制約として課した上記各従来の方法における問題、即ち、経路としては短くても、各車両の積荷が少なくなる結果、車両数が増えてしまうという問題を解決する。

図３は、本発明を実装することができるコンピュータ・ハードウェアの例を示すブロック図である。該コンピュータ・システム（３０１）は、ＣＰＵ（３０２）とメイン・メモリ（３０３）と含み、これらはバス（３０４）に接続されている。ＣＰＵ（３０２）は好ましくは、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＸｅｏｎ（商標）シリーズ、Ｃｏｒｅ（商標）シリーズ、Ａｔｏｍ（商標）シリーズ、Ｐｅｎｔｉｕｍ（商標）シリーズ、Ｃｅｌｅｒｏｎ（商標）シリーズ、ＡＭＤ社のＰｈｅｎｏｍ（商標）シリーズ、Ａｔｈｌｏｎ（商標）シリーズ、Ｔｕｒｉｏｎ（商標）シリーズ及びＳｅｍｐｒｏｎ（商標）などを使用することができる。バス（３０４）には、ディスプレイ・コントローラ（３０５）を介して、ＬＣＤモニタなどのディスプレイ（３０６）が接続される。ディスプレイ（３０６）は、そのコンピュータ・システム（３０１）上で動作中のソフトウェアについての情報を、適当なグラフィック・インターフェースで表示するために使用される。バス（３０４）にはまた、ＩＤＥ又はＳＡＴＡコントローラ（３０７）を介して、ハードディスク又はシリコン・ディスク（３０８）と、ＣＤ−ＲＯＭ、ＤＶＤ又はＢｌｕ−ｒａｙドライブ（３０９）が接続されている。ＣＤ−ＲＯＭ、ＤＶＤ又はＢＤドライブ（３０９）は、必要に応じて、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はＢＤからプログラムをハードディスク又はシリコン・ディスク（３０８）に導入するために使用される。バス（３０４）には更に、キーボード・マウスコントローラ（１１０）を介して、或いはＵＳＢコントローラ（図示せず）を介して、キーボード（３１１）及びマウス（３１２）が接続されている。

以下、図４に示す本発明の方法を示すフローチャートを参照して、本発明の方法を説明する。先ず、所与の初期解を現在の解Ｓ及び最適解Ｓ^ｂｅｓｔとして設定し、及び、局所探索の反復回数を表すτを１に設定する（４０１）。

該初期最適解Ｓ^ｂｅｓｔは、公知の方法で得られた解であってよい。例えば、図５に示すように、あらかじめ記憶された配送地点のデータを用いて、配送地点ごとに、他の総ての地点への距離を、短い順で地点を並べたリスト（以下「近傍リスト」という）を準備しておき、ある地点から最も近い未訪問の地点を探索することによって初期の最適解を生成することができる（最近傍法）。ここで、各地点間の距離は、デジタル道路ネットワーク上の最短路計算などで求めておき、地点対地点の表の形式で保持する。また、地点間の距離をユークリッド距離で表し、該近傍リストの代わりにｋ−ｄ木というデータ構造を用い、同じく最近傍法などで初期最適解を求めてもよい。その他の初期最適解生成法としては、挿入法やセービング法などがある（例えば、Ｍ．Ｍ．Ｓｏｌｏｍｏｎ，”Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ａｎｄ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍｓ ｗｉｔｈ ｔｉｍｅ ｗｉｎｄｏｗｓ ｃｏｎｓｔｒａｉｎｔｓ”， Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ，Ｖｏｌ．３５， Ｎｏ．２， ｐｐ２５４−２６５，１９８７ ）。後述する実験では、車両をある台数分（25台）用意しておき、いずれかの車両が訪問できる未訪問の地点のうち、現在位置に最も近い地点を、次々に訪問する方法（並列最近傍法）を用いて、初期最適解を求めた。

解ｔの表現形式は任意であってよい。例えば図６において、中央部の□で示す拠点から地点１、２、５に配送する経路と、４、６、３、７を配送する経路の解は、便宜的に拠点の番号を0として、(0,1,2,5,0,4,6,3,7) と表現してよい。通常は、目的関数を効率的に計算するための情報を含むデータ構造として表現される。例えば、地点１、２、５への配送量が10, 10, 20だった場合、経路上のその地点までの総配送量を計算しておき、地点１には10、地点２には20、地点５には40を関係付けておくことで、配送経路の最後の地点５に関係付けられた総配送量を確かめるだけで、その車両の積載量を知ることができる。

図４に戻ると、図示していないが、前記Ｓの近傍解からなる解集合Ｎ（Ｓ）を予め保存しておき、もしくは、所与の方法により求める。近傍解を生成するためには、任意の手法を用いてよく、例えば図７に示すように、或る経路中の２本の辺を切って新たな２本でつなぎなおす方法（２−Ｏｐｔ法）、配送地を他の経路に入れるパスシフト法（Ｐａｔｈ ｓｈｉｆｔ法）、経路中の配送地を交換するパス交換法（Ｐａｔｈ ｓｗａｐ法）等を用いることができる。

好ましくは、近傍解を作成するに先立ち、Ｏ（１）フィージビリティー・チェックを行う。これは、近傍解の数は地点数の２乗オーダー以上あり、すべての近傍解について局所探索を行なおうとすると時間がかかるからである。上記Ｏ（１）はオーダーワンと読み、配送地点数によらず定数時間で実行できることを意味する。該Ｏ（１）フィージビリティー・チェックは、経路中の削除する辺をまず決め、その辺の長さをヒントに走行距離が短縮されうる地点を限定した上で近傍解を生成する。例えば、２−ｏｐｔ法で交換される２本の辺の内、少なくとも一方は短くならないと交換後の走行距離が短縮されないので、図８（１）のように、まず地点Ａに着目し削除する辺をＡＢと決めれば、交換相手の辺は地点Ａを中心に、辺ＡＢを半径にした円の内側にある地点だけを調べれば見つかるはずである。各地点を中心にしてある半径以内の地点を求めるためには、上記近傍リストを用いると便利である。図８（１）では、地点Ｄ及びＥが候補になる。また、パスシフト法についても、図８（２）のように半径ＤＥの円の内側だけを見ることで探索候補の近傍解を限定することができる。ＢＤ＞ＤＥかつＢＥ＞ＤＥのケースについては、ＡＢ＋ＢＣ−ＡＣを半径にして地点ＡあるいはＣを中心にして探索して、近傍解を生成する（詳しくは、Ｎ．Ｐａｒｋ， Ｈ．Ｏｋａｎｏ ａｎｄ Ｈ．Ｉｍａｉ， ”Ａ ｐａｔｈ−ｅｘｃｈａｎｇｅ−ｔｙｐｅ ｌｏｃａｌ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｖｅｈｃｌｅ ｒｏｕｔｉｎｇ ａｎｄ ｉｔｓ ｅｆｆｉｃｉｅｎｔ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ” Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ Ｓｏｃｉｅｔｙ ｏｆ Ｊａｐａｎ， Ｖｏｌ．４３， Ｎｏ．１，ｐｐ．１９７−２０８， ２０００を参照されたい）。

該解集合について、局所探索を行う（４０５）。本発明は、該局所探索において、車両数の比較を第１に行った後に、下記式（１）で定義される、車両ごとの評価値Ｂ_ｋ（ｔ）の、下記式（２）で定義される車両間のばらつきの少なさを示す指標β（ｔ）が小さい解を探索し、車両数を減少する方向付けを行なうことを特徴とする。
Ｂ_ｋ（ｔ）＝Σ_{ｉ∈Ｃｋ（ｔ）} ｐ_ｉ／Ｍ （１）

β（ｔ） ＝ １−Σ_{ｋ∈σ（ｔ）}Ｂ_ｋ（ｔ）^ｍ／｜σ（ｔ）｜ （２）

上記式（１）において、ｐ_ｉは各配送地点ｉの所与の特徴量であり、これを１つの車両が訪問する配送地点の特徴量の上限値もしくは特徴量の全車両に亘る総和（Ｍ)で除することによって、車両の稼動状態、例えば積載率、を表す評価値Ｂ_ｋ（ｔ）を得る。該特徴量ｐ_ｉ及びＭの第１の例は、ｐ_ｉが下記式（３）で表される稼働時間の近似値であり、Ｍが車両の稼動時間の上限値である。
ｐ_ｉ＝nn_i + ｔ_i （３）

式（３）において、nn_iは、配送地点iに最も近い配送地点への距離と、２番目に近い配送地点への距離の平均値であり、ｔ_iは配送地点iでの作業時間（荷物の積み下ろし等）である。第２の例は、ｐ_ｉが配送地点iへの配送量であり、Ｍが車両の積載量の上限値、即ち、積載容量である。第３の例は、ｐ_ｉが配送地点iに割り当てられた定数であり、Ｍがその上限値もしくは総和である。前記定数が１の場合、Ｍは総地点数とする。第４の例は、ｐ_ｉが配送地点iに割り当てられた乱数であり、Ｍが全車両に亘る乱数の総和である。好ましくは、ｐ_ｉは上記稼働時間の近似値である。

式（２）で求められるβ（ｔ）は、評価値Ｂ_ｋ（ｔ）の車両間のばらつきの少なさを表す指標である。該β（ｔ）がより小さくなる方向、即ち、ばらつきが大きくなる方向、に局所探索することによって、車両数を減少することができる。式（２）において、Ｂ_ｋ（ｔ）のべき数ｍは、１より大きい数値であり、１．５〜３が好ましく、より好ましくは１．５〜２である。Ｂ_ｋ（ｔ）^ｍを解ｔにおいて使用される車両の合計数|σ（ｔ）|で除して正規化する。

該β（ｔ）は、上記第２の例、即ち特徴量ｐ_ｉがｉへの配送量、Ｍが積載容量の場合、所謂ビンパッキング問題に局所探索を適用する際に、解空間を平滑にするために使用されるものと同様のものである。ビンパッキング問題は、使用するビンの数を最小化するようなビンへのアイテムの詰め方を求める問題である。しかし、この問題の目的関数はビンの数であり、ビンの充填率など別の要素が考慮されないため解空間が平坦で、局所探索がうまく働かない。そのために提案されたのが、ばらつきの指標である(詳細はＴ．Ｏｓｏｇａｍｉ ａｎｄ Ｈ． Ｏｋａｎｏ “Ｌｏｃａｌ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｂｉｎ ｐａｃｋｉｎｇ ｐｒｏｂｌｅｍ ａｎｄ ｔｈｅｉｒ ｒｅｌａｔｉｏｎｓｈｉｐｓ ｔｏ ｖａｒｉｏｕｓ ｃｏｎｓｔｒｕｃｔｉｏｎ ｈｅｕｒｉｓｔｉｃｓ”， Ｊｏｕｒｎａｌ ｏｆ Ｈｅｕｒｉｓｔｉｃｓ， Ｖｏｌ． ９， ｐｐ．２９−４９， ２００３を参照されたい)。この指標は、空に近いビンと満杯に近いビンがある時、空に近いビンから満載に近いビンにアイテムを移動することにより値が減少する。図９は、容量１のビンが２つあり、大きさ0.25のアイテムが４つある場合の、３通りの詰め方を示したものである。図９（１）の詰め方は、他の２つの詰め方と比べばらつきが少なく、望ましくない。図９（２）の詰め方はばらつきが大きく、あと１つのアイテムを移動すれば右の詰め方に以降できる状態である。図９（３）はビンが１つ空になっており、最も望ましい。本発明はこの指標を、配送経路問題に適する方法で初めて適用することによって、車両数の低減を達成する。

再び図４を参照すると、係数ａが「０」に設定される（４０２）。該係数は、上記β（ｔ）を局所探索における目的関数に含めるか否かを表し、０の場合には目的関数に含まれず、１の場合には目的関数に含まれる。このように、車両数及び稼働時間もしくは走行距離を短くする方向の探索（第１局所探索）によって現在解Ｓが更新されなかったときには、車両間での積載量等のばらつきを大きくする方向の探索（第２局所探索）を行なうことによって、車両数の低減を達成する。図４記載の態様では、第１局所探索を先ず行い、次に、第２局所探索を行っているが、逆の順序であってもよい。

係数ａの設定は、上記反復回数τの愚奇を判断することによって行われる（４０３）。第１回目（τ＝０）の第１局所探索該（ａ＝０）では、目的関数にβ（ｔ）は含まれない。第１局所探索が終了し現在解Ｓが更新されなかったときには、τが一つ増加されて（４１２）、奇数と判断される結果（４０３）、係数ａが「１」とされ（４０４）、β（ｔ）が目的関数に組み込まれて、第２局所探索が行なわれる（４０５）。

第１（ａ＝０）及び第２局所探索（ａ＝１）は、下記式（４）で表される目的関数を用いて行われる。

f(ｔ,a) = （|σ（ｔ）|，aβ（ｔ），Σ_{k∈σ（ｔ）}d_k（ｔ）） （４）

ここで括弧は左から右の順に（lexicographic order）評価されることを表し、d_k（ｔ）は問題設定、即ち、求めるべき解が最短距離であるか最短時間であるか、に応じて解ｔにおける車両kの走行距離あるいは稼動時間を表す。例えば、(A,B)と(C,D)という２つの目的関数値がある時、コンピュータにおけるこれらの比較は次のように行われる：
if (A>C) then assert (A,B) > (C,D)
else if (A<C) then assert (A,B) < (C,D)
else if (B>D) then assert (A,B) > (C,D)
else if (B<D) then assert (A,B) < (C,D)
else assert (A,B) = (C,D)
式（４）において、a=1の場合（第２局所探索）において、βよりも上位で総車両数|σ|を比較する。これは、車両数が減少してもβが増大する、つまり大小関係に矛盾が生じる場合がある事が見出されたからである。

ａ＝０のとき（第１局所探索）は、車両数が最も少ない解を探索し、車両数が最も少ない解が複数ある場合には、該複数の解のうち車両の走行距離もしくは稼動時間の全車両に亘る和が最も小さい解を探索する（４０５）。図４において「arg min」（４０５）は、最小の値を得る引数を意味する。なお、最も小さい解が複数あった場合には、そのうちの任意のものを選んでよい。得られた解S_ｂを最初に設定した最適解S^bestと、上記と同様に比較し、局所探索で得られた解S_ｂの目的関数値がより小さい場合には、S_ｂをS^bestとして保存し、最適解を更新する（４０７）。

次いで、所定の終了条件を満たしているか否かが判断され（４０８）、満たしていればS^bestを出力して終了する（４０９）。終了条件としては、反復回数の上限、計算時間の上限、最適解が更新されなかった直近の反復回数の上限などを用いる。終了条件が満たされていない場合には、第１局所探索で得られた解S_ｂと現在の解Ｓについて、上記と同様に比較する（４１０）。前記解S_ｂの車両数が現在解Ｓの車両数より小さいか、車両数が同じであっても車両の走行距離もしくは稼動時間の全車両に亘る和が小さい場合には（４１０でＹｅｓ）、Ｓ_ｂを現在解Ｓとして保存して現在解を更新し、該新たな現在解Ｓの近傍解が読み出されもしくは作成され（図示していない）て、再度第１局所探索が行なわれる。そうでない場合には、局所探索の反復回数τを１つ増加し（４１２）、第２局所探索に入る。

第２局所探索では、τが偶数になることによって（４０３でＹｅｓ）、係数aが１となり（４０４）、β（ｔ）が目的関数に組み込まれ、現在の解Sの近傍について、先ず車両数が最も少ない解を探索し、車両数が最も少ない解が複数ある場合には、該複数解のうち前記指標β（ｔ）が最も小さい解を探索し、β（ｔ）が最も小さい解が複数ある場合には、β（ｔ）が同じである解のうち車両の走行距離もしくは稼動時間の和を比較して、走行距離もしくは稼動時間の和が最も小さい解を探索する。得られた解Ｓ_ｂについて、最適解Ｓ^bestと第１局所探索で用いた目的関数により比較する。即ち、解Ｓ_ｂがＳ^bestより車両数が少ないか、車両数が同じであっても走行距離等が小さいかを比較し、そうである場合には、該Ｓ_ｂをＳ^bestと置く（４０７）。次いで、所定の終了条件に達しているか否かが判断され（４０８）、達している場合にはＳ^bestを出力して終了する（４０９）。達していない場合には、得られた解S_ｂを現在の解Sと、第２局所探索で用いた目的関数を用いて比較する。即ち、車両数がより小さい場合、車両数は同じであるが指標β（ｔ）がより小さい場合、又は車両数及びβ（ｔ）が同じであるが走行距離もしくは稼動時間の和がSより小さい場合には、S_ｂにより現在解Sが更新される（４１１）。次いで、新たな現在解の近傍解集合を読み出し、もしくは作成し（図示していない）第２局所探索を繰り返す（４０５）。現在解Ｓが更新されなかったときにはτを一つ増加して、ａを０とし（４０２）、第１局所探索を行なう。このようにして、所定の終了条件に達するまで、第１局所探索と第２局所探索が交互に繰り返されて、車両数が最も少ない最適解Ｓ^bestを得る。

実施例１
ランダムに生成した時間枠のない入力データに本発明の方法を適用した。配送地点は矩形領域内にランダム一様分布で100点配置し、矩形領域の中央に拠点を配置した。各配送地点に配送する荷物はランダムに1〜10個の中から設定し、最大稼動時間は、積載容量が十分大きいトラック3台で100点を訪問できる程度とした。初期最適解は、車両を25台用意しておき、いずれかの車両が訪問できる未訪問の地点のうち、現在位置に最も近い地点を、次々に訪問する方法（並列最近傍法）を用いて求めた。

結果を図１０に示す。車両の積載容量を、荷物の総量をＷ、本実施例の場合、荷物の平均値５個×１００＝５００個、として、Ｗ／５からＷまで変化させた場合に（横軸）、各手法が反復１０回で得た最適な車両数の平均（縦軸）を示している。同図において、ＬＳは第１局所探索（ａ＝０）のみ行った場合、ＴＳは後述するタブー探索、ＢＰ（ｌｏａｄ）は車両の評価値を積載率としたもの、ＢＰ（ｕｔｉｌ）は車両の評価値を稼動率の近似値としたもの、ＢＰ（ｒａｎｄ）は配送地点の特徴量を乱数としたもの、ＢＰ（ｃｏｎｓｔ）は配送地点の特徴量を定数（本実施例では１００）としたものである。ＢＰ（ｕｔｉｌ＾３）は車両の評価値を稼動率の近似値とし、ｍ＝３としたものである。なお、その他の設定ではｍ＝２とした。各車両の積載容量が（Ｗ／５）×３の場合の各手法の結果は、ＬＳ＝４．２， ＴＳ＝４．０， ＢＰ（ｌｏａｄ）＝３．４， ＢＰ（ｕｔｉｌ）＝３．３， ＢＰ（ｒａｎｄ）＝３．４， ＢＰ（ｃｏｎｓｔ）＝３．５， ＢＰ（ｕｔｉｌ＾３）＝３．４ であった。

上記結果から以下のことが分った。目的関数にβ（ｔ）項を入れた第２局所探索を行うと、最大積載量の制約の強弱（横軸）によらず、局所探索やタブー探索と比べて少ない車両数の解を得ることができる。この点は、配送地点の特徴量として定数や乱数を用いても同様である。特徴量の中でも、稼動率の近似値を用いると、より少ない車両数の経路を求めることができる。

比較するタブー探索は、非特許文献１記載の方法を参考にした方法を用いた。図１１にそのフローを示す。同図において、ｂ（ｓ，ｔ）は解ｓから近傍解ｔ∈Ｎ（ｓ）を生成するために着目した地点（base）を表す。一度探索したbaseをタブーリストに蓄えておき、タブーリストに入れられているbaseを近傍解の探索候補から外す様にした。また、タブーリストの大きさの上限値θは、地点数の１０分の１とし、連続して１０回の反復で、現在解Ｓが更新されなければ、タブーリストを初期化するようにした。同図、ステップ１１０３の近傍探索において、タブーリストに入っているbaseを避ける判断をする。ステップ１１０４及び１１０５でタブーリストを更新する。ステップ１１０８において、探索で得られた近傍解Ｓ_bが現在解Ｓより良くない場合でも、現在解が連続して更新されない反復回数が10回以内の間は（ステップ1111）、「山登り」の動きを許して局所探索を続行した。

実施例２
次に、時間枠付きのテストインスタンスとして広く利用されているSolomonのインスタンス（詳細はＭ．Ｍ．Ｓｏｌｏｍｏｎ， “Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ａｎｄ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍｓ ｗｉｔｈ ｔｉｍｅ ｗｉｎｄｏｗｓ ｃｏｎｓｔｒａｉｎｔｓ”， Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， Ｖｏｌ． ３５， Ｎｏ． ２， ｐｐ．２５４−２６５， １９８７を参照されたい）を用いて本発明の方法を上記タブー探索と比較した。地点数はいずれも100点である。Solomonのインスタンスには６つのクラス（ランダムな点配置、クラスタ化された点配置など）がある。各クラスの１つの問題について、実施例１と同様に車両数25台の初期解から出発し、ThinkPad X32 （Intel Pentium M 1.8GHz CPU）で100秒まで実行して得られた解および収束の様子を下表１及び図１２〜１７に示す。

＊１：http://w.cba.neu.edu/~msolomon/heuristi.htmを参照されたい。

Ｒ２０１及びＲＣ２０１は、車両の積載容量が十分大きいため、最大稼動時間の制約が利いて経路長が制限されるインスタンスである。Ｒ２０１は地点の配置がランダムで、ＲＣ２０１は地点がランダムな配置とクラスタ化された配置の混合になっている。これら２つのインスタンスについて、本発明の方法とＴＳの差が顕著であり、本発明の方法における第２局所探索の効果が大きいことが分かった。

Ｒ１０１、ＲＣ１０１はＲ２０１、ＲＣ２０１と比べて最大稼動時間が長い。Ｒ１０１も同様に最大稼動時間の制約が利いて経路長が制限される。ＲＣ１０１は最大稼働時間と積載容量の両方の制約が強く、いずれかの制約が利くことで経路長が制限される。Ｒ１０１は地点の配置がランダムで、ＲＣ１０１は地点がランダムな配置とクラスタ化された配置の混合になっている。これらのインスタンスについても、本発明の方法がＴＳよりも少ない車両数の解を見つけた。

Ｃ１０１、Ｃ２０１はそれぞれ、クラスタ化された地点配置であり、Ｃ１０１は最大稼動時間が長いインスタンス、Ｃ２０１は短いインスタンスである。最大稼働時間と積載容量の両方の制約が強く、いずれかの制約が利くことで経路長が制限される。Ｃ１０１ではいずれの方法でも最適解が得られたが、Ｃ２０１では本発明の方法がＴＳよりも少ない車両数の解を見つけた。

本発明の方法は、様々なタイプの配送経路問題において、車両数がより低減された解を見出すのに有効である。

配送経路と車両数の関係の一例を示す説明図である。 図１に示す例に於ける解を、車両数と走行距離についてプロットしたグラフである。 本発明を実装することができるコンピュータ・ハードウェアの例を示すブロック図である。 本発明の方法を示すフローチャートである。 近傍リストの構造の例を示す説明図である。 配送経路の解を例示する説明図である。 近傍解の生成方法を示す説明図である。 Ｏ（１）フィージビリティー・チェックの方法を示す説明図である。 ビンパッキング問題における異なる解におけるβ（ｔ）を示す説明図である。 実施例１の結果を示すグラフである。 実施例１及び２で用いたタブーサーチのフローチャートである。 実施例２において、インスタンスＣ１０１についての結果を示すグラフである。 実施例２において、インスタンスＣ２０１についての結果を示すグラフである。 実施例２において、インスタンスＲ１０１についての結果を示すグラフである。 実施例２において、インスタンスＲ２０１についての結果を示すグラフである。 実施例２において、インスタンスＲＣ１０１についての結果を示すグラフである。 実施例２において、インスタンスＲＣ２０１についての結果を示すグラフである。

符号の説明

３０１ コンピュータ・システム
３０２ ＣＰＵ
３０３ メイン・メモリ
３０４ バス
３０５ ディスプレイ・コントローラ
３０６ ディスプレイ
３１１ キーボード

Claims (11)

1. 記憶手段を備えるコンピュータにより、複数車両の配送経路を求めるための方法であって、
   所与の現在の解Ｓの近傍解からなる解集合（Ｎ（Ｓ））を作成し、前記解集合（Ｎ（Ｓ））について、所与の終了条件に達するまで、局所探索を反復して、前記現在の解Ｓを更新して、最適解Ｓ^ｂｅｓｔを求めるステップを含み、
   該局所探索において、車両数が最も少ない解を探索するステップ、次いで、車両数が最も少ない解が複数ある場合には、該複数の解について、下記式（１）で定義される、車両ごとの評価値Ｂ_ｋ（ｔ）（ｔ∈Ｎ（Ｓ））の、下記式（２）で定義される車両間のばらつきの少なさを示す指標β（ｔ）が最も小さい解を探索するステップと、
   β（ｔ）が最も小さい解が複数ある場合には該複数の解について、走行距離もしくは稼動時間の全車両に亘る和が最も小さい解を探索するステップとを含み、
   Ｂ_ｋ（ｔ）＝Σ_{ｉ∈Ｃｋ（ｔ）} ｐ_ｉ／Ｍ （１）
   β（ｔ） ＝ １−Σ_{ｋ∈σ（ｔ）}Ｂ_ｋ（ｔ）^ｍ／｜σ（ｔ）｜ （２）
   ここで、
   ｐ_ｉ：各配送地点ｉの所与の特徴量
   Ｍ：１つの車両が訪問する配送地点の特徴量の上限値もしくは特徴量の全車両に亘る総和
   σ（ｔ）：解ｔで使用される車両の集合
   |σ（ｔ）|：解ｔで使用される車両の合計数
   Ｃ_ｋ（ｔ）：車両ｋ∈σ（ｔ）が訪問する配送地点の集合
   ｍ：１より大きい数値であり、
   前記解集合（Ｎ（Ｓ））を作成するに先立ち、配送地点数によらず定数時間で実行できるフィージビリティー・チェックを行い、走行距離が短縮され得る地点を限定した上で近傍解を生成することを特徴とする、複数車両の配送経路を求めるための方法。
2. 前記最適解Ｓ^ｂｅｓｔを求めるステップが、下記１）〜９）のステップを所与の終了条件に達するまで反復するステップであり、
   １）前記解集合について、第１局所探索を行なうステップであって
   （ｉ）車両数が最も少ない解を探索するステップ、
   （ｉｉ）車両数が最も少ない解が複数ある場合には、該複数の解のうち車両の走行距離もしくは稼動時間の全車両に亘る和が最も小さい解を探索するステップ、
   からなる第１局所探索を行なうステップ、
   ２）第１の局所探索で得られた解Ｓ_ｂが前記最適解Ｓ^ｂｅｓｔに比べて車両数が少ないか、車両数は同じであるが車両の走行距離もしくは稼動時間の全車両に亘る和が小さい場合には、前記解Ｓ_ｂを最適解Ｓ^ｂｅｓｔとして保存して該最適解Ｓ^ｂｅｓｔを更新するステップ、
   ３）前記終了条件に達しているか否かを判断し、該終了条件に達している場合にはＳ^ｂｅｓｔを出力するステップ、
   ４）ステップ３）で終了条件に達していないと判断された場合には、第１の局所探索で得られた解Ｓ_ｂが現在の解Ｓよりも車両数が少ないか、車両数が同じであっても走行距離もしくは稼動時間の全車両に亘る和が小さい場合には、解Ｓ_ｂを現在の解Ｓとして保存して現在の解Ｓを更新し、次いで、前記ステップ１）に戻るステップ、
   ５）前記ステップ４）で現在の解が更新されなかった場合には前記ステップ１）の現在の解Ｓの近傍解からなる解集合について、第２局所探索を行なうステップであって
   （ａ）車両数が最も少ない解を探索するステップ、
   （ｂ）車両数が最も少ない解が複数ある場合には、該複数の解のうち前記指標β（ｔ）が最も小さい解を探索するステップ、
   （ｃ）β（ｔ）が最も小さい解が複数ある場合には、該複数の解のうち車両の走行距離もしくは稼動時間の全車両に亘る和が最も小さい解を探索するステップ、
   を含む第２局所探索を行なうステップ、
   ６）第２局所探索で得られた解Ｓ_ｂが、前記最適解Ｓ^ｂｅｓｔよりも車両数が少ないか、車両数が同じであっても走行距離もしくは稼動時間の全車両に亘る和が小さい場合には、前記解Ｓ_ｂを最適解Ｓ^ｂｅｓｔとして保存し、該最適解Ｓ^ｂｅｓｔを更新するステップ、
   ７）前記終了条件に達しているか否かを判断し、該終了条件に達している場合にはＳ^ｂｅｓｔを出力するステップ、
   ８）ステップ７）で終了条件に達していないと判断された場合には、第２の局所探索で得られた解Ｓ_ｂが現在の解Ｓよりも車両数が少ないか、車両数が同じであっても前記指標β（ｔ）が小さいか、又は車両数及び指標β（ｔ）が同じであっても走行距離もしくは稼動時間の全車両に亘る和が小さい場合に、該Ｓ_ｂを現在の解Ｓとして保存して現在の解Ｓを更新し、該更新された現在の解Ｓの近傍解からなる解集合について、再度第２局所探索を行うステップ、
   ９）ステップ８）でＳが更新されなかった場合に、上記ステップ１）に戻るステップ、
   であることを特徴とする請求項１に記載の方法。
3. 前記特徴量ｐ_ｉが下記式（３）で定義される値であり、
   ｐ_ｉ＝nn_i + ｔ_i （３）
   （nn_i：配送地点iに最も近い配送地点への移動時間と、２番目に近い配送地点への移動時間の平均値
   ｔ_i：配送地点iでの作業時間）であり、
   Ｍが車両の稼動時間の上限値である、請求項１または２に記載の方法。
4. 前記特徴量ｐ_ｉが配送地点iへの配送量であり、Ｍが車両の積載量の上限値である、請求項１または２に記載の方法。
5. 前記特徴量ｐ_ｉが配送地点iに割り当てられた定数であり、Ｍがその総和もしくは上限値である、請求項１または２に記載の方法。
6. 前記定数が１であり、Ｍが地点数である、請求項５記載の方法。
7. 前記特徴量ｐ_ｉが配送地点iに割り当てられた乱数であり、Ｍが乱数の全車両に亘る総和である、請求項１または２に記載の方法。
8. 前記ｍが１．５〜３の数である、請求項１〜７のいずれか１項記載の方法。
9. 前記終了条件が計算時間である、請求項１〜８のいずれか１項記載の方法。
10. 複数車両の配送経路を求めるためのコンピュータ・システムであって、
    拠点、配送地点、車両及び物品の情報を記録する記憶手段と、
    現在の解Ｓを保存する現在解記憶手段と、
    最適解Ｓ^ｂｅｓｔを保存する最適解記憶手段と、
    前記記憶手段から拠点、配送地点、車両及び物品の情報を読取り、初期の現在解Ｓ及び最適解Ｓ^ｂｅｓｔを求めて、前記現在解記憶手段及び最適解記憶手段に書き込む初期値設定手段と、
    前記現在解Ｓの近傍解からなる解集合（Ｎ（Ｓ））を所与の方法により求める解集合計算手段と、
    前記解集合計算手段から各近傍解（ｔ）を読み取り、第１局所探索を行なう手段であって、
    （ｉ）現在解Ｓよりも車両数が最も少ない解を探索する手段と、
    （ｉｉ）車両数が最も少ない解が複数ある場合には、該複数の解のうち車両の走行距離もしくは稼動時間の全車両に亘る和が最も小さい解を探索する手段と、
    を含む第１局所探索手段と、
    前記解集合について、第２局所探索を行なう手段であって、
    （ａ）車両数が最も少ない解を探索する手段と、
    （ｂ）車両数が最も少ない解が複数ある場合には、該複数の解のうち、下記式（１）で定義される、車両ごとの評価値Ｂ_ｋ（ｔ）の、下記式（２）で定義される車両間のばらつきの少なさを示す指標β（ｔ）を計算し及び該指標β（ｔ）が最も小さい解を探索する探索手段と、
    Ｂ_ｋ（ｔ）＝Σ_{ｉ∈Ｃｋ（ｔ）} ｐ_ｉ／Ｍ （１）
    β（ｔ） ＝ １−Σ_{ｋ∈σ（ｔ）}Ｂ_ｋ（ｔ）^ｍ／｜σ（ｔ）｜ （２）
    ここで、
    σ（ｔ）：解ｔが使用する車両の集合
    |σ（ｔ）|：解ｔで使用される車両の合計数
    Ｃ_ｋ（ｔ）：車両ｋ∈σ（ｔ）が訪問する配送地点の集合
    ｐ_ｉ：各配送地点ｉの所与の特徴量
    Ｍ：１つの車両が訪問する配送地点の特徴量の上限値もしくは特徴量の全車両に亘る総和
    ｍ：１より大きい数値
    （ｃ）β（ｔ）が小さい解が無い場合には、β（ｔ）が同じ解のうち車両の走行距離もしくは稼動時間の和がより小さい解を探索する探索手段と、
    を含む第２局所探索手段と、
    前記第１もしくは第２探索手段から出力された解Ｓ_ｂを前記Ｓ^ｂｅｓｔと比較して、Ｓ_ｂがＳ^ｂｅｓｔよりも車両数が少ないか、車両数が同じであっても走行距離もしくは稼動時間の全車両に亘る和が小さい場合には、Ｓ^ｂｅｓｔを更新すると同時に、前記最適解記憶手段に書き込む最適解更新手段と、
    解Ｓ_ｂとＳ^ｂｅｓｔの比較後に、局所探索終了条件に達しているか否かを判断し、該終了条件に達している場合には前記Ｓ^ｂｅｓｔを出力する終了条件判断手段と、
    該終了条件に達していない場合には、前記第１もしくは第２探索手段から出力された解Ｓ_ｂを現在の解Ｓと比較して、Ｓ_ｂが前記第１探索手段の解である場合にはＳよりも車両数が少ないか、車両数が同じであっても走行距離もしくは稼動時間の和が小さい場合に、Ｓ_ｂが前記第２探索手段の解である場合には、Ｓよりも車両数が少ないか、車両数が同じであっても前記指標β（ｔ）が小さいか、車両数及び指標β（ｔ）が同じであっても走行距離もしくは稼動時間の全車両に亘る和が小さい場合に、Ｓを更新すると共に、前記現在解記憶手段に書き込む現在解更新手段と、
    現在の解Ｓが更新されなかった場合に、前記第１局所探索から前記第２局所探索へ、もしくは、前記第２局所探索から第１局所探索へと切り替えて、前記終了条件に達するまで交互に行なわせる局所探索制御手段と、
    を含み、
    前記解集合（Ｎ（Ｓ））を作成するに先立ち、配送地点数によらず定数時間で実行できるフィージビリティー・チェックを行い、走行距離が短縮され得る地点を限定した上で近傍解を生成する、複数車両の配送経路を求めるためのコンピュータ・システム。
11. 請求項１〜９のいずれか１項に記載の方法の各ステップをコンピュータ・システムに実行させる、複数車両の配送経路を求めるためのコンピュータ・プログラム。

Images