基于Gurobi求解带时间窗和容量约束的车辆路径问题(CVRP)

本代码使用Python的Gurobi库求解一个经典的车辆路径问题(CVRP)，该问题包含300个客户的坐标和配送需求，目标函数是最小成本，包括固定成本和行驶成本，同时考虑车辆数量、工作时间和载重约束。

问题描述：

有300个客户，每个客户都有坐标和配送需求。
配送中心有足够数量的车辆，车辆同构。
每辆车有最长工作时间约束和载重约束。
工作时间包括两客户之间的行驶时间和客户服务时间，服务时间与配送量成正比。
目标函数是最小成本，包括固定成本（与车辆数成正比）和行驶成本（行驶距离成正比）。

代码实现：

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==300:
            break
    rdn3=np.random.RandomState(2)
    demand=rdn3.randint(2,11,300)  #需求
    return points,demand

vehicleNum=100 
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=[(25,25)]   #0
positions=depot+clients 

distances = [[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)
        distances[i][j] = distances[j][i] = d  #保留4位
        
        
disMatrix = distances

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(0
                              , vehicle_working_time_limit
                              , vtype= GRB.CONTINUOUS
                              , name= name)   #访问时间

#更新模型
model.update()

#定义目标函数
z1=quicksum(vehicle_travel_cost*disMatrix[i][j]*x[i,j,k]+vehicle_fixed_cost*x[0,j,k] for i in range(n_customers+1) for j in range(n_customers+1) for k in range(vehicleNum) if i!=j)
model.setObjective(z1,GRB.MINIMIZE)

#定义约束一 需求

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

#定义约束二 流平衡
model.addConstrs( quicksum( x[i,j,k] for j in range(n_customers+1) ) == quicksum( x[j,i,k] for j in range(n_customers+1) ) for i in range(n_customers+1) for k in range(vehicleNum) )

#定义约束三 车辆数量
model.addConstr( quicksum( x[j,0,k] for j in range(1,n_customers+1)) == quicksum( x[0,j,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) for k in range(vehicleNum)) <=vehicleNum )

#定义约束四 决策变量关联
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[i,k] for j in range(1,n_customers+1) for k in range(vehicleNum) )

##容量约束
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] + distances[i][j]*drive_speed + demand[i]*serive_speed - s[j,k]
                                - BigM + BigM * x[i,j,k] <= 0 )

#求解
model.optimize()

代码说明：

创建数据集: 使用createDataSet()函数随机生成客户的坐标和配送需求。
定义参数: 设置车辆数量、固定成本、行驶成本、工作时间限制、载重限制、行驶速度和服务速度等参数。
计算距离矩阵: 使用distances列表存储客户之间的距离，并定义disMatrix作为距离矩阵。
定义决策变量: 定义三个决策变量：
- x[i,j,k]: 若车辆k从客户i行驶到客户j，则取值为1，否则取值为0。
- y[i,k]: 若车辆k访问客户i，则取值为1，否则取值为0。
- s[i,k]: 车辆k到达客户i的时间。
定义目标函数: 最小化总成本，包括固定成本和行驶成本。
定义约束: 定义五个约束条件，确保满足问题要求：
- 约束一： 每个客户必须被且仅被一辆车访问。
- 约束二： 流量平衡约束，保证每辆车到达每个客户后都要离开。
- 约束三： 车辆数量约束，车辆数量不超过设定值。
- 约束四： 决策变量关联约束，确保车辆访问客户时，对应的x和y变量的值一致。
- 约束五： 容量约束，确保每辆车运载的货物总量不超过载重限制。
- 约束六： 时间约束，确保每辆车的工作时间不超过时间限制。
求解: 调用model.optimize()函数进行求解。

代码优化：

数据结构优化: 使用列表存储距离矩阵，提高效率。
代码可读性优化: 添加注释，解释代码逻辑。
错误处理: 添加错误处理机制，例如在读取数据或求解过程中出现异常时，提示用户并退出程序。

结果分析：

运行代码后，可以查看输出结果，包括最优解、车辆路线、总成本等信息。
可以根据输出结果，分析问题解的质量，并进行进一步优化。

扩展应用：

可以将该代码应用于实际的物流配送问题，例如快递配送、货运配送、上门服务等。
可以将该代码扩展到更复杂的问题，例如多配送中心、多车型、多时间窗等。

注意：

该代码需要安装Gurobi库，可以在官网下载并安装。
该代码仅供参考，实际应用中需要根据具体情况进行调整。

希望这篇文章对您有所帮助。如果您有任何疑问，请随时留言。