一种考虑可靠性指标的备件运送路径优化方法

2020-09-21陈浩然葛子阳

南京理工大学学报 2020年4期

赵瑞,陈浩然,葛子阳

(1.天津理工大学理学院,天津 300384;2.北京航空航天大学可靠性与系统工程学院,北京 100191)

保障系统在维持装备的正常使用中发挥了重要作用,也就是说在装备使用时保障系统需要能够保障其正常运行操作,并且一旦装备发生故障,能够及时修复。为使保障系统发挥其作用和功能,需在保障组织中开展相应的保障活动,合理地运用保障资源,以保证保障系统功能正常执行。

在保障资源中,备件资源非常重要,直接制约着装备系统的战备完好性和持续作战能力。在备件保障活动中,备件在各级不同站点间如何合理地进行流转是一个研究的热点问题。优化备件保障过程,可以减少备件缺货量、提高备件供应水平、降低备件缺货损失。对于备件供应保障,李文等[1]给出了备件保障中心可靠度的概念以及量化方法,并提出了基于可靠度的备件保障中心多目标选址模型;翟亚利等[2]建立了考虑维修时间的随舰备件保障概率模型与串联系统的基于使用可用度的系统备件配置优化模型,给出了随舰备件配置优化算法;Liu等[3]分析证明了增材制造技术可以有效提升备件供应的动力,降低运输费用及供应时间;Tiacci等[4]分析验证了通过平行供应来降低备件供应时间的情况;Braglia等[5]建立了一种有效快速的方法挑选出适用具体情况的备件优化模型;Wang[6]认为备件的保障水平是影响保障资源延迟时间的主导因素。

Dantzig等[7]在1959年首先定义了车辆的路径规划问题(Vehicle routing problem,VRP)。Baker[8]首先研究了带时间窗的车辆调度问题。Padberg[9]利用切平面法求解大型旅行商问题。Beheshti等[10]研究了带软时间窗的车辆调度问题。Savelsbergh等[11-12]证明了车辆的路径规划是一个NP难题,传统方法很难求得最优解。遗传算法[13]、蚁群算法[14]等启发式算法及其改进算法[15-17]被广泛地应用于求解该问题。

近年来,研究人员对于备件供应路径优化问题进行了探索[18-19]。文献[18]和文献[19]均设站点需求量为确定值,并且把满足站点需求作为装备保障性的约束条件,没有考虑到通常情况下站点需求量是随机变量,而且没有考虑备件供应系统的其他重要保障性指标。本文对单车辆备件运输路径优化问题进行研究,分析影响备件运输路径的保障性及可靠性指标,考虑维修站点需求是随机变量的情况,以机会约束规划[20]的思想进行建模,并且设计混合智能算法对模型求解。

1 模型构建

1.1 问题描述

在备件供应系统中,当某站点的装备运行发生故障时,备件库为该站点供应新的备件。出现备件需求的站点需要及时得到供给,使得整个系统的保障性可以得到满足,减少由于备件短缺造成的损失。由于供应体系的运输能力有限,选择合理的路径是提升保障效率的关键,建模需考虑装备保障性约束和保障费用的情况下选择合适的运输路线。

1.2 模型假设

对于保障区域较小、维修站点较少的备件供应保障系统,一个备件库就能够满足所有站点的备件供应,在此条件下,对问题做出以下假设:

假设1各维修站点的需求量是随机变量,并且维修站点需求相互独立。

假设2备件库和维修站点的运输路径是直线连接,运输费用只和站点之间距离有关,道路是可以双向行驶的。

假设3各站点的重要等级是相同的。

1.3 符号说明

模型使用的基本符号和含义如下:i为i=1,2,…,n,表示基层级站点;i=0表示备件库;d(i,j)为站点i,j之间距离;x1,x2,…,xn为1到n的全排列;c1为单个备件订货成本;c2为单位距离成本;yi为站点i的分配运输量;ξi为站点i的备件随机需求数;l为惩罚系数;αi为站点i短缺率的置信水平上限;Di为站点i供应延迟时间上限;V为运输车速度;Ni为站点i的设备数目;Z为每台设备安装备件数;Ai为站点i的供应可用度下限;A0为系统整体可用度下限;βi为供站点i应可用度的置信水平下限;γ为系统整体可用度的置信水平下限。

1.4 单车辆备件运输路径优化机会约束规划模型

1.4.1 决策变量

模型以运输路径x1,x2,…,xn(1到n的全排列)和站点的分配运输量yi(i=1,2,…,n)为决策变量。

1.4.2 目标函数

订购费用

(1)

运输费用

(2)

式中:l作为一个惩罚系数,表示不同情况下,由于备件延误导致的损失;运输车从站点i到达i+1这段路径的运输费用与路径长度正相关,也与站点i的保障概率相关。

目标函数

minC1+C2

(3)

1.4.3 约束条件

保障系统包含保障站点和备件两个重要的部分,装备的战备完好性和持续作战能力都会受到这两个部分的影响。本文考虑的重点是保障站点的备件供应过程,战备完好率、使用可用度、平均保障延误时间、能执行任务率、备件保障概率、供应可用度等指标作用于评价备件保障方案时,都会影响决策者对备件保障方案的选取。以优化备件库到各站点的运输路径和备件运输量为模型目标,对上述指标进行筛选,其中保障延误时间用于描述需求站点的备件等待时间,这一指标对路径的选择有极大影响;备件保障概率、供应可用度都可用于度量站点的装备保障任务完成情况,对于备件运输量的优化有直接影响。

选用备件保障概率、供应可用度和保障延误时间作为模型的约束条件,使得备件发生短缺时,能够维持系统保障性在一定水平。由于站点的需求量是随机变量,不能直接比较大小,此时采用如下的原则:允许事先所做的决策在一定风险程度中不满足约束条件,但要设置一定的置信水平,使得约束条件成立的概率有一个评判的阈值,在此原则下建立的模型称为机会约束规划模型。求解机会约束规划时,各项指标符合要求的置信水平都要大于等于预先规定的值,把机会约束转化为各自的确定约束,然后求解其等价的确定性模型。下面对约束进行描述。

(1)备件保障概率。当备件库对站点的供给量yi小于站点的需求量ξi时就会发生备件短缺,式(4)保证维修站点i的备件需求ξi不能够得到满足的置信水平要不大于αi。

1-Pr{ξi≤yi}≤αii=1,2,…,n

(4)

(2)平均保障延误时间。平均保障延误时间主要包含3个方面的延误时间:等待备件、维修人员及保障设备造成的延误时间。除去人为因素,备件保障概率和描述备件供应速度的平均供应反应时间TSR是影响平均保障延误时间的主要因素,式(5)表示平均保障延误时间不超过Di。

(1-Pr{ξi≤yi})TSR≤Dii=1,2,…,n

(5)

式(6)表示站点i的平均保障延误时间不超过Di。

i=1,2,…,n

(6)

(3)供应可用度。在实际应用中,站点的供应可用度指在任意时刻站点处于可工作或者可使用状态的程度,表示为未因任何备件短缺而停机的装备数量所占装备总数百分比,式(7)是站点i的供应可用度。

(7)

站点i的供应可用度不低于Ai。运用机会约束的思想,要求站点i的可用度能够得到满足的置信水平要大于等于βi,式(8)是保证维修站点i的供应可用度要求。

(8)

式(9)为系统整体可用度,要求系统可用度A0能够得到满足的置信水平要大于等于γ。

i=1,2,…,n

(9)

于是可建立单车辆备件运输路径优化机会约束规划模型

(10)

2 混合智能算法

由于式(10)的模型中含有关于随机变量的函数,无法直接求解,因此本文设计了随机模拟来求解,将其嵌入遗传算法形成了混合智能算法。在生成染色体时,采用混合编码。染色体分为两部分,第一段采用整数编码,对应站点的排序;第二段采用实数编码,对应站点备件供给量。在后续的选择、交叉、变异操作中染色体不同的部分分别单独进行操作。在这里选择的交叉策略是在其中一段的运算结果收敛后,再调整另一段,不断循环,直到整体收敛。

具体步骤如下:

步骤1初始化产生若干染色体,采用随机模拟方法检验染色体是否能够满足提出的约束条件;

步骤2对染色体进行交叉和变异操作;

步骤3计算染色体的目标值;

步骤4根据染色体的目标值计算每个染色体适用度;

步骤5采用旋转赌轮方法选择染色体;

步骤6重复步骤2到步骤5,直到完成给定的循环次数;

步骤7选择效果最好的染色体作为模型的最优解。

3 算例验证

应用本文提出的单车辆备件运输路径优化机会约束规划模型对某备件供应保障系统进行算例分析,用以验证上述模型方法的适用性与可操作性。关于单车辆备件供应情况,将采用下列供应保障系统,不计出发点共计9个站点。已知备件订购成本为6,单位距离成本为1。备件需求量为服从泊松分布的随机变量,各站点参数如表1所示。采用本文提出的混合智能算法求解,可得到图1所示的运输路径优化结果,各站点运输量见表2。在图1中,点0代表备件库,最小总费用为2 998。