時間制約付き巡回セールスマン問題の研究

 

文教大学 情報学部 経営情報学科 97P21068 木村博一

1章:はじめに

1−1 何を

時間帯指定のある宅配便を配達する巡回路を見つける。

1−2 なぜ

増加している宅配便、さらに時間帯指定という制約が加わった。そして、時間帯指定を守りながら配達をするのには、配達ドライバーの工夫と努力によって支えられている。 ドライバーの負担を減らし、同じ時間で多くの荷物を運べるような巡回路を見つけたい。

1−3 アプローチは

ドライバーでも巡回路に沿って運べるようにする。

 

2章:研究動機

2-1 研究のきっかけ

私はいままでは、ほとんど宅急便を出したことなどなかった。インターネットのオークションで多数の個人取引をするようになってから数十個の宅急便をだした。私だけが特別ではなく1999年秋から始まったYahoo Auctionsでは1日の約9万点の新規出品がある。 宅配便の市場規模は大きく成長している。しかし、小額の個人取引をするのに600円から800円程度の宅配便の代金は高すぎる。もっとコストをさげ宅急便の代金が安くなればと思い始めたことからこの研究がはじまった。

 

2-2 宅配便の現状

宅配便の増加 インターネットの普及によりオンラインで9月のPC接続によるインターネット人口は、2,234万人。オンラインショッピングの個人利用経験率は16.6%(約370万人)[注1]  また、オークションなどで、個人取引の需要も増加しここ数年、宅配便の市場そのものが大きくなっている。

 

 

2-3 できるだけ短い距離で巡回するために

巡回セールスマン問題 宅配便のルート設定は、それぞれの家を廻ってできるだけコストをかけないように、短い距離で廻ろうとするため、巡回セールスマン問題を解くことで解決できる。

巡回セールスマン問題とは、ある地域のいくつかの家を1回だけ廻って出発地に戻ってくる経路の中で巡回距離が1番短い経路を求める問題を巡回セールスマン問題という。

 

巡回セールスマン問題を解く!

2-4 時間帯お届けサービス導入

時間帯お届けサービス 宅配便のシェアトップのヤマト運輸株式会社が1998年6月より、「時間帯お届け」というサービスがはじまる。これは、1日を6つ時間帯に分け、お客様の希望する時間帯を選んでもらい、その指定された時間に届けるサービスである。「時間帯お届け」ができると、郵便局や他の民間の宅配業者も同様のサービスをはじめた。

時間帯お届けのメリット 荷物を受け取る側は、いつ荷物が届くか知ることができる。 配達する側は、配達したときの不在率をさげることができ、1回で配達できる件数が多くなる。 宅急便を届けても不在ならば、荷物を持ち帰り再度届けることになる。時間帯お届けサービス以前は6割の荷物が配達しても不在で持ち帰るといった浪費をしている。年間取扱数7億7178万個うちの4.6億個が配達してにもかかわらず、1度持ち帰っていた。時間帯お届けのサービスを導入することにより、2割に下げることができた。

 

 

「時間帯お届け」

サービス開始以前(1998年6月以前)

・第1度目のお伺い…ご不在率約40% ・2度目、3度目お伺い…ご不在率約10%

同サービス開始後(1998年6月以降)

・第1度目のお伺い…ご不在率約20% ・2度目、3度目お伺い…ご不在率10%以下  [2]

 

「時間帯お届け」は6つの時間帯を指定と指定なしの7つに分類でき、 受取人も時間を指定することによって品物がいつ届くのか把握できる。さらに、この時間帯を指定することによって荷物を受取人に手渡す確率が上がる(不在のため再度届ける行為を減らす)と考えられる。よって、配達する側の再度配達というコスト削減につながる。 このシステムは双方にとって利益があるシステムである。

「時間帯お届け」の問題点 「時間帯お届け」サービスの現状を伺うと「サービス開始に伴う新たな配送ルートというものはございません。従来の配送ルートを使って各ドライバーが工夫をし、配達しています。」という回答をもらった。 今まではドライバー、が荷物を運ぶ巡回路を考え配送していたが、時間の制約が加わったこといより、いくら近い届け先があっても時間の制約を守らなければならないため、その指定の時間帯になったとき配達しなければならない。ドライバーは距離と時間の両方を考えながら配達をしなければならない。

解決されるとドライバーの負担を減らし、ドライバーが考えるよりも同じ時間内で荷物をより多く運ぶことができるような順回路をつくればコストが下がる。また、ドライバーの能力に左右されずに荷物を配達できる。そしてコストが下がることによって、宅配便の料金も下がる。

 

3章:問題解決

3-1 走行距離を短くする
ここで言う距離とは、トラックが走行する距離や時間をまとめて、「重み」とよぶ。家と家の間を「辺」とよび、この辺の重みをできるだけすくなくしていきたい。 例えば、ここにある配達地域の荷物を届けなければ成らない家があったとしよう。

まず、それぞれの指定時間で荷物を届けなければならないので、時間ごとに配達先を分け、巡回セールスマン問題にあてはめる。最も短い距離で巡回できるルートを見つる。

 

時間指定の各点から各点への辺の重み

10時から12時の時間指定   12時から14時の時間帯指定 14時から16時の時間帯指定

1

2

3

4

5

6

1

2

3

4

5

6

1

2

3

4

 5

6

1

2

4.4

3

4.4

2.2

1

1.5

2.5

3.3

4

2.4

1

3.9

4.7

4.6

2.4

2.5

2

2

2.5

2.2

4

3

2

1.5

1.7

1.8

2.8

2.4

2

3.9

2.6

3.4

2.2

3.7

3

4.4

2.5

2.5

3.8

4.6

3

2.5

1.7

2

3.8

3.9

3

4.7

2.6

2.1

2.4

3.5

4

3

2.2

2.5

1.8

2.4

4

3.3

1.8

2

2.2

3.4

4

4.6

3.4

2.1

2.3

2.4

5

4.4

4

3.8

1.8

2.8

5

4

2.8

3.8

2.2

2.7

5

2.4

2.2

2.4

2.3

1.5

6

2.2

3

4.6

2.4

2.8

6

2.4

2.4

3.9

3.4

2.7

6

2.5

3.7

3.5

2.4

1.5

 

3-2 最短路をみつける

巡回セールマン問題と実際の荷物を運ぶ現場の異なる点は、巡回セールスマン問題では始点と終点を同じでなけばならない。しかし時間指定の巡回路では始点を出てまた始点に戻ってくる必要はない。巡回路は必要なく最短の経路がわかれば良い。 最短の巡回路をみつけると最も短い経路も見つけることができる。それは、その巡回路の 辺のなかで1番重みがおおきものを取り除けば良い。

 

 

3‐3 提案

12時から14時までの配達してが6件ある場合、その6件を1番短い時間でまわれるルートをだす。そしてその他の時間帯してとつなぎあわすことす。しかし、そのつなぎ目にあわせる段階で1番短い巡回路ではなくなってしまう。

そこで、10時から12時までの時間帯指定の全点と12時から14時の時間帯指定全点で1番重みが小さいところを結ぶ同様に12時から14時の点と14時から16時の点も結ぶ。

さらに、最後の時間帯指定の全点と1番はじめの時間帯の全点と1番近い点を結ぶ。

 

赤でつながった点は時間が切り替わったとき(12時になったとき)始点となる。そして次の時間帯とつながれているところが終点となる。各時間帯で始点と終点を決め先ほどの巡回セールスマン問題を利用して、最短路をだす。

そして、各時間帯指定はこの始点と終点を指定した最短路をまわって、時間帯指定が切り替わるとき赤い線を通り次の時間帯にうつる。

図では始点と終点がわかれているが、これをつなげると1日の巡回ルートができる。

 

3‐4 はじめの最短路との比較

3‐2でだした最短路と3‐3の提案した経路を比較すると

 

10〜12

12〜14

14〜16

最短路

11

9.8

11.4

提案

11.6

10.1

12.4

その差

0.6

0.3

1

最短路のほうはそれぞれの最短路を壊さず、つなげるとやはり最後の始点と終点をつなげる辺の重みが大きくなってしまい、良い結果が得られなかった。

11+9.8+11.4+1.5+1.2+4=38.3

 

そして、時間帯を移動すると赤い線と、最後の終点と始点をつないだ距離を出す。

11.6+12.5+12.4+0.7+0.8+0.7=36.3

3‐5 まとめ

現段階では、提案した手法が良い結果がでる。しかし、この手法は単純で最適な答えと言う保証もない。まだまだ改良できると考えている。

 

4章:これからの課題

4‐1 時間帯指定について

今回の問題を解くときは初めからこの時間帯指定を届けられる範囲の荷物を割り当て巡回ルートを求めたが、実際は同じ時間帯指定の荷物が多くあれば実行不可能になってしまう。

4‐2 プログラムについて

今回はひとつの時間帯指定で6つと少ない数の荷物であったが実際はもっと多くの荷物を運ばなくてはならない、そうなるとプログラミングで自動的に計算ができるようにしたい。

 

謝辞

いつも思いつきでしゃべってるような私に対して、アドバイスや意見、時間を割いてもらったゼミ生

青山 隆行 安藤 慎哉 大内 徹 大島 靖雄 小川 幸子 落合 剛 工藤 真由子 

田部井 崇 辻村 大介 三浦 麻貴 三木田 誠 八木沢 伸也 それに三年生

皆さんのおかげで、良い刺激を受けて、ここまでこられました。どうもありがとう。

すべての運送会社に問い合わせましたが、情報を提供してもらえたのは、

ヤマト運輸株式会社さんだけでした。ありがとうございます。


根本俊男先生

いつまでたっても進まない研究に対して、根気よく指導をしていただき本当にありがとうございました。

 

参考にさせていただいたデータ

[1]ヤマト運輸株式会社発行 クロネコ博覧会2000

[2]ヤマト運輸株式会社 横浜主管支店 お客様サービスセンター

参考文献 [注1]

インターネット利用者動向情報サービス「Nielsen//NetRatings」
2000年9月のインターネット人口調査結果などを発表