带时间窗minizinc示例的车辆路线

debugcn 发表于 Dev

卢卡·菲亚斯基（Luca Fiaschi）

我想用minizinc建模语言用时间窗口（http://oai.cwi.nl/oai/asset/2036/2036A.pdf）来表达车辆路径问题，以便使用约束编程来解决该问题。

由于我是该建模语言的新手，并且从整体上限制了编程，所以我想知道是否有人已经用这种语言表达了这个问题。我找到了以下“ vrp（没有时间窗口）的示例示例基准” https://github.com/MiniZinc/minizinc-benchmarks/blob/master/vrp/vrp.mzn

如何修改模型以包括交货时间窗口？

耶洛诺拉

我修改了该模型以包含时间窗口。我删除了与容量相关的逻辑，因为在我的情况下不需要它。

基本上，您需要添加以下约束：

    % 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等。“带有时间窗的车辆路线选择：优化和近似。” 车辆路线：方法和研究16（1988）：65-84。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。