在接触Gurobi之前，一直使用Java语言调用cplex求解数学模型，这段时间在师兄的指点下，学习了使用python调用Gurobi的一些基础操作，感叹实在是太简易了。 在此分享一个求解Vrptw问题的小例子。

对于Vrptw问题来说，数学模型主要由以下部分组成。首先我们定义一些相关参数，一个图可以表示为 G ( V , A ) G(V,A) G(V,A)，其中 V = { 0 , 1 , . . . , n , n + 1 } V= \{ 0,1,...,n,n+1 \} V={0,1,...,n,n+1}为图中所有点的集合， A A A为图中所有弧的集合，有 ( i , j ) ∈ (i,j)\in (i,j)∈A， ∀ i , j ∈ V , i ≠ j \forall i,j\in V, i\ne j ∀i,j∈V,i​=j。弧 ( i , j ) (i,j) (i,j)的单位运输费用为 c i j c_{ij} cij​，运输时间为 t i j t_{ij} tij​，每个客户点的需求为 q i j q_{ij} qij​，可服务的时间窗为 [ e i , l i ] [e_i,l_i] [ei​,li​]，服务时长为 s e r v i serv_i servi​。令车辆的集合为 K K K，每辆车的最大载重为 Q k , ∀ k ∈ K Q_k,\forall k\in K Qk​,∀k∈K。决策变量为 x i j k x_{ij}^k xijk​，代表第 k k k辆车是否服务了弧 ( i , j ) (i,j) (i,j)； s i s_i si​为客户点 i i i开始被服务的时间。

接下来构建数学模型。 目标函数为最小化运输成本： m i n ∑ k ∈ K ∑ ( i , j ) ∈ A c i j x i j (1) min \sum_{k\in K} \sum_{(i,j)\in A}c_{ij}x_{ij} \tag{1} mink∈K∑​(i,j)∈A∑​cij​xij​(1) 约束一让车辆驶出仓库(depot)： ∑ ( 0 , j ) ∈ A x 0 j k = 1 ,   ∀ k ∈ K (2) \sum_{(0,j)\in A}x_{0j}^k =1,\ \forall k\in K \tag{2} (0,j)∈A∑​x0jk​=1, ∀k∈K(2) 约束二为流平衡(除去depot之外的点)： ∑ ( i , j ) ∈ A x i j k − ∑ ( j , i ) ∈ A x j i k = 0 ,   ∀ k ∈ K , i ∈ V ∖ { s , t } (3) \sum_{(i,j)\in A}x_{ij}^k - \sum_{(j,i)\in A}x_{ji}^k = 0,\ \forall k\in K ,i \in V\setminus \{s,t\} \tag{3} (i,j)∈A∑​xijk​−(j,i)∈A∑​xjik​=0, ∀k∈K,i∈V∖{s,t}(3) 约束三让车辆驶回depot： ∑ ( i , n + 1 ) ∈ A x i , n + 1 k = 1 ,   ∀ k ∈ K (4) \sum_{(i,n+1)\in A}x_{i,n+1}^k =1,\ \forall k\in K \tag{4} (i,n+1)∈A∑​xi,n+1k​=1, ∀k∈K(4) 约束四保证每个客户点都被服务： ∑ k ∈ K ∑ ( i , j ) ∈ A x i , j k = 1 ,   ∀ i ∈ V ∖ { s , t } (5) \sum_{k \in K}\sum_{(i,j)\in A}x_{i,j}^k =1,\ \forall i \in V\setminus \{s,t\} \tag{5} k∈K∑​(i,j)∈A∑​xi,jk​=1, ∀i∈V∖{s,t}(5) 约束五保证被服务的相邻节点开始服务时间的大小关系(去回路)： s i + t i j + s e r v i − M ( 1 − x i j ) ≤ s j ,   ∀ ( i , j ) ∈ A (6) s_i+t_{ij}+serv_i-M(1-x_{ij})\le s_j,\ \forall (i,j) \in A \tag{6} si​+tij​+servi​−M(1−xij​)≤sj​, ∀(i,j)∈A(6) 约束六保证不违反客户的时间窗： e i ≤ s i ≤ l i ,   ∀ i ∈ V ∖ { s , t } (7) e_i \le s_i \le l_i ,\ \forall i \in V\setminus \{s,t\} \tag{7} ei​≤si​≤li​, ∀i∈V∖{s,t}(7) 约束七保证不违反车辆的载重约束： ∑ ( i , j ) ∈ A x i j k q i ≤ Q k ,   ∀ k ∈ K (8) \sum_{(i,j)\in A}x_{ij}^kq_i \le Q_k ,\ \forall k \in K \tag{8} (i,j)∈A∑​xijk​qi​≤Qk​, ∀k∈K(8) 最后是决策变量的取值约束： x i j k ∈ { 0 , 1 }   ∀ ( i , j ) ∈ A , k ∈ K s i ≥ 0 ,   ∀ i ∈ V ∖ { s , t } (9) x_{ij}^k\in \{0,1\} \ \forall (i,j) \in A,k \in K \\ s_i \ge 0,\ \forall i \in V\setminus \{s,t\} \tag{9} xijk​∈{0,1} ∀(i,j)∈A,k∈Ksi​≥0, ∀i∈V∖{s,t}(9) 那么(1)~(9)式就组成了Vrptw问题的数学模型。

约束一（vehicle_depart）：

约束二（flow_conservation）：

约束三（vehicle_enter）：

约束四（customer_visit）：

约束五（time_windows）：