文教大学 情報学部 経営情報学科 97Ｐ21068 木村博一
目次
1−1 何を
時間帯指定のある宅配便の配送ルートを見つける。
1−2 なぜ
増加している宅配便、さらに時間帯指定という制約が加わった。そして、時間帯指定を守りながら配達をするのには、配達ドライバーの工夫と努力によって支えられている。 ドライバーの負担を減らし、同じ時間で多くの荷物を運べるような巡回路を見つけたい。
2-1 研究のきっかけ
私はいままでは、ほとんど宅急便を出したことなどなかった。インターネットのオークションで多数の個人取引をするようになってから数十個の宅急便をだした。私だけが特別ではなく1999年秋から始まったYahoo Auctionsでは1日の約18万点の新規出品がある。 宅配便の市場規模は大きく成長している。しかし、小額の個人取引をするのに600円から800円程度の宅配便の代金は高すぎる。もっとコストをさげ宅急便の代金が安くなればと思い始めたことからこの研究がはじまった。
2-2 宅配便の現状
宅配便の増加 インターネットの普及によりオンラインで９月のPC接続によるインターネット人口は、2,234万人。オンラインショッピングの個人利用経験率は16.6％（約370万人）[注1] また、オークションなどで、個人取引の需要も増加しここ数年、宅配便の市場そのものが大きくなっている。
2-3 時間帯お届けサービス導入
時間帯お届けサービス 宅配便のシェアトップのヤマト運輸株式会社が1998年6月より、「時間帯お届け」というサービスがはじまる。これは、1日を6つ時間帯に分け、お客様の希望する時間帯を選んでもらい、その指定された時間に届けるサービスである。「時間帯お届け」ができると、郵便局や他の民間の宅配業者も同様のサービスをはじめた。
時間帯お届けのメリット 荷物を受け取る側は、いつ荷物が届くか知ることができる。 配達する側は、配達したときの不在率をさげることができ、１回で配達できる件数が多くなる。 宅急便を届けても不在ならば、荷物を持ち帰り再度届けることになる。時間帯お届けサービス以前は６割の荷物が配達しても不在で持ち帰るといった浪費をしている。年間取扱数７億７１７８万個うちの4.6億個が配達してにもかかわらず、１度持ち帰っていた。時間帯お届けのサービスを導入することにより、２割に下げることができた。
「時間帯お届け」
サービス開始以前（1998年6月以前）
・第1度目のお伺い…ご不在率約４０％ ・2度目、3度目お伺い…ご不在率約１０％
同サービス開始後（1998年6月以降）
・第1度目のお伺い…ご不在率約２０％ ・2度目、3度目お伺い…ご不在率１０％以下 [2]
「時間帯お届け」は6つの時間帯を指定と指定なしの7つに分類でき、 受取人も時間を指定することによって品物がいつ届くのか把握できる。さらに、この時間帯を指定することによって荷物を受取人に手渡す確率が上がる（不在のため再度届ける行為を減らす）と考えられる。よって、配達する側の再度配達というコスト削減につながる。 このシステムは双方にとって利益があるシステムである。
「時間帯お届け」の問題点 「時間帯お届け」サービスの現状を伺うと「サービス開始に伴う新たな配送ルートというものはございません。従来の配送ルートを使って各ドライバーが工夫をし、配達しています。」という回答をもらった。 今まではドライバー、が荷物を運ぶ配送ルートを考えていたが、時間の制約が加わったこといより、いくら近い届け先があっても時間の制約を守らなければならないため、その指定の時間帯になったとき配達しなければならない。ドライバーは距離と時間の両方を考えながら配達をしなければならない。
解決されるとドライバーの負担を減らし、ドライバーが考える配送ルートと比べ同じ時間内で荷物をより多く運ぶことができるような配送ルートをつくればコストが下がる。また、ドライバーの能力に左右されずに荷物を配達できる。そしてコストが下がることによって、宅配便の料金も下がる。
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つの時間帯指定の組合せの数 (n-1)!個ある。 （各時間帯の荷物が6点のとき）
さらに次の時間帯指定のグループとつなぐ線の組合せ ｎ本 、1番最後の点と営業所を結ぶので 1通り
時間帯指定は3つあるので (n-1)!×ｎ×(n-1)!×ｎ×(n-1)!×１
点の数はそれぞれ6なので 5!×6× 5!×6× 5!＝1944000通りの組合せもの数がある。 これが各時間帯の荷物が7点になってしまうと134億３６９２８０００の組合せになりすべての配送ルートを調べるのは困難である。
3-3 各時間帯の最も短い配送ルートをみつける
それぞれ各時間帯ごとで最も短い配送ルート（最短路）をみつける。ここでは全探査をつかった。
そして、各時間帯の配送ルートを1日の配送ルートにつなげあわす。ここでは単純に３つの最短路どうしで始点・終点のどちらか近いほうを次の時間帯につなげた。それぞれ赤い線でつなげると1日の配送ルートがでる。 でも、赤い線の距離が長くなってしまう。 短い走行距離で荷物を配達したいので、良い1日の配送ルートとはいえない。
3‐4 提案
12時から14時までの配達してが6件ある場合、その6件を1番短い時間でまわれるルートをだす。そしてその他の時間帯してとつなぎあわすことす。しかし、そのつなぎ目にあわせる段階で1番短い配送ルートではなくなってしまう。
今の時間帯と、次の時間帯の点のうち一番距離が短いものを 先に赤い線で結ぶ。 最後の時間帯と結ぶのは営業所に1番短い点 をつなぐ。（ 10時から12時までの時間帯指定の全点と12時から14時の時間帯指定全点で1番重みが小さいところを結ぶ同様に12時から14時の点と14時から16時の点も結ぶ。）
さらに、最後の時間帯指定の全点と1番はじめの時間帯の全点と1番近い点を結ぶ。
赤でつながった点は時間が切り替わったとき（12時になったとき）始点となる。そして次の時間帯とつながれているところが終点となる。図では始点と終点がわかれているが、これをつなげると1日の巡回ルートができる。
赤い線より 時間帯指定ごとの始点と終点が決まる。
(n-2)!×(n-2)!×(n-2)＝24×24×24＝13824 通りで時間帯指定の数を掛け合わした数通りの組合せ数に減る。
4-1 配送ルートの比較
はじめの最短路との比較3‐3でだした最短路と3‐4の提案した経路を比較すると、今回は提案ルートが短い配送ルートをだした。
しかし、提案した配送ルートがどんな例の時でも いい答えをだすとは限らなかった 。
4-2 研究結果
1．研究によりわかったこと 時間の制約がある配送問題は時間帯をつなげることで時間の制約をなくすことができる。
2．時間制約を 緩和する ことができる。時間帯の数だけ (n-2)! を掛け合わした数を調べなければ 一日の配送ルートを 出せない。
4-3 これからの課題
時間帯指定について
今回の問題を解くときは初めからこの時間帯指定を届けられる範囲の荷物を割り当て巡回ルートを求めたが、実際は同じ時間帯指定の荷物が多くあれば実行不可能になってしまう。
プログラムについて
今回はひとつの時間帯指定で６つと少ない数の荷物であったが実際はもっと多くの荷物を運ばなくてはならない、そうなるとプログラミングで自動的に計算ができるようにしたい。
謝辞
アドバイスや意見、時間を割いてもらったゼミ生
青山 隆行 安藤 慎哉 大内 徹 大島 靖雄 小川 幸子 落合 剛 工藤 真由子
田部井 崇 辻村 大介 三浦 麻貴 三木田 誠 八木沢 伸也 それに三年生
皆さんのおかげで、良い刺激を受けて、ここまでこられました。どうもありがとう。
根本俊男先生
いつまでたっても進まない研究に対して、根気よく指導をしていただき本当にありがとうございました。
参考にさせていただいたデータ
[1]ヤマト運輸株式会社発行 クロネコ博覧会2000
[2]ヤマト運輸株式会社 横浜主管支店 お客様サービスセンター