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

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

1章：はじめに

1−1　何を

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

1−2　なぜ

増加している宅配便、さらに時間帯指定という制約が加わった。そして、時間帯指定を守りながら配達をするのには、配達ドライバーの工夫と努力によって支えられている。

ドライバーの負担を減らし、同じ時間で多くの荷物を運べるような巡回路を見つけたい。

1−3アプローチは

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

2章：宅配便の現状

2-1 研究のきっかけ

私はいままでは、ほとんど宅急便を出したことなどなかった。インターネットのオークションで多数の個人取引をするようになってから数十個の宅急便をだした。私だけが特別ではなく1999年秋から始まったYahoo Auctionsでは1日の約9万点の新規出品がある。

宅配便の市場規模は大きく成長している。しかし、小額の個人取引をするのに600円から800円程度の宅配便の代金は高すぎる。もっとコストをさげ宅急便の代金が安くなればと思い始めたことからこの研究がはじまった。

2-2 宅配便の増加

インターネットの普及によりオンラインで９月のPC接続によるインターネット人口は、2,234万人。オンラインショッピングの個人利用経験率は16.6％（約370万人）[注1]

　また、オークションなどで、個人取引の需要も増加しここ数年、宅配便の市場そのものが大きくなっている。

　

[1]

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

2-3 時間帯お届けのメリット

荷物を受け取る側は、いつ荷物が届くか知ることができる。

配達する側は、配達したときの不在率をさげ１回で配達できる件数が多くなる。

宅急便を届けても不在ならば、持ち帰り再度届けることになる。時間帯お届けサービス以前は６割の荷物が配達しても不在で持ち帰るといった浪費をしている。（年間取扱数７億７１７８万個うちの4.6億個）時間帯お届けのサービスを導入することにより、２割に下げることができる。

「時間帯お届け」サービス開始以前（1998年6月以前）
・第1度目のお伺い…ご不在率約４０％
・2度目、3度目お伺い…ご不在率約１０％

同サービス開始後（1998年6月以降）
・第1度目のお伺い…ご不在率約２０％
・2度目、3度目お伺い…ご不在率１０％以下　　[2]

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

2-4 「時間帯お届け」の問題点

「時間帯お届け」サービスの現状を伺うと「サービス開始に伴う新たな配送ルートというものはございません。従来の配送ルートを使って各ドライバーが工夫をし、配達しています。」という回答をもらった。

今まではドライバー、が荷物を運ぶ巡回路を考え配送していたが、時間の制約が加わったこといより、いくら近い届け先があっても時間の制約を守らなければならないため、その指定の時間帯になったとき配達しなければならない。ドライバーは距離と時間の両方を考えながら配達をしなければならない。

2-5 解決されると

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

3章：効率よく巡回するために

3-１時間帯で区切られた、巡回セールスマン問題を計画する

18時〜20時までの配達指定が10件ある場合、その10件を一番短い時間で回れるルートを出す。そしてその他の時間帯指定とつなぎあわす。しかし、そのつなぎ目にあわせる段階で一番短い巡回路ではなくなってしまうのが問題点。

時間帯指定があるので巡回セールスマン問題は時間の制約がつき難しくなる

よって、ドライバーのルートを考えなければならない負担を軽くすること、さらにドライバーの工夫したルートよりおおくの荷物を届けられるルートを研究する。

参考文献
[注1]
インターネット利用者動向情報サービス「Nielsen//NetRatings」

2000年9月のインターネット人口調査結果などを発表http://www.netratings.co.jp/press_releases/pr_231000.htm

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

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

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