基于Selenium和遺傳算法的配送路徑優化研究
——以HFZ便民直銷店為例

王西狀，陳玉蘭 （新疆農業大學 經濟與貿易學院，新疆 烏魯木齊 830052）

0 引言

隨著人們物質生活水平的提高，人們對蔬菜、水果、蛋類和肉類等生鮮農產品需求量增加的同時，其新鮮程度、獲取的價格和便利性也成為關注的重點。生鮮農產品不像其他商品，其保質期短，容易磕碰損壞，種類繁多，每種生鮮農產品的運輸條件又不盡相同。生鮮農產品配送體系的不健全，在存儲和運輸環節保鮮技術低，容易造成大量的生鮮農產品腐爛變質，這不僅僅會危害公司的利益，也會造成生鮮農產品價格的上漲和食品安全隱患，降低了人們的生活水平和生活質量。

“紅房子”社區便民直銷店（HFZ）是奎屯市重點企業——奎屯澤惠果蔬配送有限公司旗下的連鎖便民超市，建立自有物流配送中心，實現了采、配、銷一體化運營模式，目前全市共設有63個門店，遍及奎屯市各社區。通過在調研中發現，由于HFZ尚處于發展階段，相關的技術和實踐不夠成熟，忽視配送路線規劃問題，配送路線采取以司機分片區負責的方式，司機的主觀性較大，經常出現某一網點缺貨或存貨過多造成損耗的問題。本文正是基于以上背景，擬利用Selenium和遺傳算法建立HFZ社區便民直銷店生鮮農產品物流路徑優化模型，合理安排車輛和優化運輸路徑，以達到降低企業物流成本、提高企業經濟效益的目的。

1 HFZ生鮮農產品配送路徑優化模型構建

在物流配送路徑優化模型選擇方面。王玥丹（2014）、高帥仁（2018）、景曉騰（2020）、程鈺（2021）、劉娜娜（2021）、田帥輝（2021）等均采用遺傳算法求解配送路線優化問題，并證實遺傳算法在配送路線優化上具有顯著優勢。

1.1 優化目標

本文以HFZ社區便利店為例，對配送路徑進行優化，在需求量一定、車輛最大行駛距離、車輛最大裝載量及各個門店的時間窗等約束條件下，使得社區便利店的生鮮農產品配送總費用最低，距離最短。

1.2 問題描述

本文研究的是奎屯市HFZ社區便利店的生鮮農產品配送問題，具體問題描述如下：

（1）配送的車輛能夠將生鮮農產品有序的送達63家門店。

（2）HFZ配送車輛所能裝載生鮮農產品的重量是有限的，各個社區便利店的需求是一定的且小于配送車輛的裝載重量，可以將多個連鎖店的生鮮商品需求匯總裝在同一輛車上進行配送，提高配送車輛的裝載率。

（3）社區便利店的配送中心是起點也是終點，澤惠果蔬配送中心所有的配送車輛向63家便利店配送生鮮農產品，每輛車配送結束后都返回到配送中心。

（4）63家社區便利店接收生鮮農產品都有自己的時間窗約束。

（5）在Y連鎖超市生鮮商品的配送路徑優化方案時，優化目標是配送的總成本最小，約束條件有：時間窗、配送車輛裝載量的限制、配送車輛行駛距離最短。

1.3 模型假設

為了使構建的配送路徑優化模型與社區便利店的實際情況更加符合，提高模型的真實性，本文在構建配送路徑優化模型之前從多個方面提出以下假設：

（1）社區便利店的配送中心和63家門店的位置都是已知的，配送中心可以將63家社區便利店所需的生鮮農產品送達。

（2）配送車輛型號統一，車輛的最大載重量和最遠行駛距離相同。

（3）配送車輛只承擔送貨任務，不承擔取貨任務，送完生鮮農產品后返回配送中心。

（4）63家便利店需要的生鮮商品可以混裝在不同車輛上。

（5）配送車輛行駛速度已知且恒定，配送是在早高峰來臨之前，路上幾乎不存在交通擁堵狀況。

（6）配送生鮮農產品時生鮮農產品的損壞率只是與時間有聯系。

（7）63家便利店的需求量是已知的，每一個連鎖門店只能由一輛車服務。

（8）配送中心的生鮮農產品的數量能夠滿足63家連鎖門店所有的需求，配送中心的一輛冷藏車一次可以為多個社區便利店送去生鮮農產品。

1.4 參數說明

對車輛路徑優化模型中重要的參數做如下說明：

Y：目標函數；

X：配送車輛編碼；

B：配送中心和63家便利店的集合；

C：生鮮農產品配送車輛的固定費用；

C：生鮮農產品配送車輛的單位變動成本；

Q：配送中心每輛配送車輛的最大裝載量；

L：從便利店i完成配送任務后到達便利店j所用的距離；

［ET,LT］：各個便利店最早和最晚接收貨物的時間；

U：配送車輛提前到達連鎖門店等待配送產生的成本；

U：配送車輛晚點到達連鎖門店配送產生的懲罰費用；

R：便利店i的需求量（以重量計算）；

L：配送車輛x的可以行駛的最大里程；

m：運輸的時候生鮮商品損壞的概率；

m：卸貨的時候生鮮商品損壞的概率；

v：配送車在配送路途中的行駛速度；

e：配送車輛裝卸效率；

f：配送車輛數量；

T：在便利店j處的卸貨時間；

P：生鮮商品的單位價格；

Q：便利店i處卸貨后車內剩余生鮮商品的數量；

T：配送車輛到達連鎖門店i處的時間；

S：在區間（i,j）內車輛x的裝載量；

W=1，表示車輛x從便利店i到便利店j，否則W=0；

Z=1，便利店i由配送車輛x配送，否則Z=0。

1.5 目標函數

本文所要建立的HFZ社區便利店的生鮮農產品配送路徑優化模型的總目標為配送總成本最小。而生鮮農產品配送的總成本包括4個方面，分別是固定成本、運輸成本、貨損成本和等待成本或懲罰成本。雖然是生鮮農產品，但是便利店的配送沒有采用冷藏車配送，因此成本中不存在制冷成本。

（1）固定成本

固定成本只有一個，就是配送車輛司機師傅的工資，由于便利店的車輛是師傅自己的，所以不存在設備折舊費，該成本不受其他因素的影響，是固定不變的。固定成本的表達式如下：

（2）運輸成本

HFZ社區便利店的生鮮農產品的運輸成本主要是配送車輛的燃油費，影響運輸成本的因素有行駛距離的遠近和配送門店的數量。運輸成本的表達式如下：

（3）貨損成本

貨損成本主要由運輸途中的損失和卸貨時的損失兩部分組成。貨損成本的具體表達式如下：

（4）等待成本或懲罰成本

63家便利店對生鮮商品的送達時間都有自己的要求，用等待成本和懲罰費用來衡量配送車輛能否在規定時間內將生鮮農產品從配送中心送至各個便利店。如果車輛在門店的規定送貨時間之前到達連鎖門店的話，就會產生等待成本，如果車輛在門店規定的送貨時間延遲送達，那么就會產生懲罰費用。生鮮農產品配送的等待成本和懲罰成本的具體表達式如下：

以總成本最小構建HFZ社區便利店配送路徑優化模型的目標是總成本最低，即固定成本、變動成本、貨損成本、等待成本和懲罰成本相加之和最小。配送路徑優化模型如下：

1.6 約束條件

公式（8）表示HFZ社區便利店63家店都能被配送到一次；公式（9）明確了W和Z兩個變量之間的關系；公式（10）表示一條配送路線的生鮮農產品由配送中心的一輛車負責配送，車輛在執行一次任務時只能離開配送中心一次；公式（11）表示在一次配送的過程中，配送車輛在完成配送任務時，配送行駛的距離要小于配送車輛的最大行駛距離；公式（12）表示配送中心的配送車輛對生鮮農產品的最大載重量；公式（13）、公式（14）表示配送車輛的起點和終點都是配送中心；公式（15）表示63家社區便利店都能夠被配送到而且只能夠被配送到一次；公式（16）表示在一次配送的過程中，所有的配送車輛各自能裝載的最大重量相加之和要大于63家便利店的需求量之和，并且一次能滿足63家便利店的需求。

2 模型求解與結果分析

2.1 利用Selenium工具獲取距離相關數據

利用Selenium工具進行網絡爬蟲，計算63個便利店和1個配送中心之間的距離，該方法就是先輸入一個URL，然后網絡爬蟲可以按照剛才的命令和程序得到其他的URL，本文的距離查找過程是，先找到兩個便利店的位置，然后將在百度地圖里查找最短路線的編碼輸入進去，網絡爬蟲根據這個命令將其余便利店和配送中心的距離計算出來。采用這種方式的優點是可以準確得到配送中心和各個便利店之間的距離。

2.2 利用遺傳算法優化配送路徑

本文采用遺傳算法和MATLAB軟件來求解HFZ社區便利店配送路徑模型，首先確定各項運行參數，包括群體的規模、變異的概率、交叉的概率、終止進化的迭代代數。其次再經過編碼、確定初始種群、選擇、交叉、變異、終止等步驟后，求得最優解。HFZ社區便利店配送路徑優化模型求解的最終迭代收斂圖如圖1所示：

圖1 優化過程圖

圖1是通過遺傳算法和MATLAB軟件求解配送路徑優化模型進程圖，從圖1中可以看出曲線在迭代100次之前迅速下降，在這個過程中是不斷淘汰較差的個體；在迭代到100~800次下降速度緩慢，在迭代到820次之后成一條水平的直線，說明算法在此時已經得到了最優解。即HFZ社區便利店在成本最低的目標下，表1得出的車輛的行駛距離、車輛的總裝載量及車輛的裝載率。

表1 最優的配送路徑分布表

從表1可以看出，優化后的車輛裝載率基本都達到了百分之八十，并且比較均勻。用遺傳算法計算出配送的成本是每天2 980.5302元。

2.3 優化前后對比分析

優化前后數據對比如表2所示。

（1）配送總的行駛距離分析

配送路徑優化之前每次行駛的總距離為272.89km，優化后的配送路徑總距離是每次182.09km，配送前后每次配送距離相差90.8km，每次配送可以節省變動成本127.12元。

（2）車輛裝載率分析

配送中心路線優化前配送路徑是固定的8條，每條線路由一輛車進行配送，每輛車負責8~9個門店生鮮農產品的配送，所有車輛的平均裝載率為83%，從這個平均數值來看，車輛的裝載率較高，但是車輛的裝載率很不均衡。優化后配送路徑也是8條，每輛車的平均裝載率也是83%。但是優化后的裝載量符合整體的平均水平，且每輛車的裝載率較均衡，避免了優化前2次配送問題的出現。

（3）車輛配送總成本分析

車輛配送的總成本包括固定成本、變動成本、貨損成本、等待成本和懲罰成本，通過遺傳算法進行優化后，每次配送可以節省總成本299.3元，每次成本降低10.04%。為后期業務的不斷擴大減少了成本投入，提高了企業的效率，間接提高客戶的滿意度。

3 結束語

本文通過對HFZ社區便利店的實際情況進行分析，首先利用Selenium工具進行網絡爬蟲，查找63個便利店和1個配送中心之間的最短路線，然后構建考慮時間窗的生鮮農產品配送路徑優化模型，得出了車輛配送路徑的最優線路，最優路線每次配送節約了90.8km的路程，降低了299.3元的總成本費用，達到配送距離縮短，成本降低的雙目標。