輸送計画問題

　配送計画システム

輸送計画問題

生産計画 在庫管理 オーダー

輸送計画輸送計画 輸送需要

配送計画配送計画 幹線輸送計画幹線輸送計画

積載計画 配車計画

運行計画 作業計画

物流拠点

　工場　　工場　　工場　 物流拠点物流拠点 　需要地　　需要地　　需要地　 ^販売店_顧客

品種・量納期制約

オーダー在庫制約

拠点間の長距離輸送 月間・週間計画

デポを中心とした 区域配送

輸送需要の

車両への割付け 車両手配

輸送ルート 車両運用 荷積・荷卸作業

容量・時刻制約

幹線輸送計画

輸送計画問題（幹線輸送計画）

輸送ルート計画

運用ルート計画

車両割当計画

ルート候補の作成 輸送ルート決定

運用ルート決定 ルート候補の作成

割当可能性判定 最適割当

知識ベース シミュレータ

集合分割モデル マッチングモデル

知識ベース

集合分割モデル 最小費用循環流 知識ベース

割当問題

集合被覆問題

列車 １ 列車

２ 列車

３ 列車

４ 列車 駅 B ５

駅 C

駅 C 駅 A 駅 B 駅 B

駅 B 駅 B 駅 A 駅 C

　最小費用循環流モデ

ル

トラックの種類

5

400

４日 計画期間

デマンドの数

383

25

3.4

計算時間

6,558

トリップの数

796

383

問題の規模

2.75

659,043

ルートの数

583

1,010,649

輸送ルート候補の作成

輸送ルート決定

＜ビークルルーティング問題

＞ デポから複数の顧客へのコスト最小 な配送経路を求める問題

顧客

デポ

Ａ Ｂ

Ｃ

Ｄ

Ｅ

Ｆ Ｇ

Ｈ Ｉ

Ｊ

車両１

車両２ 車両３

石田啓一：物流システム構築のための技法，計測と制

御ーミニ特集物を動かす・貯える・仕分ける， vol.37,N

o.3(1998)

＜セービング法＞

＜スウィープ法＞

解の探索－列挙木－

解法：分枝限定法による解空間の探 索

１

天目健二・山口盛兄：道路網の動的経路誘導システム，計測と制御ーミ ニ特集都市道路網の交通流制御システム，

vol.41.No.3(2002)

組合せ問題の難しさ 

－ハミルトン経路問題－

　セールスマンが全ての都市を

　セールスマンが全ての都市を

1 1

出発地に戻って来る経路で最も短いものを捜す問題 出発地に戻って来る経路で最も短いものを捜す問題 です。です。

・６都市ならば、

・６都市ならば、

　　　５　　　５

!/ !/

= =

× ×

× ×

× ×

/ /

= =

・ｎ都市ならば、

・ｎ都市ならば、

　　　（ｎ－１）！

　　　（ｎ－１）！

/ /

近年近年

, ,

りました。

TSP TSP （

Traveling Salesman Problem Traveling Salesman Problem ）

原型：ハミルトン経路問題

東京大学工学部計数工学科　松井知己氏資料から

ｎ 10 100 1,000 10,000 ｎ １０ ^－５ 秒 １０ ^－４ 秒 ０．００１秒 ０．０１秒

ｎ ^２ １０ ^－４ 秒 ０．０１秒 １秒 １００秒

ｎ ^３ ０．００１秒 １秒 １６．６分 ２７７時間

２ ^ｎ ０．００１秒 １０ ^１４ 世紀 １０ ^２８４ 世紀 ？ ？ ∞ ｎ！ ０．０３６秒 １０ ^１４１ 世紀 １０ ^２５５１ 世紀 ？ ？ ∞

ｎ 10 100 1,000 10,000

ｎ １０ ^－５ 秒 １０ ^－４ 秒 ０．００１秒 ０．０１秒

ｎ ^２ １０ ^－４ 秒 ０．０１秒 １秒 １００秒

ｎ ^３ ０．００１秒 １秒 １６．６分 ２７７時間

２ ^ｎ ０．００１秒 １０ ^１４ 世紀 １０ ^２８４ 世紀 ？ ？ ∞ ｎ！ ０．０３６秒 １０ ^１４１ 世紀 １０ ^２５５１ 世紀 ？ ？ ∞

　例えば、

1MIPS (mega instructions per second)

1

100

1step

10 ^-6

　例えば、

1MIPS (mega instructions per second)

1

100

1step

10 ^-6

＜計算時間の実感＞

＜計算時間の実感＞

＜クラス P に属する問題の例

＞・線形計画問

題 ・ネットワーク計画問

＜ 題 NP 完全問題の例＞

・充足可能性問題

・整数計画問 題

・巡回セールスマン問題

・ナップサック問題

・スケジューリング問題

・集合分割問

題

＜大規模組合せ最適化問題の解法＞

メタヒューリスティクス

• アニーリング法、遺伝アルゴリズム、

　　タブーサーチ等の最適化の新解法。

• メタ（超）とついているのは、解くべき問題 　に対するヒューリスティクス（発見的知識）

　をいかにアルゴリズムにまとめあげるか論じ

ているから。

メタヒューリスティクスの方式

＜遺伝アルゴリズム（ＧＡ法）＞

＜遺伝アルゴリズム（ＧＡ法）＞

　生物の集団が自然淘汰により進化していく過程を模したものです。

　生物の集団が自然淘汰により進化していく過程を模したものです。

　複数の解（集団）を用意し、それらを組み合わせることにより、より良い解（進化）を求めてい 　複数の解（集団）を用意し、それらを組み合わせることにより、より良い解（進化）を求めてい こうという手法です。

こうという手法です。

＜遺伝アルゴリズム（ＧＡ法）＞

＜遺伝アルゴリズム（ＧＡ法）＞

　生物の集団が自然淘汰により進化していく過程を模したものです。

　生物の集団が自然淘汰により進化していく過程を模したものです。

　複数の解（集団）を用意し、それらを組み合わせることにより、より良い解（進化）を求めてい 　複数の解（集団）を用意し、それらを組み合わせることにより、より良い解（進化）を求めてい こうという手法です。

こうという手法です。

＜シミュレーテッド・アニーリング（ＳＡ法）＞

＜シミュレーテッド・アニーリング（ＳＡ法）＞

　焼きなまし法と呼ばれもので、温度を下げることにより、より強固な固体結晶を得ようとする 　焼きなまし法と呼ばれもので、温度を下げることにより、より強固な固体結晶を得ようとする 物理過程（熱力学）をもしたものです。例えば、刀鍛冶が鉄を熱しては水で冷却する作業を繰り返 物理過程（熱力学）をもしたものです。例えば、刀鍛冶が鉄を熱しては水で冷却する作業を繰り返 す（焼きなまし）ことにより、切れ味の良い（強固な）刀を作る過程です。

す（焼きなまし）ことにより、切れ味の良い（強固な）刀を作る過程です。

　最も強固な状態（最適解）に至るには、単に一度に冷却したのでは駄目で、何度も加熱（解の改 　最も強固な状態（最適解）に至るには、単に一度に冷却したのでは駄目で、何度も加熱（解の改 悪）と冷却（解の改善）を繰り返す必要があります。

悪）と冷却（解の改善）を繰り返す必要があります。

＜シミュレーテッド・アニーリング（ＳＡ法）＞

＜シミュレーテッド・アニーリング（ＳＡ法）＞

　焼きなまし法と呼ばれもので、温度を下げることにより、より強固な固体結晶を得ようとする 　焼きなまし法と呼ばれもので、温度を下げることにより、より強固な固体結晶を得ようとする 物理過程（熱力学）をもしたものです。例えば、刀鍛冶が鉄を熱しては水で冷却する作業を繰り返 物理過程（熱力学）をもしたものです。例えば、刀鍛冶が鉄を熱しては水で冷却する作業を繰り返 す（焼きなまし）ことにより、切れ味の良い（強固な）刀を作る過程です。

す（焼きなまし）ことにより、切れ味の良い（強固な）刀を作る過程です。

　最も強固な状態（最適解）に至るには、単に一度に冷却したのでは駄目で、何度も加熱（解の改 　最も強固な状態（最適解）に至るには、単に一度に冷却したのでは駄目で、何度も加熱（解の改 悪）と冷却（解の改善）を繰り返す必要があります。

悪）と冷却（解の改善）を繰り返す必要があります。

＜タブーサーチ（ＴＡ）＞

＜タブーサーチ（ＴＡ）＞

　人間には記憶があり、学習により最適解にたどり着くことができます。山登りに例えれば、一度 　人間には記憶があり、学習により最適解にたどり着くことができます。山登りに例えれば、一度 通過した頂上（局所解）に逆戻りすることを禁じる（ターブーとする）ことにより、効率的に真の 通過した頂上（局所解）に逆戻りすることを禁じる（ターブーとする）ことにより、効率的に真の 最高峰に到達できます。

最高峰に到達できます。

＜タブーサーチ（ＴＡ）＞

＜タブーサーチ（ＴＡ）＞

　人間には記憶があり、学習により最適解にたどり着くことができます。山登りに例えれば、一度 　人間には記憶があり、学習により最適解にたどり着くことができます。山登りに例えれば、一度 通過した頂上（局所解）に逆戻りすることを禁じる（ターブーとする）ことにより、効率的に真の 通過した頂上（局所解）に逆戻りすることを禁じる（ターブーとする）ことにより、効率的に真の 最高峰に到達できます。

最高峰に到達できます。

＜山登り法とメタヒューリスティクス＞

＜山登り法とメタヒューリスティクス＞

　基本的な探索方法は、通常「山登り法」と呼ばれる局所探索法です。

　基本的な探索方法は、通常「山登り法」と呼ばれる局所探索法です。

　これは、初期解からスタートして、解を徐々に改善していく手法で、局所解に到達したら探索を 　これは、初期解からスタートして、解を徐々に改善していく手法で、局所解に到達したら探索を 終了するものです。

終了するものです。

　これに対して、局所解から脱出して、さらに最適に近い解を効率良く探索しようとする手法が幾 　これに対して、局所解から脱出して、さらに最適に近い解を効率良く探索しようとする手法が幾 つか提案されいます。メタヒューリスティクスあるいは、メタ戦略と呼ばれるもので、遺伝アルゴ つか提案されいます。メタヒューリスティクスあるいは、メタ戦略と呼ばれるもので、遺伝アルゴ リズム（ＧＡ法） 、シミュレーテッド・アニーリング（ＳＡ法）、タブーサーチ（ＴＡ）等があり リズム（ＧＡ法） 、シミュレーテッド・アニーリング（ＳＡ法）、タブーサーチ（ＴＡ）等があり ます。ます。

＜山登り法とメタヒューリスティクス＞

＜山登り法とメタヒューリスティクス＞

　基本的な探索方法は、通常「山登り法」と呼ばれる局所探索法です。

　基本的な探索方法は、通常「山登り法」と呼ばれる局所探索法です。

　これは、初期解からスタートして、解を徐々に改善していく手法で、局所解に到達したら探索を 　これは、初期解からスタートして、解を徐々に改善していく手法で、局所解に到達したら探索を 終了するものです。

終了するものです。

　これに対して、局所解から脱出して、さらに最適に近い解を効率良く探索しようとする手法が幾 　これに対して、局所解から脱出して、さらに最適に近い解を効率良く探索しようとする手法が幾 つか提案されいます。メタヒューリスティクスあるいは、メタ戦略と呼ばれるもので、遺伝アルゴ つか提案されいます。メタヒューリスティクスあるいは、メタ戦略と呼ばれるもので、遺伝アルゴ リズム（ＧＡ法） 、シミュレーテッド・アニーリング（ＳＡ法）、タブーサーチ（ＴＡ）等があり リズム（ＧＡ法） 、シミュレーテッド・アニーリング（ＳＡ法）、タブーサーチ（ＴＡ）等があり ます。ます。

局所探索法 （山登り法）

現在の解現在の解

全近傍全近傍 を探索？を探索？

改善？改善？

解の更新解の更新

ＮＮ ＹＹ

近傍探索近傍探索

解の評価解の評価

ＮＮ 近傍での解の修正

評価関数の値の計算

終了終了 ＹＹ

◎◎初期解初期解

○

○

○

○

●

●

解空間解空間 評

価 関 数 の値 評 価 関 数 の値

山登り法（局所探索法）

山登り法（局所探索法）

改善？改善？

解の更新解の更新

ＮＮ ＹＹ

近傍探索近傍探索 解の評価解の評価

◎◎初期解初期解

○ ○

○

○

●

●

解空間解空間 評

価 関 数 の値 評 価 関 数 の値

評価値に対応 した確率で

＜ＳＡ法＞

＜ＳＡ法＞

○

○

○ ○

○ ○

○ ○

●

●

低温低温

シミュレーテッド・アニーリング法（ＳＡ法）

シミュレーテッド・アニーリング法（ＳＡ法）

解空間 評

価 関 数 の 値

最適解

遺伝アルゴリズム（ＧＡ法）

タブー探索法（ＴＳ法）

局所探索局所探索 局所解を一定期間 局所解を一定期間 探索禁止とする 探索禁止とする

（タブーリスト）

（タブーリスト）

＜タブー探索法＞

＜タブー探索法＞

◎

◎初期解初期解

解空間

局所解

タブーリスト 最適解

評 価 関 数 の値 評 価 関 数 の値

　２３９２都市の巡回セールスマン問題

新物流情報システムの構 成

カーＰＣ

サーバ通信 ＤＢ

サーバ 運行管理端末 実績管理端末

配車計画端末

＜ 物流センター ＞

＜車両＞

ＧＰＳ ＰＣナビ

新物流情報システムの特 徴

計算結果（配送計画）

運行実績ﾃﾞｰﾀ のﾌｨｰﾄﾞﾊﾞｯｸ

・運行実績ﾃﾞｰﾀ

・配送実績ﾃﾞｰﾀ

＜背景＞

＜目的＞

・企業活動全体の効率化、低コスト化

・物流における輸送の高度化、コスト削減

・ GPS 、地図情報システム、ナビーゲーション システム　　

　物流における種々の輸送システムに対応可

能な実用的な配送計画システムの開発

＜ビークルルーティング問題

＞ デポから複数の顧客へのコスト最小 な配送経路を求める問題

顧客

デポ

Ａ Ｂ

Ｃ

Ｄ

Ｅ

Ｆ Ｇ

Ｈ Ｉ

Ｊ

車両１

車両２ 車両３

＜物流における配送計画＞

種々の複雑な条件を考慮する必要があ る

・車両は均質ではなく、積載量や車種も異なる

・運転手の労働条件による稼動時間や休憩時間の設定

・顧客による配送時間の指定や、配送可能な車種の制 約

・車両の回転使用

・車両の運行形態

・複数のデポや集荷・配送が混在

例）

初期解作成

最適解探索

ヒ ューリスティック 手法

メ タ ヒ ューリスティ クス ・タブーサーチ

＜配送計画作成方式＞

評 価 関 数 の 値

解空間 初期解

局所解

タブーリスト 最適解

　 タブーサーチによる解空間の探索

車両を選択

未割当配 送先有り

割当可能 配送先有り

最も近い配送 先を割当てる

Ｙ

Ｙ

Ｎ 終了

Ｎ

＜初期解作成の処理フロー ＞

配送先

配送センタ

Ａ Ｂ

Ｃ

Ｄ

Ｅ

Ｆ

Ｇ

Ｈ Ｉ

Ｊ

車両１

車両２ 車両３

　　 初期解の例

最適解探索処理

修正案作成 修正案評価

配送計画更新 配送計画 記憶

更新判定

探索戦略

＜最適解探索処理の構成＞

ａ）配送先の移動（削除・追加 ^）

ｂ）配送先の交換

　　 車両割当変更操作

＜配送先の削除＞

元の配送順：Ａ→Ｂ→Ｃ→Ｄ→Ｅ→Ｆ 配送先Ｃを削除

Ａ→Ｂ→Ｄ→Ｅ→Ｆ

＜配送先の追加＞

元の配送順：Ａ→Ｂ→Ｄ→Ｅ→Ｆ 配送先Ｈを追加

Ｂ Ａ Ｃ

Ｄ Ｅ Ｆ Ｂ Ａ

Ｄ Ｅ Ｆ Ｂ Ａ

Ｄ Ｅ Ｆ Ｈ 新たな配送順：Ａ→Ｂ→Ｄ→Ｅ→Ｈ→Ｆ

（最適な位置に追加）

（他は元の配送順） 削除

追加 新たな配送順：

配送順序の決定（簡易法）

配送順序の決定（２－ｏｐｔ法）

ａ

ｂ ｃ

ｄ

ａ

ｂ ｃ

ｄ ２－ｏｐｔ法

＜配送順序の最適化＞

０ ｈ ｉ ａ ｂ ｅ ｆｇ ｃ ｄ ｊ ｋ ０

０ ｈ ｉ ａ ｃ ｇ ｆｅ ｂ ｄ ｊ ｋ ０

０：配送センタ

Ｙ Ｎ

Ｙ

Ｎ Ｙ

Ｎ

Ｙ Ｎ

これまでの最良の配送 計画よりも改善される

変更操作がタブーリス トに登録されている

更新する 現在の配送計画よ 更新しない りも改善される

現在の配送計画に対す る修正案の中で最善の ものである

変更操作をタブー リストに登録する

＜ タブーサーチの処理フロー

＞

配送伝票登録 マスタ整備

自動配車計画作成

配車計画（仮）

配車計画変更

配車計画

地図データ マスタデータ

伝票データ

他システム

配車計画サブシステム 配車計画サブシステム

運行監視サブシステム 運行監視サブシステム 運行実績サブシステム 運行実績サブシステム

実績データ

計画に沿った運行の監視 運行実績の収集および

配車計画出力

配送計画 手入力

伝票ファイル 手入力 マスタ情報

ファイル

発着地間所要時間

＜標準的な配送計画問題＞

depot

customer

garage

garage

customer

＜複数デポ配送計画問題＞

depot

customer

garage

garage

customer

depot

depot

＜集配送計画問題＞

depot

customer

garage

garage

customer

：

delivery

： pick

up