ルートごとの輸送業者の配車を集合被覆問題と整数計画法で最適化する

2022年1月31日2024年10月6日

集合被覆問題とは？

ある物流会社はトラック輸送業務をすべてアウトソーシングしています。

この会社は、得意先から産業ガスの特殊輸送を依頼されました。

依頼された輸送ルートは１０あり、毎日各ルートに１台のトラックが必要です。

 

特別仕様のトラックしか使えないため、業務委託する輸送業者は限られます。

各業者で配車可能な台数やルートも、下記のように限定されています。

 

また、輸送運賃は下記の通りです。

 

この時、全体の輸送運賃を最小にするためには、どのルートにどの輸送業者を割り当てれば良いでしょうか？

但し各輸送業者には、その業者が輸送可能なルートはすべて委託することが条件です。

このように全体をその部分集合で被覆するように、部分集合の組み合わせを最適化する問題を集合被覆問題と言います。

 

集合被覆問題をExcelソルバーで解く

定式化する

ある業者を選択すれば、その業者が受託できるルートはすべて任せないといけないので、各業者を選択するか（１）しないか（０）を変数x₁～x₁₀で表すことにします。

すると、条件は次のような表としてまとめることができます。

 

この表ではx₁～x₁₀の値は仮の数値になっていますが、例えばx₃は０になっています。

これは業者３は選択しないということなので、業者３の行（６行目）の数値をすべて０にすると、後々の計算がし易くなります。

従って、次のような表を追加で作成します。

 

このようにすると、選択されない業者の「ルート請負Y or N」や「輸送運賃」の値はすべて０になります。

そして、この表を使って次のように目的関数と制約条件を計算することができます。

目的関数

合計運賃

=(60,000+295,000+50,000+205,000)x₁+(95,000+115,000+250,000)x₂

+(110,000+60,000+225,000)x₃+(95,000+55,000)x₄

+(100,000+50,000+305,000+140,000)x₅+(135,000+225,000+200,000+150,000)x₆

+(65,000+315,000)x₇+(120,000+165,000+100,000+210,000)x₈

+(45,000+140,000+120,000)x₉+(65,000+185,000)x₁₀

 

制約条件

ルートAに割り当てられるトラック数

x₂+x₃+x₅+x₈≧1

ルートBに割り当てられるトラック数

x₁+x₅+x₇+x₉≧1

ルートCに割り当てられるトラック数

x₆+x₈+x₉≧1

ルートDに割り当てられるトラック数

x₂+x₄+x₈+x₉≧1

ルートEに割り当てられるトラック数

x₂+x₆≧1

ルートFに割り当てられるトラック数

x₆+x₈+x₁₀≧1

ルートGに割り当てられるトラック数

x₁+x₅+x₇≧1

ルートHに割り当てられるトラック数

x₁+x₃+x₄≧1

ルートIに割り当てられるトラック数

x₅+x₆≧1

ルートJに割り当てられるトラック数

x₁+x₃+x₁₀≧1

 

Excelソルバーで解く

後は前回の記事で行ったように、これをソルバーの条件設定画面で設定すれば、自動的に計算してくれます。

【輸送計画問題】DC経由にするか工場直送にするかを整数計画法で解いてみる

【ナップザック問題】発注する商品の優先順位を整数計画法で最適化する

 

データ⇒ソルバーをクリックしソルバー画面を開いて、下記のように目的関数と制約条件を入力します。

 

これを実行すると、次のような計算結果になりました。

 

業者３、４、６、７を起用すればすべてのルートをカバーでき、その時の全体運賃は１,６３５,０００円で最小になります。

 

重複を許す集合被覆問題とは？

このように全ルートが網羅されるように業者を選び、その時にかかるコストを最小化するような問題は集合被覆問題と呼ばれ、オペレーションズリサーチの１分野として知られています。

今回の例では、１０ルートのうち９ルートは４つの業者のいずれかしかカバーしていませんが、ルートHだけは２つの業者がカバーするような結果になりました。（業者３と４）

このようなのを重複を許す集合被覆問題といいます。

 

これに対し重複を許さない集合被覆問題もあり、こちらの方が厳しい条件になります。

ちなみに今回の例では重複を許さないと解がありません。

 

条件を緩めて重複を許さないケースの最適解を求める

条件を緩めて0-1整数計画法に定式化する

先に求めた解ではルートHを業者３と４が重複して請け負うことになります。

ということは、どちらかが配車できないことになります。

つまり、各業者は可能なルートはすべて請け負うことを条件としているにも拘わらず、請け負えないルートが出てくるということです。

このように、「各業者は可能なルートはすべて請け負う」という条件は厳しすぎて、配車の最適化には不向きです。

つまり、集合被覆問題をそのまま配車の最適化に適用することは現実的ではありません。

 

そこで、「各業者は可能なルートの半分以上を請け負う」というように条件を緩めてみます。

例えば、業者１は４つのルートを請け負うことができますが、そのうち２つ以上のルートを請け負えればOKとするのです。

このような問題は厳密には集合被覆問題とはいいませんが、現実にはこのようなケースの方が多いと思います。

またExcelのソルバーで解くこともできるので、このように緩和した条件で先ほどの配車を最適化してみましょう。

但し、各ルートで１台では少なすぎて解が見つからないため、各ルートで毎日２台のトラックを配車することにします。

 

まず操作変数の定義を変えます。

先ほどは各業者を選択するかしないかを決めればよかったため、変数x_iを各業者に１つずつ定義しましたが、今度は各業者が可能なルートを一括で請け負うとは限らないため、各業者／各ルートごとに１つずつ変数x_iを定義します。

表にまとめると次のようになります。

 

また、制約条件は次のようになります。

各ルートに割り当てるトラック数

x₄+x₈+x₁₃+x₂₃=2

x₁+x₁₄+x₂₁+x₂₇+x₃₀=2

x₁₇+x₂₄+x₂₈=2

x₆+x₁₁+x₂₅+x₂₉=2

x₇+x₁₈=2

x₁₉+x₂₆+x₃₁=2

x₂+x₁₅+x₂₂=2

x₃+x₉+x₁₂=2

x₁₆+x₂₀=2

x₄+x₁₀+x₃₂=2

 

各業者が請け負うルート数

x₁+x₂+x₃+x₄≧2/4

x₅+x₆+x₇≧2/3

x₈+x₉+x₁₀≧2/3

x₁₁+x₁₂≧2/2

x₁₃+x₁₄+x₁₅+x₁₆≧2/4

x₁₇+x₁₈+x₁₉+x₂₀≧2/4

x₂₁+x₂₂≧2/2

x₂₃+x₂₄+x₂₅+x₂₆≧2/4

x₂₇+x₂₈+x₂₉≧2/3

x₃₀+x₃₁+x₃₂≧2/3

 

Excelソルバーで解く

これをソルバー画面で次のように設定します。

 

これを実行すると、次のような計算結果になりました。

 

各ルートに２台ずつ重複せずに配車され、各業者も可能なルートの1/2以上を請け負えるという条件での最低合計運賃は３０５万円に最適化されました。

 

整数計画法にして中期配車計画を最適化する

先の２つの最適化手法は、日次ベースの配車はできますが、月次や年次での配車計画には使えません。

求める変数x_iが１か０の二値だからです。

そこで、これを正の整数というように定義し直して、中期の配車計画を最適化してみましょう。

制約条件は下記の通りであると仮定します。

1. 各ルートの配車トラック数は年間３００台
2. 業者１、２、３、４、７、８の年間最低配車数は２００台（すべてのルートを併せて）
3. 業者５、６、９、１０の年間配車数上限は４００台（すべてのルートを併せて）

 

これらの条件を表にまとめると次のようになります。

 

ソルバー画面では次のように設定します。

 

実行すると次のような計算結果になりました。

 

各業者の配車数の上限と下限を考慮しながら、各ルートに年間３００台を配車する場合の年間配車コストは、最小値４４８,５００,０００円に最適化されました。