基于高维多目标进化算法的露天矿卡车多目标调度优化方法

2156 编辑：中冶有色技术网来源：西安建筑科技大学

2022-08-12 15:00:40

权利要求

1.基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，包括如下步骤：

步骤1，根据露天矿实际生产调度建立主要指标体系；

步骤2，以运输成本最小、运输距离最短以及等待时间最小为目标，构建金属露天矿多目标调度模型；

步骤3，对NSGA-Ⅲ算法进行改进，得到基于距离支配关系的NSGA-Ⅲ算法；

步骤4，采用改进的算法对金属露天矿多目标调度模型进行求解。

2.根据权利要求1所述基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，所述步骤1中，首先获取露天矿的运输路网数据，包括各路段的距离及通行能力；其次，通过调取以往的实际生产数据获取矿山实际生产中装、卸载点的产量要求，实际的装、卸载所耗费的时间，最后，通过对原始的实际数据进行分析，得出空载状态及重载状态下的单位成本，以及日常维护的费用。

3.根据权利要求1所述基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，所述金属露天矿多目标调度模型如下：

F(X)＝Minimize(f1(X),f2(X),f3(X))

其中：

minf1(X)表示运输成本最小化，minf2(X)表示运输距离最小化，minf3(X)表示等待时间最小化，h表示回路个数，r＝1,2...,h，xrij表示回路r中从装载点i到卸载点j的重载运输次数，dij表示装载点i到卸载点j的距离，C1表示卡车重载运行状态下单位成本，yrji表示回路r中从卸载点j到装载点i的重载运输次数，C2表示卡车空载运行状态下单位成本，Kr表示第r个回路上卡车数量，T0表示班次时间，C3表示班次时间内卡车维修费用，Tz表示装载时间。

4.根据权利要求3所述基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，所述金属露天矿多目标调度模型还包括如下约束条件：

其中，约束条件(4)表示出矿点最小生产任务要求；约束条件(5)表示出矿点最大生产能力；约束条件(6)表示受矿点最小任务量要求；约束条件(7)表示受矿点最大生产能力；约束条件(8)表示卸载点矿石品位应该在允许范围内；约束条件(9)表示卡车数量限制；约束(10)表示在同一回路内保证车辆不拥堵的约束；

m表示装载点数目，i＝1,2,...,m，C表示卡车装载量，pi表示第i个装载点最小任务量，qi表示第i个装载点最大产出量，n表示卸载点数目，j＝1,2,...,n，gj表示第j个卸载点最小任务量，fj表示第j个卸载点最大承载力，Gi表示第i个装载点出矿品位，K表示卡车数量，ej表示第j个卸载点的品位需求，表示卸载点允许的品位波动偏差。

5.根据权利要求1或3或4所述基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，所述对NSGA-Ⅲ算法进行改进的方法如下：

在原始NSGA-Ⅲ算法中引入均匀分布的参考点，然后将参考点与原点连接形成参考线，计算所有个体到参考线的垂直距离，将个体与垂直距离最小的参考点关联；通过快速Pareto非支配排序形成非支配等级，然后按照由低到高的顺序加入归档集，在归档集种群规模大于N时，利用小生境选择技术使归档集种群规模为N，改进后使用距离支配关系对种群进行非支配排序，划分非支配层级。

6.根据权利要求5所述基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，所述距离支配关系是指，如果解X1距离支配解X2，即X1X2，则满足下列条件：

其中是个体X1到理想点的欧氏距离，是个体X2到理想点的欧氏距离，将欧氏距离作为适应度值来选择更优的解，表示两个候选解的目标值之间的夹角，即是每个候选解的所属小生境的大小。

7.根据权利要求5所述基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，所述设置为第(|P|/2)个最小夹角，以保证解集P中非支配解的比值总是在0.5，即，在非支配排序过程中，使得一半的种群处于非支配层级。

8.根据权利要求5所述基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，采用基于距离支配关系的NSGA-Ⅲ算法对多目标调度模型进行求解，具体求解过程如下：

Step 1确定种群规模，产生初始父代种群，每一个种群对应一条运行路径；

Step 2将父代群进行交叉、变异的遗传操作形成新的子代种群；

Step 3将父代种群与子代种群合并；

Step 4按照所述多目标调度模型，计算合并后种群中所有个体的目标值；

Step 5根据种群中每个个体的目标值按照距离支配关系进行非支配排序；

Step 6按照非支配层级由低到高的顺序加入归档集，到达临界层时采用小生境选择技术使归档集种群规模与初始种群规模一致；

Step 7判断是否满足设定的迭代次数这一终止条件，是则结束算法输出结果，否则转Step 2。

9.根据权利要求8所述基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，所述Step 5中，使用距离支配关系将种群个体按照目标值进行非支配排序，过程如下：

(1)根据目标函数f1(X)，f2(X)和f3(X)计算每个种群个体目标函数值，在初始化种群中，每一条运行的路径对应为算法中的一个个体；

(2)分别比较每一维目标函数值，选取每一维目标函数值的最小值作为理想点；

(3)计算种群中每个个体与其他个体之间的最小夹角，从而得出小生境大小并根据距离支配关系划分非支配层级。

10.根据权利要求8所述基于高维多目标进化算法的露天矿卡车多目标调度优化方法，其特征在于，所述根据距离支配关系划分非支配层级的方法是：

如果解X1与解X2之间的夹角小于小生境大小，则仅比较两个解到理想点之间的距离来判断非支配关系；如果两个解之间的夹角大于小生境的大小，则考虑能否在一定区间内保留到理想点较远的个体，进而保证种群多样性。

说明书

技术领域

本发明属于矿业系统工程及矿山优化技术领域，涉及露天矿车辆的智能调配，特别涉及一种基于高维多目标进化算法的露天矿卡车多目标调度优化方法。

背景技术

露天矿生产是集采掘、运输调度、破碎处理等一系列活动的大型生产系统，其中运输调度是整个生产系统的关键环节。矿车运输调度是一个涉及任务产量、生产能力、质量、设备利用率和资源问题的多目标系统，露天矿运输成本占露天矿生产成本的50-60％。根据实际生产需求建立优化调度模型，能有效降低企业的生产运营成本。从国内外来看，目前露天矿卡车运输调度的实际生产中，首先在优化规模上大多以小规模优化模拟实际生产，其次原有的单目标及多目标等露天矿调度优化模型，大多仅求解出从装载点在卸载点之间的次数，无法有效满足目前露天矿运输调度的实际需求。

发明内容

为了克服上述现有技术的缺点，本发明的目的在于提供一种基于高维多目标进化算法的露天矿卡车多目标调度优化方法，根据露天矿实际生产调度建立了主要的指标体，然后以运输成本最小和运输距离最短以及等待时间最小为目标，构建金属露天矿多目标调度模型，再对基本的NSGA-Ⅲ算法进行改进，最后采用改进的算法对金属露天矿多目标调度模型进行求解，最终可满足目前露天矿运输调度的实际需求。

为了实现上述目的，本发明采用的技术方案是：

一种基于高维多目标进化算法的露天矿卡车多目标调度优化方法，包括如下步骤：

步骤1，根据露天矿实际生产调度建立主要指标体系；

步骤2，以运输成本最小、运输距离最短以及等待时间最小为目标，构建金属露天矿多目标调度模型；

步骤3，对NSGA-Ⅲ算法进行改进，得到基于距离支配关系的NSGA-Ⅲ算法；

步骤4，采用改进的算法对金属露天矿多目标调度模型进行求解。

与现有技术相比，本发明在现有单目标调度优化模型的基础上，引入运输距离与等待时间最小两个目标，同时考虑了矿区道路的实际通行能力，构建露天矿的金属露天矿多目标调度优化模型。在早期研究中，优化调度主要采用线性规划、整数规划以及动态规划来优化调度问题。但是由露天矿调度换进复杂、需求多样，往往不能得到实际有效的结果，本发明提出的基于距离优势关系的NSGA-Ⅲ算法原理简单、容易实现，在求解过程中能有效保证解的多样性，并能够快速求解出满足要求的解集。

本发明针对矿区的实际生产需求，建立了完善的运输路径及运输车次模型，并能求出可行的解，降低运输成本有着重要的意义。

附图说明

图1是本发明中采用基于距离优势关系的NSGA-Ⅲ算法求解模型的流程图。

图2是本发明中的基于距离优势关系的示意图，能保证一定区域内相对收敛性较差但是多样性较好的解参与进化。

具体实施方式

下面结合附图和实施例详细说明本发明的实施方式。

本发明为一种基于高维多目标进化算法的露天矿卡车多目标调度优化方法，能够有效减少卡车调度过程中的运输距离和运输次数，进而显著降低企业的运输成本，并且在有效保证矿石品位的前提下能提高矿山的生产能力，显著提升矿山企业的经济效益，并且在模型构建过程中做出了路径规划和车流分配工作。

如图1所示，其主要包括如下步骤：

步骤1，根据露天矿实际生产调度建立主要指标体系，包括运输路网数据、生产指标要求、运算能力数据、成本等。

通过对露天矿的实际调研测度，首先获取露天矿的运输路网数据，包括各路段的距离及通行能力；其次，通过调取以往的实际生产数据获取矿山实际生产中装、卸载点的产量要求，实际的装、卸载所耗费的时间。最后，通过对原始的实际数据进行分析，得出空载状态及重载状态下的单位成本，以及日常维护的费用。

步骤2，根据矿山实际生产要求和指标，以运输成本最小、运输距离最短以及等待时间最小为目标，构建金属露天矿多目标调度模型如下：

F(X)＝Minimize(f1(X)，f2(X)，f3(X))

其中：

式中，目标函数(1)min f1(X)表示运输成本最小化；目标函数(2)min f2(X)表示运输距离最小化；目标函数(3)min f3(X)表示等待时间最小化；h表示回路个数，r＝1，2…，h，xrij表示回路r中从装载点i到卸载点j的重载运输次数，dij表示装载点i到卸载点j的距离，C1表示卡车重载运行状态下单位成本，yrji表示回路r中从卸载点j到装载点i的重载运输次数，C2表示卡车空载运行状态下单位成本，Kr表示第r个回路上卡车数量，T0表示班次时间，C3表示班次时间内卡车维修费用，Tz表示装载时间。

约束条件如下：

其中，约束条件(4)表示出矿点最小生产任务要求；约束条件(5)表示出矿点最大生产能力；约束条件(6)表示受矿点最小任务量要求；约束条件(7)表示受矿点最大生产能力；约束条件(8)表示卸载点矿石品位应该在允许范围内；约束条件(9)表示卡车数量限制；约束(10)表示在同一回路内保证车辆不拥堵的约束。

m表示装载点数目，i＝1，2，...，m，C表示卡车装载量，pi表示第i个装载点最小任务量，qi表示第i个装载点最大产出量，n表示卸载点数目，j＝1，2，...，n，gj表示第j个卸载点最小任务量，fj表示第j个卸载点最大承载力，Gi表示第i个装载点出矿品位，K表示卡车数量，ej表示第j个卸载点的品位需求，表示卸载点允许的品位波动偏差。

步骤3，对NSGA-III算法进行改进，得到基于距离支配关系的NSGA-III算法，改进的方法如下：

参考图2，在原始NSGA-III算法中引入均匀分布的参考点，然后将参考点与原点连接形成参考线，计算所有个体到参考线的垂直距离，将个体与垂直距离最小的参考点关联；算法保留了随机生成初始种群以后通过进化形成子代加入父代的协同进化的精英保留策略，通过快速Pareto非支配排序形成非支配等级，然后按照由低到高的顺序加入归档集，在归档集种群规模大于N时，利用小生境选择技术使归档集种群规模为N，改进后使用距离支配关系对种群进行非支配排序，划分非支配层级。

在原始的NSGA-III算法中，由于Pareto支配的限制，导致仅能从临界层选择过程中保留多样性较好的解，且这些解不一定作为相对较优的解保留到下一代种群中，因此提出一种距离支配关系提升解的多样性。距离支配关系结合小生境技术，不仅考虑到解的收敛性，同样使解的多样性得到了增强。具体来说，如果解X1距离支配解X2，即X1X2，则满足下列条件：