基于python语言，采用经典自适应大邻域算法（ALNS）对 需求拆分车辆路径规划问题（SDVRP） 进行求解。
目录
往期优质资源
经过一年多的创作，目前已经成熟的代码列举如下，如有需求可私信联系，表明需要的 问题与算法，原创不宜，有偿获取。
| VRP问题 | GA | ACO | ALNS | DE | DPSO | QDPSO | TS | SA |
|---|---|---|---|---|---|---|---|---|
| CVRP | √ | √ | √ | √ | √ | √ | √ | √ |
| VRPTW | √ | √ | √ | √ | √ | √ | √ | √ |
| MDVRP | √ | √ | √ | √ | √ | √ | √ | √ |
| MDHVRP | √ | √ | √ | √ | √ | √ | √ | √ |
| MDHVRPTW | √ | √ | √ | √ | √ | √ | √ | √ |
| SDVRP | √ | √ | √ |
1. 适用场景
- 求解CVRP
- 车辆类型单一
- 车辆容量小于部分需求节点需求
- 单一车辆基地
2. 代码调整
与CVRP问题相比，SDVRP问题允许客户需求大于车辆容量。为了使得每个客户的需求得到满足，必须派遣一辆或多辆车辆对客户进行服务，也就是需要对客户的需求进行拆分。关于如何进行拆分一般有两种方式：
- 先验拆分策略：提前制定策略对客户的需求（尤其是大于车辆容量的客户需求）进行分解，将SDVRP问题转化为CVRP问题
- 过程拆分策略：在车辆服务过程中对客户需求进行动态拆分
本文采用文献[1]提出的先验分割策略，表述如下：
（1）20/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.20Qm<=Di }
- 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.10Qm<=Di−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.05Qm<=Di−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.01Qm<=Di−0.20Qm20−0.10Qm10−0.05Qm5 }
（2）25/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.25Qm<=Di }
- 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.10Qm<=Di−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.05Qm<=Di−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.01Qm<=Di−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 # 节点id
self.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.rand_d_max = 0.4 # 随机破坏最大破坏比例
self.rand_d_min = 0.1 # 随机破坏最小破坏比例
self.worst_d_min = 5 # 最坏值破坏最少破坏数量
self.worst_d_max = 20 # 最坏值破坏最多破坏数量
self.regret_n = 5 # 后悔值破坏数量
self.r1 = 30 # 一等得分值
self.r2 = 18 # 二等得分值
self.r3 = 12 # 三等得分值
self.rho = 0.6 # 权重衰减比例
self.d_weight = np.ones(2) * 10 # 破坏算子权重
self.d_select = np.zeros(2) # 破坏算子选择次数
self.d_score = np.zeros(2) # 破坏算子得分
self.d_history_select = np.zeros(2) # 破坏算子累计选择次数
self.d_history_score = np.zeros(2) # 破坏算子累计得分
self.r_weight = np.ones(3) * 10 # 修复算子权重
self.r_select = np.zeros(3) # 修复算子选择次数
self.r_score = np.zeros(3) # 修复算子得分
self.r_history_select = np.zeros(3) # 修复算子累计选择次数
self.r_history_score = np.zeros(3) # 修复算子累计得分
（2）距离矩阵
# 初始化参数
def cal_distance_matrix(model):
for i in model.demand_id_list:
for j in model.demand_id_list:
d=math.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 d
dist = 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] = dist
model.distance_matrix[model.depot.id, i] = dist
（3）破坏算子
# 随机破坏
def createRandomDestory(model):
d=random.uniform(model.rand_d_min,model.rand_d_max)
return random.sample(model.demand_id_list_,int(d*(len(model.demand_id_list_)-1)))
# 最坏值破坏
def createWorseDestory(model,sol):
deta_f=[]
for node_no in sol.node_no_seq:
node_no_seq_=copy.deepcopy(sol.node_no_seq)
node_no_seq_.remove(node_no)
obj,_,_=calObj(node_no_seq_,model)
deta_f.append(sol.obj-obj)
sorted_id = sorted(range(len(deta_f)), key=lambda k: deta_f[k], reverse=True)
d=random.randint(model.worst_d_min,model.worst_d_max)
return [sol.node_no_seq[i] for i in sorted_id[:d]]
（4）修复算子
# 随机修复
def createRandomRepair(remove_list,model,sol):
unassigned_node_no_seq = remove_list
assigned_node_no_seq = [node_no for node_no in sol.node_no_seq if node_no not in remove_list]
# insert
for node_no in unassigned_node_no_seq:
index=random.randint(0,len(assigned_node_no_seq)-1)
assigned_node_no_seq.insert(index,node_no)
new_sol=Sol()
new_sol.node_no_seq=copy.deepcopy(assigned_node_no_seq)
new_sol.obj,new_sol.route_list,new_sol.route_distance=calObj(assigned_node_no_seq,model)
return new_sol
# 贪婪修复
def createGreedyRepair(remove_list,model,sol):
unassigned_node_no_seq = remove_list
assigned_node_no_seq = [node_no for node_no in sol.node_no_seq if node_no not in remove_list]
#insert
while len(unassigned_node_no_seq)>0:
insert_node_no,insert_index=findGreedyInsert(unassigned_node_no_seq,assigned_node_no_seq,model)
assigned_node_no_seq.insert(insert_index,insert_node_no)
unassigned_node_no_seq.remove(insert_node_no)
new_sol=Sol()
new_sol.node_no_seq=copy.deepcopy(assigned_node_no_seq)
new_sol.obj,new_sol.route_list,new_sol.route_distance=calObj(assigned_node_no_seq,model)
return new_sol
参考
【1】 A novel approach to solve the split delivery vehicle routing problem
标签：node,进阶,SDVRP,no,self,sol,算法,model,seq From： https://blog.csdn.net/python_n/article/details/136805836