济南做网站哪家好,无锡网站建设无锡网络推广,app 网站开发团队人员配置,广告公司简介模板100字基于python语言#xff0c;采用经典差分进化算法#xff08;DE#xff09;对 需求拆分车辆路径规划问题#xff08;SDVRP#xff09; 进行求解。 目录 往期优质资源1. 适用场景2. 代码调整3. 求解结果4. 代码片段参考 往期优质资源 经过一年多的创作#xff0c;目前已经成… 基于python语言采用经典差分进化算法DE对 需求拆分车辆路径规划问题SDVRP 进行求解。 目录 往期优质资源1. 适用场景2. 代码调整3. 求解结果4. 代码片段参考 往期优质资源 经过一年多的创作目前已经成熟的代码列举如下如有需求可私信联系表明需要的 问题与算法原创不宜有偿获取。 VRP问题GAACOALNSDEDPSOQDPSOTSSACVRP√√√√√√√√VRPTW√√√√√√√√MDVRP√√√√√√√√MDHVRP√√√√√√√√MDHVRPTW√√√√√√√√SDVRP√√√√
1. 适用场景
求解CVRP车辆类型单一车辆容量小于部分需求节点需求单一车辆基地
2. 代码调整 与CVRP问题相比SDVRP问题允许客户需求大于车辆容量。为了使得每个客户的需求得到满足必须派遣一辆或多辆车辆对客户进行服务也就是需要对客户的需求进行拆分。关于如何进行拆分一般有两种方式
先验拆分策略提前制定策略对客户的需求尤其是大于车辆容量的客户需求进行分解将SDVRP问题转化为CVRP问题过程拆分策略在车辆服务过程中对客户需求进行动态拆分
本文采用文献[1]提出的先验分割策略表述如下
120/10/5/1拆分规则
m20 max{ m ∈ Z ∪ { 0 } ∣ 0.20 Q m D i m\in Z^ \cup \{0\} | 0.20Qm D_i m∈Z∪{0}∣0.20QmDi }m10 max{ m ∈ Z ∪ { 0 } ∣ 0.10 Q m D i − 0.20 Q m 20 m\in Z^ \cup \{0\} | 0.10Qm D_i-0.20Qm_{20}~ m∈Z∪{0}∣0.10QmDi−0.20Qm20 }m5 max{ m ∈ Z ∪ { 0 } ∣ 0.05 Q m D i − 0.20 Q m 20 − 0.10 Q m 10 m\in Z^ \cup \{0\} | 0.05Qm D_i-0.20Qm_{20}-0.10Qm_{10} m∈Z∪{0}∣0.05QmDi−0.20Qm20−0.10Qm10 }m1 max{ m ∈ Z ∪ { 0 } ∣ 0.01 Q m D i − 0.20 Q m 20 − 0.10 Q m 10 − 0.05 Q m 5 m\in Z^ \cup \{0\} | 0.01Qm D_i-0.20Qm_{20}-0.10Qm_{10}-0.05Qm_{5} m∈Z∪{0}∣0.01QmDi−0.20Qm20−0.10Qm10−0.05Qm5 }
225/10/5/1拆分规则
m25 max{ m ∈ Z ∪ { 0 } ∣ 0.25 Q m D i m\in Z^ \cup \{0\} | 0.25Qm D_i m∈Z∪{0}∣0.25QmDi }m10 max{ m ∈ Z ∪ { 0 } ∣ 0.10 Q m D i − 0.25 Q m 25 m\in Z^ \cup \{0\} | 0.10Qm D_i-0.25Qm_{25}~ m∈Z∪{0}∣0.10QmDi−0.25Qm25 }m5 max{ m ∈ Z ∪ { 0 } ∣ 0.05 Q m D i − 0.25 Q m 25 − 0.10 Q m 10 m\in Z^ \cup \{0\} | 0.05Qm D_i-0.25Qm_{25}-0.10Qm_{10} m∈Z∪{0}∣0.05QmDi−0.25Qm25−0.10Qm10 }m1 max{ m ∈ Z ∪ { 0 } ∣ 0.01 Q m D i − 0.25 Q m 25 − 0.10 Q m 10 − 0.05 Q m 5 m\in Z^ \cup \{0\} | 0.01Qm D_i-0.25Qm_{25}-0.10Qm_{10}-0.05Qm_{5} m∈Z∪{0}∣0.01QmDi−0.25Qm25−0.10Qm10−0.05Qm5 }
在实现过程中对于需求超过车辆容量的客户必须进行需求拆分而对于未超过车辆容量的客户可以拆分也可以不拆分这里设置了参数比例进行限制。
3. 求解结果 1收敛曲线
2车辆路径 4. 代码片段 1数据结构
# 数据结构解
class Sol():def __init__(self):self.node_no_seq None # 节点id有序排列self.obj None # 目标函数self.fitness None # 适应度self.route_list None # 车辆路径集合self.route_distance_list None # 车辆路径长度集合
# 数据结构网络节点
class Node():def __init__(self):self.id 0 # 节点idself.x_coord 0 # 节点平面横坐标self.y_coord 0 # 节点平面纵坐标self.demand 0 # 节点需求
# 数据结构全局参数
class Model():def __init__(self):self.best_sol None # 全局最优解self.demand_id_list [] # 需求节点集合self.demand_dict {}self.sol_list [] # 解的集合self.depot None # 车场节点self.number_of_demands 0 # 需求节点数量self.vehicle_cap 0 # 车辆最大容量self.distance_matrix {} # 节点距离矩阵self.demand_id_list_ [] # 经先验需求分割后的节点集合self.demand_dict_ {} # 需求分割后的节点需求集合self.distance_matrix_ {} # 原始节点id间的距离矩阵self.mapping {} # 需求分割前后的节点对应关系self.split_rate 0.5 # 控制需求分割的比例需求超出车辆容量的除外self.popsize 100 # 种群规模self.Cr0.5 # 差分交叉概率self.F0.5 # 差分变异概率2距离矩阵
# 初始化参数
def cal_distance_matrix(model):for i in model.demand_id_list:for j in model.demand_id_list:dmath.sqrt((model.demand_dict[i].x_coord-model.demand_dict[j].x_coord)**2(model.demand_dict[i].y_coord-model.demand_dict[j].y_coord)**2)model.distance_matrix[i,j]max(d,0.0001) if i ! j else ddist math.sqrt((model.demand_dict[i].x_coord - model.depot.x_coord) ** 2 (model.demand_dict[i].y_coord - model.depot.y_coord) ** 2)model.distance_matrix[i, model.depot.id] distmodel.distance_matrix[model.depot.id, i] dist3邻域
#差分变异变异策略DE/rand/1/bin
def muSol(model,v1):x1model.sol_list[v1].node_no_seqwhile True:v2random.randint(0,model.popsize-1)if v2!v1:breakwhile True:v3random.randint(0,model.popsize-1)if v3!v2 and v3!v1:breakx2model.sol_list[v2].node_no_seqx3model.sol_list[v3].node_no_seqmu_x[min(int(x1[i]model.F*(x2[i]-x3[i])),model.number_of_demands-1) for i in range(model.number_of_demands) ]return mu_x
#差分交叉
def crossSol(model,vx,vy):cro_x[]for i in range(model.number_of_demands):if random.random()model.Cr:cro_x.append(vy[i])else:cro_x.append(vx[i])cro_xadjustRoutes(cro_x,model)return cro_x参考
【1】 A novel approach to solve the split delivery vehicle routing problem
