李 娜

（西安財(cái)經(jīng)大學(xué) 管理學(xué)院，陜西 西安 710100）

1 問題描述及變量定義

1.1 問題描述

新零售背景下，多功能生鮮超市應(yīng)運(yùn)而生，人們越來越注重生鮮產(chǎn)品的新鮮度以及配送時(shí)間的長短，本文總結(jié)相關(guān)路徑優(yōu)化研究現(xiàn)狀如下，張倩等[1]在研究配送路徑時(shí)，建立以配送成本，產(chǎn)品新鮮度，碳排放量為主的目標(biāo)函數(shù)，并利用果蠅算法進(jìn)行求解；肖建華[2]用變鄰域算法求解多車輛多配送中心的路徑優(yōu)化問題；王超[3]設(shè)置軟時(shí)間窗約束研究即時(shí)配送的效果，并采用了布谷鳥進(jìn)化算法求解PDVRP 問題。何美玲等[4]利用蟻群算法求解軟時(shí)間窗的路徑問題。姚臻等[5]以客戶時(shí)間窗、客戶滿意度、碳排放為約束條件，建立以碳排放量為基礎(chǔ)的總成本最小目標(biāo)函數(shù)，并應(yīng)用遺傳算法求解數(shù)學(xué)模型，得出考慮碳排放成本對于物流配送成本的重要影響。楊霞等[6]考慮生鮮產(chǎn)品新鮮度在軟時(shí)間窗約束的條件下對車輛路徑優(yōu)化問題的影響，并用插點(diǎn)分段的方式計(jì)算兩需求點(diǎn)的距離，建立成本最小模型。秦馨等[7]根據(jù)當(dāng)前訂單分批模式從訂單挑選搬運(yùn)次數(shù)方面比較四種聚類算法的差別，最后得出相應(yīng)結(jié)論。Fahimeh 等[8]針對訂單揀選和交付計(jì)劃這兩個(gè)重要且相互關(guān)聯(lián)的環(huán)節(jié)，從訂單批次揀貨處理以及向配送車輛分配訂單、規(guī)劃路線入手，以系統(tǒng)成本最小化為目標(biāo)進(jìn)行了充分研究，最終有效降低了系統(tǒng)成本并提高了揀選效率。Mar 等[9]也從訂單揀選和交付流程著手，對存在多個(gè)揀選配送位置的揀配問題進(jìn)行研究，最終不僅減少了揀選和交付成本，還避免了閑置資源的浪費(fèi)。實(shí)際生活中，訂單的產(chǎn)生是動態(tài)且具有規(guī)模性，需要考慮訂單分揀造成的時(shí)間差異對于消費(fèi)者體驗(yàn)度的影響，因此，考慮訂單分揀過程中造成的懲罰成本、新鮮度成本以及運(yùn)輸過程中的運(yùn)輸成本非常重要。

1.2 問題分析

即時(shí)配送的貨物主要為小型且分散，且不同入口訂單來源的需求要滿足多元化需求，整體呈現(xiàn)出一個(gè)動態(tài)的變化過程，現(xiàn)實(shí)中即時(shí)配送訂單分配未按照一定的規(guī)范標(biāo)準(zhǔn)，同類型以及需求點(diǎn)相近的產(chǎn)品或有特殊需求的產(chǎn)品用戶，比如有時(shí)間窗要求或要求增值服務(wù)的，未被合理分配在一起。即時(shí)配送的貨物大多為三公里之內(nèi)的貨物，在智能化配送未完全普及的背景下，人工配送是主要的配送方式，而人工配送的路徑并未完全運(yùn)用智能化算法來分析配送路徑的選擇以及順序，大多依賴于配送員主觀上的認(rèn)知，這些在很大程度上影響即時(shí)配送效率。

1.3 模型假設(shè)

1.3.1 問題假設(shè)

生鮮產(chǎn)品不區(qū)分種類，按照訂單分配；假設(shè)生鮮產(chǎn)品初始配送新鮮度以及耐腐性能無差別；配送地點(diǎn)產(chǎn)品充足，不存在因產(chǎn)品短缺而引起的時(shí)間浪費(fèi)；挑揀人員熟悉門店環(huán)境，可以及時(shí)挑揀；配送車輛統(tǒng)一出發(fā)，不考慮多時(shí)段車輛配送；配送過程中始終勻速行駛，不考慮行駛路程中突發(fā)因素對車輛速度的影響；假設(shè)配送過程中不發(fā)生堵車、車禍等意外情況；配送過程中的行駛速度是恒定的，不隨路況發(fā)生變化；配送過程中配送車輛溫度恒定，不受其他因素影響。

1.3.2 約束條件

配送車輛從生鮮產(chǎn)品配送中心出發(fā)，完成配送后返回配送中心；配送中心貨物充足，能滿足一切訂單需求；每輛車輛載重量大于當(dāng)車訂單需求量；配送車輛實(shí)現(xiàn)眾包配送，但訂單需求方只能由一個(gè)配送車輛完成。

1.3.3 變量設(shè)置表

訂單聚類中心I，配送中心O，需求點(diǎn)集合M={i},i=1,2,3,…,n，配送點(diǎn)集合N={J},J=1,2,3,…,n，運(yùn)輸車輛的集合K={k},k=1,2,3,…,n，需求點(diǎn)i 到配送點(diǎn)j 的距離dij，訂單i 的需求量Ri，車輛k 載重量Zk，客戶可接受配送時(shí)間[Ei,Li]，時(shí)間滿意度程度M（t），生鮮產(chǎn)品在t 時(shí)間的新鮮度H（t），生鮮農(nóng)產(chǎn)品的變質(zhì)率α。

2 數(shù)學(xué)模型構(gòu)建

2.1 相似性函數(shù)

由于新零售模式的影響，更多的消費(fèi)者傾向于通過線上購買物品，因此產(chǎn)生訂單的位置是多樣性的，配送端需要盡可能用最少的人力、物力、財(cái)力實(shí)現(xiàn)即時(shí)配送。K-means 聚類算法以需求點(diǎn)相距距離作為相似性的評價(jià)指標(biāo)，以多個(gè)配送中心和分散需求點(diǎn)進(jìn)行聚類，其結(jié)果受到K 值選取的影響，容易超出劃定的配送范圍，增加尋優(yōu)的復(fù)雜過程。此算法契合于即時(shí)配送確定范圍內(nèi)的尋優(yōu)問題。

Step1：計(jì)算各需求點(diǎn)，配送中心，聚類中心之間相互的距離，diI表示需求點(diǎn)與聚類中心的距離，dij表示需求點(diǎn)到配送中心的距離，dIj表示配送中心到聚類中心的距離，（Xi,Yi）表示需求點(diǎn)坐標(biāo)，（XI,YI）表示聚類中心坐標(biāo)，（Xj,Yj）表示配送中心位置坐標(biāo)。

Step3：更新訂單位置，重新計(jì)算Step1，Step2，直至訂單穩(wěn)定，結(jié)束迭代。

2.2 懲罰成本

由于配送時(shí)間的限制性而產(chǎn)生一種懲罰成本，懲罰成本大小表示顧客對于即時(shí)配送時(shí)間的滿意程度，兩者之間的關(guān)系是此消彼長，密不可分的，CC表示懲罰成本，ε1,ε2表示早到或晚到客戶點(diǎn)的時(shí)間懲罰系數(shù)，因此懲罰成本可表示為：

2.3 貨損成本

產(chǎn)品新鮮度對于顧客的回頭率具有非常重要的作用，本文引入新鮮度函數(shù)來體現(xiàn)生鮮農(nóng)產(chǎn)品的貨損成本，生鮮產(chǎn)品的新鮮度會隨著配送時(shí)間和溫度的變化而變化，假設(shè)生鮮超市農(nóng)產(chǎn)品物流配送過程中可以保證產(chǎn)品恒溫運(yùn)輸，α 為變質(zhì)率，且為固定常數(shù)，H（t）表示生鮮農(nóng)產(chǎn)品從配送中心O 到需求點(diǎn)i 中即時(shí)配送過程中發(fā)生的新鮮度變化。

當(dāng)t=0 時(shí)，H（t）=1，此時(shí)生鮮農(nóng)產(chǎn)品從配送點(diǎn)開始裝車出發(fā)，假定新鮮度為1，經(jīng)過運(yùn)輸過程中耗費(fèi)的時(shí)間t，新鮮度逐漸下降，由此表現(xiàn)出遞減的指數(shù)函數(shù)。

根據(jù)生鮮農(nóng)產(chǎn)品需求量與下降的新鮮度成線性關(guān)系的假設(shè)，只考慮訂單運(yùn)輸過程中的貨損成本，P 為貨物單價(jià)，α 表示生鮮產(chǎn)品貨損率，ti表示配送車輛Ki行駛到訂單i 的時(shí)間，t0表示配送車輛Ki從配送中心出發(fā)的時(shí)間，則貨損成本為：

2.4 運(yùn)輸成本

生鮮產(chǎn)品從集中生產(chǎn)場所流入分散需求點(diǎn)主要通過物流配送來實(shí)現(xiàn)，在配送過程中成本支出最大的部分就是運(yùn)輸成本，運(yùn)輸成本始終貫穿配送的每一時(shí)刻，在企業(yè)經(jīng)濟(jì)效益中占據(jù)重要地位，受物流運(yùn)輸距離，車輛行駛速度等主要因素影響。忽略供應(yīng)商到配送中心的距離，考慮從配送中心到需求點(diǎn)再到配送點(diǎn)的距離下的固定成本和車輛運(yùn)輸成本。

因此，建立目標(biāo)函數(shù)模型：

目標(biāo)函數(shù)表示以總配送成本最小，具體又包括以訂單分類影響的訂單分類標(biāo)準(zhǔn)和配送時(shí)間，運(yùn)輸過程中產(chǎn)生的運(yùn)輸費(fèi)用，貨損費(fèi)用，懲罰費(fèi)用。

約束條件：

約束（13）表示多個(gè)訂單需求量小于配送車輛載重量；約束（14）表示每個(gè)客戶只被一個(gè)配送車輛配送；約束（15）表示車輛從配送中心出發(fā)到完成配送，并返回配送中心；約束（16）表示第k 輛配送車輛從第i 個(gè)需求點(diǎn)到第j 個(gè)配送點(diǎn)的概率，或0，1 代表配送，0 代表不配送；約束（17）Yki表示第k 輛車到第i 個(gè)需求點(diǎn)的概率，Yki=1 或0，1 代表配送，0 代表不配送。

3 粒子群算法模型

物流配送路徑優(yōu)化問題屬于多變量、多目標(biāo)的復(fù)雜線性問題，物流配送路徑優(yōu)化方法主要有精確算法和啟發(fā)式算法兩類。這兩類方法又包含蟻群算法、遺傳算法、粒子群算法、模擬退火算法以及禁忌搜索算法等，蟻群算法適用于多目標(biāo)的優(yōu)化問題，遺傳算法適用于更復(fù)雜類型的優(yōu)化問題，粒子群算法參數(shù)設(shè)置較簡單，更適用于多峰高維的復(fù)雜計(jì)算問題[10-12]。但他們本身又具有一定的局限性，比如在粒子群算法全局搜索過程中易早熟收斂、陷入局部最優(yōu)，需提出改進(jìn)后的粒子群算法，克服粒子群算法的不足，能更好地解決配送路徑問題。

3.1 粒子編碼方式

在粒子群算法尋優(yōu)過程中，每個(gè)粒子都代表著需求點(diǎn)被選的隨機(jī)性，假設(shè)粒子維度v 與需求點(diǎn)數(shù)量n 相等，每個(gè)維度數(shù)代表相應(yīng)待選擇的需求點(diǎn)，Xi表示粒子i 的第一維編碼原始值，原始值在[1,n] 內(nèi)變化，相同的整數(shù)部分表示同一車輛配送，小數(shù)部分的數(shù)值大小表示配送的先后順序，Ki表示粒子i 的第二維編碼值，代表需求點(diǎn)選取的車輛編號，本文選取盒馬生鮮12個(gè)需求點(diǎn)的實(shí)際位置坐標(biāo)，按照數(shù)值越小越先配送的原則，進(jìn)行編碼排序，以配送中心作為初始聚類，則初始種群的配送方案（粒子）的編碼和解碼如表1 所示。

表1 配送中心與粒子間的映射關(guān)系

粒子從多個(gè)配送中心出發(fā)，逐步訪問各需求點(diǎn)位置、時(shí)間窗要求、商品新鮮度接受程度及配送車輛最大承載量，各需求點(diǎn)僅被訪問一次，訪問結(jié)束后返回配送中心。根據(jù)粒子形成的位置記憶，對需求點(diǎn)訂單進(jìn)行順序編碼和解碼，如12 個(gè)需求點(diǎn)和3輛配送車輛的順序解碼后形成的配送順序分別為車輛k1配送O1-3-O1；車輛k2配送O2-2-4-5-1-10-O2；車輛k3配送O3-7-8-12-11-O3,車輛k4配送O4-9-6-O4。如圖1 所示。

圖1 多配送中心配送方案

3.2 改進(jìn)粒子群算法

3.2.1 自適應(yīng)慣性權(quán)重

根據(jù)K-means 把多個(gè)配送中心轉(zhuǎn)化為單個(gè)配送中心求解，需求點(diǎn)i 到聚類中心I 的距離很大程度上是由距離慣性權(quán)重來決定的，粒子設(shè)置相應(yīng)的適應(yīng)度值，調(diào)整權(quán)重大小，對于路徑優(yōu)化有重要作用，因此適應(yīng)度函數(shù)如式（18）所示：

其中：w1,w2表示權(quán)重因子，且因即時(shí)配送的生鮮產(chǎn)品大部分為三公里之內(nèi)的訂單，則有w1+w2=1,w1＞w2,Daverage表示需求點(diǎn)i 的平均配送距離，Dmin表示各需求點(diǎn)i 最低配送距離，Dmax表示最長配送距離，Dtotal表示各需求點(diǎn)i 總配送距離。

3.2.2 粒子位置，速度更新

實(shí)時(shí)更新粒子位置，速度粒子的位置和速度對于粒子群算法的選優(yōu)過程占有重要地位，他們不僅能解決粒子陷入局部最優(yōu)的局面，而且快速縮短尋優(yōu)過程的時(shí)間以及準(zhǔn)確度的提高，本文在更新粒子位置和速度時(shí)把訂單產(chǎn)生的隨機(jī)性考慮在內(nèi)，不同的時(shí)間段會有新的訂單取消和產(chǎn)生，更加準(zhǔn)確設(shè)置合理的路徑。

粒子位置更新：

粒子速度更新：

3.3 改進(jìn)算法步驟

設(shè)置參數(shù)，輸入需求點(diǎn)時(shí)間窗，位置坐標(biāo)，假設(shè)車輛個(gè)數(shù)為n，求解的最大迭代次數(shù)為imax，本文取值200，當(dāng)前迭代次數(shù)t=0，首先，初始化粒子的速度和位置，即明確需求點(diǎn)位置，根據(jù)K-means 聚類算法和訂單相似性對訂單進(jìn)行合理劃分，其次，按照上述得出的目標(biāo)函數(shù)計(jì)算粒子的適應(yīng)值，降低即時(shí)物流配送總成本。在相應(yīng)的約束條件下得出單個(gè)粒子最優(yōu)值pbest和群體最優(yōu)值gbest，確定粒子初始最優(yōu)解，逐步迭代，同時(shí)改進(jìn)智能算法，直至迭代次數(shù)最大，完成路徑優(yōu)化。具體算法過程如圖2所示。

圖2 算法過程

首先，對訂單開始聚類分析：

Step1：輸入客戶基本信息，比如位置信息、時(shí)間窗要求等；

Step2：隨機(jī)選取多個(gè)配送中心和聚類中心；

Step3：利用K-means 算法解鎖粒子編碼，根據(jù)訂單相似性分配車輛，完成分批配送劃分，并按照孰近原則劃分先后順序，持續(xù)更新需求點(diǎn)訂單，直至訂單相對趨于穩(wěn)定，得出配送車輛和配送順序的合理分配，否則返回Step2，重新迭代；

Step4：初始化種群，選擇客戶，引入算法，設(shè)置種群規(guī)模N，最大迭代次數(shù)imax，權(quán)重因子w1,w2等；

Step5：按照即時(shí)配送數(shù)學(xué)模型，計(jì)算每個(gè)粒子的適應(yīng)度值，尋找種群粒子個(gè)體最優(yōu)位置bpest和群體全局最優(yōu)位置pbest；

Step6：更新粒子位置、速度、慣性權(quán)重，產(chǎn)生的個(gè)體最優(yōu)和全局最優(yōu)替代原來產(chǎn)生的個(gè)體和全局最優(yōu)；

Step7：滿足迭代次數(shù)，若是，則輸出結(jié)果，若否，則Step6，重新執(zhí)行粒子優(yōu)化策略，直至迭代結(jié)束，得到全局最優(yōu)解。

4 案例分析—盒馬生鮮

4.1 案例基本情況

以某市某區(qū)域盒馬生鮮即時(shí)物流配送為例，研究改進(jìn)后的智能算法對物流即時(shí)配送的成本影響和效率影響，并提出相應(yīng)意見，具體案例相關(guān)數(shù)據(jù)設(shè)置如表2、表3 所示。

表2 用戶點(diǎn)位置和時(shí)間窗要求

表3 相關(guān)參數(shù)設(shè)置

4.2 模型求解

本文將多個(gè)配送中心配送轉(zhuǎn)化成多個(gè)單配送中心出發(fā)，再利用K-means 算法選取其中一個(gè)需求點(diǎn)i 為聚類中心，粒子從聚類中心I 配送出發(fā)，逐步訪問各需求點(diǎn)位置、時(shí)間窗要求、商品新鮮度接受程度以及配送車輛最大承載量，各需求點(diǎn)僅被訪問一次，訪問結(jié)束后更新需求點(diǎn)信息直至穩(wěn)定形成位置記憶，最后返回配送中心。以需求點(diǎn)1 作為更新的聚類中心，解碼結(jié)果如表4 所示：

表4 聚類中心與粒子間的映射關(guān)系

根據(jù)粒子形成的位置記憶，對需求點(diǎn)訂單進(jìn)行順序編碼和解碼，形成的配送順序分別為車輛k1配送1-5-4-3-2-10-1；車輛k2配送1-6-9-1；車輛k3配送1-8-12-11-7-1，由圖3 所示。

圖3 聚類中心配送方式

4.3 算法比較

表5 改進(jìn)算法對目標(biāo)函數(shù)的影響

表6 改進(jìn)算法與傳統(tǒng)算法對比

5 結(jié)論

由此可知，注重物流運(yùn)輸效率、加強(qiáng)管理上的模式，提高物流服務(wù)質(zhì)量，優(yōu)化粒子適應(yīng)度值，改變粒子慣性權(quán)重，更新粒子位置和速度對于粒子的尋優(yōu)過程至關(guān)重要，不僅有效避免粒子陷入局部最優(yōu)，同時(shí)又能保證整個(gè)尋優(yōu)過程高速、準(zhǔn)確進(jìn)行，提升客戶滿意度，高效完成訂單配送。優(yōu)化訂單的劃分標(biāo)準(zhǔn)，注重訂單的個(gè)性化服務(wù)，以及特殊需求，提高客戶滿意度，最終降低536 元配送總成本，提高12%的配送效率。