基于遺傳算法的大張連鎖超市配送優化

□ 張維偉

(洛陽師范學院，河南 洛陽 471934)

物流配送成本是超市成本管理的重要一環，將物流配送成本細分，尋找合適的配送路線到各個門店，已成為大型連鎖超市強有力的發展手段。在配送中心到各門店配送過程中，存在著時間限制和顧客購物體驗、滿意程度掛鉤，與交通的擁擠程度所致的額外費用(燃料費用、缺貨成本)相關聯，大張連鎖超市軟時間窗約束下的車輛路徑問題[1]，是以大張門店為具體分析對象，切實依據其配送作業的實施要求，建立合理的模型，證明隱藏成本同時分析出近似最優路徑，進而幫助其完善配送管理，增強業內實力。

1 問題描述

1.1 大張連鎖超市簡介

作為河南零售商企前十的大張集團在國內已有超過60家門店，其總部位于河南洛陽，在河南省的品牌影響力巨大。大張連鎖超市是自營物流，其配送中心位于洛陽市西工區物流商貿帶，占地超200000平方米，投資超過10億，年配送能力超過50萬噸，主要滿足公司在河南省地區各門店的商品配送[2]。受門店規模的影響，“大張”門店品類、種類和數量各不相同，所以在實際分析中，挑選大張集團中規模較大、產品種類需求較多的門店，即大張盛德美和大張量販中有代表性的20家門店作為研究對象進行問題分析。

1.2 大張連鎖超市配送問題

①配送成本核算不明晰。

大張的物流配送費用僅是車輛、人員費，并未考慮到提前或超時導致的交通燃料成本、產品的缺貨成本以及管雜費，導致這部分損失在實際運作中被忽略、產生額外成本增加、客戶體驗度下降。

②物資配送設計不合理。

目前，配送中心處理各門店訂單需求時，除了生鮮食品必須額外用冷藏車配送外，其他商品是按照門店節點為單位進行配送，由于各門店配送在時間上并未設立專有人員嚴格管控，因此存在憑司機的經驗根據運輸量的多少或距離遠近直觀判斷，而忽略門店時間的重視的現象，增加了產生隱藏成本的風險。

2 模型建立

2.1 模型描述及參數建立

路徑規劃問題的意義或研究范圍體現在其約束條件上，通過設置帶有約束條件的目標函數進行大張物流配送路徑問題研究，賦予其模型實際意義，真正地達到科學規劃、降本增效的終極目的。所以為保證模型建立達到應有效果，做出如下假設：大張配送路徑研究類型是單源多點問題；各門店的產品需求量和時間窗是明確的，不存在波動變化；配送中心所能調配的車輛足夠應對各門店且配送車輛是統一規格；所設計的懲罰成本僅是由超出時間窗所產生，即指考慮時間所引起的附加成本，并非是速度、溫度等其他原因，因此假設配送環境保持恒溫、車輛行駛速度為勻速；大張連鎖超市各門店的需求信息發出，一旦配送中心開始配送任務，那么不能改變原有需求量，以免因需求量的變化影響整個配送路線的規劃；每輛配送車的實際載重量不得高于其額定載重量；每一次任務中的每輛配送車都從配送中心發出，在任務結束后返回配送中心。模型所涉及的相關參數如表1所示。

表1 相關參數設置表

2.2 模型建立

建立以成本為導向的目標函數，成本構成為三部分：固定成本、貨物運輸成本和懲罰成本。

①固定成本。

大張一次出車每條路線的司機成本為20元；所配備的東風柳汽中卡額定載重量6.6噸，價格20萬元，使用年限為10年，每輛車每天產生的固定折舊費用為200000(1-3%)÷10÷360=53.15(元)；車輛調配所產生的一次性成本為20元。固定成本見式(1)：

C1=20×W+53.15×W+c0W=(73.15+c0)W

(1)

②車輛運輸變動成本。

配送過程中產生的變動成本是隨車輛實際行駛距離變化而變化的，二者呈正比。車輛運輸變動成本見式(2)：

(2)

③懲罰成本。

大張物流的懲罰成本為超出各門店規定時間窗之外所產生的諸多成本，若在規定時間窗之前到，則容易引起門店內部物流倉儲時間安排的混亂，產生不必要的管雜費；若在規定時間窗之外，則增加燃料成本和缺貨成本。設立分段函數f(a)，其中a=Tiw，可分成四段，分段函數表達式見式(3)。

(3)

綜上所述，配送成本目標函數Z表達式及約束見式(4)和(5)。公式(4)含義為大張連鎖超市配送路徑模型中的目標函數為總成本最小；公式(5)是約束條件，即保證有且僅有1輛配送車執行大張單個門店節點的配送任務，且執行配送任務的車輛不超過大張配送中心所擁有的總車輛；配送車輛所配送的門店數量為j；每輛執行任務的配送車在完成配送路線上的任務后要返程回到配送中心；每輛配送車的實際載重量不得超過其額定載重量；各門店節點所能接受的極限時間范圍為E2Ti≤a≤L2Ti；第W輛配送車從節點i到節點j時間上的連續性。

(4)

(5)

3 算法求解

3.1 算法設置

大張配送問題采用遺傳算法，流程有八步：①確定實際參數，賦予其內涵。②設置參數編碼。大張配送路徑問題中采用實值編碼，以節點序號為編碼位置。③初始化設定。采取隨機設定模式，隨機產生N個染色體。大張配送路徑問題中染色體個數設為100，設GGAP=0.9。④選定適應度函數。設個體為i，適應度函數為fi，鑒于所求的是最小值目標函數，因而可以用其倒數表示，計算的數值越大，代表該染色體越優[3]。fi表達見式(6)，適應度值越大意味著排序越前，所對應的路線越優[4]。

(6)

⑤遺傳選擇。適應度用輪盤賭選擇法計算概率分布，算出參與選擇的染色體的各個選擇概率Pi，表達式見式(7)，再根據[0,1]內產生的均勻分布隨機數R，依次比較各染色體累計概率Pic，表達式見式(8)。

(7)

(8)

在對比中，每輪累計中第一個大于隨機數R的染色體會被選中進入下一步，而沒有被選中的則會被暫時淘汰，雖有誤傷優等染色體的概率，但能保證種群多樣性[5]。⑥染色體交叉。采用部分匹配交叉法，隨機選擇兩條路徑，對其所路過的城市，隨機選一定量城市互換，保持被交換城市不動，從未交換城市中尋找重復部分，替換成上代中與重復部分對應位置的城市，直至無重復則停止修訂[6]。⑦染色體變異。逆轉變異，隨機選取路徑，隨機選取城市固定，將固定城市之間的城市進行逆序，避免遺傳算法過早收斂的缺點[7]。⑧終止。制定最大迭代次數，在運行至此時停止，當前染色體即為近似最優路徑[8]。

3.2 算法求解

在選擇的時間窗之內，由于避開了上班高峰期，因此規定時間窗內不考慮交通阻塞所致的燃料費上升，所以設配送車輛的速度為68公里/小時恒定不變，設計到目標函數的參數對應值如表2所示，各門店信息情況如表3所示。

表2 相關參數設置表

表3 大張各門店需求信息表

遺傳算法的求解用Matlab2016a完成，設置遺傳交叉概率為0.8，變異概率為0.2；設置最大迭代次數為500次，得出優化路徑如表4所示。

表4 配送路徑規劃表

由表4可得，全部配送任務共需4輛運輸車進行。四輛配送車輛的裝載率除車輛編號2受其負責的8個門店訂單需求差異大的影響，裝載率為87.88%，其余三輛運輸車裝載率都超過了90%，說明該路徑配送方案有強合理性，可以充當近似最優解。配送途中，總配送路線歷程744.03公里，每輛配送車的路徑如圖1所示，配送方案迭代進程如圖2所示。

圖1 大張連鎖超市配送路線圖

圖2 遺傳算法優化進程圖

3.3 結果分析

配送任務的總配送成本為1507.05元，具體成本明細如表5所示，從數據中可得，懲罰成本是原先沒有注意到的一環，在實際中占比18%，證明了大張確實存在物流成本管理方面的問題，考慮隱藏成本所進行的路徑規劃，則更具有科學性、現實性。

表5 成本構成表 (單位：元)

4 結束語

對于大型連鎖超市的配送問題，若企業是自營物流，在易滿足剛需的同時，卻容易忽略各門店的軟性配送要求。通過對大張連鎖超市配送的整體情況進行敘述，設計相應懲罰成本，最終讓其成本模型更加精確。再運用MATLAB軟件對遺傳算法進行求解，得出懲罰成本在總成本中的占比，證實了隱藏成本的實際存在，也得出所對應的相似最優路徑，希望能達到相應效果，提高業內競爭力。