【进阶五】Python实现SDVRP（需求拆分）常见求解算法——蚁群算法（ACO）

基于python语言，采用经典遗传算法（ACO）对 需求拆分车辆路径规划问题（SDVRP） 进行求解。

往期优质资源

1. 适用场景

• 求解CVRP
• 车辆类型单一
• 车辆容量小于部分需求节点需求
• 单一车辆基地

2. 代码调整

与CVRP问题相比，SDVRP问题允许客户需求大于车辆容量。为了使得每个客户的需求得到满足，必须派遣一辆或多辆车辆对客户进行服务，也就是需要对客户的需求进行拆分。关于如何进行拆分一般有两种方式：

• 先验拆分策略：提前制定策略对客户的需求（尤其是大于车辆容量的客户需求）进行分解，将SDVRP问题转化为CVRP问题
• 过程拆分策略：在车辆服务过程中对客户需求进行动态拆分

本文采用文献[1]提出的先验分割策略，表述如下：

（1）20/10/5/1拆分规则

• m₂₀ =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​ }
• m₁₀ =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​  }
• m₅ =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​ }
• m₁ =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拆分规则

• m₂₅ =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​ }
• m₁₀ =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​  }
• m₅ =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​ }
• m₁ =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.alpha = 2 # 信息启发式因子
        self.beta = 3 # 期望启发式因子
        self.Q = 100 # 信息素总量
        self.rho = 0.5 # 信息素挥发因子
        self.tau = {} # 弧信息素集合
        self.tau0 = 100 # 路径初始信息素

（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]=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 movePosition(model):
    sol_list=[]
    local_sol=Sol()
    local_sol.obj=float('inf')
    for _ in range(model.popsize):
        #随机初始化蚂蚁为止
        node_no_seq=[random.randint(0,len(model.demand_id_list_)-1)]
        all_node_no_seq=copy.deepcopy(model.demand_id_list_)
        all_node_no_seq.remove(node_no_seq[-1])
        #确定下一个访问节点
        while len(all_node_no_seq)>0:
            next_node_no=searchNextNode(model,node_no_seq[-1],all_node_no_seq)
            node_no_seq.append(next_node_no)
            all_node_no_seq.remove(next_node_no)
        sol=Sol()
        sol.node_no_seq=node_no_seq
        sol.obj,sol.route_list,sol.route_distance=calObj(node_no_seq,model)
        sol_list.append(sol)
        if sol.obj < local_sol.obj:
            local_sol = copy.deepcopy(sol)
    model.sol_list=copy.deepcopy(sol_list)
    if local_sol.obj<model.best_sol.obj:
        model.best_sol=copy.deepcopy(local_sol)
# 搜索下一移动节点
def searchNextNode(model,current_node_no,SE_List):
    prob=np.zeros(len(SE_List))
    for i,node_no in enumerate(SE_List):
        eta=1/model.distance_matrix_[current_node_no,node_no] if model.distance_matrix_[current_node_no,node_no] else 0.0001
        tau=model.tau[current_node_no,node_no]
        prob[i]=((eta**model.alpha)*(tau**model.beta))
    #采用轮盘法选择下一个访问节点
    cumsumprob=(prob/sum(prob)).cumsum()
    cumsumprob -= np.random.rand()
    return SE_List[list(cumsumprob >= 0).index(True)]
# 更新路径信息素
def upateTau(model):
    rho=model.rho
    for k in model.tau.keys():
        model.tau[k]=(1-rho)*model.tau[k]
    #根据解的node_no_seq属性更新路径信息素（TSP问题的解）
    for sol in model.sol_list:
        node_no_seq=sol.node_no_seq
        for i in range(len(node_no_seq)-1):
            from_node_no=node_no_seq[i]
            to_node_no=node_no_seq[i+1]
            model.tau[from_node_no,to_node_no]+= model.Q/sol.obj
    for k in model.tau.keys():
        model.tau[k]= max(model.tau[k],0.000001)

参考

【1】 A novel approach to solve the split delivery vehicle routing problem