蟻群優(yōu)化算法下農(nóng)村生鮮配送車輛路徑對比研究

韓榮騰

摘?要：近幾年，美團(tuán)優(yōu)選、多多買菜等生鮮電商涌入農(nóng)村市場，開始針對性地解決農(nóng)村生鮮物流配送的“最后一公里”的難題。文章通過引入生鮮電商的“社區(qū)團(tuán)購”配送模式，綜合考慮農(nóng)村用戶的商品需求量、生鮮商品送達(dá)用戶時(shí)的鮮活度、商品履約率、容量受限開放式路徑規(guī)劃配送車輛等因素，以總配送成本最小為目標(biāo)構(gòu)建開放式帶時(shí)間窗容量受限車輛路徑優(yōu)化模型，利用蟻群優(yōu)化算法對該模式求解。通過算法求解的結(jié)果表明：在農(nóng)村生鮮產(chǎn)品配送中，開放式容量受限車輛路徑規(guī)劃，能有效地降低農(nóng)村生鮮物流配送的總成本，縮短車輛行駛距離，提高商品履約率。

關(guān)鍵詞：農(nóng)村生鮮配送；開放式車輛路徑規(guī)劃；容量受限；帶時(shí)間窗車輛路徑規(guī)劃

中圖分類號(hào)：F259.23???文獻(xiàn)標(biāo)識(shí)碼：A?文章編號(hào)：1005-6432（2023）10-0189-05

DOI：10.13939/j.cnki.zgsc.2023.10.189

1?引言

生鮮行業(yè)是我國民生的剛需行業(yè)。隨著疫情的出現(xiàn)，生鮮電商大量涌現(xiàn)，生鮮電商市場迅速成長，已經(jīng)在生鮮行業(yè)占據(jù)一席之地。根據(jù)中國電商委的數(shù)據(jù)，農(nóng)村生鮮網(wǎng)購消費(fèi)人群更加關(guān)注生鮮產(chǎn)品的價(jià)格和質(zhì)量，對生鮮產(chǎn)品的時(shí)效性關(guān)注度不高。而社區(qū)團(tuán)購模式保證了消費(fèi)者的低價(jià)高質(zhì)，物流配送為T+1天，商品為次日達(dá)，可以滿足農(nóng)村消費(fèi)者的需求，解決了生鮮產(chǎn)品農(nóng)村配送“最后一公里”的難題。農(nóng)村生鮮電商平臺(tái)的商品價(jià)格競爭較為激烈，生鮮電商要保證盈利與占據(jù)農(nóng)村市場份額，就要降低物流配送成本，提高商品履約率。物流配送成本的降低，商品履約率的提高，將推動(dòng)生鮮電商的核心競爭力的提高，更多的讓利于農(nóng)村消費(fèi)者，促進(jìn)農(nóng)村生鮮電商的發(fā)展。

降低農(nóng)村生鮮物流成本的關(guān)鍵是如何規(guī)劃車輛路徑的問題，通過構(gòu)建開放式車輛路徑規(guī)劃，探索規(guī)劃車輛路徑的解決方案，提高商品履約率。農(nóng)村生鮮產(chǎn)品的物流配送多使用普通車輛配送，并不涉及冷鏈車輛配送。王邦兆［1］針對生鮮配送中訂單較少以及消費(fèi)者較為分散，提出了結(jié)合改進(jìn)遺傳算法的社區(qū)搜索算法，對以成本為導(dǎo)向的多中心共同配送進(jìn)行優(yōu)化，但是要求分揀率的提高。王可山［2］認(rèn)為降低生鮮電商的配送成本應(yīng)該對配送成本、包裝成本等進(jìn)行優(yōu)化，并沒有針對配送的路徑成本進(jìn)行分析。李昌兵［3］綜合物聯(lián)網(wǎng)技術(shù)優(yōu)勢和生鮮農(nóng)產(chǎn)品的特點(diǎn)，使用RFID技術(shù)降低分揀和配送成本。付朝暉［4］引入了時(shí)變路網(wǎng)條件，構(gòu)建了生鮮配送的開放式路徑規(guī)劃車輛路徑問題優(yōu)化模型，以期降低生鮮電商的總配送成本。范厚明［5］提出車輛在完成配送任務(wù)后可繼續(xù)補(bǔ)貨進(jìn)行配送或自行結(jié)束配送任務(wù)的一種半開放式配送模式。余海燕［6］提出結(jié)合生鮮產(chǎn)品訂單的動(dòng)態(tài)性、硬時(shí)間窗等因素，設(shè)計(jì)滾動(dòng)時(shí)域延遲配送算法模式，并對其模型參數(shù)進(jìn)行敏感性分析。

現(xiàn)存的文獻(xiàn)對深入研究末端生鮮物流配送提供了大量的參考。但由于已有的文獻(xiàn)主要研究城市生鮮物流配送問題，多針對封閉式車輛路徑規(guī)劃問題，對開放式帶時(shí)間窗容量受限車輛路徑配送問題以及農(nóng)村生鮮物流配送涉及較少。文章針對農(nóng)村消費(fèi)者網(wǎng)購關(guān)注度以及社區(qū)團(tuán)購時(shí)效性等特點(diǎn)，考慮到“T+1”的配送模式、開放式車輛路徑規(guī)劃、車輛容量受限以及商品履約率等因素，以配送成本最低為優(yōu)化目標(biāo)，建立開放式車輛路徑規(guī)劃模型，并設(shè)計(jì)蟻群優(yōu)化算法求解該模型。

2?問題建模

2.1?問題描述

社區(qū)團(tuán)購主要是以多多買菜、美團(tuán)優(yōu)選等生鮮電商企業(yè)為主的一種生鮮電商模式。該模式下的農(nóng)村生鮮物流配送路徑主要涉及從配送中心到團(tuán)長門店和第三方車輛配送或自營車輛配送。大多數(shù)生鮮電商為了降低成本，多使用第三方車輛進(jìn)行配送，司機(jī)可以進(jìn)一步利用車輛的價(jià)值，因此第三方車輛在完成配送任務(wù)后，不必返回配送中心。社區(qū)團(tuán)購下的農(nóng)村生鮮物流配送，有多個(gè)“團(tuán)長”門店需要配送，各門店的地理位置已知道，配送容量不超過車輛容量，每個(gè)門店只能被一輛車服務(wù)一次。為了提高客戶滿意度，文章將針對商品的新鮮度以及客戶需求設(shè)置bj點(diǎn)履約率。假設(shè)：①每輛配送車輛從站點(diǎn)出發(fā)，配送任務(wù)完成后，不必要返回站點(diǎn)。②車輛會(huì)產(chǎn)生一定的固定成本。③車輛可提前到達(dá)門店位置，但需等待該門店最早開始服務(wù)時(shí)間進(jìn)行配送，存在一定的車輛等待時(shí)間與卸貨時(shí)間。通過上述條件構(gòu)建開放式（帶時(shí)間窗容量受限）車輛路徑規(guī)劃模式。

2.2?模型構(gòu)建

2.2.1?已知參數(shù)

S1?表示開放式路徑規(guī)劃車輛總配送距離；dij?表示客戶節(jié)點(diǎn)i到達(dá)客戶節(jié)點(diǎn)j之間的距離；Q?表示車輛的最大載裝量；Wo?表示開放式路徑規(guī)劃車輛司機(jī)的固定工資；K表示車輛的集合；FCij?表示每輛車k單位距離的燃油補(bǔ)貼，其中FCij≤Fk1;N?表示客戶的集合；qi?表示一個(gè)客戶的需求量；R?表示一組客戶的路徑（c1，?c2，?…，?cn）；?r表示一組客戶的路徑規(guī)劃（r1，?r2，?…，?rk）；?CBest?表示最優(yōu)的成本；?Li?表示在節(jié)點(diǎn)i還沒拜訪的客戶；Rej表示配送車輛在客戶節(jié)點(diǎn)j所增加的一定獎(jiǎng)勵(lì)成本；Puj表示配送車輛在客戶節(jié)點(diǎn)j所增加的一定懲罰成本；tij表示配送車輛從客戶i到達(dá)客戶節(jié)點(diǎn)j的時(shí)間；aj表示配送車輛最早到達(dá)客戶節(jié)點(diǎn)j的時(shí)間；bj表示配送車輛最晚到達(dá)客戶節(jié)點(diǎn)j的時(shí)間；ej表示配送車輛實(shí)際到達(dá)客戶節(jié)點(diǎn)j的時(shí)間。

決策變量：xijk?表示車輛k是否從節(jié)點(diǎn)i行駛到節(jié)點(diǎn)j，如果是，值為1，否則為0；vk表示車輛k是否被啟用，如果是，值為1，否則為0；yik表示車輛k是否完成客戶節(jié)點(diǎn)i的任務(wù)，如果是，值為1，否則為0。

2.2.2?模型約束條件

∑k∈K∑（i，?j）∈Ndijxijk（1）

CBest=FCij∑k∈Kvk∑k∈K∑（i，?j）∈Ndijxijk+Wo∑k∈Kvk+Rej∑k∈Kvk∑（i，?j）∈Nxijk+Puj∑k∈Kvk∑（i，?j）∈Nxijk（2）

s.t.

∑k∈K∑j∈Δ+（i）xijk=1，?i∈N（3）

∑i∈N∑k∈Kxijk=1，?j∈N（4）

∑i∈Nqi∑j∈Δ+（i）dijk≤Q，?k∈K（5）

xk0j=vk，?k∈K，?j∈N（6）

∑j∈Nx0jk≤1，?k∈K（7）

時(shí)間窗約束：（8）

xijk∈{0，?1}，?k∈K，（i，?j）∈N（9）

yik∈{0，?1}，?k∈K，i∈N（10）

其中：目標(biāo)函數(shù)（1）表示車輛行駛總距離最優(yōu)。目標(biāo)函數(shù)（2）為最優(yōu)的開放式路徑規(guī)劃車輛配送成本。約束（3）限制每個(gè)客戶只能被分配到一條路徑上。約束（4）表示每個(gè)客戶節(jié)點(diǎn)只能被訪問一次。約束（5）表示每輛車在配送中心裝配的貨物不大于車輛自身的最大承載量。約束（6）表示當(dāng)車輛被啟用時(shí)，必須從配送中心出發(fā)。約束（7）表示每輛車只能啟用一次。約束（8）將分為硬時(shí)間窗和軟時(shí)間窗?？蛻艄?jié)點(diǎn)j的時(shí)間窗范圍為［aj，?bj］，?［aj，?bj］為客戶點(diǎn)最早及最晚送達(dá)時(shí)間，對［aj，?bj］時(shí)段車輛到達(dá)客戶節(jié)點(diǎn)j將增加一定的獎(jiǎng)勵(lì)成本，對超過bj時(shí)段車輛到達(dá)客戶節(jié)點(diǎn)j將增加一定的懲罰成本，對早于aj時(shí)間點(diǎn)到達(dá)的車輛，并不設(shè)獎(jiǎng)懲，雖可能導(dǎo)致配送效率降低，但是仍可達(dá)到履約率。硬時(shí)間窗要求車輛必須在［aj，?bj］完成配送任務(wù)，即aj≤tij≤bj，軟時(shí)間窗允許車輛送達(dá)時(shí)間早于aj，晚于bj。在不超過bj時(shí)段車輛到達(dá)節(jié)點(diǎn)j，客戶j的滿意度為1，在超過bj時(shí)段車輛到達(dá)節(jié)點(diǎn)j，客戶滿意度為-1。其獎(jiǎng)勵(lì)成本為式（11），懲罰成本為式（12）。

Rej=1（aj≤tij≤bj）（11）

Puj=－1（bj≤tij）（12）

決策變量（9）表示當(dāng)車輛k從節(jié)點(diǎn)i行駛到節(jié)點(diǎn)j時(shí)，xijk=1，否則為0；決策變量（10）表示車輛k完成i的任務(wù)時(shí)，yik=1，否則為0。

3?算法驗(yàn)證及分析

車輛路徑規(guī)劃是經(jīng)典的組合優(yōu)化問題，而開放式帶時(shí)間窗容量受限車輛路徑規(guī)劃屬于VRP的衍生問題，因此需要求解的模型同樣具有NP-hard形式。蟻群算法是一種啟發(fā)式智能算法，具有降低編碼復(fù)雜性、提高效率的特點(diǎn)。

為檢驗(yàn)文章采用的蟻群優(yōu)化算法的有效性以及可行性，文章采用聊城市某多多買菜農(nóng)村社區(qū)站點(diǎn)所提供的數(shù)據(jù)。其中，車輛行駛的距離為坐標(biāo)點(diǎn)之間的距離。該多多買菜站點(diǎn)，主要配送社區(qū)為鄉(xiāng)鎮(zhèn)轄區(qū)內(nèi)的農(nóng)村門店。文章選取了其中25家多多買菜門店數(shù)據(jù)。涉及車輛的最大載重量為4500千克，車輛的行駛速度設(shè)為60千米/小時(shí)。每輛車的司機(jī)工資采用當(dāng)?shù)毓べY平均值為4500元/月，金杯汽車的百千米油耗為12升，當(dāng)?shù)?2號(hào)汽油價(jià)格的平均值為6.5元/升，因此每輛車的百千米油料補(bǔ)貼為10元。送達(dá)時(shí)間即為簽單時(shí)間，懲罰成本設(shè)為50元/每門店，獎(jiǎng)勵(lì)成本設(shè)為50元/每門店。

設(shè)配送中心以及25個(gè)門店分布在有向圖G中，配送中心為（40，50），門店等待以及卸貨時(shí)間設(shè)為90分鐘/門店，25個(gè)門店其他數(shù)據(jù)如表1所示。

文章所設(shè)螞蟻數(shù)量m=50，車輛最多使用數(shù)目kmax=25，最大迭代次數(shù)iter_max=100，其他參數(shù)設(shè)置如上文。利用Matlab工具，將蟻群優(yōu)化算法進(jìn)行運(yùn)算，所得最小成本為15371.74元，最小距離均為187.174。

為防止存在誤差，文章在計(jì)算機(jī)上運(yùn)行10次所得最小配送總成本均為15371.74，最小配送總距離均為187.174，算法結(jié)果具有穩(wěn)定性，其中運(yùn)行101次時(shí)間平均為26.522679秒，運(yùn)行時(shí)間較短，效率較高。車輛最優(yōu)路徑規(guī)劃如圖1所示，其搜索各代最小成本變化過程如圖2所示。

如圖2所示，文章所實(shí)驗(yàn)的結(jié)果具有可行性和有效性，所展示出的配送路徑為：配送路線1為0→5→3→7→8→10→11→9→6→4→2→1，配送路線2為0→13→17→18→19→15→16→14→12，配送路線3為0→22→24→25→23→22→21。

文章為證明開放式車輛路徑規(guī)劃相比封閉式車輛路徑規(guī)劃更加節(jié)省成本，采用蟻群算法計(jì)算25個(gè)門店的封閉式車輛路徑規(guī)劃，所得最優(yōu)路徑規(guī)劃如圖3所示，其搜索各代最小成本變化過程如圖4所示。其中封閉式最佳車輛配送路徑與開放式最佳車輛配送路徑相對比，多出了回到配送中心的路程，使得油料補(bǔ)貼成本有所增加，增加70元，但使用車輛一致，司機(jī)工資成本一致，獎(jiǎng)懲成本一致。

4?結(jié)語

文章將傳統(tǒng)的TSP問題加入開放式、帶時(shí)間窗及容量受限等元素，并考慮配送司機(jī)的獎(jiǎng)懲成本、對比封閉式車輛路徑規(guī)劃，以配送最小總距離與配送最佳成本為目標(biāo)，從而構(gòu)建蟻群優(yōu)化算法，為現(xiàn)實(shí)生活中農(nóng)村生鮮社區(qū)配送路徑規(guī)劃提供一個(gè)新思路。實(shí)驗(yàn)結(jié)果證明：①開放式車輛路徑規(guī)劃可以節(jié)省配送成本，縮小配送距離，節(jié)約車輛配送時(shí)間。在配送任務(wù)完成后，司機(jī)可以自由支配時(shí)間，提高了車輛使用的靈活性。②農(nóng)村一直存在的配送“最后一公里”難題得以解決，為振興農(nóng)村物流提供了一定借鑒。③與封閉式車輛路徑規(guī)劃相對比，開放式車輛路徑規(guī)劃具有更好的優(yōu)化效果，不易陷入局部最優(yōu)。

參考文獻(xiàn)：

［1］王邦兆，李慧.生鮮農(nóng)產(chǎn)品同城配送復(fù)雜網(wǎng)絡(luò)布局設(shè)計(jì)［J］.統(tǒng)計(jì)與決策，2019，35（12）：40-44.

［2］王可山，張麗彤，劉彥奇.生鮮電商配送成本影響因素及控制優(yōu)化研究［J］.經(jīng)濟(jì)問題，2019（1）.

［3］李昌兵，汪爾晶，袁嘉彬.物聯(lián)網(wǎng)環(huán)境下生鮮農(nóng)產(chǎn)品物流配送路徑優(yōu)化研究［J］.商業(yè)研究，2017（4）：1-9.

［4］付朝暉，劉長石.生鮮電商配送的兼職時(shí)變車輛路徑問題研究［J］.計(jì)算機(jī)工程與應(yīng)用，2021，57（1）：271-278.

［5］范厚明，楊翔，李蕩，等.基于生鮮品多中心聯(lián)合配送的半兼職車輛路徑問題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2019，25（1）：256-266.

［6］余海燕，唐婉倩，吳騰宇.帶硬時(shí)間窗的O2O生鮮外賣即時(shí)配送路徑優(yōu)化［J］.系統(tǒng)管理學(xué)報(bào)，2021，30（3）：584-591.