1.一种带时间窗的异构危化品运输路径规划方法,其特征在于该方法包括以下步骤：步骤1:获取基础数据，包括运输车辆信息、运输道路信息、人口分布和危化品信息；

步骤2：构建带时间窗的异构危化品运输路径规划的多目标优化模型；

多目标优化模型定义在一个完整的有向图G＝(N,L)中；N＝{0,1,2…,n}是有向图中的节点集，节点0是仓储节点，C＝{1,2…,n}为客户节点集，L为有向图中的弧集；qi是客户i的非负需求，i∈C，[Tai,Tbi]为客户时间窗，Tai代表客户可接受服务的最早时间，Tbi代表客户可接受服务的最晚时间；

设运输车队由K种车型组成，Qk是车型k的最大载重，k∈K，fck是车型k的固定使用花费，Vk是车型k的可使用车辆数，ARk是车型k的车辆事故率；arcij代表节点i,j之间的运输路径，alij为节点i,j之间的运输距离，tij为节点i,j之间的运输时间， 是车型为k的车辆从节点i到节点j的非负单位距离运输成本，pdij为节点i,j之间的暴露人口密度；

假定每一种车型具有统一的单位距离运输成本与无限的可用车辆，即，和Vk＝∞；同时假定每一条弧上的人口密度与泄漏事故概率是均匀的；模型约束为：每一辆运输车辆都必须从仓储节点出发最终回到仓储节点；每一个顾客只能在时间窗内被服务一次，不允许分割交付；运输车辆允许在最早的服务时间Tai之前到达，在这种情况下，它必须等到时间Tai到达后才开始为客户供货；车辆不允许超载；

将优化目标函数定义为一个多目标的三维向量，Minimize(Z)＝[Z1,Z2,Z3]，其中，Z1是用于最小化运输总花费的目标函数；Z2是用于最小化运输风险的目标函数；Z3是用于最小化平均车辆冗余的目标函数；优化模型需要两组变量，其中，Sivk是第一组变量，定义为类型为k的车辆v到达顾客节点i的时间；第二组变量为决策变量，定义为车辆对顾客节点的供货顺序：

式中， 为决策变量i,j∈N；k∈K；v

目标函数Z1：

目标函数Z2：

式中， 为类型为k的车辆v在弧arcij上引发危化品泄漏事故的概率；Csij为弧arcij上泄漏事故后果，表示为在距离事发地点一公里内受影响的人数；为了计算危化品事故的概率，将相应的车辆事故率、给定事故的条件概率、弧长、车辆荷载和等待时间合并如下：式中，PRij为弧arcij上给定事故的条件概率；β与α是根据危化品类型所确立的标准系数； 为类型为k的车辆v在弧arcij上的负载；wtjvk是类型为k的车辆v在节点j的等待时间；

目标函数Z3：

式中， 是类型为k的车辆v的冗余程度；

是所有使用车辆的数量；

模型约束为：

上式表示每一个顾客点只能被运输车辆访问一次；

上式表示所有车辆不准许超载；

上三式表示所有车辆必须从仓储节点0出发，在访问若干非重复客户后返回仓储节点

0；

上式表示每个客户必须在预先定义的时间窗口内得到满足，允许车辆提前到达，但不允许延迟；

步骤3:模型求解，设计基于变邻域搜索的混合多目标进化算法；

①初始种群构建

为了满足步骤2所构建模型的要求和规范，在传统前向插入算法的基础上设计了两阶段前向插入法；在第一阶段，采用固定机群放宽模型约束；为了服务尽可能多的客户，采用负载能力最大的车型组成固定机群；带时间窗异构车辆路径规划问题就转化成了带时间窗车辆路径规划问题；

上式用于定义每一条路径最初的客户点，al0i为节点i到仓储节点0的距离；anglei是节点i的极坐标角；Cs为还未被访问的客户节点集；当前路径选择了最初的客户点，前向插入法从Cs中选择一个顾客，该顾客在不违反时间和容量约束的情况下最小化当前路由中每条边之间的插入总成本；在当前路由对于未分配的客户没有一个可行的插入位置时，建立一个新的路由；当所有客户分配完毕，第一阶段结束；在第二阶段，采用最小的车辆平均冗余程度车队代替当前固定机群，即，每一条路由的运输车辆类型k都要使该车辆的冗余程度VRvk最小；将时间窗车辆路径规划问题重新转换为带时间窗异构车辆路径规划问题；

②帕累托排序

在完成初始种群构建后，采用帕累托排序法划分种群层次；帕累托排序法采用帕累托支配关系比较种群中个体之间的优劣；假设种群为P，帕累托排序法需要计算种群内每一个个体p∈P的两个参数np和Sp，np是种群中支配个体p的个体数，Sp是种群中个体p支配的个体集合；当遍历种群内所有个体后，所有np＝0的个体将被划分到种群的第一层P1，对于P1内的个体l∈P1，其所支配的个体集合为Sl，遍历Sl中的个体m∈Sl，执行nm＝nm‑1，所有nm＝0的个体将被划分到种群的第二层P2，以此类推，直到整个种群被分层；序号为1的分层P1为非支配层，P1内所有个体均为当前种群的帕累托最优解；

③进化算子

通过二进制锦标算法在当前种群内选择个体进行交叉变异操作，产生新的种群，分层序号越小的个体，被选中进行交叉变异操作的概率越大；

由于标准进化算子不能保证生成可行的子解，可能导致性能较差，基于变邻域搜索的混合多目标进化算法采用了路由交换交叉算子和路由消除变异算子；路由交换交叉算子是针对优化目标Z1与优化目标Z2所设计的，该算子允许一个染色体中的良好的路线或基因序列与种群中的其他个体共享；待交换的基因序列旅行成本较小且与时间窗口完美匹配；优化目标Z3反映了单位运输的平均成本，该优化目标可以通过完全取消特定的路线或者取消客户并部署固定成本更小的车辆来降低平均车辆冗余；因此，基于变邻域搜索的混合多目标进化算法采用路由消除变异算子来改善优化目标Z3；

④局部搜索开发

为了进一步改善种群内的个体，随机从序号为1的分层P1内选择一个非支配解作为变邻域搜索元启发式算法的初始解进行局部搜索；变邻域搜索的基本思想是通过在搜索过程中系统性地改变邻域结构集合来拓展搜索范围，获得局部最优解，然后再基于这一局部最优解改变邻域结构集合，拓展搜索范围，找到另一个局部最优解的过程；

变邻域搜索元启发式算法主要包括初始化、抖动、局部搜索和移动四个阶段；算法初始化阶段定义了一个初始解x与一组邻域结构Nμ,μ＝1,2,…,μmax；在算法抖动阶段，从初始解x的第μ个邻域中随机选择一个解x′；算法局部搜索阶段采用重定位算子从x′中产生一个新的解x″；若x″支配x，则x″将取代x成为新的初始解，反之，算法在移动阶段采用新的邻域结构Nμ重复上述过程；若所有邻域结构都不能使初始解得到进一步改善，则VNS元启发式算法停止震荡过程；

⑤算法迭代

重复②到④，直至满足算法最大迭代数；最终，基于变邻域搜索的混合多目标进化算法给出一组满足不同偏好的帕累托最优解。