面向动态分布农机装备的维修服务区域划分与优化

◎阮洁 吕雯 朱梦云

基于适应动态分布农机装备的维修服务背景下，简化问题为多旅行商问题。以江西省为例，预测每个空间区域的需求，再根据此需求进行维修服务区域划分。以维修成本最小的原则确定维修站，并采用蚁群算法对此路线进行优化，最终以实际数据检验。

一、引言

随着科学技术的不断发展，农业机械已经成为农业生产的重要组成部分，其保有量与使用量不断增加，这就对农业机械的结构、工作质量、可靠性以及服务便捷性都提出了更高的要求。然而，现阶段的一个显著问题是在农机市场快速扩展的情况下，农机维修工作的需求量也在不断增长，农机维修能力的滞后与农机维修任务量大成为了一对显著的矛盾体。对于动态移动、集群式作业的农机装备而言，随生产任务跨区域动态变化的地理位置，短时间内大量农机同时高强度作业的工作模式，故障发生后必须快速响应的维修服务要求，这些特点给服务管理和决策带来了全新挑战。因此，加强各级关联的农机维修网点建设是一件必须且长久受益的工作。

本文以维修成本最小为目标函数，建立农机维修服务区域划分的数学规划模型，并提出高效求解算法，通过模型的求解确定维修服务区域、维修点的选址及路线方案，以确定维修车各自的服务区域。

二、维修区域划分模型的建立

1.建模思路。

依据目前我国农业生产的基本情况，很多农村依靠土地流转，"连地成片"进行耕种，可以确定以一个省为大的区域，在这个省内进行服务区域划分，可以划分为若干个维修服务区域，每个维修服务区域由相近的几个县构成，在每个维修服务区域设置一个维修点。

因此，本文建模思路是不完全按照县的划分条件下去划分维修服务区域，而是为节省成本，扩大每个维修服务区域，将若干个区县划分为一个服务责任区域，根据对该省的维修服务需求进行预测，以及每个维修服务点所能承受的最大维修服务量来最终确认划分多少为多少区域，并尽量保证每个服务区域类的需求数量接近一致，再根据路线最优化方案选择出在该区域内的维修站的最佳设计点，以及根据优化得出最优维修路线。

2.假设及变量意义。

①假定以县区为一个空间单位（SU），每个维修区域单位（G）由若干个SU 构成，每个G 中只有一个维修站，维修服务是通过该维修点派出维修车进行的工作。

②现在已知每个SU 的预测需求量和每个G 内的最大服务量（N），现规定每个服务区域内的需求量要超过服务量的90%但不能超过最大服务量。

③同一个维修服务区域内SU 同时需要维修服务。

参数及变量意义：

①uiG：每个维修区域G 内的需求总和②xi：表示是否有维修站，xi∈{0，1}

③m，A 分别表示维修车总数和每辆维修车所能达到的最大服务要求。

④以点0 表示维修车的出发城市，称为原点，点1，2，……l 表示m 个维修车需要维修的SU，（l 表示每个G 内的SU 个数）因此定义以下变量：

否则

否则）

3.模型建立。

目标函数Z 表示维修路线总的成本，

其中，

cij表示维修车经过对应弧段（i，j）距离，K=1，2……m

约束条件

其中j=0，1……l；k=1，2……m

在该模型中，式（1）表示m 个维修车维修过程中路程最大的那个最小化；式（2）表示各个维修车的路程；式（3）表示从维修站出发，所有的维修点都只停留一次；式（4）表示任一条弧的终点仅有一个起点与之相连；式（5）表示任一条弧的起点仅有一个终点与之相连。

三、维修区域划分模型的求解以及优化

1.维修区域划分。

维修区域的划分对最终的农机装备派送有很大的影响。合理的区域划分能够在较短的时间，以较低的成本完成农机派送维修服务。因而选择合理的区域划分方法十分重要。

基于实际应用场景的情况，我们采用聚类算法中的K-means 算法。K-means 聚类算法主要是对于给定的样本集，按照样本之间的距离大小，将样本集划分为k 个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。假设簇划分为（C1，C2，…，Ck），目标函数是Z。

运用注意点：第一，k 的选择以区域总需求/维修车数量的值上下浮动10%左右。第二，每个区域内需求大体相似，这样有利于资源的充分利用。

传统的k-means 聚类方法，随机产生初始中心点，运行时间长，具有较大的随意性，收敛效果差。基于此，采用密度法效果较好。

初始中心点以密度来定义，运用两点间欧氏距离的方法，求解所有对象间的相互距离，并求平均数mean（D）表示，确定领域半径是对象数目，coefR 是半径调节系数，0＜coefR＜1，经验表明，coefR=0.13 效果最好。

2.基于蚁群算法的维修路线优化。

将MTSP 定义为带权无向图G（V，E）。各个县由图上的顶点Vj表示，各个县的路径有图上的边ei表示，边ei上的成本用w（ei）表示。MTSP 中，图G（V，E）上需要定义m 个闭合回路C1，C2，…，Cm（i=1，2，…，m）。V0为仓库节点，V0∈Ci，w（Ci）为回路i 成本。MTSP 问题可定义为如下模型：

蚁群算法室友意大利学者M.Dorigo等人在20 世纪90 年代初提出的一种智能算法，其真实地模拟了自然界蚂蚁群体的觅食行为。M.Dorigo 等人将其用在解决旅行商问题TSP，并取得了较好的结果。

蚁群算法的基本思路是：蚂蚁在觅食过程中，会在所经过的路径上释放一种具有挥发性的物资——信息素，不同蚂蚁个体通过感知信息素的存在及其强度指导自己的移动方向。最终，整个蚁群能够搜索出巢穴与食物源之间的最优路径。

（1）状态转移概率准则。

每台维修车选择下一个维修区县时按照如下伪随机概率选择规则进行：

其中τik（t）为t 时刻区县i 到区县j间的信息素轨迹值；ηij为相对于区县i 区县j 的能见度；α 是能见度在概率选择因素中的相对重要性系数；S 为未访问区县的集合；q 为满足均匀分布的随机数，参数qo值越低进行随机选择的概率越高；I 为随机变量，其选择根据如下分布：

根据该规则，当邻域中没有被访问的城市时，算法以概率q0选择最佳的下一城市，以概率（1-q0）按照式（9）的概率分布随机选择下一城市。这一过程直到所有城市被访问。

（2）信息素轨迹更新。

信息素轨迹更新遵循最大最小蚁群算法框架：算法开始每条路径上的信息素轨迹初始化为τmax，迭代过程中信息素轨迹限制在区间[τmin，τmax]。τmin和τmax定义如下：

其中ρ 为信息素轨迹保持系数（1-ρ即为挥发系数）；f（sgb）是全局最优解（sgb）的路径长度；n 是所有城市的数目。

解的构造过程之后，信息素轨迹以全局最优解为基础更新，更新规则如下

其中

式（12）表示只有属于全局最优解的那些边才会加强。

四、模型应用

文章中建立的维修区域划分模型以及路径优化模型将应用于江西省农机装备维修服务区域中，以县为空间单位SU，划分成不同的维修区域单位G。并基于此计算出最优的维修车的数量及其维修路径。

1.确定空间单位。

江西省共100 个空间单位。包括市辖区25 个、县级市11 个、县64 个（11 个市区不列入数据内）。

2.划分维修区域。

利用K-means 算法，对于给定的100个空间单位样本集，按照样本之间的距离大小，将样本集划分为k 簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大，使其具有"高内聚，低耦合"的特点，目的是减少维修路径，节省维修成本，提高维修效率。

3.利用蚁群算法确定维修站的所在地和路径优化。

每个维修区域有且仅有一个维修站，维修站派出维修车，基于维修车优化后的路径进行维修。

五、结语

本文针对农业生产的时间和地域差异性和维修地点不固定的问题，利用K-means 方法建立维修服务区域划分，并利用蚁群算法优化模型，提出相应求解算法，并以江西省农机维修为实例作仿真应用，打破了地理的限制，解决了跨区域维修的难题。

服务区域的合理划分和优化可进一步优化服务站配置决策及大幅度节约路径成本，在服务系统应用中具有重大意义的，特别是对于流动性强，区域范围大，样本多的服务系统，更加值得重视。