LoginSignup
1
0
@Kuranari2020

CPLEXサンプル'Car'の解説

Last updated at Posted at 2024-04-25

CPLEXサンプル'Car'の解説記事です。
サンプルはopl\examples\opl\models\Car\配下にあります。

  • 実行環境
    • Windows11 64bit
    • CPLEX 22.1.1.0 Community Edition

1.問題設定

　自動車の生産方式の1つに、大量生産に適したライン生産方式というものがあります。ライン生産方式では、エアコンやラジオなどのOptionを取り付け作業を行うユニットの前を生産中の車が流れていきます。一般にライン生産方式は、一つの種類を大量生産するのに向いているされていますが、ここでは一つのラインで複数種類を生産し、これを混流生産と言います。
参考：混流生産とは？メリットや種類、自動車業界の詳細な事例を紹介

問題設定図.png

　必要な生産数を満たすように各ユニットが流れてくる車のどれに取付作業を実施すればよいかをCP（制約プログラミング）によって解くことがゴールとなります。

データ

  • 生産する車の種類：7
  • 車に取り付けるoptionの数：5
  • 各車種の生産数：[5,5,10,10,10,10,5]
  • 各車種毎に取り付けるoptionのパターン：
Car1 Car2 Car3 Car4 Car5 Car6 Car7
option1 ○ ○ ○
option2 ○ ○ ○
option3 ○ ○
option4 ○ ○ ○
option5 ○
  • 各optionの生産能力を表すパラメータcapacity(l,u)　
capacity(l,u)
option1 (1,2)
option2 (2,3)
option3 (1,3)
option4 (2,5)
option5 (1,5)

　capacityは生産ユニットがoptionを取り付ける時の、区間幅とその区間内における生産能力を表しています。例えば、option1は、2台中1台に対して取り付けることが可能であることを、option2は、3台中2台に取り付けることが可能であることを意味しています。
capacity.png

決定変数

  • 生産する車の並び順。

    • 並び順を決定すれば、各ユニットでは何番目の車に対してoptionを取り付ければよいかを決定することができます。

  • 全ての車を生産するために必要なスロット数

    • スロットとは生産ライン上の車1台に対応する空間を指します。全ての車を生産するのに何台分の空間が必要かを決定変数として求めます。並び順の変更だけで制約を満たす解があるとは限らないため、作業する必要のない空きスロットをつくることでcapacityの制約を満たすことを許容します。

目的関数

　スロット数は少なくとも生産する車の合計分は必要であることに注意し、以下のように目的関数を定義します。

\mathsf{minimize}\ \quad S_l-D_C 

S_l:最後のスロット番号, D_C:生産する車の数の合計 \

　目的関数の値は0が最小で、このとき生産ライン上に空きスロットは存在しない並びができていることになります。空きスロットがあるとその分追加でスペースを確保することになり、生産する時間もかかるためこれを最小化することがコスト最適を達成することになります。

制約1

　各車種毎に必要な台数だけを生産する。

制約2

　各ユニットは生産能力が決まっていて、決められた割合以下で稼働する。

制約3

　最後のスロット番号以降はすべて空きスロットになる。
　本サンプルモデルでは空きスロットを途中に入れることを許容するため、最初は余裕のあるスロットを用意して最適化を行います。可能な限り前に詰めて生産することをコスト最適と定義するための制約になります。
　数式としては目的関数に含まれる$S_l$に対する制約と捉えることができます。

2. サンプルコード解説

　サンプルにはcar.modとcarseq.modの2つのモデル用意されていますが、本記事ではcarseq.modの解説します。
（補足）car.modは空きスロットの概念がなく、並び順だけを制約を解くことになるため解なしになることが多いです。

サンプルデータ

　基本的にdatファイル内でデータは定義されています。

車に取り付けるoption設定

　optionの数と車の数をはじめに宣言します。各車種の生産台数もここで宣言します。

carseq.dat(抜粋)_車種とoptionの数
nbConfs = 7;		// 生産する車の種類数
nbOptions = 5;			// 車に取り付けるoptionの数
demand = [5, 5, 10, 10, 10, 10, 5];		// 各車種の生産数

　optionは対応する車との2次元配列で表現されます。

carseq.dat(抜粋)_オプション
option = [
           [ 1, 0, 0, 0, 1, 1, 0],
           [ 0, 0, 1, 1, 0, 1, 0],
           [ 1, 0, 0, 0, 1, 0, 0],
           [ 1, 1, 0, 1, 0, 0, 0],
           [ 0, 0, 1, 0, 0, 0, 0]
        ];

　各車種毎に取り付けるoptionのパターン表と対応していて、option毎に取りつける場合は1を、取り付けない場合は0と対応します。

生産能力

　各option毎の生産能力をcapacity変数として、2つのパラメータで表しています。
パラメータ型はmodファイル内で定義されています。

carseq.mod(抜粋)_生産能力の型定義
tuple CapacitatedWindow {		// capacityを表す変数型。
  int l;		// window内のフラグONの最大数
  int u;		// windowの幅、
};
carseq.dat(抜粋)_生産能力
capacity = [
      <1,2>,
      <2,3>,
      <1,3>,
      <2,5>,
      <1,5>
   ];

その他の型定義

　.modファイル側で配列のサイズや変数の範囲を、.datファイルから読み込んで使用します。
それらに空きスロットの概念を追加しているのが、Allまたはallが名前の最初に付けられている変数です。

carseq.mod(抜粋)_その他の変数定義
int nbConfs   = ...; 
int nbOptions = ...;

range Confs = 1..nbConfs;		// 各車種を表す番号
int demand[Confs] = ...;
int nbCars = sum (c in Confs) demand[c];		//　生産数を計算
int nbSlots = ftoi(floor(nbCars * 1.1 + 5));		// スロット数
range Slots = 1..nbSlots;		// 各スロットを表す番号 
range Options = 1..nbOptions;		// 各オプションを表す番号
int option[Options,Confs] = ...; 

CapacitatedWindow capacity[Options] = ...; 

range AllConfs = 0..nbConfs;		// 車の種類に加えて、空のスロットを表す0を追加している
int nbBlanks = nbSlots - nbCars;		// 空のスロットの数
int allOptions[o in Options, c in AllConfs] = (c == 0) ? 0 : option[o][c]; // 空スロットで、optionを取り付けないというフラグを追加した新しいoption配列

決定変数

　前述した2つの決定変数をdvarで宣言します。

carseq.mod(抜粋)_決定変数
dvar int slot[Slots] in AllConfs; // 最後のスロット番号
dvar int lastSlot in nbCars..nbSlots; // 生産する車の並び順

目的関数

　前述した目的関数の数式そのままです。

carseq.mod(抜粋)_目的関数
minimize lastSlot - nbCars; // 目的関数。

制約条件

制約条件1

　決定変数slotの要素に入る、各スロットで生産される車種をその車種ごとに合計すると、demandで定義されている生産数と一致します。
　forallで各車種ごとに条件を作っています。

carseq.mod(抜粋)_制約条件1
  forall (c in Confs)
    count(slot, c) == demand[c];

制約条件2

　capacityの制約条件です。
　forallで各option毎にslotをcapacityのパラメータで分割した区間ごとに条件を作っています。sumでその区間内で作業を行う台数を合計し、それがパラメータで決められた値以下であることを表す不等式になっています。

carseq.mod(抜粋)_制約条件2
  forall(o in Options, s in Slots : s + capacity[o].u - 1 <= nbSlots)
    sum(j in s .. s + capacity[o].u - 1) allOptions[o][slot[j]] <= capacity[o].l;

ポイントは、alloptions[o][slot[j]]の部分で、slot[j]はj番目に生産される車種を表す決定変数のため、定まっていませんが、それを制約条件中の配列の添え字として使用することができます。条件を満たす解を探索することがCPの特徴です。

制約条件3

　目的関数で使われているlastSlotの制約条件です。
　lastSlotより後ろのスロットでは車は生産しないことを表します。

carseq.mod(抜粋)_制約条件3
    forall (s in nbCars + 1 .. nbSlots)
    (s > lastSlot) => slot[s] == 0;

完成コード

　サンプルとほぼ同じ内容で、日本語のコメントを追記しています。

carseq.dat
nbConfs = 7;		// 生産する車の種類
nbOptions = 5;			// 車に取り付けるoptionの数
demand = [5, 5, 10, 10, 10, 10, 5];		// 各車種の生産数

// 各車種毎に取り付けるoptionのパターン
option = [
           [ 1, 0, 0, 0, 1, 1, 0],
           [ 0, 0, 1, 1, 0, 1, 0],
           [ 1, 0, 0, 0, 1, 0, 0],
           [ 1, 1, 0, 1, 0, 0, 0],
           [ 0, 0, 1, 0, 0, 0, 0]
        ];

// 各optionの生産能力を表すパラメータcapacity(l,u)　
capacity = [
      <1,2>,
      <2,3>,
      <1,3>,
      <2,5>,
      <1,5>
   ];
carseq.mod
using CP;


// dataファイルから受け取る変数を定義
int nbConfs   = ...; 
int nbOptions = ...;

range Confs = 1..nbConfs;		// 各車種を表す番号
int demand[Confs] = ...;
int nbCars = sum (c in Confs) demand[c];		//　生産数を計算
int nbSlots = ftoi(floor(nbCars * 1.1 + 5));		// スロット数
range Slots = 1..nbSlots;		// 各スロットを表す番号 
range Options = 1..nbOptions;		// 各オプションを表す番号
int option[Options,Confs] = ...; 

tuple CapacitatedWindow {		// capacityを表す変数型
  int l;		
  int u;
};
CapacitatedWindow capacity[Options] = ...; 


range AllConfs = 0..nbConfs;		// 車の種類に加えて、空のスロットを表す0を追加している
int nbBlanks = nbSlots - nbCars;		// 空のスロットの数
int allOptions[o in Options, c in AllConfs] = (c == 0) ? 0 : option[o][c]; // 空スロットで、optionを取り付けないというフラグを追加した新しいoption配列

// 決定変数
dvar int slot[Slots] in AllConfs; // 最後のスロット番号
dvar int lastSlot in nbCars..nbSlots; // 生産する車の並び順

// 目的関数
minimize lastSlot - nbCars;

// 制約条件 
subject to {
  // Cardinality of configurations
  // count(slot, 0) == nbBlanks;		// 元のサンプルにあるが、コメントアウトしている。
  
  // 制約条件1
  forall (c in Confs)
    count(slot, c) == demand[c];

  // 制約条件2
  forall(o in Options, s in Slots : s + capacity[o].u - 1 <= nbSlots)
    sum(j in s .. s + capacity[o].u - 1) allOptions[o][slot[j]] <= capacity[o].l;

  // 制約条件3
  forall (s in nbCars + 1 .. nbSlots)
    (s > lastSlot) => slot[s] == 0;
};

実行結果

　実行構成の'Car sequencing'実行を選択すると最適化が始まります。筆者の環境では約10秒ほどで解が得られました。
image.png

　問題ブラウザーを確認すると以下のようになっています。
image.png

　lastSlotの値がnbCarsと同じになっています。これは、目的関数の値が0で最小のパターンの解となっていることを意味していて、空きスロットを作ることなく必要数が全て生産できることになります。
　slotは生産される車の並びになっていますが、これをもとに各UnitのON/OFFを図示したものが以下になります。(黄色がON)
画像1_小.png
　各Unitの稼働時間が一定の割合以下でしか稼働しないように、設計することができました。

（補足）car.modのファイルには決定変数にsetupという変数があり、これは上図のONを1に、OFFを0に対応させた二重配列です。slotが決まればこれは一意に定まります。
以下はサンプルコードにおけるこの対応を表す条件部分です。

car.mod(抜粋)_決定変数setupの条件
   forall(o in Options, s in Slots )
     setup[o,s] == option[o][slot[s]];

3.終わりに

　生産能力が低くなると、Slotの途中に0で、何も生産しないパターンが入らないと生産できなくなるはずですので、そのようなパターンも解きたいと思ってcapacityの条件をきつくして実行してみたところ、筆者の環境では40分経っても解が得られませんでした。
　こちらを参考に、executeの中で探索フェーズを指定できるようなので、サンプルコードに追加して記載してあげればうまく解けると思います。

　最後まで読んでいただきありがとうございました。

4.参考

CSPLib001 : Car Sequencing

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0