【MDVRP】Python+Gurobi求解运输标题建模实践四
本日的主题是分享Python调用运筹优化求解器（Gurobi）求解VRP扩展标题之MDVRP标题的教程。1. 模型
1.1 MDVRP标题先容
MDVRP 作为 VRP 研究的一个扩展标题，重要是针对有多个货物中转点运输的场景。相比于单车场标题，多车场标题需要解决客户需求分配、车辆运输路径选择、车辆运输模式、车场货物容量等一系列标题。
https://i-blog.csdnimg.cn/direct/1ceb28f402104095af6efda27765356e.png#pic_center
1.2 数学模型
https://i-blog.csdnimg.cn/direct/42f0db5f768b4948b2f7329915109942.png#pic_center
2. 数据布局
（1）demand文件布局
https://i-blog.csdnimg.cn/direct/df8c0ac770f64258abe71169fdfa5f0b.png#pic_center
（2）depot文件布局
https://i-blog.csdnimg.cn/direct/058e25e0f7884b01bedbe91393bf41c3.png#pic_center
3. Gurobi源码
import math
import csv
import copy
import xlsxwriter
import matplotlib.pyplot as plt
from gurobipy import quicksum,Model,GRB
# 读取文件
def read_csv_file(demand_file,depot_file):
"""
:param demand_file: 需求文件
:param depot_file: 车场文件
:return:
"""
I = []
J = []
Q = {}
C = {}
XY = {}
with open(demand_file, 'r') as f:
demand_reader = csv.DictReader(f)
for row in demand_reader:
I.append(row['id'])
Q] = float(row['demand'])
XY] = (float(row['x_coord']), float(row['y_coord']))
with open(depot_file, 'r') as f:
depot_reader = csv.DictReader(f)
for row in depot_reader:
J.append(row['id'])
XY] = (float(row['x_coord']), float(row['y_coord']))
N = I + J
for i in N:
x1, y1 = XY, XY
for j in N:
x2, y2 = XY, XY
C = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
return N,I,J,C,Q,XY
# 提取路径
def extract_routes(I,J,X,K):
I = copy.deepcopy(I)
route_list = []
for k in K:
# 提取 派送阶段路径
cur_node = None
for j in J:
for i in I:
if X.x > 0:
cur_node = i
route =
I.remove(i)
break
if cur_node is None:
continue
while cur_node not in J:
for i in I+J:
if X.x > 0:
cur_node = i
route.append(i)
if i not in J:
I.remove(i)
break
route_list.append(route)
return route_list
def draw_routes(route_list,XY,I,J):
for route in route_list:
path_x = []
path_y = []
for n in route:
path_x.append(XY)
path_y.append(XY)
plt.plot(path_x, path_y, ms=5)
demand_point_x = for n in I]
demand_point_y = for n in I]
depot_point_x = for n in J]
depot_point_y = for n in J]
plt.scatter( demand_point_x, demand_point_y, marker='s', c='b', s=30,zorder=0)
plt.scatter( depot_point_x, depot_point_y, marker='*', c='r', s=100,zorder=1)
plt.show()
# 保存结果
def save_file(route_list,total_cost,C):
wb = xlsxwriter.Workbook('路径方案.xlsx')
ws = wb.add_worksheet()
ws.write(0,0,'总费用')
ws.write(0,1,total_cost)
ws.write(1,0,'车辆')
ws.write(1,1,'路径')
ws.write(1,2,'距离')
for row,route in enumerate(route_list):
route_str =
dist = sum(C, route] for i in range(len(route) - 1))
ws.write(row + 2, 0, f'{row + 1}')
ws.write(row+2,1,'-'.join(route_str))
ws.write(row + 2, 2, dist)
row += 1
wb.close()
# 建模和求解
def solve_model(N,I,J,K,Q,V_CAP,C,XY):
"""
:param N: 所有节点
:param I: 客户节点
:param J: 车场节点
:param K: 车辆节点
:param Q: 客户需求
:param V_CAP: 车辆容量
:param C: 成本矩阵
:param XY: 节点坐标
:return: nan
"""
model = Model('MDVRP')
# 添加变量
X = model.addVars(N,N,K,vtype=GRB.BINARY,name='X')
U = model.addVars(K, N, vtype=GRB.CONTINUOUS, name='U')
# 目标函数
obj = quicksum(X*C for i in N for j in N for k in K)
model.setObjective(obj,GRB.MINIMIZE)
# 需求覆盖约束
model.addConstrs( (quicksum(X for j in N for k in K if i != j) == 1 for i in I),name='eq1' )
# 车辆容量约束
model.addConstrs( (quicksum(X*Q for i in I for j in N if i != j) <= V_CAP for k in K),name= 'eq2')
# 车辆起点约束
model.addConstrs( (quicksum(X for j in J for i in I if i != j) == 1 for k in K),name='eq3' )
# 中间节点流平衡约束
model.addConstrs( (quicksum(X for j in N if i != j) == quicksum(X for j in N if i != j) for i in I for k in K),name='eq4' )
# 车辆终点约束
model.addConstrs( (quicksum(X for i in I for j in J if i != j) == 1 for k in K), name='eq5' ) # 开放式
# model.addConstrs( (quicksum(X for i in I) == quicksum(X for i in I) for k in K for j in J), name='eq5')# 不开放式
# 破除子环
model.addConstrs(U - U + V_CAP * X <= V_CAP - Q for i in I for j in I for k in K)
model.addConstrs(Q <= U for k in K for i in I)
model.addConstrs(U <= V_CAP for k in K for i in I)
# 避免车辆直接在车场间移动
model.addConstrs( X == 0 for i in J for j in J for k in K )
# 求解
model.Params.TimeLimit = 300# 设置求解时间上限
model.optimize()
if model.status == GRB.Status.OPTIMAL or model.status == GRB.Status.TIME_LIMIT:
route_list = extract_routes(I,J,X,K)
draw_routes(route_list, XY, I,J)
save_file(route_list, model.objVal, C)
else:
model.computeIIS()
model.write('model.ilp')
for c in model.getConstrs():
if c.IISConstr:
print(f'{c.constrName}')
print("no solution")
if __name__ == '__main__':
demand_file = r'./input/demand2.csv'
depot_file = r'./input/depot.csv'
N, I, J, C, Q, XY = read_csv_file(demand_file=demand_file, depot_file=depot_file)
K = list(range(0,10))
V_CAP = 80
solve_model(N, I, J, K, Q, V_CAP, C,XY)
4. 求解结果
4.1 开放式车场
https://i-blog.csdnimg.cn/direct/3db01d5e9bbf4dba8f1951c19a077811.png#pic_center
4.2 非开放式车场
https://i-blog.csdnimg.cn/direct/212fd01b21174f9297f10e114a6f4820.png#pic_center
参考
[*]Ramos, T. R. P., Gomes, M. I., & Póvoa, A. P. B. (2019). Multi-depot vehicle routing problem: a comparative study of alternative formulations. International Journal of Logistics Research and Applications, 23(2), 103–120. https://doi.org/10.1080/13675567.2019.1630374
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]