行驶时间区间不确定的装配线物料配送路径规划

张家骅 李爱平 刘雪梅

1.同济大学机械与能源工程学院，上海，2018042.无锡工艺职业技术学院机电与信息工程学院，宜兴，214206

0 引言

准时化物料配送对企业降低生产成本、提高生产效率有重要意义。物料配送中的车辆路径规划问题是一个重要决策问题，近年来受到学者关注[1]。

文献[2-4]对装配线物料配送路径规划问题进行了研究，表明装配线物料配送路径规划模型可以按带时间窗的车辆路径规划问题进行建模与求解。吴倩云等[5]在此基础上进一步考虑了物料在配送车辆上的三维装载约束。

上述研究考虑了配送车辆行驶时间确定的情况，但在变速箱装配线等生产中，零件由配送员驾驶拖车同时对几条装配线进行配送，该配送方式并不能精确控制拖车速度和行驶路线，车间中工作人员和货物往来频繁，更增加了配送车辆行驶时间的不确定性。不确定行驶时间增加了物料不能准时送达工位的风险。KORYTKOWSKI等[6]研究发现物料能否准时送达对装配线生产性能有重要影响。TURNQUIST等[7]、VONOLFEN等[8]采用配送车辆行驶时间服从随机概率的方法研究装配线物料配送问题。李晋航等[9]对装配线中配送车辆运输时间等不确定信息进行模糊化处理，建立了混流装配线配送路径的模糊机会约束规划模型，并采用遗传算法进行了求解。然而实际生产中车辆不确定运行时间的概率分布或模糊隶属函数可能难以获得，使上述方法的应用受到了限制。

近年来，考虑不确定信息区间分布的鲁棒优化方法快速发展[10-11]，该方法不需要预知不确定信息的具体概率分布或模糊隶属度函数，只需知道信息的区间范围，这一方法在多个领域已经被广泛研究和应用，包括应用于经典的车辆路径规划问题。SUNGUR等[12]首次采用鲁棒优化方法研究了服务点需求不确定的车辆路径问题，建立了该问题的混合整数规划模型。BRAATEN等[13]针对鲁棒车辆路径优化问题的计算复杂性，提出了一种启发式方法。HU等[14]针对车辆行驶时间和服务点需求不确定的鲁棒车辆路径问题，引入路径相关不确定参数，建立了优化模型，并设计了一个两阶段智能求解算法。MUNARI等[15]研究了车辆行驶时间和服务点需求均不确定的鲁棒车辆路径问题，设计了分支定价割平面求解算法。刘洋等[16]研究了养护时间不确定的养护车辆鲁棒路径规划问题。目前未见有关鲁棒优化方法在装配线准时化物料配送车辆路径规划中的应用。

本文针对行驶时间不确定的装配线物料配送车辆路径规划问题，采用鲁棒优化方法，引入路径相关不确定参数，建立行驶时间区间不确定的装配线物料配送路径规划模型，并设计了求解该模型的混合遗传算法。

1 问题描述及模型建立

1.1 确定行驶时间的路径规划数学模型

装配线物料配送路径规划问题可以描述为：已知图G=(V，A)，V={0，1，…，n}是工位节点集合，0表示物料配送中心，所有配送车辆从配送中心0出发，完成配送任务后返回配送中心，进行下一次配送；A表示工位节点之间的弧。已知配送车辆数目为K，负责对n个工位进行物料配送，每个工位只能由一辆车服务；每辆车的最大载重Q，车厢是三维矩形(长L、宽W、高H)；第i工位的物料需求质量为qi(i=1，2，…，n)，需ai个标准料箱来运送物料，第a个料箱尺寸为lai、wai、hai(a=1，2,…，ai)；车辆需满足最大载重量约束，每个工位所需物品放入同一辆车，料箱尺寸满足车厢尺寸约束；车辆在第i工位的服务时间是ui；第i个工位的服务时间窗为[ei，bi]，如果车辆早于ei到达，则车辆进行等待；晚于bi到达则被拒绝。

问题目标是在满足约束的条件下寻找合理的车辆路径，以达到车辆总行驶距离的最小化：

(1)

(2)

(3)

(4)

(5)

(6)

∀k∈{1,2，…,K}p∈{1,2，…,n}

(7)

∀i∈V{0}a∈{1,2，…,ai}

(8)

sik+ui+tij-M(1-xijk)≤sjk

(9)

ei≤sik≤bi

(10)

xijk∈{0,1}yik∈{0,1}

目标函数式(1)表示最小化行驶距离，dij表示工位i到工位j的距离，xijk是决策变量，xijk=1表示车辆k从工位i驶往j。约束式(2)～式(5)分别表示有K辆车离开配送中心、每个工位正好被访问一次，以及进入和离开每个工位组只有一辆车，式中yik是辅助决策变量，yik=1表示工位i采用车辆k配送。约束式(6)保证车辆行驶线路的连通性。式(7)是料箱在车厢内的尺寸约束，xai，yai，zai表示的是工位i所需料箱a在车厢中的左后下角的坐标，坐标系原点位于车厢内侧左后下角顶点，即首个料箱左后下角摆放的位置顶点。式(8)是每辆车的装载容量限制。约束式(9)要求由同辆车配送的两个工位，只有配送完前一个工位，车辆行驶到后一个工位后，才能执行配送，sik为车辆k在工位i服务开始时间，ui为车辆在工位i的服务时间，tij为车辆从工位i到工位j的行驶时间，此处该时间是确定的，M是一个大的正数。式(10)是时间窗约束。

1.2 不确定行驶时间的路径规划模型

θ=0，Λk=0，表明车辆k路径中任一弧上的行驶时间均不发生波动；θ=1，Λk=|Ak|，表明车辆k所在路径中的所有弧的行驶时间都发生波动。根据鲁棒优化原理[17]，当每条路径中最多|Ak|段弧发生波动时，解仍然是可行的，说明该解是鲁棒的。

定义si,k,γk是第k条路径有γk条弧上的行驶时间发生波动的情况下车辆k在工位i的最差服务开始时间，该值可以通过下式计算得到：

(11)

其中，当i是物料中心即i=0时，车辆服务开始时间不受不确定性的影响；当i是物料需求工位时，分两种情况：①如果γk=0则表示弧上没有行驶时间发生波动，车辆最差服务开始时间等于行驶时间确定情况下的值；②如果γk≠0则车辆在工位i的最差服务开始时间与该工位的时间窗的下限、上一个工位已经达到最差服务开始时间或本工位达到最差服务开始时间相关。

按照上述分析，不确定行驶时间的路径规划模型只需要在上一节确定行驶时间的模型基础上，根据式(11)对式(9)和式(10)修改为

si,k,γk+ui+tij-M(1-xijk)≤sj,k,γk

(12)

∀i,j∈Vk=1,2，…,Kγk=0,1，…,Λk

(13)

∀i,j∈Vk=1,2，…,Kγk=1,2，…,Λk

ei≤si,k,γk≤bi

(14)

其余公式均保留不变。

2 混合遗传算法

传统的车辆路径问题被证明是NP-hard问题，本问题在传统车辆路径问题上，还需考虑时间窗，三维装载和不确定行驶时间约束，求解更加困难。智能算法是求解该类问题的主要方法，其中遗传算法被认为是最有效的求解方法之一，但单纯的遗传算法存在早熟收敛、易陷入局部最优的缺点[18]。已有研究表明，模仿鸟类飞行行为的莱维飞行可以扩大算法的搜索范围，帮助算法及时跳出局部最优[19-20]。传统的莱维飞行不能直接应用于离散优化问题，文献[21]针对旅行商问题提出一种离散莱维飞行，通过控制莱维飞行的步长来实现不同弧之间的局部搜索。本文针对所研究的问题，在上述文献的基础上，设计了另一种离散莱维飞行来增强算法的搜索能力。

图1是算法流程图，首先利用遗传算法快速找到可行解，然后通过离散莱维飞行对可行解进行局部搜索，改善解的质量。

图1 算法流程图

2.1 初始种群与适应度值评估

染色体采用自然数编码方式，自然数1,2，…,n代表工位数，0表示配送中心，车辆数K已知，可表示长度为n+K+1的向量(0，i11，i12，…，i1s，0,i21，i22，…，i2t，…，0，iK1，iK2，…,iKw，0)，其中ikj表示第k辆车服务的第j个工位的工位号。图2所示染色体表示2辆车对7个工位进行物料配送。为增加种群的多样性，按种群规模，采取随机法生成初始种群。

图2 染色体示例

根据染色体的基因值，可直接解码得到车辆的行驶路径。由图2所示染色体可得第一辆车的行驶路径是0-1-3-7-0，第二辆车的路径是0-2-4-5-6-0。根据车辆路径，可计算出第k辆车的行驶距离fdk，第k辆车的载重fqk。按照式(11)可得在不同θ下每辆车经过工位i的最差可能服务开始时间si,k,Λk。

染色体中每辆车访问过的工位可以进一步解码为(rai，xai，yai，zai，lai，wai，hai)，rai是工位i中料箱a的叠放顺序。按照料箱放置从下到上、从前到后、从左到右的规划，可以得到每辆车料箱的最终xk、yk、zk。

由以上得到的结果，可以计算出适应度值：

其中，M用来对违反约束进行惩罚。

2.2 遗传算子

轮盘赌选择就是按照适应度值计算染色体在子代中出现的概率，该方法适用于求解最大化问题，如果求解最小化问题，则需要对适应度值函数进行转化，而采用锦标赛选择可以避免此类问题并获得更好性能[22]。由于本文研究最小化问题，故采用锦标赛选择，每次从种群中随机抽取两个染色体，选择其中最好的一个进入子代种群。交叉算子采取类PMX交叉过程，若得到的子个体不合法，则通过调整0代码的位置来使染色体可行[9]。变异算子采用交换两点基因值策略[23]。

2.3 离散莱维飞行

式中，β∈[1, 2]，β一般取值为1.5；Γ(·)表示伽马函数。

文献[20]针对旅行商问题提出了一种离散莱维飞行，通过λ控制邻域搜索，实现解的更新。本文据此设置莱维飞行策略如下：如果λ≤1，则随机选择一条路径，对路径内的任一段基因序列进行逆转，实现短距离的莱维飞行；如果λ>1，则随机选择两条路径，对其进行2-opt*交换[24]，实现在路径间的邻域搜索。图3和图4是离散莱维飞行的两种不同方式的示例。

图3 路径内飞行

图4 路径间飞行

最后，将离散莱维飞行后的种群与原种群进行比较，将目标值较小的染色体保留形成新的种群，进行下一次进化，直到满足迭代要求。

3 案例分析

3.1 算法对比

文献[3]针对16个工位、6辆配送车辆的总装线物料配送路径规划问题提出了一种遗传算法进行求解，具体数据见文献[25]。针对文献[3]的问题，采用其模型和算法参数，在MATLAB平台上使用本文所提算法对该案例进行了计算，结果如表1所示。从表1中可得，本文的算法能够得到比原算法更优的结果，这主要是由于采用离散莱维飞行后扩大了算法的搜索空间，说明本文提出的算法改进策略有效。

表1 不同算法结果的对比

3.2 实例描述

某变速器装配车间由变速器总成装配线、制动器分装线、输入轴和离合器分装线、后盖分装线和主箱体分装线组成，车间共有9个物料需求工位。物料配送由2辆相同的拖车执行，拖车参数见表2。表3所示是物料使用的4种不同规格的料箱尺寸。表4所示是工位的物料需求量和需求时间窗。表5所示是工位间的距离与行驶时间，其中行驶时间用区间数表示。各物料需求工位的服务时间是1 min。

表2 拖车规格参数

表3 标准料箱规格参数

表4 各工位货物需求量和时间窗

表5 各工位间行驶距离和行驶时间

算法参数设置如下：种群规模100，交叉概率0.8，变异概率0.2，终止迭代次数100。

3.3 实例结果分析

为了分析θ对结果的影响，计算θ为0、0.1、0.5、1时的结果。θ=0表示结果不考虑不确定的影响，θ为0.1、0.5、1分别代表结果考虑低、中、高3种不确定程度。图5是不同θ下的目标值收敛曲线，表6所示是具体路径方案和目标值。从图5中可得，θ值越大，目标值收敛速度越快，这是由于随着考虑不确定程度增加，可满足约束条件的解越少，使问题可行解对应染色体空间可能性变小，种群内的解差异性增大，利于算法更早达到全局最优解。

图5 不同θ下的行驶距离的对比

表6 不同θ下的具体结果

从图5和表6中可得，θ对车辆行驶距离也有影响。θ从0增加到0.5，目标值不断增大；θ为0.5和1时，目标值保持不变。这是因为为了抵抗不确定的行驶时间，需要调整行驶路线，增加行驶距离；但当考虑了足够的不确定程度时，行驶路线不再发生变化。

以θ为0和0.1的结果分析解如何抵抗不确定行驶时间的影响。图6所示是θ=0时配送车辆的路径方案，工位号上方的是各个工位的时间窗，下方是车辆到达工位的服务开始时间。得到的路径方案保证了服务开始时间在物料配送的时间窗内，但这个方案不考虑不确定行驶时间。如果行驶时间发生波动，例如第一条路径中工位3-工位4，见表5，则存在可能的波动时间0.5 min，如果发生波动，那么实际最差的服务开始时间是18.6+0.5=19.1 min，该时间超过了工位4允许的时间窗上限，导致方案不可行。

图6 θ=0时车辆服务开始时间(min)

图7所示是θ=0.1时的路径方案，工位的服务开始时间下方的数字是考虑如果路径中发生θ=0.1不确定情况时每个工位最差服务开始时间。与θ=0路径的不同之处在于，该方案将访问顺序4和5进行了互换。由图7可以看到，即使路径中发生θ=0.1的行驶时间波动，车辆的服务开始时间依然满足时间窗要求，有效抵抗了不确定行驶时间的影响。

图7 θ=0.1时车辆服务开始时间(min)

为了进一步获得各个路径方案抵抗不确定行驶时间的能力，采用蒙特卡罗模拟法[26]对结果进行分析。在给定θ下，蒙特卡罗模拟法评价解抵抗不确定行驶时间的过程如下：①输入路径方案；②产生N个θ条件下的不确定行驶时间场景(N=10 000)，每个场景中的不确定行驶路径的路段数按照θ随机选择，路段内不确定行驶时间在各自区间内按均匀分布产生；③对解在每个场景中的可行性进行分析；④对解可行性的结果进行统计，输出解在当前θ下的可行概率。

通过调整θ可以观察不同方案抵抗不同不确定程度的能力，结果如表7所示，方案4结果同方案3。从表7中可看到，方案1抵抗不确定性的能力随着路径中的不确定程度增加而降低，这是因为该方案完全没有考虑行驶时间不确定的影响；方案2与要求一致，能够完全抵抗θ=0.1的不确定性，随着不确定性程度的增加，该方案的抵抗能力依然很强；方案3的结果则能够完全抵抗住所有不确定的情况。

表7 各方案抵抗不同不确定程度的可行概率

由上文分析可知，为了抵抗不确定性，需要调整车辆运行路径，这会导致车辆行驶距离增加，因此决策者要根据实际情况，综合运行成本来选择最佳车辆路径方案。从本案例分析可以得到，方案2能够以较短的行驶距离，使行驶路径基本不受不确定行驶时间的影响，保证装配线的稳定运行。

4 结论

(1)为了考虑装配线物料配送中车辆行驶时间区间不确定对路径规划的影响，本文采用鲁棒优化方法，引入路径相关不确定参数，建立了鲁棒路径规划模型。

(2)提出了一种求解该模型的混合遗传算法，在算法中，使用锦标赛选择算子，避免适应度值的转换；使用离散莱维飞行来提高算法的搜索性能。计算案例表明该混合算法比传统遗传算法能得到更好的解。

(3)求解结果与路径相关不确定参数有关，决策者需要根据实际情况，综合运行成本来选择最佳路径方案。