- LocalSolverホーム
- クイックスタートガイド
- 最初のビジネス問題を解く
最初のビジネス問題を解く
車両割当問題は自動車メーカーの生産ライン会社に関する有名な組合せ最適化問題です。
クラスの中には様々なオプションのセットにより分類される車両の組をスケジューリングする問題が含まれています。
組み立てラインは、様々なオプション(エアコン、サンルーフの取り付けなど)をチームによって設置する複数の作業場があります。
そのような各作業場ではパラメータPとQによって与えられた一定の仕事量を処理する能力を持ちます：
作業場は、Q車両の各連続でオプションを持つP車両を処理することができます。
問題のゴールは、処理能力が最小化される個々のクラスとそれに与えられた要求を満たし、一連の車両製造を行うことです。
すなわち、各オプションP/Q、および全長Qの各ウィンドウ、違反max(0、N-P)がカウントされ、Nは実際にこのウィンドウの内でスケジューリングされたオプション数です。
このセクションで、問題向けに簡単なLSPモデルを提供致します。
その中で、ファイルからどのようにデータの読み込みを行うのかを説明し、明確な意思決定、制約、および問題の目的を定義し、どうのように車両配列のモデリングを行うのかを解説します。またローカル・サーチをコントロールするために使用することができる複数のパラメータを導入します。
この問題向けの完全なプログラムはC++、Java、およびC#バージョンを例題集から入手頂けます。
入力データを読み込む
この問題に関する複数のデータファイルは、フォルダ・LocalSolver・例題集・車両割当問題で入手頂けます。こちらからダウンロード頂けます。ファイルのフォーマット：
1行目：車両数、オプション数、クラス数- 2行目：各オプションに対する、ブロックで（パラメータP）このオプションを使う車両の最大数
- 3行目：各オプションに対する、最大数を参照するための（パラメータQ）ブロックサイズ
- そして、各クラスに対する、クラスのインデックス：このクラスにおける車両数：各オプションに対する。（このクラスがそれを（0または1）必要としているかに関わらず）
下記は入力データを読み込むinput()関数です。注：不確定な変数はnilと等しく、これは既存の変数の確認が可能です。ここで、inFileNameまたはsolfileNameが定義されていない場合、エラーが表示されます。ファイルに（改行に関係なく）ただ単に次々と整数を読み込みました。
/* Reads instance data. */
function input() {
usage = "\nUsage: localsolver car_sequencing.lsp "
+ "inFileName=inputFile solFileName=outputFile [lsTimeLimit=timeLimit]\n";
if (inFileName == nil) error(usage);
if (solFileName == nil) error(usage);
inFile = openRead(inFileName);
nbPositions = readInt(inFile);
nbOptions = readInt(inFile);
nbClasses = readInt(inFile);
ratioNums[1..nbOptions] = readInt(inFile);
ratioDenoms[1..nbOptions] = readInt(inFile);
for [c in 1..nbClasses] {
readInt(inFile); // Note: index of class is read but not used
nbCars[c] = readInt(inFile);
options[c][1..nbOptions] = readInt(inFile);
}
}問題のモデリング
LSP言語で最適化問題をモデリングするうえで、最も重要なステップの1つは、取りうる意思決定を定義することです。これらの意思決定は、それらをインスタンス化することで、モデル(特に制約と目的)のすべての他の表現を評価することが可能です。LocalSolverは、所与の目的と制約に対し最もよい実行可能な意思決定の発見を目指します。ここで、生産ラインにおける車両のオーダーを決定したいと思います。0-1モデリングで、ポジションpの車両がクラスcと0またはその他に属する時、cp[c][p]が1と等しくなるように、nbClasses*nbPositions変数cp[c][p]を定義しています。
cp[1..nbClasses][1..nbPositions] <- bool();ユーザー・モデルの制約定義は、これとは別の重要なモデリング作業です。一般的に、制約は必要とされる要求のみとすべきです。車両割当問題で、同じ位置に2台の車両を与えることは物理的に不可能なため、すべてのP/Q比率を常に満たすことは不可能です。(目的とここで定義した理由です)。それが、探索スペースと1の解から別の解に移行する機能を定義するため、制約の使用を制限することはローカル・サーチのモデリングで特に重要です。ここで、私達は制約の2つの族に割り当てる要求を表現します。：1つのポジシションあたり、確実に1台の車両を与え、各クラスに対する車両の需要を満たします。
for [c in 1..nbClasses]
constraint sum[p in 1..nbPositions](cp[c][p]) == nbCars[c];
for [p in 1..nbPositions]
constraint sum[c in 1..nbClasses](cp[c][p]) == 1;注：目的を記述するために、複数の中間表現を導入します。まず最初に、、ポジションpの車両がオプションoを持ち0ではない場合、1と等しいことを表現するop[o][p]を宣言します。
op[o in 1..nbOptions][p in 1..nbPositions] <-
or[c in 1..nbClasses : options[c][o]](cp[c][p]);実際、このポジションがこのオプション取るためにクラスの1つを取った場合、オプションoはポジションpで表します。このようなクラスの表はiteration [c in 1..nbClasses : options[c][o]]を使用し指定します。中間表現を定義するこの機能は、モデルをより読みやすく、より効率的にします。（その他、複数の表現で、この中間表現が使用される場合）同様に、タイムオプションoの数は下記のように定義することで、ポジションjとポジションj+Q[o]-1間を表します。
nbCarsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1]
<- sum[k in 1..ratioDenoms[o]](op[o][p+k-1]);最終的に、過剰設備のペナルティ関数は、上記の問題仕様書で定義された通りに記述することができます。
nbViolationsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1]
<- max(nbCarsWindows[o][p]-ratioNums[o], 0);注：ここでは合計を表現するために、異なる方法が使われています。実際に、演算子sumを使用し合計を定義することができ、また算術演算子+、-も使用することが可能です。最後のステップは、目的関数（全ての違反の合計）を定義することです。
obj <- sum[o in 1..nbOptions]
[p in 1..nbPositions-ratioDenoms[o]+1](nbViolationsWindows[o][p]);
minimize obj;下記は車両割当問題に対応するLSPモデルの関数model()を解くコードです。
function model() {
// 0-1 decisions:
// cp[c][p] = 1 if class c is at position p, and 0 otherwise
cp[1..nbClasses][1..nbPositions] <- bool();
// constraints:
// for each class c, no more than nbCars[c] assigned to positions
for [c in 1..nbClasses]
constraint sum[p in 1..nbPositions](cp[c][p]) == nbCars[c];
// constraints: one car assigned to each position p
for [p in 1..nbPositions]
constraint sum[c in 1..nbClasses](cp[c][p]) == 1;
// expressions:
// op[o][p] = 1 if option o appears at position p, and 0 otherwise
op[o in 1..nbOptions][p in 1..nbPositions] <-
or[c in 1..nbClasses : options[c][o]](cp[c][p]);
// expressions: compute the number of cars in each window
nbCarsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1]
<- sum[k in 1..ratioDenoms[o]](op[o][p+k-1]);
// expressions: compute the number of violations in each window
nbViolationsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1]
<- max(nbCarsWindows[o][p]-ratioNums[o], 0);
// objective: minimize the sum of violations for all options and all windows
obj <- sum[o in 1..nbOptions]
[p in 1..nbPositions-ratioDenoms[o]+1](nbViolationsWindows[o][p]);
minimize obj;
}ソルバーをパラメータ化する
いくつかのパラメータはローカル・サーチをコントロールする目的で関数param()で定義します。
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 60;
lsTimeBetweenDisplays = 3; // the number of seconds between each display
lsNbThreads = 4; // number of parallel searches launched
}この最後の関数で、モデルが完成します。複数のコントロール・パラメータは、LSPファイルで定義する代わりに、コマンド行で設定します。
例えば、localsolver/examples/carsequencing/instances/carseq_500_8_20_08.の例題で、（localSolverライセンスがサイズで制限されている場合、問題サイズが小さい例題free_trial_csを使用ください）下記のコマンド行により、300秒間で解に到達します。
> localsolver car_sequencing.lsp inFileName=instances/carseq_500_8_20_08.in solFileName=sol.txt lsTimeLimit=30arallel searches launched
}全てのコントロール・パラメーターはセクションBuilt-in variables and functions.で、参照頂けます。上記のコマンド行を使用し、LocalSolverをスタートさせるこ、下記のアウトプットを得ます。
LocalSolver 2.0 (build 20120213)
Copyright (C) 2012 Bouygues SA, Aix-Marseille University, CNRS.
All rights reserved (see Terms and Conditions for details).
Run input...
Run model...
Run param...
Run solver...
Model:
expressions = 27001, operands = 75873
decisions = 10000, constraints = 520, objectives = 1
Param:
time limit = 30 sec, no iteration limit
seed = 0, nb threads = 4, annealing level = 1
Objectives:
Obj 0: minimize, no bound
Phases:
Phase 0: time limit = 30 sec, no iteration limit, optimized objective = 0
Phase 0:
[3 sec, 308456 itr]: obj = (68), mov = 1248013, inf = 83.4%, acc = 0.8%, imp = 1380
[6 sec, 588195 itr]: obj = (52), mov = 2394957, inf = 79.9%, acc = 0.7%, imp = 1455
[9 sec, 874330 itr]: obj = (45), mov = 3616826, inf = 79.4%, acc = 0.7%, imp = 1482
[13 sec, 1155344 itr]: obj = (38), mov = 4768613, inf = 78.4%, acc = 0.7%, imp = 1509
[16 sec, 1428567 itr]: obj = (30), mov = 5891541, inf = 77.4%, acc = 0.7%, imp = 1529
[19 sec, 1721793 itr]: obj = (27), mov = 7036828, inf = 76.8%, acc = 0.7%, imp = 1540
[22 sec, 2011834 itr]: obj = (23), mov = 8198412, inf = 76.7%, acc = 0.7%, imp = 1550
[25 sec, 2270191 itr]: obj = (23), mov = 9295094, inf = 76.5%, acc = 0.7%, imp = 1553
[28 sec, 2567075 itr]: obj = (22), mov = 10405504, inf = 76.2%, acc = 0.7%, imp = 1557
[30 sec, 2730517 itr]: obj = (22), mov = 11071294, inf = 76.2%, acc = 0.7%, imp = 1562
2730517 iterations, 11071294 moves performed in 30 seconds
Feasible solution: obj = (22)
Run output...各3番目の秒で、(パラメータlsTimeBetweenDisplaysに応じた)探索に関する状況の要約リポートが表示されます：経過した秒数とイタレーション数が実行され、目的関数の値は、予約語(セパレートを使用して)で与えます。
- movは実行されたムーブの総数です。注：複数の探索が並行的に実行されるので、イタレーション数より多くなります。
- infは実行不可能なムーブ率です。（実行不可能解につながるムーブ）
- accは取られたムーブの率です。（シミュレーティドアニーリング手法で取られたコストを持つ実行可能解につながるムーブ）
- impは確実に改善するムーブの総数です。注：これは並行探索のすべてを蓄積するため、最善の目的関数が変更されない間は、この数の増加を確認することが可能です。
lsVerbosity to 0.の設定で、全ディスプレイの解除が行えます。
解を記述する
探索の最後で、LocalSolverにより呼び出される関数output()を定義します。
例えば、ここでいくつかの変数に割り当てられるべき名前を持つファイルに問題の解を記述するために、関数の定義を選択します。（例えば、コマンド行の中で）
下記のフォーマットで解を記述します。
- 1. 1行目＝目的関数
- 2. 2行目＝nbポジションにポジション1のクラス
ファイルに記述するには、最初のパラメータとして出力ファイルを取り、通常、printとprintln関数を使用します。
function output() {
solFile = openWrite(solFileName);
println(solFile, getValue(obj));
for [p in 1..nbPositions][c in 1..nbClasses : getValue(cp[c][p])]
print(solFile, c-1, " ");
println(solFile);
}
