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

王西狀，陳玉蘭 （新疆農(nóng)業(yè)大學(xué) 經(jīng)濟(jì)與貿(mào)易學(xué)院，新疆 烏魯木齊 830052）

0 引言

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

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

1 HFZ生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化模型構(gòu)建

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

1.1 優(yōu)化目標(biāo)

本文以HFZ社區(qū)便利店為例，對(duì)配送路徑進(jìn)行優(yōu)化，在需求量一定、車輛最大行駛距離、車輛最大裝載量及各個(gè)門店的時(shí)間窗等約束條件下，使得社區(qū)便利店的生鮮農(nóng)產(chǎn)品配送總費(fèi)用最低，距離最短。

1.2 問題描述

本文研究的是奎屯市HFZ社區(qū)便利店的生鮮農(nóng)產(chǎn)品配送問題，具體問題描述如下：

（1）配送的車輛能夠?qū)⑸r農(nóng)產(chǎn)品有序的送達(dá)63家門店。

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

（3）社區(qū)便利店的配送中心是起點(diǎn)也是終點(diǎn)，澤惠果蔬配送中心所有的配送車輛向63家便利店配送生鮮農(nóng)產(chǎn)品，每輛車配送結(jié)束后都返回到配送中心。

（4）63家社區(qū)便利店接收生鮮農(nóng)產(chǎn)品都有自己的時(shí)間窗約束。

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

1.3 模型假設(shè)

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

（1）社區(qū)便利店的配送中心和63家門店的位置都是已知的，配送中心可以將63家社區(qū)便利店所需的生鮮農(nóng)產(chǎn)品送達(dá)。

（2）配送車輛型號(hào)統(tǒng)一，車輛的最大載重量和最遠(yuǎn)行駛距離相同。

（3）配送車輛只承擔(dān)送貨任務(wù)，不承擔(dān)取貨任務(wù)，送完生鮮農(nóng)產(chǎn)品后返回配送中心。

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

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

（6）配送生鮮農(nóng)產(chǎn)品時(shí)生鮮農(nóng)產(chǎn)品的損壞率只是與時(shí)間有聯(lián)系。

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

（8）配送中心的生鮮農(nóng)產(chǎn)品的數(shù)量能夠滿足63家連鎖門店所有的需求，配送中心的一輛冷藏車一次可以為多個(gè)社區(qū)便利店送去生鮮農(nóng)產(chǎn)品。

1.4 參數(shù)說明

對(duì)車輛路徑優(yōu)化模型中重要的參數(shù)做如下說明：

Y：目標(biāo)函數(shù)；

X：配送車輛編碼；

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

C：生鮮農(nóng)產(chǎn)品配送車輛的固定費(fèi)用；

C：生鮮農(nóng)產(chǎn)品配送車輛的單位變動(dòng)成本；

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

L：從便利店i完成配送任務(wù)后到達(dá)便利店j所用的距離；

［ET,LT］：各個(gè)便利店最早和最晚接收貨物的時(shí)間；

U：配送車輛提前到達(dá)連鎖門店等待配送產(chǎn)生的成本；

U：配送車輛晚點(diǎn)到達(dá)連鎖門店配送產(chǎn)生的懲罰費(fèi)用；

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

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

m：運(yùn)輸?shù)臅r(shí)候生鮮商品損壞的概率；

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

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

e：配送車輛裝卸效率；

f：配送車輛數(shù)量；

T：在便利店j處的卸貨時(shí)間；

P：生鮮商品的單位價(jià)格；

Q：便利店i處卸貨后車內(nèi)剩余生鮮商品的數(shù)量；

T：配送車輛到達(dá)連鎖門店i處的時(shí)間；

S：在區(qū)間（i,j）內(nèi)車輛x的裝載量；

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

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

1.5 目標(biāo)函數(shù)

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

（1）固定成本

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

（2）運(yùn)輸成本

HFZ社區(qū)便利店的生鮮農(nóng)產(chǎn)品的運(yùn)輸成本主要是配送車輛的燃油費(fèi)，影響運(yùn)輸成本的因素有行駛距離的遠(yuǎn)近和配送門店的數(shù)量。運(yùn)輸成本的表達(dá)式如下：

（3）貨損成本

貨損成本主要由運(yùn)輸途中的損失和卸貨時(shí)的損失兩部分組成。貨損成本的具體表達(dá)式如下：

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

63家便利店對(duì)生鮮商品的送達(dá)時(shí)間都有自己的要求，用等待成本和懲罰費(fèi)用來衡量配送車輛能否在規(guī)定時(shí)間內(nèi)將生鮮農(nóng)產(chǎn)品從配送中心送至各個(gè)便利店。如果車輛在門店的規(guī)定送貨時(shí)間之前到達(dá)連鎖門店的話，就會(huì)產(chǎn)生等待成本，如果車輛在門店規(guī)定的送貨時(shí)間延遲送達(dá)，那么就會(huì)產(chǎn)生懲罰費(fèi)用。生鮮農(nóng)產(chǎn)品配送的等待成本和懲罰成本的具體表達(dá)式如下：

以總成本最小構(gòu)建HFZ社區(qū)便利店配送路徑優(yōu)化模型的目標(biāo)是總成本最低，即固定成本、變動(dòng)成本、貨損成本、等待成本和懲罰成本相加之和最小。配送路徑優(yōu)化模型如下：

1.6 約束條件

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

2 模型求解與結(jié)果分析

2.1 利用Selenium工具獲取距離相關(guān)數(shù)據(jù)

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

2.2 利用遺傳算法優(yōu)化配送路徑

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

圖1 優(yōu)化過程圖

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

表1 最優(yōu)的配送路徑分布表

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

2.3 優(yōu)化前后對(duì)比分析

優(yōu)化前后數(shù)據(jù)對(duì)比如表2所示。

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

配送路徑優(yōu)化之前每次行駛的總距離為272.89km，優(yōu)化后的配送路徑總距離是每次182.09km，配送前后每次配送距離相差90.8km，每次配送可以節(jié)省變動(dòng)成本127.12元。

（2）車輛裝載率分析

配送中心路線優(yōu)化前配送路徑是固定的8條，每條線路由一輛車進(jìn)行配送，每輛車負(fù)責(zé)8~9個(gè)門店生鮮農(nóng)產(chǎn)品的配送，所有車輛的平均裝載率為83%，從這個(gè)平均數(shù)值來看，車輛的裝載率較高，但是車輛的裝載率很不均衡。優(yōu)化后配送路徑也是8條，每輛車的平均裝載率也是83%。但是優(yōu)化后的裝載量符合整體的平均水平，且每輛車的裝載率較均衡，避免了優(yōu)化前2次配送問題的出現(xiàn)。

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

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

3 結(jié)束語

本文通過對(duì)HFZ社區(qū)便利店的實(shí)際情況進(jìn)行分析，首先利用Selenium工具進(jìn)行網(wǎng)絡(luò)爬蟲，查找63個(gè)便利店和1個(gè)配送中心之間的最短路線，然后構(gòu)建考慮時(shí)間窗的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化模型，得出了車輛配送路徑的最優(yōu)線路，最優(yōu)路線每次配送節(jié)約了90.8km的路程，降低了299.3元的總成本費(fèi)用，達(dá)到配送距離縮短，成本降低的雙目標(biāo)。