多目標生鮮食用菌配送路徑

羅 奇，周 煜

（1.武漢體育學院體育工程與信息技術學院，湖北 武漢 430079；2.武漢體育學院研究生院，湖北 武漢 430079）

蟻群算法是由Marco Dorigo[1]在1992年提出的一種群集智能算法，其核心內容還是利用了自然界螞蟻通過信息素進行間接通訊，利用信息素信息和與問題相關的啟發式信息逐步構造出問題的解。這種系統的組織是從一開始的無序狀態逐漸轉變為有序過程，即螞蟻一開始是盲目覓食的，找到食物后會越來越有序地向食物所在地進發，形成一個有序的覓食過程。這種自組織性大大增強了蟻群算法的魯棒性。通過將這一算法應用在生鮮食用菌物流配送路徑上，希望能夠為食用菌物流配送路徑的優化提供科學依據。

1 食用菌生鮮物流配送問題

食用菌生鮮冷鏈物流面對的都是冷藏冷凍的生鮮食用菌類產品，從食用菌原材料入廠的那一刻起，在生產過程、裝卸搬運、物流運輸和倉庫保存等全過程，應一直處于低溫環境，用于保證生鮮食用菌的品質[2]。由于生鮮食用菌產品從出廠到物流運輸，再經過配送最終到達消費者的手上需要較長的時間，而生鮮食用菌產品本身的品質保障時效較短，為了延長保鮮期限，人們采取了制冷冷藏技術，并將其應用于生鮮食用菌產品的物流配送全過程中，低溫環境有效減少了生鮮食用菌的腐爛變質，保證了產品的質量。

冷鏈物流從本質上來說也屬于物流，具備一般物流的所有特點[3]。但由于生鮮食用菌的特殊性，冷鏈物流除有低溫貯藏的要求外，還都有一個時效性要求，即整個食用菌產品的物流配送流通時間要盡可能的短。

目前，壓縮物流配送時間的方法主要是建立多級物流倉庫，增加物流節點，以增加物流配送點到客戶的距離，從而縮短配送時間。但這也帶來新的問題，就是物流配送路線的合理性問題。即需要將貨物一個個送到所有的物流節點，走一條什么樣的路線能夠不遺漏一個節點，而且所有的路線距離最短或用時最少，這就是所謂的路徑優化問題，也是食用菌產品物流配送中首先需要解決的問題。如果對多配送目標進行規劃是很復雜的工作，更有一些配送中心自身并不清楚需要什么樣的目標，只是為了完成配送任務或者只是得到各方都可以接受的配送路徑。因此，多種配送目標造成了生鮮食用菌配送路徑規劃的難題。

2 食用菌配送路徑蟻群算法

2.1 蟻群算法基本原理

通過2只螞蟻覓食過程來說明蟻群算法的基本原理[4]，詳見圖1。

如圖1所示，X點為1個蟻穴，設定這時有2只螞蟻出去覓食，螞蟻a和螞蟻b，Y點為食物所在位置，Z點只是中途需要經過的一個地點，即路徑上的一點。假定XYZ圍形成等邊三角形，即XYZ三點間的距離相等，而且2只螞蟻移動速度相同。

2只螞蟻從W1時刻開始從蟻穴X點出發覓食，螞蟻a和螞蟻b分別選擇了XY和XZ兩條路徑；當到W2時刻時，螞蟻a已經走到了Z點，而螞蟻b也走到了Y點，2只螞蟻在其所走過的XY和XZ兩條路徑上都留下了信息素痕跡（用虛線來表示信息素的痕跡），這時兩條路徑上的信息素的濃度是一樣的。隨后螞蟻b發現了食物并將食物通過原路徑XZ搬回了蟻穴，沒ZX又留下了自己的信息素痕跡，這時路徑XZ上的信息素濃度會增加（因為螞蟻b釋放了2次信息素）；而螞蟻a則繼續前行從Z點向Y點進發。需要說明的是在覓食的初始階段，環境中是沒有信息素的。

等到W3時刻時，螞蟻b已經到達了蟻穴X點，而螞蟻a則到達了食物所在地Y點。這時螞蟻b已經第二次離開蟻穴X點，它面臨著兩個選擇，走XZ還是走XY路徑，但螞蟻的路徑選擇不是盲目的，它是根據一定的轉移規則選擇移動方向的，即每條可行的路徑上殘留的信息素濃度，它發現XY路徑上的殘留信息素濃度較高（釋放了2次信息素），因此，螞蟻b選擇XY路徑去尋找。

與此同時，螞蟻a則在Y點找到了食物準備返回蟻穴X點。它也面臨著2個選擇，即XY路徑和YZ路徑，同樣，它也發現XY路徑上的殘留信息素濃度較高（釋放了2次信息素），因此它也選擇XY了路徑返回蟻穴而不是按原路返回。后來的大批螞蟻會選擇XY這條線路的概率會更大，經過的螞蟻越多，由于螞蟻群體中每個螞蟻的信息素不斷更新，XY路徑上的信息素痕跡會不斷被加強，如此往復從而形成正反饋機制，便利更多的螞蟻有機會選擇XY這條更短的路徑來找到食物。

2.2 食用菌配送路徑蟻群算法數學模型的建立

在對食用菌配送路徑實際的蟻群進行建模的過程中，需要解決蟻群中整個蟻群的內部機制、螞蟻個體的建模問題、信息素的更新機制等，根據蟻群算法解決問題的步驟[5]。采用蟻群算法對食用菌配送路徑優化問題建立數學模型。

在物流中心所輻射的地區中有n個需要配送的節點，配送員需要不重復的一次經過所有的物流配送節點進行送貨。建立模型的目的就是他按照怎樣的路徑送貨，從才能使走過的距離最短。我們采用蟻群算法來求解這個配送路徑的問題，將這個問題的算法描述如下。

假設物流配送節點i的坐標為：ci=（xi，yi），i=1，2，3，…，n，這里物流中心所輻射管理的所有物流配送節點總和為 C={c1，c1，c1，… cn}，物流配送節點i，j之間的距離（dij，cm） 計算公式為：

為每只螞蟻設置1個記錄表，用于記錄其走過的物流配送節點，避免重復走過某個物流配送節點，記錄表中第一條記錄就是螞蟻初始時刻所在的物流配送節點，也可以理解為配送中心的位置，當所有的物流配送節點都已經加入記錄表的時候，表示螞蟻已經走完了所有的物流配送節點，完成了配送全過程。令τij（t）為物流配送節點i，j之間的信息素的量，初始時刻其取值為τij（0）=c，其中c為常數。

假設在（t，t+n） 時刻所有螞蟻完成一次周游，則在t+n時刻物流配送節點i，j之間的信息素。

信息素（τij，t）含量計算公式為：

式中：ρ表示時間段（t，t+n） 之間信息素的揮發系數，因此（1-ρ） 就表示信息素的剩余量；而揮發系數取值范圍為 [0，1]；△τij表示在時間段（t，t+n）之間信息素的增加量，計算公式為：

式中：k表示螞蟻的編號；m為螞蟻的數量。

式中：ηi，j為啟發式因子（啟發函數），計算公式為ηi，j＝（di，j）-1，ηi，j表示了螞蟻從物流配送節點i轉移到物流配送節點j的期望程度；s表示螞蟻k下一步選擇的物流配送節點；Jk（i）表示在物流配送節點i處螞蟻k可以選擇走的物流配送節點的集合。m是信息啟發式因子，而n為能見度啟發式因子，n值的增加會降低路徑搜索過程中的隨機性，減弱算法的全局搜索性能。因此，m和n的大小決定了蟻群算法的收斂速度，過大的取值會降低蟻群算法搜索過程的隨機性，過小則會影響算法的準確性和性能。因此這兩個參數需要相互配合，以便調螞蟻在路徑尋找過程中的啟發信息多少，使螞蟻沿著正確的啟發信息來選擇下一個節點。

通過對式（4） 分析可知，物流配送節點i，j的信息素含量決定了螞蟻的選擇概率，τij反映了蟻群在這條路徑上以前螞蟻的經驗值大小，即信息素的強度，是一個積累的信息量。如果物流配送節點i，j之間的距離比較短，信息啟發式因子m和能見度啟發式因子n的值會增加，以便螞蟻選擇這條相對比較短的路徑；如果物流配送節點i，j之間的距離比較長，那兩個啟發式因子就變小，以增加螞蟻選擇其它路徑的概率，從局部來看是增加了路徑選擇的隨機性，減緩了收斂速度，但從全局來看避免了陷入局部最優解的問題，增加了路徑優化的可能性。

3 結果與分析

設置參數后進行循環。根據蟻群（ant-cycle）模型，螞蟻每進行一次路徑的循環，就根據信息素更新公式和每條路徑上的信息素痕跡含量，重新計算這個螞蟻所走過的路徑距離，如果比原來距離短（即比上次更優路徑），就把這條路徑保存下來并更新信息素，輸出路徑結果。經對參數的多次選值、調整和測試，得到最優配送路徑距離及迭代次數。

隨著信息啟發式因子m值的增加，蟻群算法會快速收斂；當能見度啟發式因子n值變小時，也會加快收斂速度，但n值小于0.1時，會導致局部收斂，很快達到局部最優解，即很少的迭代就可以得到“最優”路徑，但這并不是全局最優路徑，要適當調大信息素重要因子n值，雖然會帶來路徑距離的增加，但對全局最優解來說是值得的。而啟發因子η在一定區間里面的浮動對最優距離影響不大。

通過20組試驗參數的調整比較，得到本次試驗的最佳參數為m=6，n=1，η=0.2。

4 結論

采用蟻群算法適用于食用菌配送路徑中的多目標求解問題，可以有效減少配送時間，節約配送成本，將配送路線與途徑的地點最大化優化。從本質上，蟻群算法是一種基于群體的啟發式隨機搜索算法，有很強的隨機搜索性能，又可以快速收斂，很好地避免在多目標路徑求解中陷入局部最優的問題，可以快速準確地得到路徑規劃的全局最優解。