考虑工位服务满意度的物料配送路径优化研究

张守京，段 娇，童傅娇

（1.西安工程大学 机电工程学院，西安 710600；2.西安市现代智能纺织装备重点实验室，西安 710048）

0 引言

随着全球化经济进程的加速，离散制造企业之间的竞争愈发激烈，在车间运行过程中，生产物流中的辅助时间（物料的存储、搬运等）占总时间的90%～95%[1]，因此优化生产物流的运行水平对企业的生存与发展起着至关重要的作用，但是在目前离散制造车间生产物流的运行环节中，普遍存在着运输成本高、配送效率低、工位服务满意度差等问题[2]。随着生产精益化、智能化、协同化的不断发展，如何改善现有离散制造车间生产物流的运输效率，提高工位服务满意度，已经成为了广大离散制造企业亟需解决的重大难题之一。

车间物料配送路径优化问题本质上是车辆路径问题（Vehicle Routing Problem，VRP），由学者Danting和Ramser于1959年首次提出[3]。从理论研究方面看，物料配送路径优化问题已被证实是NP-hard问题[4]，其求解复杂度高，计算量大。初期对该类问题的研究主要集中在以行驶路径最短、消耗成本最低或所用时间最少等单目标优化方面，随着科技的进步，研究热点逐渐转向多目标优化，考虑因素更加多样，更符合车间物料实际配送过程，Muller[5]在考虑软时间窗的基础上，将多目标优化问题进行分解，并采用启发式算法对其进行求解；Murao H[6]等对带有模糊变量和惩罚函数的软时间窗约束的VRP进行了研究；Xia Y[7]分析了开放式车辆路径问题（OVRP），在考虑软时间窗和满意率的基础上建立了双目标OVRP模型，并运用带自适应惩罚机制和多邻域结构的改进禁忌搜索算法（ITSA）进行求解；楼振凯[8]则针对配送多目标优化问题，综合考虑了车辆使用数及运输总里程，基于双层规划思想，建立了带模糊时间窗的多目标优化模型，并运用模拟退火算法进行求解；张佳佳[9]等研究了装卸点可充电模式下的电动汽车冷链配送路径优化问题，以配送总成本为优化目标，使用粒子群算法进行求解，研究结果表明这种边充电边卸载的方式有效的降低了在配送过程中由于充电而带来的成本增加问题。

现阶段，学者们对车辆路径问题的研究主要集中在模型建立和求解算法两方面，在模型建立方面，主要是从优化目标和约束条件等对模型进行改进；李思国，郭宇等[10]针对离散制造车间环境复杂、外部干扰因素众多的情况，提出了基于改进遗传算法的物料配送路径实时规划方法，建立了车间实时环境下的物料配送模型，并使用融合TSA和GA对模型进行求解；严正峰[11]等为解决实际生产过程中工位物料需求时间不确定的问题，提出了基于模糊软时间窗的复杂机械装配车间配送路径优化方法，并建立了带模糊软时间窗的物料配送路径优化模型，采用动态规划算法和模拟退火算法相结合的混合算法对模型进行求解；在算法求解方面，主要从对智能算法的应用及改进入手，如Ferani E.Zulvia，R.J[12]等针对易腐产品的运输成本高、空气污染严重等问题，提出了一个可优化易腐产品运输成本、变质成本、碳排放的绿色车辆路径问题，并使用多目标梯度进化算法（MOGE）进行求解；Asma M.Altabeeb，Abdulqader[13]等针对电容车辆路径问题，提出了一种新的混合型车辆路径规划算法，即CVRP-FA算法，该算法结合了两种局部搜索算子和遗传算子，提高了求解质量，加快了收敛速度，并通过在82个基准测试实例上测试，结果表明该算法具有较快的收敛速度和计算精度；Zhong X[14]等在研究了物流配送中的两阶段车辆路径问题（2E-VRP）之后，运用人工蜂群和遗传算法相结合的混合算法（ABCGA）进行求解，试验结果表明ABCGA 算法具有效果稳定、效率高等优点。

结合以上文献的研究内容，以及对现有车间物料配送路径优化问题分析后，发现在部分车间内部存在着由于配送小车不能在各工位规定的时间窗内将所需物料送达，导致时间惩罚成本较高，工位服务满意度较低；不合理的路线规划，使得配送过程中小车使用数量增多，配送距离增大，配送成本增加等问题。因此，本文在考虑各工位生产物料需求的基础上，建立了多目标车间物料配送路径优化模型，蚁群算法是一种正反馈群智能优化算法，且具有并行性、强鲁棒性、适应性、易与其他算法相结合等优势，但其收敛速度较慢，容易陷入局部最优，因此本文分别使用基本蚁群算法和改进的蚁群算法对模型进行求解，并将其所得结果进行对比，结果显示改进的蚁群算法可以减少配送小车使用数量及配送成本、提高工位服务满意度并缩短配送距离。

1 问题描述与符号说明

1.1 研究问题

在传统车间物料配送路径优化问题中，优化目标常常为配送距离最短、所用时间最少或者配送成本最低，往往忽略了配送过程中配送小车的服务质量或各工位的服务满意度，即配送小车是否能够在工位要求的配送时间窗内将所需物料按时送达，避免出现因物料配送不及时而导致的工位停工停产现象发生。随着科技的发展与进步，在日益激烈的社会环境下，提高“服务质量”或“服务水平”等标语在各大车间内随处可见，显然其已经成为了企业提高自身竞争能力、生产效率以及服务质量的重要因素之一，但是在离散制造车间的生产物料配送过程中，各种不确定因素会导致工位生产节拍发生波动，致使各工位的物料需求时间也随之发生变化，各配送小车对工位的服务质量千差万别，进而导致各工位对不同时间内物料配送活动的服务满意度不尽相同，因此本文将工位服务满意度作为优化目标之一，并用惩罚代价最小来描述工位服务满意度最高，结合配送路径最短、配送小车使用数量最少，构成多目标车间物料配送路径优化模型，分别使用基本蚁群算法和改进的蚁群算法对模型进行求解，将结果进行对比，从而体现出改进后算法对该问题求解的有效性。时间窗惩罚示意图如图1所示。

图1 时间窗惩罚示意图

文中的工位服务满意度可表示为：

某离散制造车间内有K辆容量为Q的配送小车，现需要对N个待配送工位进行物料配送任务，各工位位置和所需物料数量等均为已知，则考虑工位服务满意度的车间物料配送任务为各配送小车将车间配送中心的物料在各工位需求的时间窗内配送至各工位，在配送过程中，配送小车按照规划的路线进行配送，并根据各工位时间窗跨度大小调整配送工位的服务顺序，保证优先服务物料需求紧急程度较高的工位，从而提高配送车间物料的配送效率，确保整个配送过程中使用小车数最少、配送路径最短以及工位服务满意度最高。当配送小车将工位所需物料送达至工位且返回原配送中心时，表示该配送任务结束。为了便于研究，该任务需要满足以下约束条件。

1）运载能力约束。每个工位i的物料需求量qi均已知，每条配送路径上各工位的物料需求量之和不能超过配送小车的最大载重量Q。

2）配送小车约束。配送小车的停止、启动、装卸料时间及小车故障等因素均忽略不计；所有配送小车从配送仓库出发，完成任务后返回配送中心；一辆配送小车可以同时服务多个工位，但每个工位只能由一辆配送小车进行物料配送活动；在整个配送过程中，配送小车的行驶速度已知且恒定。

3）配送中心约束。车间内仅有一个物料配送中心，且配送中心位置已知，物料充足，能够满足所有工位的物料需求。

4）时间窗约束。如图1所示，对于每个工位i，配送小车必须在内进行服务，若配送小车到达时间早于ei，则必须在工位处等待，若配送小车到达时间晚于li，则服务必须被延迟。

1.2 符号与决策变量

由于本文符号和变量较多，为方便分析，在此将各符号按表1进行解释说明。

表1 符号说明

2 数学模型

在上述多目标优化模型中，i，j=0表示配送小车的起始点和终止点，dij表示工位i到工位j之间的距离，式(2)表示配送小车行驶的距离最小，式(3)表示工位服务满意度最大，即惩罚代价最小，式(4)表示所用配送小车的数量最少，式(5)表示每辆配送小车配送的物料需求量不能超过小车的最大载重量，式(6)表示每个工位只能由一辆配送小车进行配送，式(7)表示配送小车从配送仓库出发，最终返回配送仓库，式(8)表示消除支路，式(9)表示到达和离开配送工位为同一配送小车，式(10)、式(11)为决策变量。

上述所建模型属于多目标优化模型，为便于求解，本文结合单位配送成本ck、单位等待惩罚成本ce、单位延迟惩罚成本c1以及配送小车固定启动成本ca，将其转化为单目标优化模型，即求配送小车在配送过程中的总成本，处理后的目标函数为：

3 改进蚁群算法设计

本文所研究的车间物料配送路径优化问题属于NPhard问题，随着社会的发展和算法的演变，目前对该类问题的求解研究较多的是启发式算法[15～17]，比如：遗传算法（GA）、禁忌搜索算法（TSA）、模拟退火算法（SA）等，在众多启发式算法中，蚁群算法凭借其具有采用分布式并行计算机制，有自组织、正反馈与较强的鲁棒性，可以使问题在较短的时间内得到较为满意的可行解，且易于其他启发式算法相融合的优势，深受大多数学者喜爱，但其也存在因搜索时间较长而导致收敛速度较慢，易陷入局部最优的缺陷。因此本文对基本蚁群算法进行改进，主要分为三部分：1）通过在基本蚁群算法的状态转移规则上加入 “时间窗跨度”因素，调整待配送工位的服务顺序，对物料需求紧急程度较高的工位优先配送，从而提高配送小车服务质量，提升工位服务满意度；2）得到当次迭代最优解时，使用2-opt局部邻域搜索算法，对最优解进行交叉操作，并对交叉后的结果进行比较，从而得出全局最优解，帮助其跳出局部最优；3）采用自适应信息素更新策略，对信息素挥发因子做分段取值处理，使其在各阶段能动态调整信息素更新，以此来提高算法的全局搜索能力，加快收敛速度。

3.1 转移规则设计

在基本蚁群算法的转移规则中，状态转移概率仅与信息素浓度和可见度有关，本文为了使配送小车可优先服务物料需求紧急程度较高的工位，加入了“时间窗跨度”因素，即优先配送时间窗跨度值较小的工位，从而提高工位服务满意度。具体描述如下：

令工位i的时间窗跨度为with=li-ei，当两个待配送工位i1、i2均未被访问过时，比较这两个工位的时间窗跨度值，若i1的跨度值比i2低，说明工位i1的物料需求紧急程度高于工位i2，即两工位相比，i1更具有配送任务紧迫性，故在配送过程中应优先服务工位i1。因此设是蚂蚁k从工位i转移到工位j的状态转移概率，则转移规则如式(13)所示：

在式(13)中，τij为信息素浓度，ηij为可见度，且ηij=1/dij，α为信息素重要因子，表示轨迹的相对重要性，反应了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，β为启发函数重要因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径的受重视程度，γ为时间窗跨度重要因子，表示待配送工位的服务顺序，反映了当工位物料需求紧急程度较高时执行该任务的紧迫程度，且γ为在[0，1]上的服从均匀分布的随机变量，γ0(0≤γ0≤1)为用来控制转移规则的参数，本文取γ0=0.5；为配送小车k从i点出发可以访问的所有工位点j的集合，其中工位点j表示未被服务过且均满足容量约束和时间窗约束。令一只蚂蚁从车间配送中心出发，按照式(13)的转移规则计算状态转移概率，并使用轮盘赌法依次选择下个待访问工位点j，若找不到满足要求的工位j，则该蚂蚁返回配送中心，继续派遣另一只蚂蚁按上述步骤依次进行，直到所有待配送工位点全部被访问完成为止。

3.2 自适应信息素更新策略

对蚁群算法而言，蚂蚁在搜索路径的过程中分为两个阶段，即全局搜索阶段和收敛阶段，并且在整个路径搜索过程中，信息素挥发因子的取值将直接关系到蚁群算法的全局搜索能力和收敛速度，若的取值过大，则蚂蚁选择已经搜索过的路径可能性较大，很容易出现局部收敛；若的取值过小，会影响算法的收敛速度，因此，本文采取自适应信息素更新策略，即随着算法迭代次数的增加，将算法分为初期、中期和后期，信息素挥发因子按照每个时期的设定值进行动态调整。初期的取值较大，加强信息素浓度，以此增强算法的全局搜索能力，而在中期和后期，的取值较小，进而降低信息素对蚁群的影响，以便较快的收敛到最优解，具体取值规则如式(14)所示：

为了避免残留信息素过多引起残留信息淹没启发信息，当所有蚂蚁完成一次循环后，需要对残留信息素进行更新，由此，t+1时刻在路径(i，j)上的信息量可按式(15)进行调整：

在式(15)和式(16)中，ρ为信息素挥发因子，(1-ρ)表示信息素残留因子，为了防止信息素无止境增加，在基本蚁群算法中，ρ的取值范围是(0，1)；Δτij(t)表示本次循环中路径(i，j)上的信息素增量，在初始时刻，表示第k只蚂蚁在本次循环中留在路径(i，j)上的信息量。

在式(17)中，Q为常数，表示每只蚂蚁所释放的信息素总和，Lk表示第K只蚂蚁在本次循环中所走路径的总长度。

3.3 2-opt局部优化

2-opt属于局部搜索算法，其基本思想是“交换”，即将一条路径转化为另一条路径，只要操作能降低当前路径的长度和成本，算法则会在给定集合内反复进行操作，直到任何操作都不能继续更新为止，即产生了一条局部最优路径[18]。其基本原理是：用(i，j)，(i+1，j+1)来替换(i，i+1)，(j，j+1)经过变换之后线路中的路径(i+1，...，j)被进行反向处理，即满足以下条件时：

变换后的路径如图2所示。

图2 2-opt交换示意图

蚁群算法每次迭代后，大部分蚂蚁搜索的结果对当前最优解并没有贡献，若对这些没有贡献的路径使用2-opt，会消耗大量的运行时间，针对该问题，本文采取的方法是当所有蚂蚁完成遍历后得到单次最优解时，使用2-opt局部搜索算法进行二次优化，对最优解进行交叉操作，从而扩大解的搜索空间，改善种群信息结构，帮助算法大概率的跳出局部最优解，提高算法的搜索能力。

改进后的蚁群算法步骤如下：

1）初始化dij、NC_max、n、m、α、β、γ等参数。

2）将m只蚂蚁全部放置到车间配送中心，创建并初始化禁忌表tabuk，按照式(14)设置ρ的值。

3）在满足配送小车装载量限制以及工位配送时间窗约束的前提下，每只蚂蚁按照式(13)计算状态转移概率，根据轮盘赌选择策略选择下一个待访问工位点j′，并判断配送小车是否满足约束，并将其路径添加至禁忌表tabuk中。

4）修改禁忌表tabuk，直到所有蚂蚁遍历完所有工位点并返回配送中心，且禁忌表更新满足时间窗约束和载重约束。

5）对当次迭代的最优解按式(18)采用2-opt算法进行局部优化，得出优化后的成本f(t)和f(t+1)。

6）比较f(t)和f(t+1)的大小，若f(t)≺f(t+1)，则返回f(t)，否则返回f(t+1)，直到t达到最大设定值时，更新全局信息素，否则返回循环，t=t+1。

7）判断是否满足结束条件(N c ＞N c_m a x？)若Nc≤Nc_max，则Nc=Nc+1，并转至步骤2)，若Nc＞Nc_max，则完成迭代，输出最终结果。

改进后蚁群算法流程图如图3所示

图3 改进后蚁群算法流程图

4 实例验证

为了验证改进后蚁群算法的可行性，假设某离散制造车间有1个物料配送中心、14个待配送工位，以及多辆配送小车，小车最大载荷量为Q=50kg，行驶速度为S=50m/min，本文采用软时间窗，配送小车早到的单位等待成本为ce=5元/h，晚到的单位延迟成本为cl=10元/h，单位行驶费用为ck=5元/m，固定启动成本为ca=50元/辆，分别用基本蚁群算法和改进后的蚁群算法对问题进行求解。在Windows10环境下，运用MATLABR2018b语言进行编程，蚁群算法相关参数如表2所示，各工位配送任务表如表3所示，工位与配送中心以及工位间的距离如表4所示。

表2 蚁群算法参数

表3 各工位配送任务表

表4 工位与配送中心间以及工位间的距离

本文分别使用基本蚁群算法及改进的蚁群算法在MATLAB2018b上进行求解，且设定蚂蚁初始数量为m=50，最大迭代次数为NC_max100，信息素重要因子α=1，启发函数重要因子为β=3时，时间窗跨度重要因子γ=2，基本蚁群算法中信息素挥发因子ρ=0.4；改进后最大信息素挥发因子为ρmax=0.85，最小为ρmin=0.15，且全局信息素常量为Q=5，当两种算法在迭代100次后，小车配送路径图如图4、图5所示，不同颜色的路线代表不同配送小车的配送路径。当使用基本蚁群算法对问题进行求解，得出整个配送过程需要5辆配送小车进行配送，配送路径图如图4所示，具体配送路线为：小车1：0-1-6-3-0；小车2：0-12-10-5-0；小车3：0-11-0；小车4：0-2-14-9-0；小车5：0-13-7-4-8-0；

图4 基本蚁群算法-小车配送路径图

图5 改进的蚁群算法-小车配送路径图

当使用改进后的蚁群算法对问题进行求解，得出整个配送过程只需要4辆配送小车，配送路径图如图5所示，且改进后配送小车的具体配送路线为：小车1：0-1-6-3-0；小车2：0-5-10-7-4-11-0；小车3：0-13-12-8-0；小车4：0-2-14-9-0；

图6为基本蚁群算法和改进后蚁群算法求解出的最优路径长度收敛趋势图，从图6可以明显的看出改进后的蚁群算法求解的结果比基本蚁群算法更优，且收敛速度更快，具体仿真结果如表5所示。

图6 最短路径收敛对比图

表5 最短路径长度仿真结果

图7为基本蚁群算法和改进后蚁群算法求解出的最优成本收敛趋势图，具体仿真结果如表6所示。

图7 最优成本收敛对比图

表6 最优成本仿真结果

蚁群算法和改进后蚁群算法求出的结果对比如表7所示。

表7 两种算法结果对比

正如表7所示，改进前配送小车的最短距离为440m，即运输成本为2200元；配送工位的服务满意度成本为372.5元；配送过程需要5辆配送小车，即小车的固定启动成本为250元，总成本为2822.5元。改进后配送小车的最短距离为360m，即运输成本为1800元；配送工位的服务满意度成本为322.5元；配送过程需要4辆配送小车，即小车的固定启动成本为200元，总成本为2322.5元。将两种算法的求解结果对比得出：最短距离减少了18.2%；工位服务满意度提高了13.4%；小车数量减少了1辆；总成本降低了17.8%，以上数据验证了改进后蚁群算法对求解本文所研究问题的有效性。

5 结语

针对离散制造车间的物料配送路径优化问题，多数均单纯从配送的经济性角度进行考虑，即以最低的总成本满足所有工位的需求，往往忽略了配送小车的服务质量或配送工位的服务满意度，而在当前激烈的市场竞争中，满意度已经成为了车间物料配送路径优化问题不得不考虑的重要因素之一，因此本文建立了考虑工位服务满意度的车间物料配送路径优化模型，并分别使用基本蚁群算法和改进蚁群算法对该模型进行求解，最后通过在MATLAB上对实例进行仿真，发现改进后的蚁群算法与基本蚁群算法相比，在解决配送距离、工位服务满意度以及小车使用数等三方面都有一定程度的提升和降低，进一步验证了该模型和算法的合理性和普适性。