基于遺傳算法的末端配送路徑優(yōu)化

王志強 岑枝

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

關鍵詞：末端配送;遺傳算法;路徑優(yōu)化

一、序言

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

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

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

1.問題描述

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

2.模型假設

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

（1）假設

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

②要交付的車輛的規(guī)格和速度相同。

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

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

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

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

（2）約束條件

①快遞員以交貨地點為出發(fā)地點。

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

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

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

3.建立數(shù)學模型

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

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

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

三、求解

1.基礎數(shù)據(jù)

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

將其具體位置用MATLAB表現(xiàn)出來如圖1：

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

2.利用MALAB進行求解

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

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

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

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

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

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

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

四、結論

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

參考文獻：

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

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

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

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

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

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

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

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