韓榮騰

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

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

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

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

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

2?問(wèn)題建模

2.1?問(wèn)題描述

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

2.2?模型構(gòu)建

2.2.1?已知參數(shù)

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

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

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

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

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

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

文章所設(shè)螞蟻數(shù)量m=50，車(chē)輛最多使用數(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í)間較短，效率較高。車(chē)輛最優(yōu)路徑規(guī)劃如圖1所示，其搜索各代最小成本變化過(guò)程如圖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。

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

4?結(jié)語(yǔ)

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

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

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

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

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