Document

配送計画を立てる
•
•
•
•
•
•
基本的な配送計画
特殊ケース
多種の制約
バリエーション
近傍探索
近傍探索の高速化
配送計画とは
・デポ（配送基地・荷物の集積所）に荷物があり、それをト
ラックで顧客に配送する際の、最適な配送の仕方（各ト
ラックのルート）を求める問題
問題例１：部品配送
・ある部品工場から、他の工場へ、週に1度部品の配送を行
う。部品の量は大体一定なので、毎週同じルートで配送し
ても差し支えない
・配送コストを抑えるため、配送ルートを固定してトラックの
台数と移動距離を最小化したい（一回きっちり解きたい）
・工場間距離はナビで計算か、直線距離
問題例２：宅急便
・宅急便の集配所から、トラックでお客に荷物を配送する。
・コスト最小化のため、台数と移動距離を最小化したい。
・お客は毎日変わるので、毎日解きたい
・お客が指定した時間に到着する必要がある。
11:00!
17:00!
午前中!
問題例３：乗合いタクシー
・複数のお客が乗合うタクシーの会社がある
・あちこちで順番に、指定した時間にお客を拾い／降ろす
（お客を拾い空港へ向かう等。乗り降りの順番はどうでもいい）
・移動距離が長いと客から文句が来る
・他の客のために大回りをすると文句が来る
・他の客の待ち時間が長いと文句が来る
問題例４：工作機械のスケジュール
・工作機械で、それぞれの製品を修理する
・製品 i を修理した後、製品 j の修理を始めるには、セット
アップの時間が dij かかる
・使用する機械の数を少なく、総セットアップ時間を短くしたい
お客が沢山いると難しい
・小さい問題は人手で簡単に解けるが、客が増えると、とり
あえずのルートを見つけるだけでも大きな手間がかかる
基本的な配送計画
入力：顧客の集合と、顧客間・顧客デポ間の移動距離
各顧客でのサービス時間
解：デポに始まりデポに終わる、トラックのルートの集合
目的関数：運送コスト（トラックの総移動距離）、あるいはトラッ
クの台数（解に含まれるルートの数）の最小化
制約条件：
・各顧客は、どれかのトラックのルートに含まれていること
・場合によっては、（トラックの台数）
・各トラックの最大移動距離（運転手の労働時間）
特殊ケース１
・トラックの台数が1台だと、巡回セールスマン問題になる。
少なくとも、巡回セールスマン問題よりは難しい
特殊ケース２
・特殊なグラフを作り、目的関数をトラックの台数最小化に
すると、ビンパッキングになる
ai+aj/2
aj/2
各大きさ ai
大きさ b
ai/2
長さ b
その他の制約
・実際の問題を解こうとすると、いろいろな制約が必要
最大積載量：各トラックについて顧客に届ける荷物の総重量
が、最大積載量を超えないこと
時間指定：トラックの、顧客への到着時間に、（ある範囲の）
指定がある
トラックの大きさ：トラックに種類がある場合（10t、2tなど）、各
顧客にサービスできるトラックの種類の限定（狭い道に面す
る顧客には大型トラックは使えない、など）
到着の順序：ある顧客をサービスしてから、ある顧客へ行くこ
と、などのルート内の順序
ドライバーの労働時間のばらつき：長いルートと短いルートが
あるのは、良くない
バリエーション１
・デポが複数の場合
・顧客は、どのデポのトラックがサービスしても良い
顧客対デポの制約：ある顧客をサービスできるデポの制限
バリエーション２
・トラックルートの、始点と終点のデポが異なっても良い場合
始点と終点が異なるトラックの台数制約
始点と終点の組みに対する禁止制約
バリエーション３
・回転（一度デポに戻ること）をゆるす場合
乗合いタクシー問題
・荷物を降ろす顧客と、荷物を積み込む顧客がある
顧客対デポの制約：「顧客Aを乗せる」と「顧客Aを降ろす」
は同じトラックでサービス
問題の難しさ
・ NP-hard と呼ばれる、難しい問題のクラスに属する
・ 01 整数計画問題として定式化できる
ただし、整数計画ソルバーで解いても、効率が悪い
・近似解法・発見解法を使うのが普通
・近実用上十分な精度の解が得られる
（そもそも人手で解くより、はるかに短時間、手間もかからない。
それにそれなりの解の精度があれば十分）
（そもそも、移動距離・サービス時間の誤差が最初からある）
近似解法１
・デポからの方角で、顧客をグループ分けする
・それぞれの区画を、トラック1台で回る
・それぞれの区画は巡回セールスマン問題で解く
・計算時間は、O(巡回セールスマン問題 × グループ数)
顧客数 → +∞ のとき、最適解の2倍程度に収束する
セービング法
・最初、すべてのトラックのルートを空にする
・顧客を１つずつ、最も移動距離が増えないルート（挿入可能
なルート）に挿入する
・計算時間は O（顧客数2）
平均的に、誤差10-20%くらいに収まる
近傍探索１
・ルート内の変更
 巡回セールスマンの近傍探索を使えばよい
2-opt、挿入近傍など
数：（長さ）2（台数）
近傍探索２
・ルートの組に対する変更
移動：ある顧客を、別のルートのどこかの位置に挿入
数：（長さ）2（台数）2
近傍探索３
・ルートの組に対する変更
2-exg：２つのルートを途中で切り、後半を交換
数：（長さ）2（台数）2
近傍探索４
・ルートの組に対する変更
クロス近傍： 2つのルートの部分ルートを交換する
数：（長さ）4（台数）2
全部使うと強力。局所探索でも最適解近くまで行く
例題
・距離は縦横に移動した数、最大積載量は10、最大移動距離は 20
4
2
3
8
3
4
2
1
4
1
2
5
例題
・距離は縦横に移動した数、最大積載量は10、最大移動距離は 20
4
2
3
8
3
4
2
1
4
1
2
5
例題
・距離は縦横に移動した数、最大積載量は10、最大移動距離は 20
4
2
3
8
3
4
2
1
4
1
2
5
例題
・距離は縦横に移動した数、最大積載量は10、最大移動距離は 20
4
2
3
8
3
4
2
1
4
1
2
5
例題
・距離は縦横に移動した数、最大積載量は10、最大移動距離は 20
4
2
3
8
3
4
2
1
4
1
2
5
例題
・距離は縦横に移動した数、最大積載量は10、最大移動距離は 20
4
2
3
8
3
4
2
1
4
1
2
5
例題
・距離は縦横に移動した数、最大積載量は10、最大移動距離は 20
4
2
3
8
3
4
2
1
4
1
2
5
例題
・距離は縦横に移動した数、最大積載量は10、最大移動距離は 20
4
2
3
8
3
4
2
1
4
1
2
5
実際の計算時間
・仮に、顧客数を1000、トラックを30台とする
 ルートの長さはだいたい30になる
・それぞれの近傍の大きさは
（長さ）2（台数）2 ≒ （顧客数）2
≒ 100万
（長さ）4（台数）2 ≒ （長さ）2（顧客数）2 ≒ 10億
・近傍1つの目的関数の評価に、長さ分の計算時間がかかる
 全部の近傍の評価をする、300億
・パソコンは1秒で1億回くらいの計算ができる
 3000秒。だいぶ遅い（局所探索でも1日かかりそう）
計算の高速化
・近傍1つの目的関数の評価に、長さ分の計算時間がかかる
ここを速くする
・よく見ると、近傍の各解は、1箇所ずつ異なっている
・異なる部分についてだけ O(1) 時間で再計算する。
・ルートの距離、最大積載量など、だいたいの制約がチェック可
・到着時間の制約も、工夫するとできる
（ルートの長さ／３）倍くらいの高速化
計算の高速化２
・改善の可能性のある近傍だけチェックする
・クロス近傍は、2-exg 近傍を２回行ったもの
（ルートの長さが）改善されるなら、どちらかの2-exgで改善がある
・改善のある2-exg 近傍を含むクロス近傍だけチェックする
（一概には言えないが）300倍くらいの高速化
計算の高速化３
・目的関数の計算時間の改善
‥ ‥ 10倍
・改善の可能性のある近傍だけチェックする ‥ ‥ 300倍
合計3000倍
一回の計算が1秒になった。
これなら、1分ぐらいで、局所探索も終わりそう
課題：到着時間指定などの難しい制約が入っていると
こう、うまくはいかない
・どうしたものか
まとめ
・基本的な配送計画の紹介
（入力、出力、変数、制約、目的関数の定義）
・特殊ケースと難しさ
・よく使われるいろいろな制約
最大積載量、到着時間、トラックの種類、到着順
・拡張問題
複数デポ、回転、始終点不一致、乗り降ろし
・近似解法
エリア分割、セービング法
・近傍探索
巡回セールスマンのもの、挿入、2-exg、クロス
・近傍探索の高速化
目的関数の評価法、可能性のない候補の除外

Download Report