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

2023年10月12日

集合被覆問題とは?

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

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

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

 

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

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

 

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

 

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

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

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

 

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

定式化する

ある業者を選択すれば、その業者が受託できるルートはすべて任せないといけないので、各業者を選択するか()しないか()を変数x1~x10で表すことにします。

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

クリックすると拡大します

 

この表ではx1~x10の値は仮の数値になっていますが、例えばx3は0になっています。

これは業者3は選択しないということなので、業者3の行(6行目)の数値をすべて0にすると、後々の計算がし易くなります。

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

クリックすると拡大します

 

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

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

目的関数

合計運賃

=(60,000+295,000+50,000+205,000)x1+(95,000+115,000+250,000)x2

+(110,000+60,000+225,000)x3+(95,000+55,000)x4

+(100,000+50,000+305,000+140,000)x5+(135,000+225,000+200,000+150,000)x6

+(65,000+315,000)x7+(120,000+165,000+100,000+210,000)x8

+(45,000+140,000+120,000)x9+(65,000+185,000)x10

 

制約条件

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

x2+x3+x5+x8≧1

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

x1+x5+x7+x9≧1

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

x6+x8+x9≧1

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

x2+x4+x8+x9≧1

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

x2+x6≧1

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

x6+x8+x10≧1

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

x1+x5+x7≧1

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

x1+x3+x4≧1

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

x5+x6≧1

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

x1+x3+x10≧1

 

Excelソルバーで解く

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

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

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

 

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

クリックすると拡大します

 

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

クリックすると拡大します

 

業者3、4、6、7を起用すればすべてのルートをカバーでき、その時の全体運賃は,635,000円で最小になります。

 

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

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

今回の例では、10ルートのうち9ルートは4つの業者のいずれかしかカバーしていませんが、ルートHだけは2つの業者がカバーするような結果になりました。(業者3と4)

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

 

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

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

 

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

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

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

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

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

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

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

 

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

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

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

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

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

 

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

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

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

クリックすると拡大します

 

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

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

x4+x8+x13+x23=2

x1+x14+x21+x27+x30=2

x17+x24+x28=2

x6+x11+x25+x29=2

x7+x18=2

x19+x26+x31=2

x2+x15+x22=2

x3+x9+x12=2

x16+x20=2

x4+x10+x32=2

 

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

x1+x2+x3+x4≧2/4

x5+x6+x7≧2/3

x8+x9+x10≧2/3

x11+x12≧2/2

x13+x14+x15+x16≧2/4

x17+x18+x19+x20≧2/4

x21+x22≧2/2

x23+x24+x25+x26≧2/4

x27+x28+x29≧2/3

x30+x31+x32≧2/3

 

Excelソルバーで解く

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

クリックすると拡大します

 

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

クリックすると拡大します

 

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

 

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

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

求める変数xiが1か0の二値だからです。

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

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

  1. 各ルートの配車トラック数は年間300台
  2. 業者1、2、3、4、7、8の年間最低配車数は200台(すべてのルートを併せて)
  3. 業者5、6、9、10の年間配車数上限は400台(すべてのルートを併せて)

 

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

クリックすると拡大します

 

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

クリックすると拡大します

 

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

クリックすると拡大します

 

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

 

無料の運行管理システムAI-Contactフリート

このような配車のアルゴリズムは輸送管理システム(TMS)の一機能として含まれている場合があります。

このTMSは幅広い概念ですが、運行管理動態管理を含む場合もあります。

そして、この運行管理や動態管理を完全無料のクラウドサービスで提供している会社があります。

 

通常、無料というのは眉唾もので、始めは無料だけども、どこかの携帯電話会社みたいに途中で有料化宣言するとか、気づかないうちにいつの間にか有料になっていたということが多いですね。

でも、この会社は永久に無料で提供することを宣言しています。

そのシステムの名はAI-Contactフリートです。

これは「運行管理」、「動態管理」、「車両管理」等をオールインワンで提供するクラウドサービスです。

運送業を行っている物流会社だけでなく、自社トラックで輸送を行っている荷主会社自社のサービスエンジニアを多く抱える電気設備会社、更には社用車を多く抱える一般会社等、様々な会社に適用可能です。

またこれだけの機能が詰まっていて無料なので、中小企業だけでなくダイハツ工業メイデンアイシン戸田建設NTT東日本等の大企業にも採用されています。

Web説明会も毎日開催されているようです。

少しでも興味のある方は、お気軽に問い合わせてみてはいかがでしょうか。