车辆配送 (VRP) 中的时间最小化

Question

我正在解决车辆配送问题，简单的优化函数是

最小化： 所有车辆游览距离的总和

在 AMPL 中似乎是这样的

minimize objective_function:
sum {i in city, j in city,k in vehicle} x[i,j,k]*D[i,j];

其中 x 是单个车辆的二进制矩阵标记游览，D 是距离矩阵

我想做的是尽量减少车队完成操作所需的时间。其中时间计算为距离与速度的关系"D[i,j]/S"。 任何建议我应该如何将其添加到当前的目标函数中？ 到目前为止，我所做的是将我的目标函数更改为此

minimize objective_function:
sum {i in city, j in city,k in vehicle} x[i,j,k]*(D[i,j]/S[k]);

这给了我每辆车所花费的所有时间的总和。但是由于所有车辆的时间都是并行开始的，因此我只需要从每辆车的时间中选择最大值。这将是完成整个特派团的时候。必须用 AMPL 对其进行编码才能使用 CPLEX 求解。

Answer 1

var max_time;
subject to definemaxtime {i in city, j in city, k in vehicle}: 
max_time >= x[i,j,k]*(D[i,j]/S[k]);
minimize objective_function: max_time;

编辑：哎呀，这不太正确，这为单次旅行提供了最长的时间。应该是：

var max_time;
subject to definemaxtime {k in vehicle}: 
max_time >= sum{i in city, j in city} x[i,j,k]*(D[i,j]/S[k]);
minimize objective_function: max_time;