基于最優(yōu)遍歷的巡回采茶問題研究

陳明新　劉嘉旺　戴厚平

摘? 要：針對(duì)茶農(nóng)采茶路線最優(yōu)化的實(shí)際問題，本文首先應(yīng)用奇偶作業(yè)點(diǎn)法將抽象出來的茶田區(qū)域圖（非歐拉圖）轉(zhuǎn)化成歐拉圖，再以Fleury算法為基礎(chǔ)來尋找該歐拉圖的最優(yōu)巡回路線。最后以湖南省湘西自治州保靖縣的一片茶田區(qū)域?yàn)槔?，?duì)該方法的可行性和有效性進(jìn)行了說明。通過對(duì)比分析，表明利用Fleury算法制定出的采茶路線，可以節(jié)約時(shí)間及人力，提高茶農(nóng)采茶的效率，為茶農(nóng)采茶提供了一些參考和依據(jù)。

關(guān)鍵詞：采茶路線最優(yōu)化;奇偶點(diǎn)作業(yè)法;Fleury算法

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

但是對(duì)于茶農(nóng)采茶路線規(guī)劃的實(shí)際問題，目前鮮有相關(guān)參考文獻(xiàn)。本文將結(jié)合實(shí)際的茶農(nóng)采茶問題，通過實(shí)地采集茶田相關(guān)數(shù)據(jù)，利用Fleury算法對(duì)茶農(nóng)的采茶路線進(jìn)行合理規(guī)劃，提高茶農(nóng)采茶的效率，節(jié)約人力、物力。

1? 采茶問題

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

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

2? 算法設(shè)計(jì)

2.1? 奇偶作業(yè)法

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

奇偶作業(yè)法實(shí)行的依據(jù)為：

設(shè)C是一條能經(jīng)過帶權(quán)連通圖G的任意一條邊至少一次的回路。C是該帶權(quán)連通圖G的最優(yōu)回路的充分必要條件是C對(duì)應(yīng)的歐拉圖G^*能夠滿足以下條件：

（1）帶權(quán)連通圖G的每條邊在歐拉圖G^*中能夠重復(fù)出現(xiàn)的次數(shù)不超過1。

（2）帶權(quán)連通圖G的每個(gè)包含重復(fù)出現(xiàn)邊的圈在歐拉圖G^*中的重復(fù)出現(xiàn)邊的權(quán)重之和不超過這個(gè)圈的權(quán)重之和的一半。

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

2.2? Fleury算法

當(dāng)茶田圖形可以抽象為歐拉回路時(shí)，應(yīng)用Fleury算法對(duì)該茶田圖形進(jìn)行路徑搜索，可得到歐拉回路。Fleury算法的基本步驟為：

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

Step2：設(shè)P_i=v₀e₁v₁e₂…eivi如果EG-{e₁，e₂，…，e_i}中沒有與v_i關(guān)聯(lián)的邊，則計(jì)算停止，否則從EG-{e₁，e₂，…，e_i}中任取一條邊e_i+1。

（i）e_i+1與v_i相關(guān)聯(lián);

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

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

令i=i+1，返回Step3。

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

在選擇目標(biāo)茶田道路時(shí)，要判斷這條茶田道路的終點(diǎn)是否符合Fleury原理的判定，若符合則可以更新采茶路徑，以便于進(jìn)行下一次的采茶過程，若找不到下一個(gè)茶田交叉點(diǎn)，則返回之前的步驟重新搜索可以實(shí)現(xiàn)的茶田道路。

在選擇下一個(gè)茶田交叉點(diǎn)時(shí)，要進(jìn)行多次判斷：

3? 數(shù)值算例

3.1? 茶田平面圖形

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

根據(jù)圖論理論，設(shè)茶田區(qū)域內(nèi)各個(gè)茶田的交叉點(diǎn)為圖G中的頂點(diǎn)，記為V（G）各茶田為圖G的邊，記為E（G）。本文通過走進(jìn)茶田進(jìn)行實(shí)地測量，得出了各茶田之間邊的權(quán)重，具體如下圖所示。

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

3.2? 檢驗(yàn)過程

對(duì)圖3進(jìn)行檢驗(yàn)，計(jì)算已添加重復(fù)的邊的每個(gè)圈的權(quán)數(shù)和與每個(gè)圈所含重復(fù)的邊的權(quán)數(shù)之和。如表1所示。

根據(jù)表1可知，包含重復(fù)邊的所有圈所含重復(fù)的邊的權(quán)數(shù)之和沒有超過該圈的權(quán)數(shù)總和的一半。因此可以判定此方案為最優(yōu)方案。

3.3? 求解流程

根據(jù)Fleury的算法的思想，從起點(diǎn)v₁出發(fā)，最終回到v₁。其中求解的部分過程流程如圖4所示。

在求解過程中，每一個(gè)點(diǎn)選擇的邊都是與該點(diǎn)相關(guān)聯(lián)的邊。特別，如果與該點(diǎn)關(guān)聯(lián)的邊為橋且唯一的話，那么仍選擇這一條邊。上述行進(jìn)路線可由圖5來表示。

將圖5所示的茶農(nóng)采茶的行進(jìn)路線連接起來，最終我們可以得到茶農(nóng)在茶田采茶的最優(yōu)化采茶路線為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₇₈各進(jìn)行了兩次，該回路重復(fù)走過15.9米。

3.4? 對(duì)比分析

通過Fleury算法，得出了新的茶農(nóng)采茶路線。為了評(píng)估該采茶路線的合理性和可行性，我們進(jìn)行了兩次采茶工作。第一次按照茶農(nóng)根據(jù)實(shí)際經(jīng)驗(yàn)制定好的采茶路線進(jìn)行采茶工作，第二次按照新的采茶路線進(jìn)行采茶工作。最后對(duì)比兩次采茶工作中茶農(nóng)的行走距離與所需時(shí)間，對(duì)比結(jié)果如表2所示。

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

4? 結(jié)? 論

本文首先對(duì)黃金茶產(chǎn)業(yè)現(xiàn)狀進(jìn)行了分析，概括了在疫情條件下茶農(nóng)在采茶過程中所面臨的問題，再介紹了奇偶作業(yè)法以及Fleury算法。最后以湖南省湘西土家族苗族自治州保靖縣某一茶田區(qū)域?yàn)槔瑢?duì)茶農(nóng)采茶路線進(jìn)行了研究，驗(yàn)證了Fleury算法在茶農(nóng)采茶路線問題中的應(yīng)用，節(jié)約效果明顯。本文通過運(yùn)籌學(xué)等數(shù)學(xué)學(xué)科知識(shí)，尋找茶農(nóng)采茶最佳遍歷路線，希望在茶農(nóng)采茶實(shí)現(xiàn)高質(zhì)量的同時(shí)，能夠?qū)μ岣咿r(nóng)民的采茶效率提供一些幫助。

參考文獻(xiàn)：

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

[2] 應(yīng)沈靜，袁仁斌，陶駿，等.基于遍歷求二叉樹的程序設(shè)計(jì)與探討 [J].科技風(fēng)，2021（14）：83-87.

[3] 陳鏡宇，郭志軍，尹亞昆.基于混合算法的智能割草機(jī)全遍歷路徑規(guī)劃及其系統(tǒng)設(shè)計(jì) [J].計(jì)算機(jī)科學(xué)，2021，48（S1）：633-637.

[4] 熊億民.基于改進(jìn)蟻群算法的全向移動(dòng)機(jī)器人全遍歷路徑規(guī)劃 [J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2021，30（6）：209-214.

[5] 李玲玉.基于開源GIS和鄉(xiāng)村郵遞員問題的交警巡邏路線優(yōu)化研究與應(yīng)用開發(fā) [D].上海：華東師范大學(xué)，2020.

[6] 管梅谷.奇偶點(diǎn)圖上作業(yè)法 [J].數(shù)學(xué)學(xué)報(bào)，1960（3）：263-266.

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

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

作者簡介：陳明新（2002—），男，侗族，湖南懷化人，本科在讀，研究方向：數(shù)學(xué)與應(yīng)用數(shù)學(xué);

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