基于K-means算法和集合覆盖模型的维修站选址

张守京，李梦丹

（西安工程大学 机电工程学院，陕西 西安 710048）

1 引言

目前，我国汽车市场正面临着总体市场空间不断扩大的良好机遇，同时汽车工业的高速发展也带来了售后服务基础设施的缺乏问题和对售后服务的高需求和个性化要求，使得企业之间的竞争也日益激烈。由于我国汽车售后服务发展滞后，给汽车工业的发展带来了一定的阻碍。在汽车行业激烈的竞争中，竞争的焦点已不仅仅限于产品和价格，同时，要善于发现和了解顾客需求，创造服务差异化，不断完善售后服务体系以提高客户满意度，因此建立服务站就显得尤为重要。加快服务站建设对重卡汽车的发展同样具有十分重要的意义，因此本文在满足服务需求的基础上对此展开研究。

选址是一个传统的话题，涉及方方面面，例如公共设施[1]、售后服务站[2-4]、物流配送中心[5-8]、加油站[9]、充电站[10-11]等设施的选址，合适的选址不仅可以降低成本，同时还可以提高顾客满意度。维修服务站是售后服务系统的核心部分，因此选择合适的方法就显得尤为重要。集合覆盖模型[12-16]在选址问题中是一种比较常用的模型，可以在成本最小的情况下达到最大的顾客满意度。该模型可以结合传统的线性规划，利用LINDO 软件求解以及采用科学的评价方法[17]，也可以利用启发式算法如粒子群算法[18]、聚类算法进行选址[19]，使结果更加具有科学性。新兴的数据挖掘[20-21]也可以给选址提供一定的思路，可以结合车联网信息，利用地理信息系统[22-23]相关软件直观的显示需求地点并进行数据分析。

已经有许多学者对选址做了大量研究，但是基于大数据的维修服务站选址相对较少。许多企业在服务站的建设方面都是依据以往经验，忽略了需求量与建站数量相一致的原则，这就造成了一定的资源浪费，部分地区设施因需求小而闲置，部分设施因需求大而不能满足当前维修需求。为满足用户需求，建立车联网大数据信息管理平台对车辆的运行轨迹以及维修等进行记录与管理，通过对海量数据的挖掘与分析，归纳客户需求，将有助于维修服务站的选址。本文利用k-means 算法对车联网数据进行聚类分析，结合集合覆盖模型对重卡维修服务站展开选址。

图1 维修站选址研究流程

2 研究方法及流程

2.1 研究流程

维修站选址，即基于车辆行驶轨迹以及历史维修记录等大数据，通过采取数据、分析整理、归纳总结等，选择合适的维修服务站点，旨在第一时间满足客户需求，提高客户满意度，打造高标准服务体验。本文首先对数据进行区域划分，采用K-means 算法进行聚类，然后在某区域中进行集合覆盖选址，依此类推，得到全国范围内的选址方案。研究流程如图1所示。

2.2 K-means算法区域聚类

本文所要分析的数据量相对较大，属于空间地理位置信息，因此采用K-means 算法对其进行分析与归类，将某一区域内距离较近的点划分为一个区域（即将具有相似特征的点归为一类）。

K-means 聚类算法是聚类分析在现实应用中最重要的算法，它能够快速有效地处理较大的数据集合。K-means算法根据聚类的个数K，将已有的数据集划分成K个簇，算法采用迭代更新的方法，在第一轮中，根据随机选定的K 个初始中心点将对象集划分成K 个初始簇，之后根据每个簇的中心迭代重新划分每个对象所属的类，而每个簇的平均值将被作为下一轮迭代的中心点，直到中心点不再发生改变，即产生了最后的聚类结果。K 表示类的数量；K-means可以自动分配样本到不同的类，但是不能决定究竟要分几个类。K 必须是一个比训练集样本数小的正整数。K-means 算法常采用误差平方和准则函数作为聚类准则函数，定义为:

其中，Mi是类Ci中全部数据对象的均值，p是类Ci中的每个数据对象。可以看出，Jc是样本和聚类中心的函数。在样本集给定的情况下，Jc的值取决于K个聚类中心Mi。Jc描述了n个样本聚类成K个类型时所产生的总的误差平方和。显然，若Jc值越大，说明误差越大，聚类结果不好，因此寻求使Jc最小的聚类结果，即在误差平方和准则下的最优结果。

本文利用K-means 算法将全国范围内的车辆需求点进行聚类分析，在给定K值的情况下，找到一个点使某区域内所有点到达该点的距离最小，该点即为聚类中心。该区域内的点具有一定的相似特征，即该区域内的需求点为一类。

2.3 集合覆盖模型

在利用K-means 算法对数据进行聚类分析的基础上，对车辆所行驶的轨迹进行了区域划分，接下来根据分类结果，在给定的选址区域内使用特定的选址模型求出模型的可行解，并从中选择最符合目标函数的一组作为模型的最优解，转化为实际选址问题的结果。以聚类结果中数量最多的一个区域为例，做出区域内选址。维修站的建设目的在于可以快速高效的为行驶的车辆提供各种服务，因此建立的维修站应满足以下需求：建立的维修站可以满足全部的需求点，同时考虑顾客满意度最大，因此考虑使用覆盖模型进行求解。

对于大多数的覆盖类选址问题，可以叙述如下：已知需求点集合和潜在的设施点集合，对于给定的服务半径，①设施点的数量无限制时，要求寻找一种设施点的配置方式，使得使用最少的服务设施以覆盖所有的需求点；②给定设施点数量时，要求找到一种设施点配置方式，使得其覆盖的需求点尽可能的多。其中情形一为集合覆盖问题，而情形二为最大覆盖问题。为了满足所有需求点的需求，使服务水平尽可能的达到最大，因此选择集合覆盖模型（如图2所示）进行区域内维修站的选址。

图2 集合覆盖模型图示

覆盖模型是对已知的一些需求点确定一组服务设施来满足这些需求点的需求。该模型中，需要确定服务设施的数量和合适的位置。集合覆盖模型为用最小数量的设施点覆盖所有需求点。如何确定设施点能够覆盖需求点，由于基本覆盖模型的应用较为广泛，其符号记法一般也稍有差异，在介绍模型之前，先对部分符号做如下规定：

N—区域中的需求点（车辆停靠点）集合，N={1，2，···，n}；

M—区域中可建立设施的候选点结合，M={1，2，···，m}；

xi为0-1变量，xi=1，在i 点建立设施；xi=0，不在i点建立设施，i∈M；

令sij表示设施点i到需求点j的距离，L表示某设施点最大覆盖半径，定义变量yij，满足

3 实例分析

在产品差异化逐渐缩小的环境下，各类产品致胜的关键已经逐渐由质量演变为售后服务，而重型汽车行业体现的尤为明显。在此基础上，展开对某重汽维修服务站的选址，确保用户在最短时间内得到最好的售后维修服务。

3.1 数据预处理

首先进行数据收集与处理。车辆信息包含车辆识别号码(VIN)、车辆停靠点以及轨迹的经纬度坐标、高度、行驶里程等，见表1。将汽车的运行以及停靠轨迹作为需求点，在进行聚类时只需考虑经纬度坐标即可达到聚类效果，因此对数据进行剔除，得到目标所需要的数据。

表1 原始数据包含信息

本文选取两个月的记录进行数据分析，共包含七万多条数据，即共需要对76 160 对地理坐标点进行聚类分析。

3.2 区域划分

K-means算法需要对输入的数据进行处理，针对停靠以及维修点进行选址，则选取行驶轨迹、停靠点维修点的地理坐标作为输入数据组，用matlab 进行仿真，车辆运行轨迹可视化如图3所示。利用kmeans算法对车辆的行驶轨迹、停靠点等76 160个地理坐标进行聚类划分，从车辆运行轨迹可以看出，需求点的分布不够均匀，西北和东北区域相对分散，中部和南部较集中，因此除去东北和西北两个区域，其他按照四个方位分为四个区域，因此设定初始聚类数目为6，利用K-means算法将全国范围内的需求点划分为6 个区域，并用不同的颜色标识，如图4所示。利用Arcgis工具绘制需求点在地图上的方位，如图5所示。

图3 车辆运行轨迹可视化

图4 车辆轨迹聚类可视化

图5 需求点聚类结果可视化

经过迭代计算，在聚类个数为6 的情况下，每一类的聚类中心以及每个区域所含需求点的个数见表2。

表2 聚类结果

可以看出，第三个区域需求点较多，第六个区域需求点较少。通过观察，选取包含需求点数量最多的区域进行区域内选址。接下来需要考虑所有的需求点，建立合适的模型，考虑约束条件，在选定区域内进行选址，以此类推，在其他区域内选址，做出全国范围内的维修服务站选址决定。

3.3 区域内维修站选址

维修站的选址采取集合覆盖模型，要求满足所有的维修需求，本文考虑距离因素，距离在一定程度上可以反映响应时间、服务水平等因素。选址的首要依据是进行需求分析，车辆经过的任何地方都有可能成为需求点，最终选择的候选维修站需要满足在统计内的所有需求点的需求，且维修站数量最少。

按照该企业原有维修数据统计，全国范围内的临时维修服务活动大多集中在270 个左右的临时维修服务站点，企业可接受建立300个左右维修服务站的费用。两个月内需求点的数量76 160 个，可以得出，一个维修站需要满足大概260个需求点的维修需求。根据聚类的结果，得出每一个区域所需要建立的维修站数量最多如下：35、65、76、36、40、33 个，总数为285个。利用matlab2018a得到满足需求的维修站地理坐标。

首先选择需求点最多的范围进行集合覆盖模型选址，以第三个区域为例，主要包括内蒙、河北、山东、吉林、河南等地，得出不同覆盖半径下的维修站数量，在满足费用要求的情况下，建立76 个维修站，维修半径0.998 4L（地理半径），可以覆盖该区域的全部需求点20 336 个，使顾客满意度最大。76 个维修站坐标见表3，不同覆盖半径所需维修站数量变化趋势如图6所示，第三区域维修站可视化如图7所示。

表3 第三区域内设施坐标列表

得出第三个区域内选址地点后，需要对其他五个区域利用聚类算法进行集合覆盖模型的选址，在满足成本的要求下，求出各自范围内维修服务站的数量，完成全国范围内的选址计划。最终得到285组地理坐标，部分地理坐标对应实际地理位置见表4。

图6 不同覆盖半径下维修站数量

图7 第三区域内选址地点可视化

表4 各区域内选址地点呈现

通过对集合覆盖模型的求解，得出各个区域内维修站的坐标，根据地理信息系统得出实际对应的地点，共得出285个维修站的选址地点。利用ArcGis软件在全国范围内的选址结果，如图8所示。

图8 全国范围服务站选址地点可视化

4 结语

维修服务站的选址大多依据经验进行，对于小范围小规模的选址具有一定的可行性，但是大范围连锁性质的选址以及大批量的建设服务设施必须以科学的方法为依据。

随着信息技术的发展，大数据的成熟与应用，使得在解决实际问题时有了新的思路。本文结合车联网大数据中的轨迹信息以及停靠信息，将其作为选址所需要考虑的因素，对于大规模的选址具有一定的意义。对于维修服务站选址相似课题，可以将车辆的记录作为选址的依据。本文所考虑的选址因素较为单一，今后的研究应聚焦于因素的选择上，比如服务水平、距离成本、运营成本等。此外，应加大信息共享程度，通过车联网将数据及时反馈，涵盖的信息应该更加多样，可以和地理信息系统相结合，及时调整以达到最大的顾客满意度。