ノードからの出発が「n時間ごと」にのみ発生することをモデル化したいと思います。これを 2 つの変数を使用してモデル化し始めました。starttime[i,j,k] は、車両 k が j を目的地として i を出発した時刻を示します。 i から j、それ以外は 0。モデルは次のとおりです。
maximize maxdrive: sum{i in V, j in V, k in K} traveltime[i,j]*x[i,j,k];
subject to TimeConstraint {k in K}:
sum{i in V, j in V} (traveltime[i,j]+servicetime[i])*x [i,j,k] <= 1440;
subject to StartTime{i in V,j in V, k in K}:
starttime[i,j,k] + traveltime[i,j] - 9000 * (1 - x[i,j,k]) <= starttime[j,i,k];
subject to yvar{i in V, j in V}:
sum{k in K} x[i,j,k] <= maxVisits[i,j];
subject to Constraint1{i in V, j in V, k in K, g in V, h in K}:
starttime[i,j,k] + TimeInterval[i]*x[i,j,k] <= starttime[i,g,h];
問題の制約は「Constraint1」で、i は起点ノード、j は目的地ノード、k は車両です。インデックス g は、後の出発が任意の宛先ノードにできることを示すために使用されます。TimeInterval は、意図した間隔に対応します。つまり、i での TimeInterval が 2 時間の場合、i から出発する次の車両の開始時刻は、前の出発から 2 時間未満であってはなりません。オリジンは特定の製品（オリジンノードからのみ利用可能）に対応していますが、車両を特定のオリジンノードに限定しないでください。バックホールなどを利用するためにノード間をジャンプできる必要があります。つまり、実施したいこの制約は、車両自体ではなく起点ノードを制限するものではありません。
「移動時間を最大化する」という目的関数は奇妙に思えるかもしれませんが、目的関数は実際には時代遅れです。制約が満たされている場合、ソリューションは適切です。移動時間を最大化することは、単に変数 x を 1 に「強制」しようとすることです。
問題は次のとおりです。どうすればこれを行うことができますか? この定式化では、すべての x[i,j,k] 変数が答えから消えます (この制約がなければ、バイナリ変数 x の一部は 1 になり、他の変数は 0 になります。解は maxVisits 要件を満たします。制約があると、すべての x 変数は次のようになります。 0 とすべての starttimes も 0 になります. MINTO (ソルバー) は、問題が実行不可能であるとは述べていません. また、プログラムがすべての出発の比較であることを認識できるように、どのように車両を分離するのですか?時間次元を含めると、より多くの変数が得られます。
編集: 非線形ソルバーを使用して新しいモデルを試した後、奇妙な結果がいくつか見られました。具体的には、車両が 1 日に稼働できる時間の上限として 1440 (分) という制限を使用しています。このモデルを使用すると、解はすべての変数で 0 になりますが、i、j、k のすべての組み合わせの開始時間は 720 (1440 の半分) です。この解決策の原因について何か手がかりはありますか? この制約は、x が 1 でなければならない 0 より大きい starttime の間のリンクをどのように削除しましたか?
subject to StartTimeSelf{i in V, j in V, k in K, g in K, h in V}:
starttime[i,j,k]*x[i,j,k] + TimeInterval[i]*x[i,j,k] + y[i,k] <= starttime[i,h,g]*x[i,j,k];