配送計画問題に対するセービング法

配送計画問題について

一箇所の配送センターから複数個所の需要地に複数台の車両で需要量を配送するとき、
総配送距離が最短となる車両経路を計画する問題です。

• 車両の容量上限と車両の配送距離上限(一日に配送できる距離)の制約を設けています。
• 配送センターは画面の中央です。
• 配送先はアプレットの右上端にあるプルダウンメニューから問題例を選ぶか、
  画面上をクリックすることで配置することができます。
  配置された青円の大きさは需要量を示しています。
  ただし、画面上をクリックした際は、各配送先の需要量はすべて同じになります。
• SOLVEボタンでセービング法による求解の動作を開始します。
• 動作中にSTOPボタンまたは画面をクリックすると一時停止します。
• SOLVEボタンで動作を再開します。
• CLEARボタンで配送先を消去します。

セービング法について

配送計画問題に対してはいろいろな解き方があるのですが、ここではセービング法という方法を紹介します。

セービング法は、図1に示すアイディアにもとづいた方法です。
つまり、配送センターにもどらず配送先をハシゴすることによって
距離を節約(セービング)していく方法です。

図1 セービング法の基本アイディア： 　　青円の配送先2箇所をハシゴすると、 　　赤矢印→二本分の長さと青矢印→の 　　　　　長さの差だけ総距離を縮めることができる

最初は一切ハシゴなしからはじめて、もっとも節約できる距離が
大きい配送先から順にハシゴしていきます。
このとき、ハシゴが車両の容量上限や配送距離上限の制約から
みて可能かどうかも判断します。

飲み屋のハシゴで、はら具合と帰りの時間を気にするのといっしょですね。