Capacitated Vehicle Routing Problem (CVRP) Optimization with Gurobi and Python

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 = 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  # 保留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("\n\n-----optimal value-----\n")
print(model.ObjVal)

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

Memory Optimization

This code uses a large number of decision variables, which can lead to out-of-memory errors, especially when dealing with large datasets. To address this, the code can be optimized for memory usage by applying the following steps:

Efficient Data Structures: Employ NumPy arrays for disMatrix and other relevant variables to leverage vectorized operations and minimize memory footprint.
Manual Memory Management: Use del statements to explicitly delete variables that are no longer needed after each loop iteration. This helps reclaim memory used by those variables.
Sparse Matrix Representation: If disMatrix is expected to be sparse (mostly zeros), consider using a sparse matrix representation from SciPy, which can significantly reduce memory consumption.
Early Variable Creation: Create variables only when they are actually required within the constraints or objective function. Avoid unnecessary variable creation in advance.
Consider Gurobi's Dense/Sparse Options: Investigate Gurobi's options related to dense and sparse matrix representation to see if they can be leveraged for further memory optimization.

By implementing these techniques, the memory usage of the code can be effectively managed, reducing the likelihood of out-of-memory errors. It's crucial to assess the dataset size and adapt memory optimization strategies accordingly.

Capacitated Vehicle Routing Problem (CVRP) Optimization with Gurobi and Python