带有时间 windows 的车辆路径 minizinc 示例
Vehicle routing with time windows minizinc example
我想用 minizinc 建模语言表达随时间 windows (http://oai.cwi.nl/oai/asset/2036/2036A.pdf) 的车辆路径问题,以便使用约束规划来解决它。
由于我不熟悉该建模语言和整体约束编程,所以我想知道是否有人已经用这种语言表达了这个问题。我找到了“vrp(没有时间windows)https://github.com/MiniZinc/minizinc-benchmarks/blob/master/vrp/vrp.mzn
的以下示例基准
如何修改模型以包含交货时间 windows?
我修改了该模型以包含时间 windows。我删除了与容量相关的逻辑,因为我不需要它。
基本上你需要添加这些约束:
% 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 等。 "Vehicle routing with time windows: optimization and approximation." 车辆路径:方法与研究 16 (1988): 65-84.
我想用 minizinc 建模语言表达随时间 windows (http://oai.cwi.nl/oai/asset/2036/2036A.pdf) 的车辆路径问题,以便使用约束规划来解决它。
由于我不熟悉该建模语言和整体约束编程,所以我想知道是否有人已经用这种语言表达了这个问题。我找到了“vrp(没有时间windows)https://github.com/MiniZinc/minizinc-benchmarks/blob/master/vrp/vrp.mzn
的以下示例基准如何修改模型以包含交货时间 windows?
我修改了该模型以包含时间 windows。我删除了与容量相关的逻辑,因为我不需要它。
基本上你需要添加这些约束:
% 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 等。 "Vehicle routing with time windows: optimization and approximation." 车辆路径:方法与研究 16 (1988): 65-84.