【进阶六】Python实现SDVRPTW（需求拆分）常见求解算法——禁忌搜索+模拟退火算法（TS+SA）

基于python语言，采用经典禁忌搜索（TS）+模拟退火（SA）对 带硬时间窗的需求拆分车辆路径规划问题（SDVRPTW） 进行求解。

往期优质资源

1. 适用场景

• 求解SDVRPTW
• 车辆类型单一
• 车辆容量小于部分需求节点需求
• 单一车辆基地
• 带硬时间窗

2. 代码调整

2.1 需求拆分

与SDVRP问题相比，SDVRPTW问题不仅允许客户需求大于车辆载重，而且考虑了客户节点的时间窗约束。为了使得每个客户的需求得到满足，必须派遣一辆或多辆车辆在规定时间窗内对客户进行服务。对于需求节点的拆分，这里依然采取先验拆分策略，本文采用文献[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​ }

在实现过程中，对于需求超过车辆容量的客户必须进行需求拆分，而对于未超过车辆容量的客户可以拆分也可以不拆分，这里设置了参数比例进行限制。

2.2 需求拆分后的服务时长取值问题

节点的服务时长会影响车辆的行进时间，进而会影响与节点时间窗的匹配问题。一般来说，节点的服务时长与需求量成正比关系，在进行节点需求拆分后，新节点的需求量降低，其服务时长理应也降低。但从标准数据集来看，各需求节点的服务时长均采用同一数值。因此本文在代码实现过程中也采用固定值，不考虑新节点服务时长的变化。当然，如有需要，也可以设置单位货物的服务时长，根据拆分后节点的具体需求量设置相应的服务时长。

3. 求解结果

3.1 TS

（1）收敛曲线

（2）车辆路径

（3）输出内容

3.2 SA

（1）收敛曲线

（2）车辆路径

（3）输出内容

4. 代码片段

（1）数据结构

import math
import random
import numpy as np
import copy
import xlsxwriter
import matplotlib.pyplot as plt
import csv
import time
# 数据结构：解
class Sol():
    def __init__(self):
        self.obj=None # 目标函数值
        self.node_no_seq=[] # 解的编码
        self.route_list=[] # 解的解码
        self.timetable_list=[] # 车辆访问各点的时间
        self.route_distance_list = None
        self.action_id = None  # 对应的算子id
# 数据结构：需求节点
class Node():
    def __init__(self):
        self.id=0 # 节点id
        self.x_coord=0 # 节点平面横坐标
        self.y_coord=0  # 节点平面纵坐标
        self.demand=0 # 节点需求
        self.start_time=0 # 节点开始服务时间
        self.end_time=1440 # 节点结束服务时间
        self.service_time=0 # 单次服务时长
        self.vehicle_speed = 0 # 行驶速度
# 数据结构：车场节点
class Depot():
    def __init__(self):
        self.id=0 # 节点id
        self.x_coord=0 # 节点平面横坐标
        self.y_coord=0  # 节点平面纵坐标
        self.start_time=0 # 节点开始服务时间
        self.end_time=1440 # 节点结束服务时间
        self.v_speed = 0 # 行驶速度
        self.v_cap = 80 # 车辆容量
# 数据结构：全局参数
class Model():
    def __init__(self):
        self.best_sol=None # 全局最优解
        self.sol_list=[] # 解的集合
        self.demand_dict = {}  # 需求节点集合
        self.depot = None  # 车场节点集合
        self.demand_id_list = [] # 需求节点id集合
        self.distance_matrix = {}  # 距离矩阵
        self.time_matrix = {}  # 时间矩阵
        self.number_of_demands = 0 # 需求点数量
        self.demand_id_list_ = []  # 经先验需求分割后的节点集合
        self.demand_dict_ = {}  # 需求分割后的节点需求集合
        self.distance_matrix_ = {}  # 原始节点id间的距离矩阵
        self.time_matrix_ = {}  # 原始节点id间的时间矩阵
        self.mapping = {}  # 需求分割前后的节点对应关系
        self.split_rate = 0.5 # 控制需求分割的比例（需求超出车辆容量的除外）
        self.popsize = 100 # 种群规模
        self.split_rate = 0.5 # 控制需求分割的比例（需求超出车辆容量的除外）
        self.tabu_list=None # 禁忌表
        self.TL=30 # 禁忌长度

（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 genInitialSol(node_no_seq):
    node_no_seq=copy.deepcopy(node_no_seq)
    random.shuffle(node_no_seq)
    return node_no_seq
# 定义邻域算子
def createActions(n):
    action_list=[]
    nswap=n//2
    #第一种算子（Swap）：前半段与后半段对应位置一对一交换
    for i in range(nswap):
        action_list.append([1,i,i+nswap])
    #第二中算子（DSwap）：前半段与后半段对应位置二对二交换
    for i in range(0,nswap-1,2):
        action_list.append([2,i,i+nswap])
    #第三种算子（Reverse）：指定长度的序列反序
    for i in range(0,n,4):
        action_list.append([3,i,i+3])
    return action_list
# 执行邻域搜索
def doAction(node_no_seq,action):
    node_no_seq=copy.deepcopy(node_no_seq)
    if action[0]==1:
        index_1=action[1]
        index_2=action[2]
        temporary=node_no_seq[index_1]
        node_no_seq[index_1]=node_no_seq[index_2]
        node_no_seq[index_2]=temporary
        return node_no_seq
    elif action[0]==2:
        index_1 = action[1]
        index_2 = action[2]
        temporary=[node_no_seq[index_1],node_no_seq[index_1+1]]
        node_no_seq[index_1]=node_no_seq[index_2]
        node_no_seq[index_1+1]=node_no_seq[index_2+1]
        node_no_seq[index_2]=temporary[0]
        node_no_seq[index_2+1]=temporary[1]
        return node_no_seq
    elif action[0]==3:
        index_1=action[1]
        index_2=action[2]
        node_no_seq[index_1:index_2+1]=list(reversed(node_no_seq[index_1:index_2+1]))
        return node_no_seq

参考

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