2

制約プログラミングを使用して解決するために、タイム ウィンドウ ( http://oai.cwi.nl/oai/asset/2036/2036A.pdf ) を使用した配車問題を minizinc モデリング言語で表現したいと思います。

私はそのモデリング言語と制約プログラミング全体に慣れていないので、誰かがこの問題をこの言語にすでに表現しているかどうか知りたいです。「vrp (タイム ウィンドウなし)」の次のサンプル ベンチマークを見つけましたhttps://github.com/MiniZinc/minizinc-benchmarks/blob/master/vrp/vrp.mzn

配送の時間枠を含めるようにモデルをどのように変更できますか?

4

1 に答える 1

1

そのモデルを修正して、タイム ウィンドウを含めました。私の場合は必要ないため、容量関連のロジックを削除しました。

基本的に、次の制約を追加する必要があります。

    % Departure time constraints
constraint
    forall(i in 1..N, j in 1..N)(
        DepartureTimes[i] + TravelTimes[i, j] - DepartureTimes[j] <= (1 - x[i, j]) * 1000000
    );

    % Time windows constraints
constraint
    forall(i in 1..N)(
        TimeWindows[i, 1] <= DepartureTimes[i]
    );

constraint
    forall(i in 1..N)(
        DepartureTimes[i] <= TimeWindows[i, 2]
    );

完全なコードは次のとおりです: https://github.com/jlhonora/vrp-minizinc

そして参考文献: Desrochers, Martin, et al. 「タイム ウィンドウを使用した車両ルーティング: 最適化と近似」。車両ルート: 方法と研究16 (1988): 65-84。

于 2016-04-08T14:56:18.837 に答える