基于遺傳算法的末端配送路徑優化

王志強 岑枝

摘 要：我國快遞業的快速發展，末端配送在各個方面的水平卻不高，同時，在自動化智能信息方面，標準不統一、重復分配、分配效率差和其他瓶頸問題日益嚴重。本文以某快遞公司末端配送為研究對象，建立以配送成本最小為目標的末端配送路徑數學模型，并結合遺傳算法使用MATLAB軟件計算出最符合客戶需求的配送方案。

關鍵詞：末端配送;遺傳算法;路徑優化

一、序言

網絡零售的快速發展和快遞基礎設施的逐漸完善，促使中國快遞業實現了跨越式增長，國家郵政局官方網站發布的統計數據顯示，2019年上半年，全國快遞公司總量為277.6億，同比增長25.07%。中國快遞行業正處于快速發展階段，市場規模持續增長，也帶來了快遞末端配送難的問題。特別是在“雙十一”期間，郵件處理訂單的數量呈指數增長，并且末端配送問題更為突出。在此背后，它反映了快遞行業末端效率低下和質量低劣的缺點。

末端配送作為物流的最后一個環節，此環節的質量和效率極大地影響了客戶滿意度，通常無法通過運輸車輛來實現這一聯系，有時必須應對復雜的道路。一些數據表明，快遞末端的配送成本和時間占整個配送鏈的三分之一以上。那么如何有效提高末端配送的運營效率并降低末端配送的成本，對于物流企業乃至社會發展至關重要。

二、末端配送模型建立模型

1.問題描述

通常，快遞送貨車的載貨量有限，并且在末端配送過程中，商品種類很多，快遞包裝也不統一。快遞員要盡可能縮短配送距離，避免在某個位置花費太多時間以提高配送效率。因此，如何規劃自己的送貨路線是最重要的問題。從線性規劃的角度來看，此問題的目標是使配送路徑最短。可以將其描述如下：在廣州市海珠區，有一個配送點，從這個配送點出發，向11個不同的客戶點進行配送，配送車輛都存在容量限制，以配送路程最小或時間最短為目標。

2.模型假設

為了方便路線的規劃，可以將配送人員在末端配送過程中遇到的問題轉換成可以解決的數學模型，從而使計算機仿真的結果更加接近實際結果。假設和約束條件。

（1）假設

①快遞可以交付給每個點的客戶。

②要交付的車輛的規格和速度相同。

③送貨車輛僅從快遞點出發，完成派送任務后，必須返回該點以形成閉路。

④每個配送員對每個客戶的送貨路線是已經規劃好的路線。

⑤當客戶不在家里或拒絕簽收時，訂單將退回給服務點。

⑥將位置簡化為點，以便獲得有關該位置的特定信息。

（2）約束條件

①快遞員以交貨地點為出發地點。

②必須滿足每個配送點的需求：通常，分配點的需求不超過車輛的容量■。

③在配送每個訂單的過程中，路線不超過L。

④在完成運送到上一個客戶的地點后，必須將車輛運送到客戶的下一個地點或將其退回快遞點。

3.建立數學模型

針對本文的目標，建立如下的模型。

其中xijk為0，1變量，表示快遞員第k次服務的快遞點集合Vk，具體的：

式（1）為目標函數，表示快遞員一共m次所配送的總路徑長度;式（2）為每輛車單次配送的容量約束;式（3）為快遞員單次配送的距離約束（為保證服務質量）;式（4）、（5）表示快遞員只經過服務點一次;式（6）約束了所有車輛起始終點都在配送中心。

三、求解

1.基礎數據

末端配送主要集中在客戶的11個點上，在本文中，將選擇這11個點作為模型中的配送點，以單個固定配送中心的形式，主要考慮的是負載能力，最大數量為（200個單位）和車輛數量，MATLAB模擬了末端的最佳配送路徑，最后達到了科學合理地將快件配送到每個客戶的目的。快遞點和11個客戶的位置坐標（經度和緯度坐標是從百度地圖中獲得的），客戶的請求如下表1所示。

將其具體位置用MATLAB表現出來如圖1：

由于在實際配送中，兩客戶點間的距離不是單純兩點之間的距離，本文采用百度地圖對上述11個客戶點進行測量，得出它們之間的距離，具體的距離矩陣（單位：km）如表2所示。

2.利用MALAB進行求解

本模型主要是從路徑最小化入手，根據客戶的地理位置以及各個客戶點之間的距離，在滿足載重容量以及車輛數目的前提下，利用MATLAB進行編程，模型采用遺傳算法進行求解，最終得到優化路徑，具體如圖2所示。

由運行結果可知改進遺傳算法求得的最優解：

1-11-10-12-1-4-3-1-7-2-5-1-6-8-9-1

在最優的配送路線中，共選用四條路徑對這11個客戶（1-12）點進行配送，從上圖可以看出，車輛對客戶的配送路線分別為：

其具體的配送量和配送路程如表3所示。

運用MATLAB軟件得到的遺傳算法最優配送方案的最優適應度函數值隨迭代次數的變化情況如圖3所示。

通過運用MATLAB軟件求解遺傳算法得到最優配送方案，不僅科學規劃了最優配送路線，達到配送成本最低，也大大地提高了配送效率，減少配送員隨機配送造成的時間和成本浪費，由此可見基于遺傳算法建立的數學模型科學可行。

四、結論

快遞問題是一個多樣而復雜的問題，尤其是在尋求經濟利益與環境保護的理想結合時，其末端的配送占據了物流配送總成本的大部分。如今，隨著電子商務的迅猛發展，越來越多的人選擇線上下單線下取貨方式，由此產生的配送問題不容忽視。使用大數據和數學模型來優化配送路線已成為優化末端配送路線的發展趨勢。本文中使用MATLAB軟件優化遺傳算法的路徑還將最低配送成本作為優化的最終目標，同時考慮了配送成本與配送里程之間的關系，及忽略了某些因素，并結合了遺傳算法，在實際情況中，將最小配送成本轉換為最小配送距離是優化的最終目標。另外，研究路徑優化模型中的某些假設和限制可能會干擾最終結果，并且研究問題并不完美，如何進一步降低配送成本仍然有待研究。

參考文獻：

[1]陳先受.眾包模式下快遞企業末端配送路徑優化研究[D].浙江工商大學，2018.

[2]章雪巖，桂欣，鄭巧然.最后一公里配送路徑優化研究[J].物流技術，2017，36（06）：116-121.

[3]安冬梅.基于共同配送下的石家莊城市配送體系研究[D].石家莊經濟學院，2014.

[4]饒衛振，金淳.求解大規模CVRP問題的快速貪婪算法[J].管理工程學報，2014，28（02）：45-54.

[5]李保偉.多配送中心的城市物流配送車輛路徑問題研究[D].合肥工業大學，2013.

[6]金碩.基于遺傳算法的連鎖企業配送多目標VRP研究[D].東北大學，2011.

[7]王正國.供應商管理庫存系統中配送優化方法研究[D].華中科技大學，2006.

作者簡介：王志強（1995.06- ），男，漢族，山東日照人，碩士學歷，山東科技大學，研究方向：精益生產、物流管理;岑枝（1998.06- ），女，漢族，廣西賀州人，本科學歷，山東科技大學，研究方向：物流管理