O2O模式下生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化

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

1 引言

O2O（Online To Offline）模式下生鮮農(nóng)產(chǎn)品電子商務(wù)為顧客提供線上交易、線下配送的服務(wù)。從生產(chǎn)地到達(dá)需求地的過程中，對(duì)生鮮農(nóng)產(chǎn)品損失率影響較大的是配送質(zhì)量，農(nóng)產(chǎn)品易腐性對(duì)配送服務(wù)的時(shí)效性要求較高，物流企業(yè)以顧客為中心，首先考慮配送時(shí)間約束，又兼顧配送成本。因此，配送質(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ì)量研究不斷多元化。對(duì)于線上交易，一般以提升交易效率和可靠性為研究熱點(diǎn)，針對(duì)生鮮農(nóng)產(chǎn)品電商平臺(tái)發(fā)展模式[1]、運(yùn)營策略[2]和影響顧客購買行為的因素[3]進(jìn)行研究。在配送路徑研究方面，國內(nèi)外學(xué)者一般以車輛行駛路徑最短、運(yùn)輸費(fèi)用最低、配送車輛數(shù)量最少、配送時(shí)間最短等單個(gè)或多個(gè)指標(biāo)作為目標(biāo)函數(shù)，建立多約束下的優(yōu)化模型，采用混合啟發(fā)式算法[4-5]、元啟發(fā)算法[6]、遺傳算法[7-8]、蟻群算法[9-10]等求得模型最優(yōu)解或滿意解。

本文在以上研究的基礎(chǔ)上，針對(duì)目前O2O模式下生鮮農(nóng)產(chǎn)品配送中存在的問題，以顧客滿意度最大和配送成本最小為目標(biāo)，引入配送消耗成本和時(shí)間窗懲罰成本兩個(gè)決策變量，在顧客時(shí)間窗、車輛行駛最大里程和最長時(shí)間的限制下構(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)品交易線上平臺(tái)接收、整理、處理顧客訂單；

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

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

2.1 配送目標(biāo)

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

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

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

2.2 約束條件

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

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

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

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

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

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

根據(jù)以上問題描述，以配送成本（包括配送車輛固定成本、配送車輛變動(dòng)成本、生鮮農(nóng)產(chǎn)品消耗成本和時(shí)間懲罰成本）最低為目標(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)生的固定費(fèi)用（元/輛）；e表示車輛單位距離運(yùn)輸成本（元/km）；v表示配送車輛的行駛速度（km/h）；n表示顧客總數(shù)；i=0,1,...,n表示實(shí)體店和顧客，其中i=0表示實(shí)體店；（Xi,Yi）表示顧客i位置坐標(biāo)；dij（i,j=1,2,...,n）表示顧客i到顧客j的距離（km），dij=dji；doj（j=1,2,...,n）表示實(shí)體店到顧客j的距離（km）；qi（i=1,2,...,n）表示顧客對(duì)生鮮農(nóng)產(chǎn)品的需求量（kg）；p表示生鮮農(nóng)產(chǎn)品平均單價(jià)（元/kg）；β表示配送中農(nóng)產(chǎn)品損耗的比例；ti表示配送車輛到達(dá)顧客i的時(shí)刻；tij表示配送車輛從顧客i到顧客j的行駛時(shí)間，tij=dij/v；tki表示車輛k到達(dá)顧客i后進(jìn)行服務(wù)的時(shí)間（min）；[Ei,Li]表示顧客i設(shè)置的時(shí)間窗，其中Ei表示顧客設(shè)置時(shí)間窗的起始時(shí)刻，Li表示顧客設(shè)置時(shí)間窗的終止時(shí)刻；δ1表示配送車輛早于顧客設(shè)置的時(shí)間窗帶來的懲罰系數(shù)；δ2表示配送車輛晚于顧客設(shè)置的時(shí)間窗帶來的懲罰系數(shù)；Qmax表示配送車輛的最大載貨量（kg/輛）；Lmax表示配送車輛的單程行駛最大里程（km）；Tmax表示配送車輛行駛的單程配送最長時(shí)間（min）。

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

4 模型求解

4.1 掃描算法

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

（1）建立極坐標(biāo)系。以實(shí)體店的位置作為極點(diǎn)，以X軸方向?yàn)檎较颍O坐標(biāo)系，并對(duì)所有顧客所在的位置，進(jìn)行極坐標(biāo)系的變換。

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

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

4.2 遺傳算法

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

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

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

（3）計(jì)算染色體的適應(yīng)度。O2O模式下生鮮農(nóng)產(chǎn)品配送路徑目標(biāo)是使配送總成本最小，即目標(biāo)函數(shù)值最小，而適應(yīng)度值應(yīng)該是非負(fù)的，適應(yīng)度值越大，表示個(gè)體的性能越好，被選擇到下一代的概率越大。因此需要將目標(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）選擇操作。采用輪盤賭方式進(jìn)行選擇，從群體中選擇一些個(gè)體，這些個(gè)體被選中的概率與它們的相對(duì)適應(yīng)度值成正比，能夠保證適應(yīng)度高的個(gè)體以更大的概率被選中。設(shè)群體大小為M，個(gè)體r適應(yīng)度為fr，則個(gè)體r被選中的概率這種選擇方式首先保證了所有個(gè)體都有幾率遺傳到下一代,并且適應(yīng)度高的個(gè)體會(huì)被優(yōu)先選擇,保證了優(yōu)良基因可隨迭代過程持續(xù)傳遞。

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

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

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

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

5 模型驗(yàn)證

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

某生鮮農(nóng)產(chǎn)品實(shí)體店線上交易平臺(tái)9：00至10:00點(diǎn)接到17個(gè)顧客訂單，即n=17（人），生鮮農(nóng)產(chǎn)品平均單價(jià)p=7（元/kg），顧客相關(guān)信息（地理坐標(biāo)、需求量、時(shí)間窗、車輛到達(dá)位置至離開的服務(wù)時(shí)間）見表1和圖1。實(shí)體店擁有5輛相同型號(hào)并配備了保鮮箱的電動(dòng)車。電動(dòng)車的長寬高為56cm，車廂最大裝載量為Qmax=25（kg/輛），單位距離運(yùn)輸成本e=0.4（元/km），平均車速v=35（km/h）。考慮到車與配送人員一一對(duì)應(yīng)，且電動(dòng)車的固定成本很小，因此車輛產(chǎn)生的固定費(fèi)用Pk=20（元/輛）。根據(jù)以往數(shù)據(jù)，配送中農(nóng)產(chǎn)品損耗的比例β=2%。單程里程約束Lmax=35（km），單程時(shí)間約束Tmax=60（min），早于時(shí)間窗懲罰成本系數(shù)δ1=0.2，晚到時(shí)間窗產(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)配送路徑總成本較高。這是因?yàn)檫z傳算法求解時(shí)，有較大的隨機(jī)性，當(dāng)種群規(guī)模、交叉概率、變異概率和最大迭代數(shù)等遺傳參數(shù)確定時(shí)，種群中個(gè)體的數(shù)量多，隨機(jī)性大，初始種群找到最優(yōu)解的可能性小，即使經(jīng)過選擇、交叉和變異的操作會(huì)增加尋找到最優(yōu)解的概率，但其仍存在著隨機(jī)性，最優(yōu)解被找到的概率依然較小。相比較而言，首先運(yùn)用掃描算法進(jìn)行路線分區(qū)，使運(yùn)用遺傳算法計(jì)算的種群個(gè)體數(shù)量減少，在遺傳參數(shù)確定的條件下，初始種群較易找到最優(yōu)解，且經(jīng)過選擇、交叉和變異操作進(jìn)一步優(yōu)化解，最終得到最優(yōu)解的概率大大增加；且這些個(gè)體相對(duì)位置集中，有利于優(yōu)化最短路徑，使生鮮配送車輛的變動(dòng)成本、生鮮損耗成本和時(shí)間懲罰成本降低，從而降低了生鮮配送總成本。此外，采用掃描算法預(yù)先分區(qū)后，每個(gè)區(qū)域的變量數(shù)量相對(duì)減少，遺傳算法迭代次數(shù)降低，計(jì)算速度更快。

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

6 結(jié)語

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