（東北林業(yè)大學(xué) 交通學(xué)院，黑龍江 哈爾濱 150040）

1 引言

O2O（Online To Offline）模式下生鮮農(nóng)產(chǎn)品電子商務(wù)為顧客提供線上交易、線下配送的服務(wù)。從生產(chǎn)地到達需求地的過程中，對生鮮農(nóng)產(chǎn)品損失率影響較大的是配送質(zhì)量，農(nóng)產(chǎn)品易腐性對配送服務(wù)的時效性要求較高，物流企業(yè)以顧客為中心，首先考慮配送時間約束，又兼顧配送成本。因此，配送質(zhì)量是衡量O2O模式下生鮮農(nóng)產(chǎn)品供應(yīng)鏈最為關(guān)鍵的指標(biāo)，優(yōu)化配送路徑也成為物流環(huán)節(jié)最為關(guān)注的技術(shù)問題之一。

近年來，O2O模式下的生鮮電商取得了快速的發(fā)展，隨著生鮮農(nóng)產(chǎn)品需求量的增加，線上交易和線下服務(wù)質(zhì)量研究不斷多元化。對于線上交易，一般以提升交易效率和可靠性為研究熱點，針對生鮮農(nóng)產(chǎn)品電商平臺發(fā)展模式[1]、運營策略[2]和影響顧客購買行為的因素[3]進行研究。在配送路徑研究方面，國內(nèi)外學(xué)者一般以車輛行駛路徑最短、運輸費用最低、配送車輛數(shù)量最少、配送時間最短等單個或多個指標(biāo)作為目標(biāo)函數(shù)，建立多約束下的優(yōu)化模型，采用混合啟發(fā)式算法[4-5]、元啟發(fā)算法[6]、遺傳算法[7-8]、蟻群算法[9-10]等求得模型最優(yōu)解或滿意解。

本文在以上研究的基礎(chǔ)上，針對目前O2O模式下生鮮農(nóng)產(chǎn)品配送中存在的問題，以顧客滿意度最大和配送成本最小為目標(biāo)，引入配送消耗成本和時間窗懲罰成本兩個決策變量，在顧客時間窗、車輛行駛最大里程和最長時間的限制下構(gòu)建O2O模式下生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化模型，結(jié)合掃描法與遺傳算法，獲得模型的最優(yōu)解。

2 生鮮農(nóng)產(chǎn)品配送問題描述

O2O模式下生鮮農(nóng)產(chǎn)品配送問題可以簡單描述為下列過程：

（1）生鮮農(nóng)產(chǎn)品交易線上平臺接收、整理、處理顧客訂單；

（2）將顧客收貨位置、生鮮農(nóng)產(chǎn)品需求量、設(shè)置的時間窗等配送信息傳遞至線下實體店；

（3）線下實體店根據(jù)配送信息，完成生鮮農(nóng)產(chǎn)品的出庫，設(shè)計最優(yōu)配送路徑，逐一訪問顧客位置，完成生鮮農(nóng)產(chǎn)品的配送任務(wù)。

2.1 配送目標(biāo)

（1）提高顧客的滿意度。一方面，顧客線上交易時間雖然隨機化，但對生鮮農(nóng)產(chǎn)品的接收時間有要求；另一方面，線下實體店盡量在顧客可接收時間內(nèi)及時完成配送，保證產(chǎn)品新鮮度。

（2）降低配送成本。生鮮商品屬于易腐、易耗產(chǎn)品，線下配送成本不僅包括配送車輛的固定成本和變動成本，也包括產(chǎn)品損耗成本和時間懲罰成本。

考慮以上配送目標(biāo)，在建模時引入車輛行駛最大里程和最長行駛時間的約束條件，同時引入顧客時間窗，當(dāng)不能滿足顧客可接收時間要求時，增加早到或晚到的懲罰成本。車輛的固定成本（如車輛折舊費用）與運輸里程和顧客數(shù)量都沒有直接關(guān)系；車輛的變動成本（如油耗）與運輸距離有關(guān)。生鮮農(nóng)產(chǎn)品的損耗成本可簡化為運輸時間的線性函數(shù)，這是由于在時間—溫度變化品質(zhì)耐性研究中，隨著保存溫度、時間的增加，產(chǎn)品質(zhì)量會受到影響，而溫度在一定時間內(nèi)變化不大，可以不考慮。時間懲罰成本是生鮮配送早于或晚于顧客設(shè)定的時間窗完成交貨產(chǎn)生的費用。

2.2 約束條件

（1）生鮮農(nóng)產(chǎn)品實體店數(shù)量為1個，接收線上顧客訂單信息，有充足貨源滿足顧客需求，擁有多輛型號相同的專用配送車輛，實體店為線下配送服務(wù)的出發(fā)地點。

（2）顧客收貨的地理位置、時間窗限制和對生鮮農(nóng)產(chǎn)品的需求量（單一品種）根據(jù)線上訂單信息可知，每個顧客需求量低于配送車輛的最大載重量，各顧客之間距離低于配送最大行駛里程。

（3）線下配送車輛要在顧客設(shè)置的時間窗內(nèi)完成配送服務(wù)，否則產(chǎn)生懲罰成本。

（4）每條配送線路只安排一輛配送車輛，每條線路上顧客需求量之和不超過配送車輛最大載重量，配送線路的長度不能超過設(shè)定的最大里程；配送線路的行駛時間不能超過設(shè)定的最大時長。

（5）配送車輛配送途中交通條件較好，以勻速行駛至各顧客點，完成所有配送任務(wù)后回到生鮮農(nóng)產(chǎn)品實體店。

3 配送路徑優(yōu)化模型

根據(jù)以上問題描述，以配送成本（包括配送車輛固定成本、配送車輛變動成本、生鮮農(nóng)產(chǎn)品消耗成本和時間懲罰成本）最低為目標(biāo)函數(shù)，建立數(shù)學(xué)模型如下：

約束條件：

決策變量：

式中：i=0,1,...,n;j=0,1,...,n;k=1,2,...,m;Z表示O2O模式下生鮮農(nóng)產(chǎn)品配送成本（元）；m表示配送車輛總數(shù)（輛）；Pk表示配送車輛k產(chǎn)生的固定費用（元/輛）；e表示車輛單位距離運輸成本（元/km）；v表示配送車輛的行駛速度（km/h）；n表示顧客總數(shù)；i=0,1,...,n表示實體店和顧客，其中i=0表示實體店；（Xi,Yi）表示顧客i位置坐標(biāo)；dij（i,j=1,2,...,n）表示顧客i到顧客j的距離（km），dij=dji；doj（j=1,2,...,n）表示實體店到顧客j的距離（km）；qi（i=1,2,...,n）表示顧客對生鮮農(nóng)產(chǎn)品的需求量（kg）；p表示生鮮農(nóng)產(chǎn)品平均單價（元/kg）；β表示配送中農(nóng)產(chǎn)品損耗的比例；ti表示配送車輛到達顧客i的時刻；tij表示配送車輛從顧客i到顧客j的行駛時間，tij=dij/v；tki表示車輛k到達顧客i后進行服務(wù)的時間（min）；[Ei,Li]表示顧客i設(shè)置的時間窗，其中Ei表示顧客設(shè)置時間窗的起始時刻，Li表示顧客設(shè)置時間窗的終止時刻；δ1表示配送車輛早于顧客設(shè)置的時間窗帶來的懲罰系數(shù)；δ2表示配送車輛晚于顧客設(shè)置的時間窗帶來的懲罰系數(shù)；Qmax表示配送車輛的最大載貨量（kg/輛）；Lmax表示配送車輛的單程行駛最大里程（km）；Tmax表示配送車輛行駛的單程配送最長時間（min）。

式（2）與（3）表示每個顧客恰好被訪問一次；式（4）表示每輛配送車輛從實體店出發(fā)并最終返回實體店；式（5）與（6）表示配送車輛到達每個顧客后，必須離開該顧客；式（7）為車輛載貨量約束；式（8）為車輛行駛最大里程單程里程約束；式（9）為時間約束；式（10）為最長時間單程時間約束。

4 模型求解

4.1 掃描算法

本文采用掃描算法劃分車輛配送區(qū)域，具體步驟如下：

（1）建立極坐標(biāo)系。以實體店的位置作為極點，以X軸方向為正方向，建立極坐標(biāo)系，并對所有顧客所在的位置，進行極坐標(biāo)系的變換。

（2）分組。首先劃分第一組，從正方向開始，按逆時針方向掃描，將顧客逐個加入到第一組中，累加計算顧客的需求量，當(dāng)累加值超出車輛載貨量時，重新建立新的一組，繼續(xù)掃描，直到所有的顧客都分組完成。

（3）劃分區(qū)域。根據(jù)分組的結(jié)果劃分車輛配送區(qū)域。

4.2 遺傳算法

針對每一區(qū)域，采用自適應(yīng)能力強、收斂速度快的遺傳算法進行路徑優(yōu)化求解，設(shè)計遺傳算法如下：

（1）編碼。采用自然數(shù)編碼方式，其中0表示配送中心和不同路徑之間的分隔符，例如個體編碼020130表示兩條路徑，第一條路徑為配送中心—顧客2—配送中心，第二條路徑為配送中心—顧客1—顧客3—配送中心。

（2）初始種群。初始種群是進行遺傳進化操作的第一代種群，由N個個體組成，通過隨機方式生成。群體規(guī)模的大小影響種群多樣性和運算速度，進而影響遺傳算法優(yōu)化的最終結(jié)果及其計算效率，一般取值為40～100。

（3）計算染色體的適應(yīng)度。O2O模式下生鮮農(nóng)產(chǎn)品配送路徑目標(biāo)是使配送總成本最小，即目標(biāo)函數(shù)值最小，而適應(yīng)度值應(yīng)該是非負的，適應(yīng)度值越大，表示個體的性能越好，被選擇到下一代的概率越大。因此需要將目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)度，設(shè)Zr為染色體r的目標(biāo)函數(shù)值，則染色體r的適應(yīng)度函數(shù)值fr為：，表示目標(biāo)函數(shù)值Zr與適應(yīng)度函數(shù)值fr成反比。

（4）選擇操作。采用輪盤賭方式進行選擇，從群體中選擇一些個體，這些個體被選中的概率與它們的相對適應(yīng)度值成正比，能夠保證適應(yīng)度高的個體以更大的概率被選中。設(shè)群體大小為M，個體r適應(yīng)度為fr，則個體r被選中的概率這種選擇方式首先保證了所有個體都有幾率遺傳到下一代,并且適應(yīng)度高的個體會被優(yōu)先選擇,保證了優(yōu)良基因可隨迭代過程持續(xù)傳遞。

（5）交叉操作。采用順序交叉法，首先隨機選擇一對父代中幾個基因的起止位置（兩染色體被選位置相同），然后生成一個子代，并保證子代中被選中的基因的位置與父代相同，接著找出第一步選中的基因在另一個父代中的位置，最后再將其余基因按順序放入上一步生成的子代中。

交叉操作需要確定交叉概率，交叉概率與父代間發(fā)生交叉概率有關(guān)，一般情況取0.5上下[11]。

（6）變異。采用隨機變異法，即隨機選擇兩點并交換位置，可保持群體的多樣性，增強遺傳算法的隨機搜索能力，以防止出現(xiàn)過早收斂現(xiàn)象。變異概率一般取0.1-0.3[11]。

（7）設(shè)置終止條件。采用事先確定最大遺傳代數(shù)作為遺傳算法的終止規(guī)則，保證能有效地獲得可行的最優(yōu)解，而不是無限地循環(huán)計算，其值根據(jù)研究的問題而定。

5 模型驗證

5.1 參數(shù)設(shè)置

某生鮮農(nóng)產(chǎn)品實體店線上交易平臺9：00至10:00點接到17個顧客訂單，即n=17（人），生鮮農(nóng)產(chǎn)品平均單價p=7（元/kg），顧客相關(guān)信息（地理坐標(biāo)、需求量、時間窗、車輛到達位置至離開的服務(wù)時間）見表1和圖1。實體店擁有5輛相同型號并配備了保鮮箱的電動車。電動車的長寬高為56cm，車廂最大裝載量為Qmax=25（kg/輛），單位距離運輸成本e=0.4（元/km），平均車速v=35（km/h）?？紤]到車與配送人員一一對應(yīng)，且電動車的固定成本很小，因此車輛產(chǎn)生的固定費用Pk=20（元/輛）。根據(jù)以往數(shù)據(jù)，配送中農(nóng)產(chǎn)品損耗的比例β=2%。單程里程約束Lmax=35（km），單程時間約束Tmax=60（min），早于時間窗懲罰成本系數(shù)δ1=0.2，晚到時間窗產(chǎn)生的懲罰成本系數(shù)為δ2=0.3。遺傳算法求解中，種群規(guī)模為60，交叉概率是0.8，變異概率0.2，迭代次數(shù)500次。

表1 顧客基本信息

圖1 顧客位置

5.2 模型求解

本文分別采用遺傳算法、遺傳算法結(jié)合掃描算法兩種求解方法，掃描算法分區(qū)如圖2所示，求得的配送路徑和成本見表2，最優(yōu)配送路徑如圖3所示：

圖2 掃描算法分區(qū)

表2 兩種求解方法求解的配送路徑

由表2和圖3可知，與不預(yù)先采用掃描算法相比，只采用遺傳算法確定的最優(yōu)配送路徑總成本較高。這是因為遺傳算法求解時，有較大的隨機性，當(dāng)種群規(guī)模、交叉概率、變異概率和最大迭代數(shù)等遺傳參數(shù)確定時，種群中個體的數(shù)量多，隨機性大，初始種群找到最優(yōu)解的可能性小，即使經(jīng)過選擇、交叉和變異的操作會增加尋找到最優(yōu)解的概率，但其仍存在著隨機性，最優(yōu)解被找到的概率依然較小。相比較而言，首先運用掃描算法進行路線分區(qū)，使運用遺傳算法計算的種群個體數(shù)量減少，在遺傳參數(shù)確定的條件下，初始種群較易找到最優(yōu)解，且經(jīng)過選擇、交叉和變異操作進一步優(yōu)化解，最終得到最優(yōu)解的概率大大增加；且這些個體相對位置集中，有利于優(yōu)化最短路徑，使生鮮配送車輛的變動成本、生鮮損耗成本和時間懲罰成本降低，從而降低了生鮮配送總成本。此外，采用掃描算法預(yù)先分區(qū)后，每個區(qū)域的變量數(shù)量相對減少，遺傳算法迭代次數(shù)降低，計算速度更快。

圖3 最優(yōu)配送路徑圖

6 結(jié)語

對于O2O模式下生鮮農(nóng)產(chǎn)品實體店，配送成本直接影響企業(yè)利潤，配送服務(wù)質(zhì)量影響企業(yè)的可持續(xù)發(fā)展。本文深入分析線上交易、線下配送的O2O生鮮農(nóng)產(chǎn)品供應(yīng)鏈模式，以配送總成本最低和顧客滿意度最大為目標(biāo)函數(shù)，建立了線下配送路徑優(yōu)化模型。模型的約束條件既考慮了消耗成本、車輛行駛里程和行駛時間，又考慮了顧客收貨的時間窗及其懲罰系數(shù)。最后采用掃描算法預(yù)先分區(qū)，再用遺傳算法求得最優(yōu)配送路徑。與不采用掃描算法相比，該綜合算法降低了生鮮配送總成本，提高了計算速度。采用掃描算法分區(qū)時，本文考慮了顧客收貨時間窗和車輛額定載貨量，但沒有考慮各顧客之間道路交通條件，后續(xù)研究中加入交通擁堵系數(shù)、道路條件等指標(biāo)，以使分區(qū)更加合理。