Python调用Cplex求解VRPTW问题

 文章参考了ZhaoDongqiang(C++调用cplex求解VRPTW模型),补充了在Jyputer编辑器中用Python调用Cplex求解VRPTW问题,修正了模型中的小错误,具体如下:

目录

1 VRPTW数学模型

2 Python调用Cplex求解

2.1 调用所需的库 

2.2  初始化参数

2.3 调用docplex建模

2.4 求解结果

 3 结语


1 VRPTW数学模型

Python调用Cplex求解VRPTW问题

 

2 Python调用Cplex求解

2.1 调用所需的库 

import pandas as pd
import numpy as np
from docplex.mp.model import Model
import matplotlib.pyplot as plt

2.2  初始化参数

 data.txt 内容如下:

40	50	0	0	1236	0
45	68	10	912	967	90
45	70	30	825	870	90
42	66	10	65	146	90
42	68	10	727	782	90
42	65	10	15	67	90
40	69	20	621	702	90
40	66	20	170	225	90
38	68	20	255	324	90
38	70	10	534	605	90
35	66	10	357	410	90
35	69	10	448	505	90
25	85	20	652	721	90
22	75	30	30	92	90
22	85	10	567	620	90
20	80	40	384	429	90
20	85	40	475	528	90
18	75	20	99	148	90
15	75	20	179	254	90
15	80	10	278	345	90
30	50	10	10	73	90
30	52	20	914	965	90
28	52	20	812	883	90
28	55	10	732	777	90
25	50	10	65	144	90
25	52	40	169	224	90
40	50	0	0	1236	0
df = pd.read_csv('data.txt',sep='\t',header=None)
M=10000
c_num = 25 #顾客数
v_num = 3  #卡车数
q = 500    #卡车的容量
CM = [i for i in range (1,c_num+1)]  #顾客列表
V = [i for i in range(1,v_num+1)]   #卡车列表
N = [0]+CM+[26]   #结点列表

#读取txt文件
x_loc = list(df.iloc[:,0])
y_loc = list(df.iloc[:,1])
d = list(df.iloc[:,2])
lbtw = list(df.iloc[:,3])
ubtw = list(df.iloc[:,4])
t_service = list(df.iloc[:,5])
t_service[0]

#各个节点之间的弧
A = [(i,j) for i in N for j in N if j!=i]

#各节点之间的距离
C={(i,j):np.floor(np.hypot((x_loc[i]-x_loc[j]),(y_loc[i]-y_loc[j]))*10)/10 for i,j in A}

#将两点距离作为时间
t={(i,j):0 for i,j in A}
for i,j in C:
    t[i,j]=C[i,j]+t_service[i]

#画出坐标散点图
import matplotlib.pyplot as plt
plt.scatter(x_loc[1:25],y_loc[1:25],c='b')
plt.plot(x_loc[0],y_loc[0],c='r',marker='s')
for i in CM:
    plt.annotate('%d'%i,(x_loc[i]+0.5,y_loc[i]))    
plt.annotate("%d"%0,(x_loc[0]+0.5,y_loc[0]))


#初始化A_car 和 S_time,作为决策变量s和x字典的键值 
A_car=[(k,i,j) for k in V for i,j in A ]
S_time=[(k,i) for k in V for i in N]

Python调用Cplex求解VRPTW问题

 图1 各点的坐标散点图

2.3 调用docplex建模

mdl=Model("VRPTW")

#决策变量
x=mdl.binary_var_dict(A_car,name='x')
s=mdl.continuous_var_dict(S_time,name='s')

#目标函数
mdl.minimize(mdl.sum(C[i,j]*x[k,i,j] for k,i,j in A_car))

#约束1-8:
#约束1
mdl.add_constraints(mdl.sum(x[k,i,j] for k in V for j in N if j!=i\
                           )==1 for i in CM)
#约束2
mdl.add_constraints(mdl.sum(d[i]*mdl.sum(x[k,i,j] for j in N if j!=i)\
                            for i in CM)<=q for k in V)
#约束3
mdl.add_constraints(mdl.sum(x[k,0,j] for j in N if j!=0)==1 for k in V)

#约束4
mdl.add_constraints(mdl.sum(x[k,i,h] for i in N if i!=h)==mdl.sum(x[k,h,j] for j in N if j!=h) for h in CM for k in V)

#约束5
mdl.add_constraints(mdl.sum(x[k,i,c_num+1] for i in N if i!=(c_num+1))==1 for k in V)
#约束6
mdl.add_constraint(mdl.sum(x[k,0,j] for k in V for j in N if j!=0)<=v_num)
#约束7

mdl.add_constraints(s[k,i]+t[i,j]-M*(1-x[k,i,j])<=s[k,j] for k in V for i,j in A)

#约束8
mdl.add_constraints(s[k,i]<=ubtw[i] for k in V for i in N)
mdl.add_constraints(s[k,i]>=lbtw[i] for k in V for i in N);

#求解
solution=mdl.solve()
print(solution)

solution for: VRPTW
objective: 191.3
x_1_0_20=1
x_1_20_24=1
x_1_21_26=1
x_1_22_21=1
x_1_23_22=1
x_1_24_25=1
x_1_25_23=1
x_2_0_13=1
x_2_12_26=1
x_2_13_17=1
x_2_14_12=1
x_2_15_16=1
x_2_16_14=1
x_2_17_18=1
x_2_18_19=1
x_2_19_15=1
x_3_0_5=1
x_3_1_26=1
x_3_2_1=1
x_3_3_7=1
x_3_4_2=1
x_3_5_3=1
x_3_6_4=1
x_3_7_8=1
x_3_8_10=1
x_3_9_6=1
x_3_10_11=1
x_3_11_9=1
s_1_1=967.000
s_1_2=825.000
s_1_3=65.000
s_1_4=727.000
s_1_5=15.000
s_1_6=621.000
s_1_7=170.000
s_1_8=255.000
s_1_9=534.000
s_1_10=357.000
s_1_11=448.000
s_1_12=652.000
s_1_13=30.000
s_1_14=567.000
s_1_15=384.000
s_1_16=475.000
s_1_17=99.000
s_1_18=179.000
s_1_19=278.000
s_1_20=10.000
s_1_21=917.000
s_1_22=825.000
s_1_23=732.000
s_1_24=132.000
s_1_25=224.000
s_1_26=1075.600
s_2_1=912.000
s_2_2=825.000
s_2_3=65.000
s_2_4=727.000
s_2_5=15.000
s_2_6=621.000
s_2_7=170.000
s_2_8=255.000
s_2_9=534.000
s_2_10=357.000
s_2_11=448.000
s_2_12=687.800
s_2_13=30.800
s_2_14=594.800
s_2_15=407.800
s_2_16=502.800
s_2_17=124.800
s_2_18=217.800
s_2_19=312.800
s_2_20=10.000
s_2_21=914.000
s_2_22=812.000
s_2_23=732.000
s_2_24=65.000
s_2_25=169.000
s_2_26=815.800
s_3_1=940.600
s_3_2=848.600
s_3_3=106.100
s_3_4=755.000
s_3_5=15.100
s_3_6=662.800
s_3_7=198.100
s_3_8=290.900
s_3_9=570.600
s_3_10=384.500
s_3_11=477.500
s_3_12=652.000
s_3_13=30.000
s_3_14=567.000
s_3_15=384.000
s_3_16=475.000
s_3_17=99.000
s_3_18=179.000
s_3_19=278.000
s_3_20=10.000
s_3_21=914.000
s_3_22=812.000
s_3_23=732.000
s_3_24=65.000
s_3_25=169.000
s_3_26=1049.200

2.4 求解结果

#选出那些决策变量为1时所经过的弧
active_arcs=[ a for a in A_car if x[a].solution_value > 0.9]

#画出VRPTW的结果
import matplotlib.pyplot as plt
plt.scatter(x_loc[1:25],y_loc[1:25])
plt.plot(x_loc[0],y_loc[0],c='r',marker='s')
for i in CM:
    plt.annotate('%d'%i,(x_loc[i]+0.5,y_loc[i]))
    
    
plt.annotate("%d"%0,(x_loc[0]+0.5,y_loc[0]))
for k,i,j in active_arcs:
    if k==1:
        plt.plot((x_loc[i],x_loc[j]),(y_loc[i],y_loc[j]),c='r')
    if k==2:
        plt.plot((x_loc[i],x_loc[j]),(y_loc[i],y_loc[j]),c='g')
    if k==3:
        plt.plot((x_loc[i],x_loc[j]),(y_loc[i],y_loc[j]),c='b')
        

Python调用Cplex求解VRPTW问题

 

 3 结语

目前Python调用Cplex的相关文章较少,本文在ZhaoDongqiang(C++调用cplex求解VRPTW模型)的基础之上,利用Python调用Cplex解决了VRPTW问题。

 

上一篇:python 小记


下一篇:07-Nginx搭建高可用集群