时间戳

首页 > 解决方案 > 使用 Gurobi for python 的 VRP 模型中的可选节点出现问题

python - 使用 Gurobi for python 的 VRP 模型中的可选节点出现问题

问题描述

我目前正在研究车辆是电动的 VRP 问题。这意味着我有范围限制和充电站作为可选访问的节点。

在我的模型中，我有以下内容：

O = [0] # depot
N = [1,2,3,4,5,6,7] # deliveries
V = [0,1,2,3,4,5,6,7] # all nodes which must be visited
F = [8,9] # charging stations.
G = [0,1,2,3,4,5,6,7,8,9] # all the nodes

此外，我有一个距离矩阵，其中包含所有节点之间的距离。我在每个交货点也有重量要求。我当前的模型如下所示：

m = Model('E-VRP')
x = m.addVars(G, G, vtype=GRB.BINARY)
lw = m.addVars(G, vtype=GRB.CONTINUOUS) # for calculating load weight
d = m.addVars(G, vtype=GRB.CONTINUOUS) # for calculating distance driven

m.setObjective(quicksum(distance[i,j]*x[i,j] for i in G for j in G if i!=j), GRB.MINIMIZE)

# Restrictions

m.addConstrs(quicksum(x[i,j] for j in V if j!=i)== 1 for i in N)  #1
m.addConstrs(quicksum(x[i,j] for i in V if i!=j)== 1 for j in N)  #2

m.addConstrs ((x[i,j]==1) >> (lw[i] + Dw[i] == lw[j])  #3
              for i in G for j in G if i!=0 if j!=0)
m.addConstrs (lw[i] >= Dw[i] for i in G);  #4 (Dw being demand in weight at delivery)
m.addConstrs (lw[i] <= Qw for i in G);     #5 (Qw being weight capacity of vehicle)

m.addConstrs ((x[i,j]==1) >> (d[i] + distance[i,j] == d[j])
              for i in G for j in G if j>0);   #6
m.addConstrs (d[i] <= Qr for i in G);          #7 (Qr being range restriction of vehicle)

前三个限制的组合使该模型成为工作容量的车辆路线问题。它在 depot (0) 开始和结束，如果 Qw 小于 lw，则模型将进行多条路线。

当我施加范围限制时，问题就来了。我有两个问题：

首先，该模型不会使充电站成为路线的一部分。我知道限制 #1 和 #2 规定必须有从列表 V 到 N 的连接，反之亦然，这意味着对于节点 j，列表 V 中必须有一个 i（不包括充电站）。但是，每当我尝试“放开”前两个限制时，该模型都会建议不会在站点开始或结束的子游览。有人对我如何解决这个问题有任何建议吗？

其次，我的变量 d 用于跟踪行驶距离，它只会在返回站点之前将到最后一个节点的距离相加。我意识到我的代码 j>0 表明该站点不能成为我的旅行变量中的目的地，但是，这是我让它适用于所有其他节点的唯一方法。

对这些问题的任何帮助将不胜感激。

兄弟，

维克多

标签： pythongurobirestrictionvehicle-routing

解决方案

推荐阅读