利用K-means算法进行最优土壤普查路径的任务规划研究

摘****要

土壤普查，堪称揭示大地奥秘的重要工具，对于维持生态系统的平衡以及确保粮食安全具有不可替代的作用！本文围绕提出的4个问题，重点探讨了在多种限制条件下，工作组实施土壤采样时的最优路径选择。针对问题1，采用暴力求解算法进行处理；对于问题2，则结合k-means聚类算法与暴力求解法加以解决；问题3则借助TOPSIS评价模型予以分析；而问题4则通过暴力求解算法与百度地图API共同计算曲线距离的方式进行应对。

在问题1的设定下，假设采样点坐标已知且速度固定，构建了一个基于暴力搜索法的最优路径模型。首先运用欧几里得距离公式将经纬度数据转换为实际距离（单位：千米），并建立8个采样点之间的距离矩阵。同时引入0-1型决策变量模型，并借助Python编程语言及暴力求解算法得出最优路径方案。最终确定的最佳采样顺序为44—61—158—83—147—100 —31—115；最短行程距离为5.45千米，所需工作时间为6.789390424932063小时。

在问题2的情境中，将附件中的所有数据绘制于散点图中以观察其分布特征。利用k-means聚类方法将222个样本点划分为28个簇，每个簇包含约8个样本点位。完成聚类分析后对各簇进行颜色标注以验证是否满足题设要求。随后针对每个簇分别采用暴力搜索法计算其最优路径，并从中得出时间最长的路线为59—3—210—82—199—130—7—42，耗时达8.3210182156617小时；而耗时最短的路线为187—152—126—51—33—89，仅需5.41207154918711小时。

对于问题3的情况，则构建了一个基于TOPSIS评价体系的优化模型。利用该模型对问题二所得数据以每组8个点作为基准进行差值计算并形成矩阵，并对其进行标准化处理后应用TOPSIS方法找出各行、列的最大值和最小值。计算结果显示最大值与最小值的距离分别为：最大值为 、最小值为 。最终归一化得分为 ，接近于 ，表明第二问所分配的工作时间较为均衡稳定。当所有采样点按照每组7个点位进行聚类分组时共形成 个簇，在此情况下分配方案最为理想。

至于问题四的情形，则建立了一种基于电子地图平台的曲线通勤模型。首先通过百度地图将各采样点可视化展示于地图之上，并依据第一问中采用暴力求解方法获得的八个关键节点最优路径作为基础参考框架；接着使用百度地图开放平台API来精确测量这些节点之间沿道路的实际弯曲路径总长度和所需总时间分别为 千米以及 小时。

关键词**** 旅行商问题；最优路径规划；0-1型决策变量建模；穷举搜索策略；K-Means聚类技术；TOPSIS评估方法

目 录

基于K-means算法的土壤最佳普查路线及任务安排研究.............. 0

摘 要.......................................................................................... 0

一、题目复述.............................................................................. 2

二、题目剖析.............................................................................. 3

二一、关于第一个题目的解析............................................ 3

二二、关于第二个题目的解析............................................ 4

二三、关于第三个题目的解析............................................ 5

二四、关于第四个题目的解析............................................ 6

三、假设条件说明...................................................................... 7

四、术语定义与符号解释.......................................................... 7

五、数学建模及其求解过程......................................................
（五）第一部分的问题建模及解决方案...............................
（六）第二部分的问题建模及解决方案...............................
（七）第三部分的问题建模及解决方案...............................
（八）第四部分的问题建模及解决方案...............................

六、模型评估与改进措施..........................................................
六一 模型的优势之处 .....................................................
六二 模型存在的不足 .....................................................
六三 模型的应用前景 .....................................................

参考资料....................................................................................

附录资料 ...................................................................................

一、问题重述与背景分析

土壤普查作为揭示地球生态奥秘的重要工具，对于保持自然生态平衡以及确保粮食安全具有关键意义。目前，有一个工作团队为了全面掌握土壤资源的数量、质量、分布及利用情况，在前期准备阶段需要首先明确普查区域，制定详细的普查计划，并规划最佳路线，以更高效地完成土壤采样任务，从而保障日常取样的顺利进行。

问题1：31、44、61、83、100、115、147、158这8个采样点为工作组某日的采样目标。工作组可在这些点之间以20km/h的速度直线通行。请确定起始点与最优路径，使当日的工作时间最短，并计算具体时长。

问题2：将附件1中所有数据按照就近原则划分为28个簇，每个簇的点位数量以8个为基准。同时，工作组可在这些点之间以20km/h的速度直线通行。对每个簇求解最优路径，并计算各簇工作时间的最大值和最小值。

问题3：工作组的理想工作时间为8小时，但由于地理环境等因素影响，整体工作时间可能有所延长，但不得超过8.5小时。基于此标准，请判断第二问模型中所有最优路径的时间是否符合8至8.5小时的要求，并评估工作时间是否均衡。若自行设定每日采样点数量，请提供在不超过8.5小时内实现最均衡采样点分配的方案。

问题4：在第一问的基础上，工作组采用专车通勤方式，在第一问涉及的8个点之间移动。根据附件提供的最优路径信息，并结合网络电子地图API计算出完成当日工作的最短时间。

二、问题分析框架构建

2.1问题1的分析

问题1旨在使工作组能够更高效地完成每日任务，从而设计出最优的行进路线。

问题1属于旅行商数学问题（TSP问题），并且具体表现为不返回初始出发点的旅行商问题。针对该类问题，通常采用蚁群算法、贪心算法、Dijkstra算法以及暴力搜索法等方法进行求解。

附件1中提供的数据包括点位编号、经纬度信息以及工作组在各点的采样时间。本题主要依赖于经纬度数据进行分析。

在问题1设定的条件下，需对附件1中提及的8个目标采样点进行分析。已知行驶速度为20km/h，首先将各点的经纬度转换为弧度值，随后运用欧几里得距离公式计算任意两点之间的直线距离（单位为公里），进而构建这8个采样点之间的距离矩阵。最后通过暴力求解算法并结合Python软件，确定最优路径方案。

图2-1 问题1流程示意图

2.2问题2的分析

问题2为了更高效地推进任务实施，首先需要拟定普查计划，明确每日的工作范围，确保每日所覆盖的区域划分科学合理。

问题2归类为聚类分析类型的问题，针对该类问题通常可采用k-means方法、k-medoids算法、凝聚型算法、分裂型算法、DBSCAN算法以及OPTICS算法等多种处理方式。

附件1中提供的数据内容包含点位编号、地理坐标信息以及工作组在对应位置进行采样的具体时间。

在问题2的约束条件下，对附件1中的全部采样点进行分析时，应首先将各数据点转化为散点图形式以观察其分布特征，随后应用K-means算法对所有样本点进行聚类划分，并通过暴力搜索方法确定每个聚类中的最佳解。

图2-2 问题2流程示意图

2.3问题3的分析

问题3属于评估优化类问题。

在问题3中，以问题2为基础，旨在判断每日工作时间是否实现合理分配与均衡分布。通过对问题2中划分出的28个聚类所对应的最优路径进行评估，确定数据集中的最大值与最小值，并进一步分析最大值是否超出8.5小时的阈值。随后，将数值8设定为基准点，计算差值并转化为矩阵形式，对矩阵进行标准化处理。接着运用TOPSIS方法得出归一化评分，并将其与数值1进行对比分析，从而判断工作时间是否达到均衡状态。

图2-3问题3流程示意图

2.4问题4的分析

在问题1的约束条件下，工作组的通勤方式调整为沿乘车曲线进行移动，无法实现两点之间的直线通行。

问题4被归类为最优路径相关的研究范畴。

针对问题4，可通过电子地图这一工具来开展对最优路径以及最短距离的计算与分析。

图2-4 问题4流程示意图

三、模型假设构建与分析

1．假定地球呈现为一个标准的正球体形态，其半径取值为平均半径6371km。

2．假定工作组在前往各个采样点位移动过程中，不会受到诸如高墙、铁道等构筑物的干扰。

3．假定工作组在各采样点执行采样任务时，无需考虑天气状况所带来的影响。

4．假定工作组在各采样点之间通勤时，不会遭遇交通拥堵、红灯等可能降低行进速度的情形。

四、定义与符号说明

五、模型的建立与求解

数据预处理：

1．信息的完整性与可信度

2．对原始数据实施

5.1问题1的模型建立与求解

5.1.1 基于暴力搜索法的最优路径模型建立

通过应用欧几里得距离公式进行计算得出结果

i点与j点之间的间距

式中：ij=0,1,2,3,4,5,6,7,8。

将8个点之间的间距构建成矩阵 M
表5-1距离矩阵

定义Mij为i点与j点之间的距离。将包含8个点位的编号集合表示为n{1,2,3,4,5,6,7,8}。设P为所有可能路径的集合，其中每条路径P是集合n中元素到自身元素的映射关系，且对于任意i，P(i)

P(I)适用于所有i

i。在此设定中，假定所有点均位于同一平面内，忽略实际地形及地理条件的影响，并将速度表示为V0。

完成该段距离Dij所需耗费的时间为：

（1.3）

以路径构建为基础的TSP问题数学表达方式，可将任意一条行进路线表示为

（1.4）

（1.5）

在模型中，每个路径节点的到达时间Tvi与其前一节点的到达时间Tvi-1之间存在累加关系，

该关系可通过递推公式进行表达：

（1.6）

针对TSP问题，可构建一种0-1型的决策变量模型：

最小化∑{i=0}^n ∑{j=0}^n x_{ij} t_{ij},

因此

（1.7）

（1.8）

5.1.2基于暴力搜索法的最优路径模型的求解

图5-1问题1采样点散点图

对已完成预处理的八个采样点数据，首先借助Python软件（相关编程代码见）生成对应的散点图，以直观展示各采样点的分布情况。

5.1.3基于暴力搜索法的最优路径模型结果

借助Python编程语言开发的软件程序（详见附件问题1解题lab.py），成功计算出了8个节点的最优行进路线：

44>>>>61>>>>158>>>>83>>>>147>>>>100>>>>31>>>>115
所获得的最短路径长度为5.45千米。

图5-2 问题1路径示意图

5.2问题2的模型建立与求解

5.2.1 基于k-means聚类算法的聚类模型建立

利用Python对附件1中所列所有点的经纬度数据进行可视化处理，以确定各点之间的相对空间位置关系。

图5-3所示为所有采样点位分布图

首先，假设有28个初始位置点，并且存在一个包含8个数据的数据集。这些初始位置点被设定为各个群组的中心。接下来，计算每个数据点与所有初始位置点之间的距离，并根据距离的远近对每个数据点进行归类，将其分配至距离最近的初始位置点。随后，对每个初始位置点所对应的全部数据点进行求和运算，并计算其平均值，从而得到新的群组中心。最终，持续执行聚类操作，直至群组中心的位置不再发生任何变化为止。

5.2.1 基于k-means聚类算法的聚类模型的求解

以群组中心作为各簇的核心位置，对所属簇内的点集实施染色排列处理。

图5-4采样点位聚类图

通过问题1中（1.1）和（1.2）式，对每个簇内的点位进行计算，从而确定各点之间的间距。

假定所有采样点均处于同一平面，并忽略实际地形及地理条件的影响，设定速度为V0。依据问题一中的（1.1）、（1.4）、（1.5）和（1.6）式可推导出相应结果：

基于此，针对TSP问题构建了0-1型的决策变量模型：

最终依据公式（1.7）与（1.8）进行计算，得出最短路径以及完成该路径所需的工作时长。

5.2.3基于k-means聚类算法的聚类模型结果

对全部数据进行整理后，可确定所有路线规划中时间最长与最短的路径。其中耗时最长的路径为59 >>>> 3 >>>> 210 >>>> 82 >>>> 199 >>>> 130 >>>> 7 >>>> 42，对应的总时间为8.3210182156617小时；而耗时最短的路径为187 >>>> 152 >>>> 126 >>>> 51 >>>> 33 >>>> 89，其所需时间为5.41207154918711小时。

5.3问题3的模型建立与求解

5.3.1 基于TOPSIS算法的优化评价模型建立

将问题2所获取的时间数值输入至矩阵中，以8作为基准点，计算各数据与基准点之间的距离，并对所得结果进行正向化处理，形成如表5-2所示的差值表。

鉴于第28簇仅经过6个点位，因此将其排除。

5.3.2基于TOPSIS算法的优化评价模型的求解

5.3.3 基于TOPSIS算法的优化评价模型结果

借助Python软件（详见附件 问题3 lab3.py）可计算得出D+i=15.3685533，D-i=123.1363744482378，S=0.889039660727。该数值与1较为接近，表明当前工作时间未出现超时现象，且整体工作时长保持相对稳定状态。

5.4问题4的模型建立与求解

5.4.1 基于电子地图的曲线通勤模型建立

工作组将通勤方式调整为专车曲线通勤模式，构建HTML超文本标记语言网页，以观察地图上八个点位的展示效果。通过应用最优化路径模型，对最优路径进行计算分析。

图5-5 问题4模型分布点

5.4.2 基于电子地图的曲线通勤模型求解

依据问题4中所设定的点位，结合问题1中的（1.1）与（1.2）公式，可计算出各点之间的间距。

假定所有点均处于同一平面内，并忽略实际地形及地理条件的影响，将速度表示为V0。

通过运用问题一中的（1.1）、（1.4）、（1.5）以及（1.6）式，可以推导出相应的结果：

基于TSP问题，构建了0-1型的决策变量模型如下：

mini Ti,i=0n j=0n xijtij,

最终借助（1.7）与（1.8）两个公式，计算得出最短路径曲线以及当日所需的工作时长。

图5-6 问题4的分析结果

5.4.2 基于电子地图的曲线通勤模型结果

依据所附的Python程序（详见附件 问题4 lab4.py）进行计算后获得的数据表明，8个点之间最佳路径的曲线距离为12.637千米，而完成该路径所需最少耗时为7.148516666666667小时。

六、模型的评价及优化

6.1 模型的优点

1. 在应对大规模数据处理任务时，所构建的模型具备较高的结果复用性。

2. 针对包含大量距离坐标点的样本数据集，能够高效便捷地完成聚类分析操作，从而提升数据在实际应用过程中的便利性与操作效率。

6.2 模型的缺点

1. 采用暴力搜索策略会导致计算效率低下，处理速度较慢。

2. 针对问题2中所应用的k-means聚类方法，其仅能获得局部最优解，而无法达到全局最优解的目标。

3. 在处理大规模数据集时，部分程序存在较高的代码复用率，导致整体结构冗余繁杂，进而影响分析结果的清晰度与可读性。

6.3 模型的推广

该模型的应用范围不仅限于样本点的路径规划，还能够应用于城市内居民点之间的最佳路径设计、机器人通过深度学习实现的最优移动轨迹规划，以及智能车辆中灰度识别传感器所采用的最佳路径选择等多个方面。

参考文献综述

[1]姚佼,吴秀荣,李皓,等.基于改进K-means算法的物流配送中心选址研究[J].物流科技,2024,47(05):10-13+19.DOI:10.13714/j.cnki.1002-3100.2024.05.003

[2]邬俊俊.大规模旅行商问题的智能优化算法研究[D].重庆大学,2022.DOI:10.276解晓乐.基于深度强化学习的智慧物流园区长途配送路径规划方法[J].广州航海学院学报,2024,32(01):30-34+68.

[3]李刚,智宏鑫.电力巡检机器人路径规划方法综述[J].电力科学与工程,2024,40(04):1-11.70/d.cnki.gcqdu.2022.001888

[4]解晓乐.基于深度强化学习的智慧物流园区长途配送路径规划方法[J].广州航海学院学报,2024,32(01):30-34+68.

[5]牟治宇,张煜,范典,等.基于深度强化学习的无人机数据采集和路径规划研究[J].物联网学报, 2020, 4(3):10.DOI:10.11959/j.issn.2096.