コラム・特集

8.5 配送モデル

IEハンドブック
第11部 計画と管理

第8章 ディストリビューションとロジステックス

8.5 配送モデル

車の配分,ルート等に関するオペレーション・モデルを配送モデル(Delivery Model)と呼ぶ。この問題解決の手法には,3つの基本的な方法がある。
1.密集地クラスターが初めで,その次にルート
2.ルートが初めでその次に密集地の配送(Cluster)
3.密集地とルートを同時に配送

これらは実行可能なルートと組み合わせの作成に関するものである。実行可能ルートの最適セットを決める問題は難しい問題の1つである。カバーしたり分離したりするモデルのクラスが,ルートを決める問題の解決手段に使われる。最も 魅力的な数学的プログラム方法である。このアプローチのうちルート問題を解くための手法はCharnesとMillerによって,また配送の問題は QuantとBalinskiによって開発された。

このアプローチの主要な点は,おのおのの実行可能なルートを,マトリックスの行として扱うことである。好ましい行の組み合わせ,すなわち,使用可能な車に相当する行が選ばれる。明らかに配送問題では,実行可能なルートの数は,実際列挙した数より多すぎ,評価よりも大きすぎる。しかしながら,このアプローチは可能なルートを生み出すために有効的であり,作り出されたルートのベストなサブセットを選択することもできる。もし,ルートが明確に作り出されれば,そのアプローチは最適でなくとも良いセットをつくるであろう。車のルートを決める方法として,まず初めにカバリングとパーティショニング・モデルについて述べる。

カバリングとパーティショニング・カバリング問題は,整数プログラムであり,次のように定義づけられている。

最小 ΣCi XJ                                                (17)

ここで

Σ AI Xj≧ 1 j i=1,… m                                      (18)

Xj=0ま た は 1                                                (19)

ここで,Aijすべてはコンスタントで0か 1の価である。
Aij=0か 1で あるのでXjも 0か 1で ある。式00の条件が少なくとも1位の変動Xjが iの条件において1になることを示す。パーティショニング・モデルは,式uOの条件が=になることを除いては,カバリング・モデルに似ている。

カバリングとパーティショニング問題の正確な解を得るためには,多くの計算時間が必要である,しかしながら,特別の構成のために,いくつかのヒューリスティック手法が役に立ち,それにより良い解が得られる。カバリングとパーティショニング・モデルは, 最適の施設への割り当てとルートを決めるときに役立つ。これは割り当てルートが,施設への割り当てを暗黙の内 に固定化してしまうからである。

このモデルを理解するために,4個所の施設から10個所の客に配送する例をあげてみる(図表11.8.4ネットワークを参照)。

この例では,どの客もユニットロードでの運搬を要求していると仮定する(ユニットロード 以下のオーダーであれば,他の客のオーダーと混ぜる方法もとれないこともないが 図表11.8.5で列にカバリング問題を示す。

各行には実行可能な運搬ルートが示されている。40行 (1行が 1 客)と 20列 (1列が1実行可能ルート)。ルートが列挙してあるカバリング問題の例が11.11.5であるもしルートjが客iに運んだ場合に行Xjは列iの所に1が示されている。費用が下の行の費用行に示されている。例えばXl行は,客 N01に運ぶには,ルートの合計費用と して24(往復距離は考慮されている)。しかし,図表11.11.4で見ると施設1から客1へ直接でなく ,客2を通過して客1に行くことになっているので,このルート(施設1から客1のルート)はない。

それには,例えば車の積載容量制限等の理由がある。そこでX 11ルートを見ると,客1と客2はルートX 1のときと同じ費用である。X 11は X 1より 好ましいルートであることがわかる。行 X 11は X1より優位(Dominate) という。

技法には,好ましくない行と,余分な列があることは事実だ。もちろんX 11をカバーしてX 1を選ぶような設計はない(Optimization Scheme) 。

変数Xj=1ということは,ルートXjが決められたということである。Xj=0とは,Xjが選べないことを示す。“ Cover”という意味は,解決案の中で選ばれた行の組み合わせをいう。 例えば,図表11.8.5の問題での“Cover”(解決案)は, X 20=1, X 13=1, X 15=1’X 9=1, X 10=1であり,その費用は27+24+24+30+6=111 である。この結論はパーティションとも呼べる。なぜなら,カバリング・モデルにある制約条件が同様に満足されている。

Cullen Et Al は,線型計画法の二変数解法と同じように,実行可能な解が定められるとき,金額についてもカバリング・モデルの列として解く方法を示した。二変数のように,プライス全額(Covering Prices)は次の3つのことを満たす。(1)負数でない,(2)制約条件が満足されない場合は0,(3)カバーする1つの解決案の行に掛けるとき,費用の行をたさねばならない。これらの価格は,選ばれた案より改善する案があるかどうか判断するためのカバリング・モデルの行として応用される。方法は線型計画法のシャドープライスの計算と似ている (14部 2章を参照)。これらの価格は図表11.11.4のネットワークに記載されている。

ルートの制約の1つの変化は,すべての制約条件を満足させるルートを探すために取り 上げられる。また,費用に関してはルートが 決まってから費用が決められるという制 約だけがある。カバリングとパーティショニング・モデルにより追加される制約条件としては,複数の車の型とか,施設の大きさ等が考えられる。

密集地を先にその後ルートをつくる方法(Cluster-first-and-then-Route Approach)

この考え方(手法)は,車の容量制約を第1に考慮しなければならない場合に適している。考え方は,グループか客が密集している所を初めに車に割り当てて,その後密集地区を通過して1ル ートをつくる。この方法はルートに制限がある場合には適しない。例えば,到着時間が決められている等。なぜなら,ル ート上の配送地点が決定するまでルートが決められない。

こ のアプローチの基本的な考え方は,初めにルートの費用を見積もる。その後の費用は,車の容量制限を満足させるポイントに集めるための基準になる。ここで2つの手法を紹介する。1つの手法はローカル・アルケーション・アプローチである。この手法において,距離による費用は,運んだユークリッド 距離*に比例すると仮定する。

われわれは実際の距離は知らないので,だいたい次のように仮定をする。車は,第1に 倉庫から密集地を通り、その後配送地点へ行き,各所へ配送した後密集地にもどり,密集地から倉庫にもどってくる。この考え方は,図表11.8.6に示してある。

 

客から密集 地,プラス,密集地から施設までの距離を2倍する。これにより1台の車が密集している各グループのサービスのために運ぶ距離がだいたい判断できる。これは客と密集地のそれぞれの距離を2倍にする。密集地の中を行ったり来たりする案より能率的なルートがあるという事実を考えて,距離を2倍にする代わりに乗数0<λ≦2が適応される。

そこで数学的モデルを展開させると,以下のようになる。ここで( x 0,y 0 )を固定した施設の場所の座標とし , (x j , y j )を需要点の座標とする。(χ i,y i)を知らされていない密集(Cluster)地とする。A j を車 i の容量, b jを客 jの必要量とする。

最小ΣΣλ 〔 (Xj―Xi)2+(Yj一Yl)2〕Xij+2ΣΣ〔 (Xi~XO)2+(Yi YO)2・・・(20)

ただし
Σ Xij≦ Ai・・・・・・・・・・・・(21)

Σ Xij =Bj・・・・・・・・・・・・(22)

Xij≧ 0・・・・・・・・・・・・・(23)

ここでX ijとはディマンド ・ポイント j の必要量であり, i から供給されたものを示す。

これは最適解を求めるには実際的でない。しかしCooperは,このモデルの最適解を地区的に決めるための反 復法を示した。彼の手法は,(1)もし,m個のクラスター・ポイント(Xi,Yi)のセットi=1,… ,m,が,ある座標のもとに固定であれば,そこで次のモデルは,単純な運搬モデルになる。また(2)もし,Xijが指定されていれば,次には制約のない施設の場所のモデルを考えればよい(Facility Location Model)。手順は次の通り

ステップ0 固定クラスターポイントのどれかのセッ卜で始める。(Xi,Yi)i=1,… ,m

ステップ1 (χi,yi)が与えられ, χij の値を満足させる運搬問題を解く ,

ステップ2  χijの 値が与えられ,(χ i,ノi),i=1 …m*。新しいクラスター・ポイントのセットのために施設の場所を決める問題を解く .

ステップ3 ステップ1とステップ2を繰り返し,ある基準が満足されるまで繰り返す。

別のクラスター ・ポイントのセット(Xi,Yi),i=1,… m.から始めて,手順を進めることにより,最後に地区,地区の最適な点を見つけることができる。また,指定されたXij の 値をもって手順を始めることも可能であり,直接ステップ2に進むこともできる。このモデルは,常に2つの問題がその解決のために考えられる,という点からすると,場所の決定モデルとしても考えられよう。

ひとたびモデルが解かれると,もはやクラスター・ポ イントに目を向ける必要はない。というのは,クラスター・ポイントはクラスターを決めるための1つの機能であるからだ。これらのクラスター・ポイントは同じ車に割り当てられる。

初めのクラスター・ポイントと異なったクラスター・ポイントでまた始めることにより,違ったクラスター・ ポイントのセットが達成できる。そこで,この方法はカバリングとパーテショニング・モデルに採用される。クラスタリング利用の第2の方法はツリー・グローウイング ・アプローチである。

1本の木はネットワークと結びついているが,サイクルをなしてはいない。図表11.8.6で示してあるネットワークは,特別なケースの木である。木の発育に際して,再び新しいクラスター・ポイントのセットが選ばれる。そして木がつくられ,またはサイクルをなさない追加されたリンクによって育ち,1台の車でまかなえる多くのデリバリー・ポ イントを持った木が建てられる。ここでは費用は,木の長さに比例するという絶対条件がある。木に付け加えるリンクの選び方には色々ある。最も一般的な選び方は,現在の木に近く,最も安いリンクを選ぶことだ。もし1本の木だけが育てば,最短に広がった 木にならざるをえない(最短の木はすべてのデリバリー・ポイントを包含している)。

巡回セールスマン問題
1台の車が行くべき,いくつかのポイントが決められても,次には訪問する順序を決めなければならない。しかし ,この順序に対して,(要求される )制限がすべてのポイント に影響を与える場合,最短距離のルートを見付ける問題として有名な巡回セールスマン 問題というのがある。最適解法は,そのような問題を解く方法である。

しかしながら,それほど大きなサイズの問題でなくとも (例えば20から50のデリバリー・ポイントでも )計算時間は過大である。その結果,すばらしい能率的なヒューリ スティックス手法が開発された。このセールスマン問題を最も広く使用されているものは「オプティマル法Jと呼ばれ,Lin and kernighanによるものだ。

これ以外によいルートが見出せないというルートが見つかったときに,そのルートをオプティマルと決定する。 もし,ルートrが少なければ,オプティマル・ルートを見つけることは容易である。ここで例を挙ける。
図表11.8.7aを見ると,初めに図表11.8.7bのルートと各リンクについて考えてみる。仮に(BC)と (FD)リンクを取ってみて結びつきを変えてみる。(BC)を (B.F) に(FD)を(CD)に変えてみる。前より良いルート になるかを比較してみると,良くなっていることがわかる。これは図表11.8.7cに示されている。

他の結びつき(リンク)について,同様の方法で変えてみては良くなったか比較してみる。この操作を繰り返し行い,これ以上改善する余地がない ルートを発見 する。結果として2オプティ マルが得られる。ここでわれわれはどんなにリンクを変えても,1つのループをなしていなければならないことを忘れてはならない。 例えば,先例で(B_C) を(BF)に 変え,(F.D)を (EF)に 変える。距離は縮まるが, 1ループでなくなってしまう。

r 回繰り返し行うための時間が増えるので,一般的には3オプティマル・ルート以上は見出せない。多くの問題のために,3オプティマル・ポイントが見出されることはすばらしいことである。

オプティマルの概念は ,ルートを決めるに 当たって,そこにある制限を考慮するときにも役立つであろう。実行可能なルートをつくる r ―リンクの変更だけが, 許される変更であることにもなる。オプティマ ル方法は,1つのルートで,リンクの数は初めに考えたルートのときと同じでなくてはならない。セールスマン問題を解くヒューリスティック法については,最近Gloven et al が発表している。

ルート配送をした後に密集地域への配送車のルート 問題のアプローチのもう1つの方法は,初め,すべてのポイントを訪問する1つのシンのレ・ルート (セールスマン問題のように)を決める.その次にいくつかの部分に分ける。それぞれの部分は,シングル・ ルートになっているようにする。ゴミ回収問題がこのアプローチの方法をとっている。

この方法は密集地域先方法に似て,処理できる制約の中において使われる。分割を細かくすることにより,容量の制約や距離の制約を満足させることができる。しかしながら,個々の配送量が車の容量より少なくないと,車の容量が第1に重要な制約である場合には,この方法はうまくいかない。

もう1つの欠点は,もし配送する所が多い場合には,セールスマンの問題の最適解を見出すことは困難である。そこで発見法的方法に助けをかりて,全ポイントに立ち寄る方法を見つけ,その後,各分割された部分での立ち寄り方を発見する。各リンクに立ち寄ら なければならないような特別なケース(例えばゴミ回収)の最適なルー トを発見するためには,他に能率的な方法がまだある。

密集地域とルート配送を一緒に
複雑なルートの制約を十分考慮するためには,クラスターとルートを同時に組み合わせたヒューリスティックス法による手法が使用できる。各ステップにおいてできることをやりながら,配送先を加えていくことにより,ル―卜を 作っていくやり方である。そのルートの作り方に は1本ずつ作るか,平行に数本作るか,どちらかの方法をとる。数本のルート を作るほうが,好結果をもたらすことが多いが,計算に時間がかかる。そこで,ヒューリスティック法によるルートの作り方を,費用による手法と幾何的配置手法のどちらか,または両方を使った方法で考えてみる。次にこの2つの概念について述べる。

費用による手法
プライスの観念は初期のルートを作るとき,またはすでにあるルー トを改善しようとする場合に用いられる。たとえば,すでに可能なルートが現存すると仮定する。 配達先を1,Piを iを通るルートにかかる費用または見積りとする。い ま新しいセットのルー トを作り,配達先 iをその新しいルー トrに入れるとする。追加の費用の見積りをCi とすると,Pi―Ciが iを現在のルートのセ ットからrに入れたことにより発生した費用である。この見積りがあれば,費用の改善を示す点を考えながら,新しいルートを作 り上げることができる。

此の取りかかり方はClarkeとWrightのセイビング方法としてよく知 られている。彼らは,初期のルートの組み合わせ(セット)から始まり,次々に1つずつの配達先を加えていく。各配達先 (Delivery Point)の費用 (値段)は,倉庫から配達先の間の往復費用となる(すなわち,Pi=2 Qio,Qioは倉庫と配達先の間の費用である)。j点がルートrにおける唯一の点と仮定する。1点をルートrに足すことによる増加費は,ルートrの新しい費用差し引くルートrの元の費用,またはCir=Qoi+Qij+Qoi-2QoJと Pi=2Qoiだから,P-Cir=Qoi +QOJ-Qij=Sij, 量Sijは,点 iと jと同じルートに入れた「節約」(Savings)と呼ぶ。

まずこの節約費用を,大きい順にならべたリストを作る。新しいルートを作る1つの方法は,リストの上から始まり,2点の i と j を最初のSilに符合しながらできた道筋が,ルートにある制約条件を満たすならば,それでルートが決められる。

またリストの次の組について同様の検討を行う。次々とリストの総ての組み合わせについて検討する。

もう1つの費用の変化は,ルート r の中ですでに現存する結ばれた2点 (配送先)の間に,もう1点 (配送先) を差し入れる場合に,その費用の増加を実際に計算することだ。ルートに入れる最良な場合を決定し,それに関 連する費用を見積もり,Cirとする。このように配送先を追加していって,実行可能な,かつ好ましい費用(Pi-Cir)を持つルートを作り上げることができる。前回の方法とこの手順は,Cullenがよく繰り返し使っている 方法である。この手順では,ある特別のルートを選ぶことから始めるのだが,各配達先への費用を固定にする (Pi=m,Piを コンスタント にする)ことにすれば,追加費の最も低い配送先を,ルートに次々と加えていけばできる。この手順は新しく組み立てられたルートを初期のセットとして,繰り返し使うことができる。

しかし,ルートが1つ以上の配達先を含むときは,費用の見積もりは複雑になる。実際費用への影響が少ないことにこしたことはない。選ばれたルートは,すべて間題を仕切るセットの中へ合併されて,それからこの中から最良のルートの組み合わせを選ぶ。このほうが,かなりより良いルートを選択することができる。また最後のルートの選択をより改善するためには,前章で議論されたオプティマルの手順を用いるのが望ましいかも知れない。他のプライシング方法を知りたければCullenその他を見るとよい。

幾何学的な相対的配置
基本的な取りかかり方は,重複しないように幾何的に地区を分けて,地区ごとにルートを作ることである。この方法で最もよく知られているのはGillet およびGilletとMiller のスイープ(掃く)方法である 。この取りかかり方は,すべてのルートはある施設(倉庫)から始まり,そこへ返ってきて終わることと,ルートを花びら的配置になすことが好まれる事実を利用した(図表11. 8.8)本質的に,これは地方を,倉庫を中心にした時計上に位置すると考えるのだ。時計の針の初期の位置があたえられ,そこから掃くように回る。その針が出くわす先々は,実行可能なルートなら同じルートに入れる。

ある程度の車の容量が使い果たされたときは,新しいル ートを始める。それで幾何学的に区分された地区は,切られたパイのような形になる。図表11.8.9aの4区切は4つの配送のグループを形づくっている。 図表は ,この区切の中の届先の間で4台の車の経過を示す区切の境に当たるところにある 届先を,組織的に変えることによって,ルートを改良することができる。

カラーによる表示経路の問題を解決する最も有望な新しいテクニッ クは, カラーグラフィックを使うことである。 カラーグラフィックは,経路の問題を扱うすべての数学的な解決方法に対して使うことができる。それは完全に自動化されているようなプロ セスにおいて理解するガイドとなり,扱いにくい空間的情報をも与えることができる。人間がすることを電算機に複写させようとする代わりに,それはその過程において人間の手助けをする。電算機の役割は人間にルートの作り方の知識をあたえ,それを表示してそのモデルを解くことにある 。

先に論議したCullenその他の組織 (系統)は,この電算機を役立てたやり方である取りかかり方に添っている。適切な数のルートが作成されるまでこのプロセスを続ける。それから計算機でセットを仕切る問題を解決し,得られたルートの中から最も良いのを選ぶ。この方法はルートに改良の余地が無くなるまで繰り返される。実際の表示は7色の色を使い,インプットはライトペンをディスプレーに軽く触れることによって入れられる。

本コラムは絶版となっている「IEハンドブック(サルベンティ編・日本能率協会訳・1986)」をアーカイブとして掲載するものです。このハンドブックの各章は多くの事例と理論を通して生産性向上に対するアイデアを提供するべく専門家によって執筆されています。基盤をなしているIEの考え方・原則はインダストリアル・エンジニアリングにかかわるすべてのひとに有用でしょう。

関連記事一覧

2019ものづくり公開セミナーガイド

B2Bデジタルマーケティングセミナー

ものづくり人材育成ソリューション

マーケティング分野オンラインセミナー