IT评测·应用市场-qidao123.com技术社区

标题: 【MDVRP】Python+Gurobi求解运输标题建模实践四 [打印本页]
作者: 科技颠覆者    时间: 2024-9-9 23:31
标题: 【MDVRP】Python+Gurobi求解运输标题建模实践四
本日的主题是分享Python调用运筹优化求解器（Gurobi）求解VRP扩展标题之MDVRP标题的教程。
  
  
1. 模型

1.1 MDVRP标题先容

MDVRP 作为 VRP 研究的一个扩展标题，重要是针对有多个货物中转点运输的场景。相比于单车场标题，多车场标题需要解决客户需求分配、车辆运输路径选择、车辆运输模式、车场货物容量等一系列标题。

1.2 数学模型


2. 数据布局

（1）demand文件布局

（2）depot文件布局

3. Gurobi源码

  1. import math
  2. import csv
  3. import copy
  4. import xlsxwriter
  5. import matplotlib.pyplot as plt
  6. from gurobipy import quicksum,Model,GRB
  8. # 读取文件
  9. def read_csv_file(demand_file,depot_file):
  10.     """
  11.     :param demand_file: 需求文件
  12.     :param depot_file: 车场文件
  13.     :return:
  14.     """
  15.     I = []
  16.     J = []
  17.     Q = {}
  18.     C = {}
  19.     XY = {}
  20.     with open(demand_file, 'r') as f:
  21.         demand_reader = csv.DictReader(f)
  22.         for row in demand_reader:
  23.             I.append(row['id'])
  24.             Q[row['id']] = float(row['demand'])
  25.             XY[row['id']] = (float(row['x_coord']), float(row['y_coord']))
  26.     with open(depot_file, 'r') as f:
  27.         depot_reader = csv.DictReader(f)
  28.         for row in depot_reader:
  29.             J.append(row['id'])
  30.             XY[row['id']] = (float(row['x_coord']), float(row['y_coord']))
  31.     N = I + J
  32.     for i in N:
  33.         x1, y1 = XY[i][0], XY[i][1]
  34.         for j in N:
  35.             x2, y2 = XY[j][0], XY[j][1]
  36.             C[i, j] = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
  37.     return N,I,J,C,Q,XY
  38. # 提取路径
  39. def extract_routes(I,J,X,K):
  40.     I = copy.deepcopy(I)
  41.     route_list = []
  42.     for k in K:
  43.         # 提取 派送阶段路径
  44.         cur_node = None
  45.         for j in J:
  46.             for i in I:
  47.                 if X[j, i,k].x > 0:
  48.                     cur_node = i
  49.                     route = [j,i]
  50.                     I.remove(i)
  51.                     break
  52.         if cur_node is None:
  53.             continue
  54.         while cur_node not in J:
  55.             for i in I+J:
  56.                 if X[cur_node, i, k].x > 0:
  57.                     cur_node = i
  58.                     route.append(i)
  59.                     if i not in J:
  60.                         I.remove(i)
  61.                     break
  62.         route_list.append(route)
  63.     return route_list
  64. def draw_routes(route_list,XY,I,J):
  65.     for route in route_list:
  66.         path_x = []
  67.         path_y = []
  68.         for n in route:
  69.             path_x.append(XY[n][0])
  70.             path_y.append(XY[n][1])
  71.         plt.plot(path_x, path_y, ms=5)
  72.     demand_point_x = [XY[n][0] for n in I]
  73.     demand_point_y = [XY[n][1] for n in I]
  74.     depot_point_x = [XY[n][0] for n in J]
  75.     depot_point_y = [XY[n][1] for n in J]
  76.     plt.scatter( demand_point_x, demand_point_y, marker='s', c='b', s=30,zorder=0)
  77.     plt.scatter( depot_point_x, depot_point_y, marker='*', c='r', s=100,zorder=1)
  78.     plt.show()
  79. # 保存结果
  80. def save_file(route_list,total_cost,C):
  81.     wb = xlsxwriter.Workbook('路径方案.xlsx')
  82.     ws = wb.add_worksheet()
  83.     ws.write(0,0,'总费用')
  84.     ws.write(0,1,total_cost)
  85.     ws.write(1,0,'车辆')
  86.     ws.write(1,1,'路径')
  87.     ws.write(1,2,'距离')
  88.     for row,route in enumerate(route_list):
  89.         route_str = [str(i) for i in route]
  90.         dist = sum(C[route[i], route[i + 1]] for i in range(len(route) - 1))
  91.         ws.write(row + 2, 0, f'{row + 1}')
  92.         ws.write(row+2,1,'-'.join(route_str))
  93.         ws.write(row + 2, 2, dist)
  94.         row += 1
  95.     wb.close()
  96. # 建模和求解
  97. def solve_model(N,I,J,K,Q,V_CAP,C,XY):
  98.     """
  99.     :param N: 所有节点
  100.     :param I: 客户节点
  101.     :param J: 车场节点
  102.     :param K: 车辆节点
  103.     :param Q: 客户需求
  104.     :param V_CAP: 车辆容量
  105.     :param C: 成本矩阵
  106.     :param XY: 节点坐标
  107.     :return: nan
  108.     """
  109.     model = Model('MDVRP')
  110.     # 添加变量
  111.     X = model.addVars(N,N,K,vtype=GRB.BINARY,name='X[i,j,k]')
  112.     U = model.addVars(K, N, vtype=GRB.CONTINUOUS, name='U[k,i]')
  113.     # 目标函数
  114.     obj = quicksum(X[i,j,k]*C[i,j] for i in N for j in N for k in K)
  115.     model.setObjective(obj,GRB.MINIMIZE)
  116.     # 需求覆盖约束
  117.     model.addConstrs( (quicksum(X[i,j,k] for j in N for k in K if i != j) == 1 for i in I),name='eq1' )
  118.     # 车辆容量约束
  119.     model.addConstrs( (quicksum(X[i,j,k]*Q[i] for i in I for j in N if i != j) <= V_CAP for k in K),name= 'eq2')
  120.     # 车辆起点约束
  121.     model.addConstrs( (quicksum(X[j,i,k] for j in J for i in I if i != j) == 1 for k in K),name='eq3' )
  122.     # 中间节点流平衡约束
  123.     model.addConstrs( (quicksum(X[i, j, k] for j in N if i != j) == quicksum(X[j, i, k] for j in N if i != j) for i in I for k in K),name='eq4' )
  124.     # 车辆终点约束
  125.     model.addConstrs( (quicksum(X[i,j,k] for i in I for j in J if i != j) == 1 for k in K), name='eq5' ) # 开放式
  126.     # model.addConstrs( (quicksum(X[j,i,k] for i in I) == quicksum(X[i,j,k] for i in I) for k in K for j in J), name='eq5')  # 不开放式
  127.     # 破除子环
  128.     model.addConstrs(U[k, i] - U[k, j] + V_CAP * X[i, j, k] <= V_CAP - Q[i] for i in I for j in I for k in K)
  129.     model.addConstrs(Q[i] <= U[k, i] for k in K for i in I)
  130.     model.addConstrs(U[k, i] <= V_CAP for k in K for i in I)
  131.     # 避免车辆直接在车场间移动
  132.     model.addConstrs( X[i,j,k] == 0 for i in J for j in J for k in K )
  133.     # 求解
  134.     model.Params.TimeLimit = 300  # 设置求解时间上限
  135.     model.optimize()
  136.     if model.status == GRB.Status.OPTIMAL or model.status == GRB.Status.TIME_LIMIT:
  137.         route_list = extract_routes(I,J,X,K)
  138.         draw_routes(route_list, XY, I,J)
  139.         save_file(route_list, model.objVal, C)
  140.     else:
  141.         model.computeIIS()
  142.         model.write('model.ilp')
  143.         for c in model.getConstrs():
  144.             if c.IISConstr:
  145.                 print(f'{c.constrName}')
  146.         print("no solution")
  147. if __name__ == '__main__':
  148.     demand_file = r'./input/demand2.csv'
  149.     depot_file = r'./input/depot.csv'
  150.     N, I, J, C, Q, XY = read_csv_file(demand_file=demand_file, depot_file=depot_file)
  151.     K = list(range(0,10))
  152.     V_CAP = 80
  153.     solve_model(N, I, J, K, Q, V_CAP, C,XY)
复制代码
4. 求解结果

4.1 开放式车场


4.2 非开放式车场


参考


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4