基于最優遍歷的巡回采茶問題研究

陳明新　劉嘉旺　戴厚平

摘? 要：針對茶農采茶路線最優化的實際問題，本文首先應用奇偶作業點法將抽象出來的茶田區域圖（非歐拉圖）轉化成歐拉圖，再以Fleury算法為基礎來尋找該歐拉圖的最優巡回路線。最后以湖南省湘西自治州保靖縣的一片茶田區域為例，對該方法的可行性和有效性進行了說明。通過對比分析，表明利用Fleury算法制定出的采茶路線，可以節約時間及人力，提高茶農采茶的效率，為茶農采茶提供了一些參考和依據。

關鍵詞：采茶路線最優化;奇偶點作業法;Fleury算法

中圖分類號：O212? ? ? ? ? ? ? ? ? 文獻標識碼：A文章編號：2096-4706（2021）20-0091-04

Research on Itinerant Tea Picking Problem Based on Optimal Traversal

CHEN Mingxin， LIU Jiawang， DAI Houping

（School of Mathematics and Statistics， Jishou University， Jishou? 416000， China）

Abstract： Aiming at the actual problem of optimizing the tea picking route of tea farmers， this paper first applies the odd-even operation point method to convert the abstracted tea field area map （non-Euler diagram） into an Euler diagram. Then， based on the Fleury algorithm， the optimal itinerant route of the Euler graph is found. Finally， a tea field area in Baojing County， Xiangxi Autonomous Prefecture， Hunan Province is taken as an example to illustrate the feasibility and effectiveness of this method. Through comparative analysis， it is shown that the tea picking route developed by the Fleury algorithm can save time and manpower， improve the efficiency of tea picking of tea farmers， and provide some reference and basis for tea farmers to pick tea.

Keywords： optimum tea picking route; odd-even point operation method; Fleury algorithm

0? 引? 言

自2020年以來黃金茶的生產總量及生產總值都在穩固上升，產業項目建設力度也在不斷加大，基地的規模也在不斷擴展。政府通過強扶優茶葉新型經營主體，建立貧困戶與經營主體的利益聯結，充分發揮企業、合作社的示范帶動作用，助推產業脫貧攻堅和實現產業持續健康發展.同時為了著力打造優勢明顯、布局合理、配套完備、品質優異的黃金茶的特色產業集群，各地的人們也都一直在做出不懈的努力。但2020年爆發的新冠疫情導致交通運輸嚴重受阻，消費者活動受限，致使消費行為的發生困難，直接導致黃金茶價格降低，嚴重滯銷。因此，設計有效的采茶路線，可以降低茶農在采茶方面的成本，從而提高茶農的經濟收入。茶農采茶問題實質上就是路徑規劃的問題，目前國內很多學者在路徑規劃方面做了研究，彭永昆等[1]提出了一種基于回溯的雙向完全遍歷路徑規劃算法，實現了工作環境的全覆蓋;應沈靜[2]等介紹了二叉樹的四種遍歷方法，實現了四種條件下求解二叉樹的程序;陳鏡宇[3]研究了智能割草機器人路徑規劃問題;熊億民[4]提出了基于改進蟻群算法的全向移動機器人全遍歷路徑規劃方法。這些研究成果開展了最優邊遍歷的理論探索和實證研究，提供了較好的有益參考。

但是對于茶農采茶路線規劃的實際問題，目前鮮有相關參考文獻。本文將結合實際的茶農采茶問題，通過實地采集茶田相關數據，利用Fleury算法對茶農的采茶路線進行合理規劃，提高茶農采茶的效率，節約人力、物力。

1? 采茶問題

采茶一直都是茶農的一項關鍵工作，采茶過程進行的好與否與茶農經濟收入高低有著直接的關系。在采茶期，如果茶農對成熟茶田的采茶路徑進行有效規劃，可以使得采茶的經濟成本明顯降低。采茶的目標路徑一般為全部成熟或者大部分都成熟了的茶田。在實際的采茶過程中，茶農需將每條目標茶田路徑至少走過一遍。茶農從采茶的起點出發，按照預先制定好的采茶路線進行采茶工作，完成所有目標茶田路徑的采茶任務后返回起點。在茶農的采茶工作中，采茶路徑的設計是關鍵一環，好的采茶路徑可以提高茶農的采茶效率，使得采茶成本最小化，提高茶農的經濟收入。當前，茶農主要是依據個人的經驗來制定采茶路徑，以這樣的方式設計出的采茶路線往往不是最優的。茶農采茶問題的關鍵是優化采茶路線，設計出最短的采茶路線，從而提高茶農的采茶效率。本文基于單茶農和單出發點研究茶農采茶路線優化問題。茶農采茶路線設計的問題類似于圖論中的郵遞員問題;郵遞員以郵局為起點進行郵件分送工作，區域內所有道路都有郵件需要分送，要求沿著道路完成郵件的分送，最后回到郵局，并且保證這個過程中走過的路徑總長度最短。通過分析，可以發現茶農采茶路線優化問題與郵遞員問題的相似之處。

茶農采茶路線優化問題的模型為：茶農從起點出發去遍歷所有目標茶田，最后返回起點。他必須經過每條目標茶田至少一次，要求為茶農設計一條采茶路線，使得整個采茶過程中的路程最短。本文中茶農的起點與郵遞員問題中郵遞員的起點相似，位于目標茶田道路上。茶農采茶路線優化問題可以抽象為圖論的問題，該問題的實際圖論模型為：把茶農所遍歷的茶田區域網看作是一個帶權的連通圖G（V，E），E表示茶農遍歷區域內的所有茶田，V表示該區域內茶田的交叉點和采茶起點，目標茶田用P表示且有P?E，非目標茶田用P＼E表示，邊上的權值代表對應茶田道路的長度，茶農最優采茶路線為求圖G的一個包含P中所有邊（至少一次）且經過起點的回路，并使得這條回路的所有權值之和最小。

2? 算法設計

2.1? 奇偶作業法

首先介紹奇偶點作業法[6]以及使用奇偶作業點法使得非歐拉圖變成歐拉圖的具體步驟。

奇偶作業法實行的依據為：

設C是一條能經過帶權連通圖G的任意一條邊至少一次的回路。C是該帶權連通圖G的最優回路的充分必要條件是C對應的歐拉圖G^*能夠滿足以下條件：

（1）帶權連通圖G的每條邊在歐拉圖G^*中能夠重復出現的次數不超過1。

（2）帶權連通圖G的每個包含重復出現邊的圈在歐拉圖G^*中的重復出現邊的權重之和不超過這個圈的權重之和的一半。

奇偶點作業法實施的具體步驟：第一步：通過任意一個方案找出圖中所有奇數點（所連接的邊的數量為奇數條），以加邊的方式將奇數點進行配對，直至新圖中不再出現奇數點為止;第二步：按照路徑規劃[7]的方法反復計算，直到圖中重復的邊總長度變短。第三步：按照上述的條件（2）重復執行第二步。

2.2? Fleury算法

當茶田圖形可以抽象為歐拉回路時，應用Fleury算法對該茶田圖形進行路徑搜索，可得到歐拉回路。Fleury算法的基本步驟為：

Step1：任取v₀屬于V（G），令P₀=v₀。

Step2：設P_i=v₀e₁v₁e₂…eivi如果EG-{e₁，e₂，…，e_i}中沒有與v_i關聯的邊，則計算停止，否則從EG-{e₁，e₂，…，e_i}中任取一條邊e_i+1。

（i）e_i+1與v_i相關聯;

（ii）除非沒有別的邊可以選擇，否則e_i+1不應該是G_i=G-{e₁，e₂，…，e_i}的割邊。

Step3：設e_i+1=（v_i，v_i+1），把e_i+1，v_i+1加入P_i。

令i=i+1，返回Step3。

茶農采茶問題路徑優化問題的主要邏輯與Fleury算法步驟相對應[8]，首先，判斷該圖是否為歐拉圖，如果不是，則通過奇偶點作業法將其化成歐拉圖;其次，確定歐拉回路的采茶起點和起始茶田道路：再次，尋找接下來需要經過的茶田道路和茶田交叉點，直到完成采茶任務;最后，得出采茶路徑以及對應的權重，完成茶農采茶路徑的優化;

在選擇目標茶田道路時，要判斷這條茶田道路的終點是否符合Fleury原理的判定，若符合則可以更新采茶路徑，以便于進行下一次的采茶過程，若找不到下一個茶田交叉點，則返回之前的步驟重新搜索可以實現的茶田道路。

在選擇下一個茶田交叉點時，要進行多次判斷：

3? 數值算例

3.1? 茶田平面圖形

本文根據圖論理論，將整個茶田區域抽象成一個無向圖，并將每個茶田看作一條邊，通過Fleury算法搜索出走完整個茶田區域并回到原點的最短路徑。在得出最后結果之前，本文對所計算的結果進行了檢驗，以確保模型的合理性以及算法的可行性。

根據圖論理論，設茶田區域內各個茶田的交叉點為圖G中的頂點，記為V（G）各茶田為圖G的邊，記為E（G）。本文通過走進茶田進行實地測量，得出了各茶田之間邊的權重，具體如下圖所示。

按照奇偶作業法的假設條件，第一步先是判斷圖G是否是歐拉圖。通過條件，我們可以看出在圖2中，頂點v₁、v₄、v₅、v₇、v₈是奇數點，所以圖2非歐拉圖。將非歐拉圖轉化成歐拉圖就需要添加重復邊。給v₁、v₇的邊增加一條重復的邊;給v₄、v₅的邊增加一條重復邊，給v₇、v₈的邊增加一條重復邊，且使得增加的重復邊權值之最小。據上述分析，可通過奇偶點作業法得到圖3，此時圖3中無奇數頂點，即為歐拉圖。

3.2? 檢驗過程

對圖3進行檢驗，計算已添加重復的邊的每個圈的權數和與每個圈所含重復的邊的權數之和。如表1所示。

根據表1可知，包含重復邊的所有圈所含重復的邊的權數之和沒有超過該圈的權數總和的一半。因此可以判定此方案為最優方案。

3.3? 求解流程

根據Fleury的算法的思想，從起點v₁出發，最終回到v₁。其中求解的部分過程流程如圖4所示。

在求解過程中，每一個點選擇的邊都是與該點相關聯的邊。特別，如果與該點關聯的邊為橋且唯一的話，那么仍選擇這一條邊。上述行進路線可由圖5來表示。

將圖5所示的茶農采茶的行進路線連接起來，最終我們可以得到茶農在茶田采茶的最優化采茶路線為C={v₁e₁₂v₂e₂₃v₃e₃₄v₄e₄₅v₅e₂₅v₂e₂₇v₇e₆₇v₆e₄₆v₄e₄₅v₅e₅₆v₆e₆₈v₈e₇₈v₇e₁₇v₁e₁₉v₉e₈₉v₈e₇₈v₈e₇₈v₇e₁₇v₁}，由此可以得出邊e₁₇、e₄₅、e₇₈各進行了兩次，該回路重復走過15.9米。

3.4? 對比分析

通過Fleury算法，得出了新的茶農采茶路線。為了評估該采茶路線的合理性和可行性，我們進行了兩次采茶工作。第一次按照茶農根據實際經驗制定好的采茶路線進行采茶工作，第二次按照新的采茶路線進行采茶工作。最后對比兩次采茶工作中茶農的行走距離與所需時間，對比結果如表2所示。

通過分析表2可知，按照Fleury算法制定的采茶路線進行采茶工作，可減少73.5米的行走距離，節約采茶時間16.5分鐘。按照一人采茶，一天十次采茶來計算，可節約時間165分鐘。因此，依據Fleury算法制定的采茶路線能夠節約時間，提高茶農采茶的效率。

4? 結? 論

本文首先對黃金茶產業現狀進行了分析，概括了在疫情條件下茶農在采茶過程中所面臨的問題，再介紹了奇偶作業法以及Fleury算法。最后以湖南省湘西土家族苗族自治州保靖縣某一茶田區域為例，對茶農采茶路線進行了研究，驗證了Fleury算法在茶農采茶路線問題中的應用，節約效果明顯。本文通過運籌學等數學學科知識，尋找茶農采茶最佳遍歷路線，希望在茶農采茶實現高質量的同時，能夠對提高農民的采茶效率提供一些幫助。

參考文獻：

[1] 彭永昆，徐勝，陳元電，等.基于回溯的室內機器人完全遍歷路徑規劃 [J].工業控制計算機，2021，34（6）：33-36.

[2] 應沈靜，袁仁斌，陶駿，等.基于遍歷求二叉樹的程序設計與探討 [J].科技風，2021（14）：83-87.

[3] 陳鏡宇，郭志軍，尹亞昆.基于混合算法的智能割草機全遍歷路徑規劃及其系統設計 [J].計算機科學，2021，48（S1）：633-637.

[4] 熊億民.基于改進蟻群算法的全向移動機器人全遍歷路徑規劃 [J].計算機系統應用，2021，30（6）：209-214.

[5] 李玲玉.基于開源GIS和鄉村郵遞員問題的交警巡邏路線優化研究與應用開發 [D].上海：華東師范大學，2020.

[6] 管梅谷.奇偶點圖上作業法 [J].數學學報，1960（3）：263-266.

[7] 彭光超.基于郵遞員問題的深圳供電局變電站巡視路線研究 [D].天津：天津大學，2016.

[8] 侯茂盛，孫明利，楊帆，等.基于改進Fleury算法的激光掃描投影路徑規劃方法 [J].應用光學，2019，40（3）：493-499.

作者簡介：陳明新（2002—），男，侗族，湖南懷化人，本科在讀，研究方向：數學與應用數學;

通訊作者：戴厚平（1979—），男，漢族，湖南隆回人，副教授，博士，主要研究方向：微分方程數值解和數學建模。