|
時間制約付き巡回セールスマン問題の研究
文教大学 情報学部 経営情報学科 97Ｐ21068 木村博一
研究動機 宅配便の市場規模は大きく成長しています、しかし宅配便の料金高くもっと下がって欲しい。 そうなればもっと宅配便が利用できる。では宅配便のコストを下げるにはどうしたら良いか考えてみました。
研究内容 宅配便を宅配するのは、巡回セールスマン問題にあてはまります。巡回セールスマン問題とは、ある地域のいくつかの家を１回だけよって出発地に戻ってきて、その経路の中で巡回したときの距離が１番短い経路を求める問題を巡回セールスマン問題といいます。 簡単に言うと「何件もある家を1番短い距離でまわって来い！」という問題です。 さらに問題があります、各家は時間帯を指定してくるので、その時間を守りながら配達をしなければなりません。配達先のすぐ近くに別の家の荷物があっても、その家の指定した時間以外では届けてはならないのです。 「1番短い距離」を見つけるだけでは時間指定が守れません。現在は、配達ドライバーの工夫と努力によって毎日の宅配ルートが考えられています。 |