CPLEXの最適化 - 1台のマシンで一連の製品を計画する

Question

これは私の問題です。私は、10の製品をパッケージ化するとしましょう。 10種類すべての製品の包装は同じライン/マシンで行われます。

異なる製品間に異なるセットアップ時間があります。たとえば、製品1から製品2までのセットアップ時間（高さを調整し、小さなクリーンアップを行う必要があります）は30分です。製品2から製品1まで（高さを調整するだけで、クリーンアップは必要ありません）、セットアップ時間は15分です。製品1から製品3までは5分かかります。

セットアップ時間を最小限に抑えようとしています。

どうすればこの問題を解決できますか？私の実際の問題には100種類の製品があります（100×100のマトリックスなので）

Traveling Salesmanの問題と本当に似ています。違いは、必ずしも製品1（またはTSPのA市）から離れる必要はなく、最後に製品1に戻る必要はありません。

これは私が過去に使用したTSPコードです。問題を解決するために修正することはできますか？それとも私はそれを行うことができる他の方法はありますか？

ありがとうございます！

// *********************** 
// Parameters 
// *********************** 

int  N  = ...; 

range V = 1..N; 

// arcs 

tuple  arc  {int v_dep; int v_arr;} 
setof(arc) A  = {<i,j> | i,j in V: i != j}; 

// Matrix Setup Time 

float   D[V][V] = ...; 

// *********************** 
// Decision variable 
// *********************** 


// x [<i,j>]= 1 if node j follows i 

dvar boolean x[A]; 

// flow conversion 

dvar float+ y[A]; 


// *********************** 
// Objective 
// *********************** 

// Minimize setup times 

minimize sum (<i,j> in A) D[i][j]*x[<i,j>]; 




subject to { 


forall (v in V) 

    sum (a in A: a.v_arr == v) x[a] == 1; 


forall (v in V) 

    sum (a in A: a.v_dep == v) x[a] == 1; 



forall (v in V:v != 1) 

sum (a in A: a.v_arr == v) y[a]-sum (a in A: a.v_dep == v) y[a] == 1; 


    sum (a in A: a.v_arr == 1) y[a]-sum (a in A: a.v_dep == 1) y[a] == -(N-1); 

forall (a in A) 

y[a] <= N*x[a]; 

}; 

Answer 1

私はよくあなたの問題を理解していれば、あなたは私が製品に0

を私は製品への製品0からコスト0で、「製品0」を作成することにより、TSPにそれを削減し、製品から0を要することができます

パッケージの問題は、「製品0」で始まりTSPで終わるTSPになります。