【MDVRP】Python+Gurobi求解运输问题建模实践四

今天的主题是分享Python调用运筹优化求解器（Gurobi）求解VRP扩展问题之MDVRP问题的教程。

1. 模型

1.1 MDVRP问题介绍

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

1.2 数学模型

2. 数据结构

（1）demand文件结构

（2）depot文件结构

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[row['id']] = float(row['demand'])XY[row['id']] = (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[row['id']] = (float(row['x_coord']), float(row['y_coord']))N = I + Jfor i in N:x1, y1 = XY[i][0], XY[i][1]for j in N:x2, y2 = XY[j][0], XY[j][1]C[i, j] = 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 = Nonefor j in J:for i in I:if X[j, i,k].x > 0:cur_node = iroute = [j,i]I.remove(i)breakif cur_node is None:continuewhile cur_node not in J:for i in I+J:if X[cur_node, i, k].x > 0:cur_node = iroute.append(i)if i not in J:I.remove(i)breakroute_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[n][0])path_y.append(XY[n][1])plt.plot(path_x, path_y, ms=5)demand_point_x = [XY[n][0] for n in I]demand_point_y = [XY[n][1] for n in I]depot_point_x = [XY[n][0] for n in J]depot_point_y = [XY[n][1] 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 = [str(i) for i in route]dist = sum(C[route[i], route[i + 1]] 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 += 1wb.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[i,j,k]')U = model.addVars(K, N, vtype=GRB.CONTINUOUS, name='U[k,i]')# 目标函数obj = quicksum(X[i,j,k]*C[i,j] for i in N for j in N for k in K)model.setObjective(obj,GRB.MINIMIZE)# 需求覆盖约束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' )# 车辆容量约束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')# 车辆起点约束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' )# 中间节点流平衡约束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' )# 车辆终点约束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' ) # 开放式# 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')  # 不开放式# 破除子环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)model.addConstrs(Q[i] <= U[k, i] for k in K for i in I)model.addConstrs(U[k, i] <= V_CAP for k in K for i in I)# 避免车辆直接在车场间移动model.addConstrs( X[i,j,k] == 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 = 80solve_model(N, I, J, K, Q, V_CAP, C,XY)

4. 求解结果

4.1 开放式车场

4.2 非开放式车场

参考

1. 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