车辆路径中的时间最小化 (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”的距离。有什么建议我应该如何将其添加到当前的 objective 函数中？到目前为止我所做的是将我的 objective 函数更改为这个

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;

车辆路径中的时间最小化 (VRP)

Time Minimization in Vehicle Routing (VRP)

cplex

ampl