Excelによるネットワーク計画法（2）

最短路と配達路
古林 隆
Illl‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖川……l‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖＝‖‖‖‖‖‖仰Illl…

向（始点から終点への向き）の長さde，逆方向（終3．最短路

点から始点への向き）の長さdfをセルに書き込むと，枝の長さが与えられているネットワークで，ある一ネットワークを表示し，すべての2点間の最短距離お点sから他の一点tへの路の中で，長さが最小であるよび次点（最短路で始点の次に通る点）をセルに出力ものを点sから点tへの最短路といい，その長さを最する．さらに，路の始点sと終点tを入力すると，点短距離という．ここで，点s，点tをそれぞれ路の始sから点tへの最短路を矢線で表示する．

点，終点という。枝の長さとしては，そこを通過する

ただし，始点と終点が一致している枝（輪というこのにかかる時間やそこに物を運ぶときの費用をとることもある）は，存在しないものとする．ともあるので，枝の長さは，向きによって異なってい＜注＞ Ⅹ，yを書き込む行の数は，nであり，e，fてもよいし，負であってもよいことにする．などを書き込む行の数は，mである．n，mが定まっ

最短路・最短距離を求めるアルゴリズムは，次の三つの場合に分けて考えられている．てから，足りない行は，挿入（またはコピー）すればよい．

（a）枝の長さがすべて非負であるネットワークで，◆アルゴリズム

ある一点から他のすべての点への最短路を求め

ここでは，ウォーシャル・フロイド法を用いる．

る場合

すべてのi，jに対して，d（i，j）が点iから点jへの（b）負の長さの杖が存在するネットワークで，ある最短距離，p（i，j）が次点（点iの次に通る点）になる

一点から他のすべての点への最短路を求める場

ようにするが，まず，それらの初期値を，次のように合・定める．

（c）全最短路（すべての二点間の最短路）を求める

d（i，j）の初期値（a）点iと点jの間に杖が存在するとき，点iから場合最短路を求めることは，それ自体が目的になることもあるが，むしろ他の問題のアルゴリズムの中のサブ点jへの向きの長さ（b）点iと点jの間（i≠j）に枝が存在しないとき，ルーチンとして使われたり，入力データを作るのに使われたりすることが多い．ここでは，巡回セールス問
題，配達路問題など多くの問題の入力データを作るのに必要な（C）の場合をとりあげる．

十分大きい正数M（c）i＝jのとき，Op（i，j）の初期値j次に，h＝1，2，…，nの順に，すべてのi，jに対して，＜注＞ グラフとネットワークは，ほとんど同じ意味次の（1），（2）を実行する．

で使われるが，今回からは，接続関係以外に，枝に長（1）dh＝d（i，h）＋d（h，j）とする．

さや点に配達量などが付与されるので，ネットワーク（2）dh＜d（i，j）であれば，d（i，j）＝dh，p（i，j）＝p（i，ということにする．

h）とする．
終了したときのd（i，j）が，点五から点jへの最短距［NP3］図9に示すように，点の数n，枝の数m，離であり，p（i，j）が次点である．最短路の一部も，ま各点のⅩ座標，y座標，各枝の始点e，終点f，順方た最短路になっているから，次点を順々に見ていけば（i＝p（i，j）とすることを繰り返せば），最短路が求め

こばやし たかし 法政大学

〒184−8584小金井市梶野町3−7−2
1999年5月号

られる．

負の長さの枝が存在する場合，最短距離が存在しな© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（31）253

閣9 NP3のシート

ネットワークの表示「＝10： Cn ＝ 5：CS ＝ 4：Ga ＝ 2

いことがある。そのときは，d（i，i）の中に負が現れる。
㊥プⅢグラムFor k ＝1To m
岳 ＝餞（k）ニ j＝f（k）

C品川 s喝memセ（x（け，y（邑），X（j），y（j）v cs）
N⑳X七 kFor＝ て To nC∂＝ nod8（…，X（i），y（り．「．cn）

ここでも，点と枝を表示するサブルーチンを用いる（前回の図3参月酎。

デ｝タの入力は，NP2のプログラム（前回の図7）

闊ex七 右のe（k），Hk）を読み込む部分の次に，de（k），df（k）

図10 ネットワークの表示のプログラムを読み込む部分

de（k）＝Cells（3＋k，9）：df（k）＝Cells（3＋k，10）を付け加えればよい。

最短距離■次点の計算
0

ネットワークの表示の部分を図10に示す。枝の表m

示に，サブルーチンsegmentを用いた。点を表示す

999：P（右，j）＝j︶．−JJu・︼︻︼・・．¶■■■■

．﹂

rFO

丁Fori＝1To n0．

︶Å・け∴−一・・モe．しM相川．バM

七るサブルーチンnodeより先に実行していることに注意されたい。なお，点の色は，黄色（色番号cn＝5），

Next 云For 決 ＝1To 汀】

枝の色は9 音（色番号cs＝4）である。変数caは，

盲 ＝＝℡（k）：j＝ず（k）

d（i，j）＝de（k）こ d（j，邑）＝dず（k）

ここでは使用していないが，後で最短路を示す矢線の闊ex七 k

色番号に用いている（図13参照）。最短距離旬次点のFor h ＝1To n

計算と津∫力の部分を図11に示す。ここで，M＝999

For 毒 ＝1To n
For」＝1To nとした包 また，m（枝の数）が大きくなると，最短距副h＝＝出（巨 翫）＋d（h，j）

離。次点を出力する行を下げる必要があるので，行番

げdh〈d（工」）Then号がmによって変わるようにした。

d（呂，j）＝dh：P（巨」）＝p（盲，h）

実行例を図12に示す。なお，点番号の背景を塗りEnd 弓fNext j

つぶすことや表の罫線の一部を太くするのは，プログ掴ex七 呂

ラムを実行した後シート上で範囲を指定して行った。

Next h最短距離◎次点を出力した後，路の始点と終点を与最短距蘭巨次点の出力

えると，最短路を矢線で表示するようにするには，図J＝ m ＋16F（〕r 盲 ＝1To n13に示すプログラムを付け加えればよい。m＝12のCe【ls（u十i．1）ニi￠e＝s（叫＋瑠 ＋）＝ 呂：Oei日s（u．n＋1♯ 岳）＝：・﹂ ／1＼

ヽ−・・一・−﹂

Pn．．J

l十＋﹂U︑lノ．﹂＋サ

Ce＝s（u＋Ge‖＄（u閃・lFor」＝1To

Next jとき，始点は，セルB18に，終点は，セルB19に書き込むことになっている。B18が0（空欄でもよい）であれば，何も行わない。

s＝3，t＝5としたときの実行例を図14に示す。矢Next；練の色は9 赤（色番号ca＝2）であるp

S10p
図1且 最短距離ふ次点の計算と出力のプログラム
盈艶租（32）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。リサーチef de df
2 60 60
3 55 65
4 30 40
6 80 80

2 4 45 50
2 5 70 65
3 6 50 60
4 5 90 90
4 6 55 55
4 7 70 80
5 7 70 60
6 7 80 75

次 点

最短距離
0 60 55 30 120 80 100

2 3 4 4 6 4
4 5 4 4守 60 0 115 45 70 100 115

2…を亮 65 125 0 95 185 50 130 Ⅶ

3口

ヰ 40 50 95 0 90 55 70

2藩 80 105 60 55 140 0 80

4 3 4 7 6 7口

66

4 5 6 7

亮 125 65 180 90 0 145 70 2 2 2 4 5 4 7う1120 125 135 80 60 75 0 4 5 6 4 5 6 7
図12 NP3の実行例

最短路の表示4．配達路

u ＝ m ＋ 6

s＝Cells（u，2）：t＝Cells（u＋1，2）

ネットワークの一点（センターと呼ぶことにする）

lf s 〉 O Then

Celis（u＋2，2）＝d（＄，t）
l＝ s

から他のすべての点へ品物を配達するときに，配達車の．走行距離を最小にする配達路を求めることを考える．

Do Whileiく〉 tj＝p（i，t）

Callarrow（x（i），y（i）．x（j），y（j），「，Ca）

配達車の容量（積載可能量）が総配達量以上であれば，すべての品物を一度に載せられるので，配達順序だけi＝」Loop求めればよい．走行距離を最小にする配達順序を求めEnd げ

図13 最短路の表示のプログラム

る問題は，巡回セールスマン問題と呼ばれている．
ここでは，配達車の容量が総配達量より小さいとする．この場合・は，センターから何回かに分けて配達しなければならない．すなわち，配達先をそれらへの配達量の和が配達車の容量を超えないように分けて，それぞれについて，配達順序を決めて，走行距離の和が最小になるようにしなければならない．

［NP4］図15に示すように，点の数n，各点への配図14 最短路の表示
1999年5月号

達量a，すべての二点間の最短距離d，車の容量bを© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（33）255

セービング値の計算
し」1＝ n ＋ 9

Foriニ 2 ToJI
For j ニ＝2 Tc n膵iく〉 j Th⑳m

S（巨」）＝d（巨1）＋d（1，j）−出（石 j）
訊か‖s（M■十 巨′ 2＋．）＝s（i．j）
EIse￠￠＝s（Ml＋ 盲，2＋ け ＝ ＊＊＊′′臥痛ザNex七jNexセ 壷

初期解For 良 ＝ 2 To r篭

図15 N韮）4のシート

q（毒）＝a（り：neX（け ＝ト：七a巨（け ＝ 石dr（毒）＝d（㌣ 盲）＋d（巨1）N◎Xt 墓

セルに書き込むと，配達順序，積載量をセルに出力す配達路の結合るゥ ここで，センターは，点1とする。

Do・ニ・・ノ ∴、＿上smax ＝ OFく⊃r ∴ ＝ 21■o rl

いろいろなアルゴリズムが提案されてし1るが，ここ膵q（け 〉0■m礪抑

では，最も単純なセービング法を用いることにするpForJ＝2 To n
邑ずiく〉」And q（」）〉O Tれ◎n

まず，センターからすべての点へ往復する（n二1）偶せj ＝七a＝（りの配達路を初期解とし，二つの配達路を結合することげq（り ＋q（j）く＝b And s（引，」）〉smax Th◎nsmax＝s（七i，j）：g＝ 石：h＝jを繰り返して，総走行距離を減少させていく。

End け

用いる変数の意味は，次のとおりである。ただし，

巨md 隆ずト軍ext」

いずれもi＝2，3，…タmとする。

巨nd 岳fNex竃；q（i）：積載量＝＝ slmり（†O Then

センターを出発して最初に配達する点iに対して9n◎X（廿a＝（g））＝わ：セail（g）＝七眉‖（h）

その配達路で配達する量の和を示す。その他の一rlにdr（gl＝dr（g）＋dr（h）一SmaX
q（g）＝q（g）＋q（m）：q（れ）＝0

ついては，0とする。

巨nd：十Loop し汀ヒ＝ smax ＝0nex（i）：ノ責iの次に配達する一【烹nex（i）＝1であれば9 点iからセンターにもどるこ

図柑 セービング法のプログラムとを示す。
tail（i）：最後に配達する点（1）セービング値の計算

q（i）＞0であるiに対して，その配達路（最初に配上の（＊）式でセービング値を計算する。

達する庶がiである配達路）で最後に配達する点を（2）初其馴直の設定示す。

すべてのi（i≠1）に対して，
q（i）＝a（i），neX（i）＝1，tail（i）＝i，dr（i）∴走行距離

dr（i）＝d（い）十d（i，1）

q（亘）＞0であるiに対して，その配達路の走行距離を示す。とする。

s（i，j）（ま≠j）：セービング値（3）配達路の結合

次の手順をsmax＝0になるまで繰り返す。（後判

点iからセンターにもどって，改めて点jに行くかわりに，点互から直接点jに行くことによって，減定）少する（節約される）距離を示す。次式で計算でき（3．1）i≠1，j≠1，i≠j，q（i）＞0，q（j）＞0，る。

q（i）＋q（j）≦bs（i，j）＝d（i，1）十d（1，j）∬d（i，j）
手順は9 次のとおりである。

（＊）

をすべて満たす（i，j）の中で，S（tail（i），j）を最大にする対を求め，それを（g，h），最大値をsmaxとする。ただし，そのような（i，j）が存在しない

256（34）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ①リサーチ

配達路の出力nr ＝ 0：drt ＝ 0：u2 ＝ ul＋ 3 ＋ n

Fori＝ 2 To n
けq（i）〉O Then＝ ＝i：nr ＝ nr ＋1：k ＝ 2Dok ＝ k ＋1a

Cell＄（u2＋nr，k）＝il＝ ＝nex（＝）

Loop Until＝ ＝1
Cells（u2＋nr，8）＝dr（i）

dells（u2＋nr，9）＝q（i）
drt＝drt＋dr（i）※凄 ㌻≡≡j≡樋≒ ≡≡5≡ ※庵0 60 55 30 120 80 100

E 500 60 0 115 45 70 100 ‖5
さ 200 65 125 0 95 185 50 130
巧 300 40 50 95 0 90 55 70
350 125 65 180 90 0 145 70
450 80 105 60 55 140 0 80

7 400 120 125 135 80 80 75 0Endlf
Nexti

Cell＄（u2十nr＋1，8）＝drt≡j≡≡≡せ ≡≡j≡薄 ≡≡‡≡ヰ ≡≡慈 ≡≡≡≡桓 ‡≡≡≡寺＊＊＊

図17 配達路の出力のプログラム

04．5

110

4045

き 0 ＊＊＊ 0 0 95 35
500

＊＊＊70

6570

さ 120 0 65 ＊＊＊ 60 155

35

ときは，SmaX＝0とする．
字55（3．2）smax＞0であれば，配達路を結合する．
nex（tail（g））＝h，tail（g）＝tail（h），
dr（g）＝dr（g）十dr（h）−SmaX，q（g）＝q（g）＋q（h），q（h）＝0とする．

図18 NP4の実行例◆プログラムセービング値を計算して，配達路を求めるまでの部分を図16に，配達路を出力する部分を図17に示す．

◆プログラムの改良

セービング値を出力する行の番号および配達路を出力

上述の方法では，最適解（総走行距離を最小にするする行の番号は，点の数nによって変わるようにな配達路）が求められるとは限らない．別の解を求めたっている．

ければ，（g，h）に選ばれた（i，j）（図18の例では，（3，6），

NP3の例で用いたネットワークに配達量などを付（6，4），（7，5））の一部に対して，S（i，j）＝0とおいて，与して実行した例を図18に示す．最短距離dは，図配達路の結合をやり直すようにすればよい．他のセー12のセルB29からH35までをコピーして，貼り付ビング値を変える必要はないので，初期解を求める部

けた．

分にもどれるようにして，指定した（i，j）に対して，s（i，j）＝0とおいた後，配達路の結合を実行すればよ求められた配達路は，

Rl：1→2→1
R2：1→3→6→4→1
R3：1→7→5→1い．（プログラムを変えたくなければ，無駄が多いが，表のd（i，j）の値をd（i，1）＋d（1，j）にすればよい，）（次号に続く）の3本であり，総一走行距離は，605である．

1999年5月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（35）257