基于启发式算法求解电动汽车碰撞测试排程问题

曹剑雕 陈淮莉

(上海海事大学物流科学与工程研究院 上海 201306)

0 引 言

汽车碰撞测试是汽车生产中的重要一环,其结果往往作为验证和提升汽车质量的重要考量。消费者也常以此作为购买依据。但是由于碰撞测试的破坏性,使它们的调度既特别重要又受到限制。测试调度过程希望能最大限度地提高车辆的利用率,即安排在同一辆测试车的测试尽可能多以使被毁坏的车辆数量最少,从而增加可用于其他用途或测试的未损坏部件的供应。

在汽车碰撞测试方面,国内研究较少,蓬勃发展的电动汽车也为测试提出了新要求。我国研究此类问题主要还是从整车的结构框架设计要求出发。Sun等[1]研究了新能源汽车发展过程中碰撞的结构性能。为了使新能源汽车不少于传统燃料汽车乘员保护性能,认为需要关注的加强和优化结构,如复发纵梁、横梁面前、侧板b、阈值和上肢的刚度。Zhang等[2]根据燃油车和电动汽车的区别,对碰撞测试中的汽车电池的安放位置上提出一些建议。

相较于国内,国外研究比较深入,在汽车碰撞测试方面,国内研究较少,国外则比较深入,Garey等[3]证明了机器数量不确定并行机调度属于NP-Hard问题。而后有学者将碰撞测试调度问题看作是典型的装箱和并行机器调度问题的混合,Garey等[4]研究将不同尺寸的物品装入容量有限的箱子中,并确定所需箱子的最小数量。在此基础上,Elhedhli等[5]则提出了一种具有项目间冲突的装箱问题。作者给出了该问题的集划分公式,并提出了一种分枝定价算法,将定价问题作为一个有冲突的背包问题来解决。在碰撞测试调度的背景下,研究人员努力将各种理论方法和技术扩展到实际应用中。Kravchenko等[6]以最大限度地减少机器的数量为目标,同时满足项目的时间窗要求。使用一种两阶段的方法,首先使用一个时间索引公式来形成项目序列,然后使用启发式方法把项目分配给每台机器。Bartels等[7]考虑将建立原型车辆作为决策的一部分,并将问题描述为混合整数规划(Mixed Integer Programming,MIP)模型。Limtanyakul等[8]提出了一种使用MIP和约束规划(Constrained Programming)的混合模型安排碰撞测试;他们使用MIP来估计原型车的需求和CP来寻找一个完整可行的时间表,然而,这些削减纯粹是组合的,可能会导致缓慢的收敛。冯忠魁等[9]考虑原型样车可用性,测试优先顺序和资源能力等方面的约束,采用约束规划来求解测试排程问题,Lockledge等[10]应用多阶段数学规划模型来求解原型样车排程问题。算法上,Lin等[11]将提出的迭代混合遗传算法与禁忌搜索和蚁群算法做了比较。Liu[12]提出了一种新颖的混合遗传算法(HGA),用于确定性调度问题,多个不相关的并行机上处理具有任意优先级约束的多个作业。

综上所述,汽车测试问题上,多以最少数量原型车作为目标函数,在求解策略和算法上有较深入的研究,少有将碰撞测试作为特定研究对象。本文将原型车测试当中的碰撞测试为研究对象,首先使用整数规划(Integer Programming)模型将碰撞测试聚合成组。将分组的碰撞视为单个测试,而后通过混合贪心策略的启发式算法将符合测试排程要求的测试安排到原型车,在求解上,分别使用以上方法和约束规划(Constrained Programming)求解,分析两种方法的性能。

1 问题描述

1.1 问题概述

电动汽车碰撞测试具有破坏性,通常安排在一般测试之后,某些测试项目损坏程度高,往往一辆车只能安排这一项测试,非其测试时间段则空闲,测试项目中不同测试速度下不同接触面测试比例较多,可提前设置其兼容性要求,减少车辆的损坏。

传统原型车车辆测试如图1所示,图1中间的横线表示m辆的原型车,用来测试右边表示n项测试。图左表示的是L个样车变体,这是因为不同的测试要求所造成的,另外是为了了解各个零部件之间最好的搭配和协调。在测试中,为了贴合实际,将原型车的可用、准备时间、可用时间、各项测试的时间因素,测试要求等考虑。建立模型,使得所有的测试都能在截止时间内有序地安排在符合要求的原型车上。

图1 原型车测试示意图

本文研究的是新能源汽车中的电动汽车碰撞测试问题。电动汽车普遍采用的是高密度电池模块来代替燃油。一般来说,汽车在进行各种测试前,无论是燃油车还是电动车,其动力系统应该是最先准备好的,在电动汽车中电池作为一个模块已经通过了各项安全的要求,但是在整车实验和现实中电动汽车发生自燃的现象来看,往往是因为在汽车发生碰撞时电池部分受损引起的,因此,在碰撞测试中考虑电池因素很有必要,更符合实际情况。

1.2 问题假设

(1) 测试一旦开始就不能中断。

(2) 测试的有关时间都是已知的。

(3) 任意时刻任意原型或者变体只能执行一项测试。

(4) 不存在特殊优先关系的约束之间具有同等优先级。

(5) 每一项测试的执行时间具有不确定性,且该测试执行时间与测试顺序无关,测试顺序都将以最后的优化调度结果给出。

(6) 各项测试之间的转换时间忽略不计。

(7) 每辆原型车最多匹配一个变体,凡使用一辆原型车或者是变体车都可以视为使用了一辆原型车。

本文主要研究的是新能源汽车中的电动汽车碰撞测试问题。电动汽车与传统汽车最大的不同就是动力源的不同。电动汽车普遍采用的是高密度电池模块来代替燃油。这样的改变也将对碰撞测试提出新的要求。一般来说,汽车在进行各种测试前,无论是燃油车还是电动车,其动力系统应该是最先准备好的,在电动汽车中就是电池作为一个模块已经通过了各项安全的要求,但是在整车实验和现实中电动汽车发生自燃的现象来看,往往是因为在汽车发生碰撞时电池部分受损引起的,因此,在整车碰撞测试后,对电池进行一些测试很有意义和很有必要的。本文结合了传统燃油汽车的碰撞测试经验与电动汽车的特点进行深入研究。

1.3 聚合测试组整数规划参数设置及模型

T是碰撞测试项目的集合∀t∈T={1,2,…,n}。

I是原型车的集合∀i∈I={1,2,…,m}。

ut1.t2,i∈{0,1},取值为1时,表示t1、t2安排在同一辆车,且t1在t2之前测试,取0则为其他情况。

Ei是所有类似于{t1,t2}的集合,并且不符合测试的各项要求,比如:在碰撞测试中,速度高的测试应安排在速度低的测试之前,是因为速度高的测试项目损坏程度可能会影响到后续速度低的测试。

(1)

s.t.

(2)

(3)

ut1,t2,i=0,{t1,t2}∈Ei,i∈I

(4)

ut1,t2,i∈{0,1},t1,t2∈T,i∈I

式(1)是最大数量碰撞测试组;式(2)保证每个测试至少与另外一个安排在同一辆原型车上,同时保证每一对测试最多安排在一辆车;式(3)确保每一辆原型车至多使用一次;式(4)加强兼容性要求。

此模型主要考虑的汽车碰撞测试项目中测试匹配原则较多,如上所述速度高低不同下的碰撞毁坏程度不同,能在一定程度上降低汽车损伤。为了成对匹配的数量最大化,可以迭代多次使更多的单个测试匹配起来,提高求解效率。求出测试匹配集合后需要更新匹配集的各项数据。设测试匹配集tG=(t1,t2,…,tn),ptG、dtG、rtG分别为处理时间、截止时间、投放时间。

rtG∶=dtG-ptG;

fori=n-1:1do

rtG∶=min{dtI,rtG}-ptI

end

2 启发式算法

启发式算法的定义为一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。电动汽车碰撞测试问题一定程度上也属于NP-hard 问题,因此采用一种混合贪心策略的启发式算法,使测试项目在贪心策略下通过启发式算法安排到原型车上,该算法综合利用了贪心算法和启发式算法特点。

2.1 参数设置

T(与1.3节不同)是碰撞测试匹配集tG的集合tG=(t1,t2,…,tn),将单个匹配集视为单个测试项目。

I(与1.3节不同)是已经安排有测试集的原型车的集合∀i∈I={1,2,…,m}。

V是样车变体的集合∀v∈V={1,2,…,i}。

M是原型车数目。

N是测试数目。

E是不相容测试集的集合。

pt为测试t的处理时间。

dt为测试t的最后期限。

rt为测试t的投放时间。

ai为第i辆汽车的准备时间。

Ct为测试t的完成时间。

st为测试t的开始时间。

2.2 贪心-启发式算法

贪心-启发式算法代码如算法1所示。

算法1贪心-启发式算法

%将原型车集合I可用时间降序排列

%将测试项目集合I处理时间降序排

Foreachi∈Ido

Foreacht∈Tdo

Ifi有可用时间 then

Ifi上可用时间满足测试t,则将t安排在i上;

End

Else

If 排程可满足问题是可行的,则t安排在上;

End

End

End

从测试集T中移除已经分配的测试;

在i′∈I中找出最少可用时间的,这样i′上的测试集可以重新分配给i;

Ifi′≠ithen

将所有测试从i重新分配到i′;

在I中调换i和i′的位置;

End

End

该算法的核心思想是尽可能每次都将测试安排到已使用的原型车上,并且符合测试排程要求,从而提高车辆的利用率达到减少使用原型车的数量的目的。

2.3 测试排程满足模型

当在贪心启发式算法中将每项新测试安排到原型车时,基于测试之间的兼容性关系和单个测试发布日期和截止日期,必须确定是否存在可行的排序,为了有效地解决这个问题,提出一个全整数规划模型来求解排程的可满足性问题。在实际求解CP问题中,往往将约束传播算法与搜索策略相结合。这样能够加快求解的效率。

it1.t2∈{0,1},取值为1时,表示t1、t2安排在同一辆车,且t1在t2之前测试,取0则为其他情况。

Zi.v∈{0,1} ,取值为1时,表示第i辆原型车匹配第v个样车变体,,取0则为其他情况。

(5)

s.t.

st1+pt2≤st2+M(1-it1.t2)

(t1,t2)∈T*T,t1≠t2

(6)

it1.t2+it2.t1=1 (t1,t2)∈T*T

(7)

it1.t2=0 (t1,t2)∈E

(8)

st≥rtt∈T

(9)

st≥ait∈T,i∈I

(10)

st+pt≤ct≤dtt∈T

(11)

it1.t2∈{0,1}st≥0

式中:T*T表示的是分配在同一辆车上测试的集合。

式(5)为目标函数,为最小数量原型车,将决策变量原型车与变体联系起来,每使用一辆变体相当于使用一辆原型;式(6)通过使用大M公式对被分配给同一车辆的测试执行成对排序关系;式(7)表示的是安排在同一辆车上进行的测试只执行一次;式(8)加强测试兼容性要求,加快求解时间。式(9)至式(11)确保测试在时间窗口内进行,测试在预定时间内完成。

2.4 约束规划模型

此模型参数与前文一样,在此不赘述。

(12)

s.t.

Xi.t≤Zi.vi∈I,t∈T

(13)

(14)

xi.j=xi.ki∈I∀j.k∈Tj≠k

(15)

at1+pt1≤at2+M(1-it1.t2)

(t1,t2)∈Tt1≠t2

(16)

it1.t2+it2.t1≤1 (t1,t2)∈Tt1≠t2

(17)

itlows,thighs=1 (tlows,thighs)∈T

(18)

it正,t侧=1 (t正,t侧)∈T

(19)

pt≥ait∈T,i∈I

(20)

rt+pt≤ct≤dtt∈T

(21)

xi.t∈{0,1},it1.t2∈{0,1},st≥0

式(12)为目标函数,为最小化最晚完工时间;式(13)将决策变量X原型车与变体V联系起来,每使用一辆变体相当于使用一辆原型;式(14)确保每一项测试集都被分配到车辆进行测试;式(15)表示的是安排在同一辆车上进行的测试集;式(16)和式(17)通过使用大M公式对被分配给同一车辆的测试集执行成对排序关系;式(18)和式(19)表示分配到同一辆汽车的碰撞测试集,低速碰撞集必须安排在高速碰撞集之前,正面碰撞集也必须安排在侧面碰撞集之前,这样直接设定碰撞测试中的某些测试排程顺序能够极大地减少搜索时间,加快可行解的求解时间。式(20)至式(21)确保每次测试在其时间窗口期间执行以及一些变量值域。

3 算例及结论

选取某电动汽车碰撞测试的24项测试项目为例。有关于24项测试项目的相关数据如表1所示。原型样车准备好的时间都为0,能够完成每项测试t的测试车辆集合如表2所示。除此之外,测试之间还存在一些要求。

表1 某车型24项碰撞测试数据

续表1

表2 测试与可用样车变体集合表

1) 测试当中的第8、第9、第10项测试不能放在同一辆车上进行测试。

2) 测试当中的第19、第20项测试必须放在同一辆测试。

3) 测试当中的第4项测试优先于第7项测试,并且必须安排在同一辆车上进行测试。

给定原型车数量6,编号分别为(i1,i2,…,i6)。将这个值作为CP模型中的原型车数量参数,其相应的准备时间为(0,2,4,2,5,3)。表3为样车与变体之间的关系。

表3 样车与变体关系

在MATLAB中求解该案例,排程方案如表4所示,分析表4, 24项测试被合理地安排到编号为i1、i2和i6上,与图2原型车的1、2和3对应。原型车数量为6,减少了一半,完成时间为36 d,达到测试要求。整个测试车辆的平均利用率超过70%,属于高利用率。之后使用CP约束规划方法对同问题进行求解,得出的结果在原型车数量和完工时间上相同,证明此算法在电动汽车碰撞测试排程问题上的有效性。

表4 某车型24项碰撞测试排程方案 单位:d

图2 某车型24项碰撞测试排程甘特图

现有文献多以汽车一般测试作为研究对象,碰撞测试是整个汽车测试的重要环节,因其破坏性一般安排在所有测试之后,特选取某新车型20项汽车测试数据如表5所示,在是否使用本文模型算法情况下来分别求解进行分析。

表5 某新型车辆20项测试数据

由表6可知,在使用本文算法和模型情况下,测试时间比没有使用本文算法和模型下缩短了4 d,在原型车数量上,由5减少到3。

表6 求解结果

以上数据规模较小,为了验证算法的普遍适用性,扩大数据规模进行分析,数据如表7所示并使用CP求解。

表7 数据集信息及CP求解结果

为了更好地体现算法特点,将是否使用聚合碰撞测试模型进行分别求解,求解结果如表8所示。

表8 求解结果数据

通过分析表7和表8,可以得出以下几个结论:(1) CP约束规划在求解较大规模数据时不能在规定时间内找到可行解,本文算法则都能快速求得可行解;(2) 实际原型车数量使用与碰撞测试数呈正相关关系,符合实际情况,相对原给定原型车数量,实际使用数量有大幅下降;(3) 在两种可求解到可行方案方法中,未对碰撞测试进行聚合的求解速度是较快的,对碰撞测试进行启示在实际测试中,启示应该尽可能完善匹配测试集,减少匹配时间;(4) 对碰撞测试进行聚合的情况下,求解较慢,但减少实际原型车数量较多。

4 结 语

本文主要是研究电动汽车碰撞测试排程问题,考虑电动汽车特点和碰撞测试的具体内容,测试之间的兼容性比较多,在模型和算法设计中进行体现,将单个测试项目聚合成测试集,得到新的测试集数据,而后采用贪心启发式算法对满足测试排程要求测试进行排程。通过实例证明本文算法在电动汽车碰撞测试排程问题上的有效性和可行性。对于后续的研究,可进一步优化测试匹配集的细节同时将测试的不确定性情况考虑进来,使模型更加完善。