• 日期: 2025-04-23
  • 标签: 常规

以下 Python 代码使用 Gurobi 库解决车辆路径问题 (CVRP)，并提供了一些优化建议以提高内存效率：

from gurobipy import *
import numpy as np

def createDataSet():  # 创建数据集
    rdn1 = np.random.RandomState(1)
    points = []
    i = 0
    while True:
        x = round(rdn1.uniform(0, 100), 1)
        y = round(rdn1.uniform(0, 100), 1)
        if 45 <= x <= 55 and 45 <= y <= 55:
            continue
        points.append((x, y))
        i += 1
        if i == 100:
            break
    rdn3 = np.random.RandomState(2)
    demand = rdn3.randint(2, 11, 30)  # 需求
    return points, demand

vehicleNum = 50
clients, demand = createDataSet()
n_customers = len(clients)
vehicle_fixed_cost = 300  # 固定成本
vehicle_travel_cost = 1.5  # 行驶成本
vehicle_working_time_limit = 480  # 工作时间限制 min
vehicle_capacity_limit = 60  # 车辆容量限制
drive_speed = 0.75  # 车辆行驶速度 km/min
serive_speed = 2.5  # 实际单位货物服务速度  min
depot = [(50, 50)]  # 0
positions = depot + clients


disMatrix = [[0] * (n_customers + 1) for _ in range(n_customers + 1)]
for i in range(n_customers + 1):
    for j in range(i + 1, n_customers + 1):
        d = round(((positions[i][0] - positions[j][0]) ** 2 + (positions[i][1] - positions[j][1]) ** 2) ** 0.5, 4)
        disMatrix[i][j] = disMatrix[j][i] = d  # 保留 4 位


BigM = 100000

model = Model('CVRP')

x = {}
y = {}
s = {}
# 定义决策变量
for i in range(n_customers + 1):
    for k in range(vehicleNum):
        name = 'y_' + str(i) + '_' + str(k)
        if i != 0:
            y[i, k] = model.addVar(lb=0, ub=1,
                                    vtype=GRB.BINARY,
                                    name=name)
        for j in range(n_customers + 1):
            if (i != j):
                name = 'x_' + str(i) + '_' + str(j) + '_' + str(k)
                x[i, j, k] = model.addVar(lb=0, ub=1,
                                        vtype=GRB.BINARY,
                                        name=name)

for i in range(n_customers + 1):
    for k in range(vehicleNum):
        name = 's_' + str(i) + '_' + str(k)
        s[i, k] = model.addVar(lb=0, ub=vehicle_working_time_limit,
                              vtype=GRB.CONTINUOUS,
                              name=name)  # 访问时间

# 定义目标函数
obj1 = LinExpr(0)
obj2 = LinExpr(0)
for i in range(n_customers + 1):
    for k in range(vehicleNum):
        for j in range(n_customers + 1):
            if (i != j):
                obj1.addTerms(vehicle_travel_cost * disMatrix[i][j], x[i, j, k])  # 第一项为系数

for k in range(vehicleNum):
    for j in range(n_customers + 1):
        if (j != 0):
            obj2.addTerms(vehicle_fixed_cost, x[0, j, k])

model.setObjective(obj1 + obj2, GRB.MINIMIZE)


# 定义约束一 需求
model.addConstrs(quicksum(y[i, k] for k in range(vehicleNum)) == 1 for i in range(1, n_customers + 1))

# 定义约束二 流平衡
for k in range(vehicleNum):
    for h in range(1, n_customers + 1):
        expr1 = LinExpr(0)
        expr2 = LinExpr(0)
        for i in range(n_customers + 1):
            if (h != i):
                expr1.addTerms(1, x[i, h, k])

        for j in range(n_customers + 1):
            if (h != j):
                expr2.addTerms(1, x[h, j, k])

        model.addConstr(expr1 == expr2, name='flow_conservation_' + str(i))
        expr1.clear()
        expr2.clear()

# 定义约束三 车辆数量
# model.addConstr( quicksum( x[0,j,k] for j in range(1,n_customers+1)) == quicksum( x[j,0,k] for j in range(1,n_customers+1)) for k in range(vehicleNum) )
# model.addConstr( quicksum( x[0,j,k] for j in range(1,n_customers+1) ) <=1 for k in range(vehicleNum) )
for k in range(vehicleNum):
    expr3 = LinExpr(0)
    expr4 = LinExpr(0)
    for j in range(1, n_customers + 1):
        expr3.addTerms(1, x[0, j, k])
        expr4.addTerms(1, x[j, 0, k])
    model.addConstr(expr3 == expr4)


for k in range(vehicleNum):
    expr5 = LinExpr(0)
    for j in range(1, n_customers + 1):
        expr5.addTerms(1, x[0, j, k])
    model.addConstr(expr5 <= 1)

# 定义约束四 决策变量关联
for k in range(vehicleNum):
    for j in range(1, n_customers + 1):
        model.addConstrs(quicksum(x[i, j, k] for i in range(n_customers + 1) if i != j) == y[j, k])

for k in range(vehicleNum):
    for i in range(1, n_customers + 1):
        model.addConstrs(quicksum(x[i, j, k] for j in range(n_customers + 1) if i != j) == y[i, k])

## 容量约束
model.addConstrs(quicksum(demand[i] * y[i, k] for i in range(1, n_customers + 1)) <= vehicle_capacity_limit for k in range(vehicleNum))

# 时间约束
for k in range(vehicleNum):
    for i in range(n_customers + 1):
        for j in range(n_customers + 1):
            if (i != j):
                model.addConstr(s[i, k] + disMatrix[i][j] * drive_speed + demand[i] * serive_speed - s[j, k]
                                - BigM + BigM * x[i, j, k] <= 0)

model.addConstr(s[0, k] == 0 for k in range(vehicleNum))
# 返回时间约束

model.addConstr(quicksum((s[i, k] + demand[i] * serive_speed + disMatrix[i][0] * drive_speed) * x[i, 0, k] for i in range(1, n_customers + 1)) <= vehicle_working_time_limit for k in range(vehicleNum))


model.Params.TimeLimit = 600  # 设置求解时间上限
# 求解
model.optimize()

# 打印结果
print("

-----optimal value-----")
print(model.ObjVal)

for key in x.keys():
    if (x[key].x > 0):
        print(x[key].VarName + ' = ', x[key].x)

代码优化建议

  • 内存泄漏问题：由于循环中不断创建变量，没有及时清除，可能导致内存泄漏。建议在每次循环结束时，手动清除相关变量的内存，例如使用 del 语句删除不再需要的变量。
  • 更高效的数据结构：可以使用 numpy 数组来存储模型中的参数和变量，以提高内存效率和代码可读性。

例如：

# 使用 numpy 数组存储距离矩阵
disMatrix = np.zeros((n_customers + 1, n_customers + 1))
for i in range(n_customers + 1):
    for j in range(i + 1, n_customers + 1):
        d = round(((positions[i][0] - positions[j][0]) ** 2 + (positions[i][1] - positions[j][1]) ** 2) ** 0.5, 4)
        disMatrix[i][j] = disMatrix[j][i] = d

# 使用 numpy 数组存储决策变量
x = np.zeros((n_customers + 1, n_customers + 1, vehicleNum))

通过以上优化建议，可以提高代码的内存效率，避免出现 "out of memory" 错误。

注意：

  • Gurobi 库需要单独安装。
  • 代码中的参数可以根据实际情况进行调整。
  • 以上优化建议仅供参考，具体实现需要根据实际情况进行调整。
Python 使用 Gurobi 求解车辆路径问题 (CVRP) 优化代码示例

原文地址: https://www.cveoy.top/t/topic/n5tS 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录