基于K-means算法和TSP模型的采樣路徑規劃

摘要：研究旨在通過結合k-means算法和旅行商問題（TSP） 模型，分析土壤采樣路徑。首先將采樣點的經緯度坐標轉換 為平面坐標，針對單日多點的采樣路徑優化建立TSP模型，并分別應用動態規劃和遺傳算法求解，最終得到優化路徑。 隨后，為了進行多日采樣任務分配，利用k-means聚類算法將樣品劃分為若干個簇，并在每個簇內建立TSP模型進行路 徑優化。最后，相比其他研究，文章引入實際道路網絡和交通狀況，通過第三方地圖服務的路徑規劃API獲取真實的行 駛距離和時間數據，構建出更為精準的TSP模型。

關鍵詞：路徑規劃；TSP模型；動態規劃；遺傳算法；k-means聚類

中圖分類號：TP3 文獻標識碼：A

文章編號：1009-3044（2025）13-0028-04

0 引言

在土壤采樣路徑規劃研究中，近年來的研究主要 集中在優化采樣效率和提高數據準確性上?，F有工 作多采用傳統的路徑優化算法（如貪心算法和模擬退 火） ，但這些方法在復雜地理環境和實際應用中往往 難以有效適應。此外，部分研究雖然考慮了空間數據 的影響，但未能充分整合多種算法的優勢，導致路徑 規劃的精度和效率不足。

本研究綜合運用了多種計算機相關算法，包括動 態規劃[1] 、遺傳算法[2] 、k-means 聚類算法[3] 等，針對土 壤采樣[4] 路徑優化和任務分配問題進行了深入探討。

區別于大多數研究未能充分考慮實際地理環境狀況 的影響，本文旨在通過數學建模與優化算法，提升土 壤采樣工作的精準性和科學性。首先，建立了旅行商 問題（TSP） 模型[5] ，通過先使用動態規劃對較小規模采 樣點集合進行精確求解，獲得初步的優化路徑。在此 基礎上，使用遺傳算法對更大規模的采樣點進行優 化，以此求解較優采樣路徑[6] 。其次，利用k-means聚 類算法將采樣點合理劃分為多個簇，并在每個簇內應 用遺傳算法優化路徑；最后，結合實際道路狀況，引入 真實數據，進一步保證TSP模型的精準性[7] 。本文的 研究不僅提高了土壤采樣的效率，還為相關領域的決 策提供了定量依據。

1 基于TSP模型的單日采樣路徑優化

1.1 坐標轉換的建立

使用墨卡托投影（Mercator Projection）將經緯度坐 標轉換為平面直角坐標系下的x-y坐標。

1） 計算中間變量

第一偏心率

5）決策變量為二進制：

xij ∈ { 0，1}，?i，j = 1，2，...，8

使用求解TSP問題的算法，如分支定界法、切平面 法或啟發式算法，求解得到最優解。輸出最優解，即完 成采樣點采樣任務的最短工作時間和對應的最優 路徑。

4 結束語

研究圍繞采樣任務的路徑優化問題，采用旅行商 問題（TSP） 模型進行分析，旨在提高采樣效率和資源 利用率。針對多個采樣點的任務，研究提出了多種算 法解決方案，包括動態規劃和元啟發式算法（如遺傳 算法） ，以求得最短路徑和最優工作時間。首先，針對 單日多點采樣路徑優化，建立 TSP 模型，并應用動態 規劃和遺傳算法求解最優采樣路徑。接著，利用 k means 聚類將樣品劃分為若干簇，在每個簇內建立 TSP模型確保工作量均衡。此外，引入實際情況分析， 通過第三方地圖獲取真實數據，構建更精準的TSP模 型。與此同時，采樣點的地理分布和環境變化也可能 影響模型的適用性。其次，算法的計算效率在面對大 規模數據時可能存在瓶頸。未來考慮改進算法以提 高處理大規模數據的能力，探索更多元啟發式算法的 組合應用，以及考慮環境變化因素對路徑規劃的影 響，以實現更為靈活和高效的土壤采樣方案。綜上所 述，本研究通過算法模型的應用，優化了采樣任務的 路徑規劃，提升了工作效率，為相關領域的任務管理 提供了有效的解決方案。

參考文獻：

[1] 丁志杰，王亞飛，章翼辰，等.基于復合動態采樣的自動駕駛 礦車節能路徑規劃方法[J]. 汽車工程，2024，46（4）：588-595， 642.

[2] 林海濤，曹健銘，李漢森，等.一種利用遺傳算法處理類別不 平衡問題的欠采樣方法[J]. 韓山師范學院學報，2024，45（3）： 11-23.

[3] 王世剛，關紅利.自定義聚類中心點的快速K-means聚類點 云精簡算法[J].工業控制計算機，2024，37（8）：123-125.

[4] 楊厚城，夏丹燕，米亞龍，等.一種農田自動土壤采樣車的仿 真設計與試驗[J].農機化研究，2025，47（5）：67-74.

[5] 鄔俊俊.大規模旅行商問題的智能優化算法研究[D].重慶： 重慶大學，2022.

[6] 李軍，郭育煒，葉威.基于路段轉移采樣的最優路徑集計算方 法[J].華南師范大學學報（自然科學版），2022，54（4）：82-88.

[7] 蒲思睿 . 基于 GIS 構建物流配送 TSP 優化模型的建模研究 [J].現代商業，2018（18）：16-17.

【通聯編輯：朱寶貴】