i,n+1k​=1, ∀k∈K(4)
约束四保证每个客户点都被服务：
$$\stackrel{\sum }{k\in K}\stackrel{\sum }{(i,j)\in A}{x}^{i,j}=1,\forall i\in V\setminus \{s,t\}\text{\hspace{1em}(5)}$$
约束五保证被服务的相邻节点开始服务时间的大小关系(去回路)：
$$s^i+t^{ij}+ser{v}^i-M(1-x^{ij})\le s^j,\forall (i,j)\in A\text{\hspace{1em}(6)}$$
约束六保证不违反客户的时间窗：
$$e^i\le s^i\le l^i,\forall i\in V\setminus \{s,t\}\text{\hspace{1em}(7)}$$
约束七保证不违反车辆的载重约束：
$$\stackrel{\sum }{(i,j)\in A}{x}^{ij}{q}^i\le Q^k,\forall k\in K\text{\hspace{1em}(8)}$$
最后是决策变量的取值约束：
$$x^{ij}\in \{0,1\}\forall (i,j)\in A,k\in K{s}^i\ge 0,\forall i\in V\setminus \{s,t\}\text{\hspace{1em}(9)}$$
那么(1)~(9)式就组成了Vrptw问题的数学模型。

python调用Gurobi求解Vrptw

首先我们定义一下需要用到的参数：

class Data:
    customerNum = 0
    nodeNum     = 0
    vehicleNum  = 0
    capacity    = 0
    cor_X       = []
    cor_Y       = []
    demand      = []
    serviceTime = []
    readyTime   = []
    dueTime     = []
    disMatrix   = [[]]   

• 1
• 2
• 3
• 4
• 5
• 6
•  
• 7

根据式(2)~(8)定义决策变量，并加入模型当中：

约束一（vehicle_depart）：

for k in range(data.vehicleNum):
	//同样先定义一个线性表达式
    lhs = LinExpr(0) 
    for j in range(data.nodeNum):
        if(j != 0):
       		//约束系数与决策变量相乘	
            lhs.addTerms(1, x[0,j,k])  
    //将约束加入模型
    model.addConstr(lhs == 1, name= 'vehicle_depart_' + str(k)) 

k in range(data.vehicleNum):
    for h in range(1, data.nodeNum - 1):
        expr1 = LinExpr(0)
        expr2 = LinExpr(0)
        for i in range(data.nodeNum):
            if (h != i):
                expr1.addTerms(1, x[i,h,k])

        for j in range(data.nodeNum):
            if (h != j):
                expr2.addTerms(1, x[h,j,k])

        model.addConstr(expr1 == expr2, name= 'flow_conservation_' + str(i))
        expr1.clear()
        expr2.clear()

 

作者：夏旸，清华大学，工业工程系/深圳国际研究生院 (硕士在读) 刘兴禄，清华大学，清华伯克利深圳学院（博士在读）